# QuadricClustering

VTKExamples/Cxx/Meshes/QuadricClustering

### Description

The algorithm used is the one described by Peter Lindstrom in his Siggraph 2000 paper, "Out-of-Core Simplification of Large Polygonal Models." The general approach of the algorithm is to cluster vertices in a uniform binning of space, accumulating the quadric of each triangle (pushed out to the triangles vertices) within each bin, and then determining an optimal position for a single vertex in a bin by using the accumulated quadric.

Seealso

QuadricDecimation and Decimation.

Other Languages

See (CSharp)

### Code

QuadricClustering.cxx

    #include <vtkPolyData.h>
    #include <vtkSphereSource.h>
    #include <vtkXMLPolyDataReader.h>
    #include <vtkQuadricClustering.h>
    #include <vtkSmartPointer.h>
    #include <vtkPolyDataMapper.h>
    #include <vtkProperty.h>
    #include <vtkRenderWindow.h>
    #include <vtkRenderWindowInteractor.h>
    #include <vtkRenderer.h>
    #include <vtkCamera.h>

    #include <vtkNamedColors.h>

    int main(int argc, char *argv[])
    {
      vtkSmartPointer<vtkPolyData> inputPolyData;
      if(argc > 1)
      {
        vtkSmartPointer<vtkXMLPolyDataReader> reader =
          vtkSmartPointer<vtkXMLPolyDataReader>::New();
        reader->SetFileName(argv[1]);
        reader->Update();
        inputPolyData = reader->GetOutput();
      }
      else
      {
        vtkSmartPointer<vtkSphereSource> sphereSource =
          vtkSmartPointer<vtkSphereSource>::New();
        sphereSource->SetThetaResolution(30);
        sphereSource->SetPhiResolution(15);
        sphereSource->Update();
        inputPolyData = sphereSource->GetOutput();
      }

      vtkSmartPointer<vtkNamedColors> colors =
        vtkSmartPointer<vtkNamedColors>::New();

      std::cout << "Before decimation" << std::endl << "------------" << std::endl;
      std::cout << "There are "
                << inputPolyData->GetNumberOfPoints() << " points." << std::endl;
      std::cout << "There are "
                << inputPolyData->GetNumberOfPolys() << " polygons." << std::endl;

      vtkSmartPointer<vtkQuadricClustering> decimate =
        vtkSmartPointer<vtkQuadricClustering>::New();
      decimate->SetInputData(inputPolyData);
      decimate->UseFeatureEdgesOn();
      decimate->Update();

      vtkSmartPointer<vtkPolyData> decimated =
        vtkSmartPointer<vtkPolyData>::New();
      decimated->ShallowCopy(decimate->GetOutput());

      std::cout << "After decimation" << std::endl << "------------" << std::endl;
      std::cout << "There are "
                << decimated->GetNumberOfPoints() << " points." << std::endl;
      std::cout << "There are "
                << decimated->GetNumberOfPolys() << " polygons." << std::endl;
      std::cout << "Reduction: " <<
        static_cast<double>((inputPolyData->GetNumberOfPolys() - decimated->GetNumberOfPolys())) /
        static_cast<double>(inputPolyData->GetNumberOfPolys()) << std::endl;

      vtkSmartPointer<vtkPolyDataMapper> inputMapper =
        vtkSmartPointer<vtkPolyDataMapper>::New();
      inputMapper->SetInputData(inputPolyData);

      vtkSmartPointer<vtkProperty> backFace =
        vtkSmartPointer<vtkProperty>::New();
      backFace->SetColor(colors->GetColor3d("gold").GetData());

      vtkSmartPointer<vtkActor> inputActor =
        vtkSmartPointer<vtkActor>::New();
      inputActor->SetMapper(inputMapper);
      inputActor->GetProperty()->SetInterpolationToFlat();
      inputActor->GetProperty()->SetColor(colors->GetColor3d("flesh").GetData());
      inputActor->SetBackfaceProperty(backFace);

      vtkSmartPointer<vtkPolyDataMapper> decimatedMapper =
        vtkSmartPointer<vtkPolyDataMapper>::New();
      decimatedMapper->SetInputData(decimated);

      vtkSmartPointer<vtkActor> decimatedActor =
        vtkSmartPointer<vtkActor>::New();
      decimatedActor->SetMapper(decimatedMapper);
      decimatedActor->GetProperty()->SetColor(colors->GetColor3d("flesh").GetData());
      decimatedActor->GetProperty()->SetInterpolationToFlat();
      decimatedActor->SetBackfaceProperty(backFace);

      // There will be one render window
      vtkSmartPointer<vtkRenderWindow> renderWindow =
        vtkSmartPointer<vtkRenderWindow>::New();
      renderWindow->SetSize(600, 300);

      // And one interactor
      vtkSmartPointer<vtkRenderWindowInteractor> interactor =
        vtkSmartPointer<vtkRenderWindowInteractor>::New();
      interactor->SetRenderWindow(renderWindow);

      // Define viewport ranges
      // (xmin, ymin, xmax, ymax)
      double leftViewport[4] = {0.0, 0.0, 0.5, 1.0};
      double rightViewport[4] = {0.5, 0.0, 1.0, 1.0};

      // Setup both renderers
      vtkSmartPointer<vtkRenderer> leftRenderer =
        vtkSmartPointer<vtkRenderer>::New();
      renderWindow->AddRenderer(leftRenderer);
      leftRenderer->SetViewport(leftViewport);
      leftRenderer->SetBackground(colors->GetColor3d("burlywood").GetData());

      vtkSmartPointer<vtkRenderer> rightRenderer =
        vtkSmartPointer<vtkRenderer>::New();
      renderWindow->AddRenderer(rightRenderer);
      rightRenderer->SetViewport(rightViewport);
      rightRenderer->SetBackground(colors->GetColor3d("slate_grey").GetData());

      // Add the sphere to the left and the cube to the right
      leftRenderer->AddActor(inputActor);
      rightRenderer->AddActor(decimatedActor);

      // Shared camera looking down the -y axis
      vtkSmartPointer<vtkCamera> camera =
        vtkSmartPointer<vtkCamera>::New();
      camera->SetPosition (0, -1, 0);
      camera->SetFocalPoint (0, 0, 0);
      camera->SetViewUp (0, 0, 1);
      camera->Elevation(30);
      camera->Azimuth(30);

      leftRenderer->SetActiveCamera(camera);
      rightRenderer->SetActiveCamera(camera);

      leftRenderer->ResetCamera();
      leftRenderer->ResetCameraClippingRange();

      renderWindow->Render();
      interactor->Start();

      return EXIT_SUCCESS;
    }

### CMakeLists.txt

    cmake_minimum_required(VERSION 3.3 FATAL_ERROR)

    project(QuadricClustering)

    find_package(VTK COMPONENTS
      vtkCommonColor
      vtkCommonCore
      vtkCommonDataModel
      vtkFiltersCore
      vtkFiltersSources
      vtkIOXML
      vtkInteractionStyle
      vtkRenderingCore
      vtkRenderingFreeType
      vtkRenderingOpenGL2 QUIET)
    if (NOT VTK_FOUND)
      message("Skipping QuadricClustering: ${VTK_NOT_FOUND_MESSAGE}")
      return ()
    endif()
    message (STATUS "VTK_VERSION: ${VTK_VERSION}")
    if (VTK_VERSION VERSION_LESS "8.90.0")
      # old system
      include(${VTK_USE_FILE})
      add_executable(QuadricClustering MACOSX_BUNDLE QuadricClustering.cxx )
      target_link_libraries(QuadricClustering PRIVATE ${VTK_LIBRARIES})
    else ()
      # include all components
      add_executable(QuadricClustering MACOSX_BUNDLE QuadricClustering.cxx )
      target_link_libraries(QuadricClustering PRIVATE ${VTK_LIBRARIES})
      # vtk_module_autoinit is needed
      vtk_module_autoinit(
        TARGETS QuadricClustering
        MODULES ${VTK_LIBRARIES}
        )
    endif ()

### Download and Build QuadricClustering

Click here to download QuadricClustering and its CMakeLists.txt file. Once the tarball QuadricClustering.tar has been downloaded and extracted,

    cd QuadricClustering/build

If VTK is installed:

    cmake ..

If VTK is not installed but compiled on your system, you will need to specify the path to your VTK build:

    cmake -DVTK_DIR:PATH=/home/me/vtk_build ..

Build the project:

    make

and run it:

    ./QuadricClustering

WINDOWS USERS

Be sure to add the VTK bin directory to your path. This will resolve the VTK dll's at run time.