In computer graphics, working with highly complex models can degrade rendering performance. One technique to mitigate this situation is to simplify a model by reducing its constituent triangles. This project presents an efficient algorithm to achieve this based on a research paper by Garland-Heckbert titled Surface Simplification Using Quadric Error Metrics.
The central idea of the algorithm is to iteratively remove edges in the mesh through a process known as edge contraction which merges the vertices at an edge's endpoints into a new vertex that optimally preserves the original shape of the mesh. This vertex position can be solved for analytically by minimizing the squared distance between it and adjacent triangle faces affected by the edge contraction. With this error metric, edges can be efficiently processed using a priority queue to remove edges with the lowest cost until the mesh is sufficiently simplified. To facilitate the implementation of this algorithm, a data structure known as a half-edge mesh is employed to efficiently traverse and modify edges in the mesh.
The following GIF presents a real-time demonstration of successive applications of mesh simplification on a polygon mesh consisting of nearly 70,000 triangles. At each iteration, the number of triangles is reduced by 50% eventually reducing to a mesh consisting of only 1,086 triangles (a 98.5% reduction). Note that although fidelity is reduced at each step, the mesh retains an overall high-quality appearance that nicely approximates the original shape of the mesh.
This project requires OpenGL 4.1, CMake 3.22, and a C++20 compiler. It is has been confirmed to build and run on and the Microsoft C/C++ Optimizing Compiler Version 19.37.32825 and Clang 17.04 with libc++. To facilitate project configuration, building, and testing, CMake Presets are used with ninja as a build generator.
This project uses vcpkg to manage external dependencies. To get started, run git submodule update --init to clone vcpkg as a git submodule. vcpkg can then be initialized by running .\vcpkg\bootstrap-vcpk.bat on Windows or ./vcpkg/bootstrap-vcpkg.sh on Linux. Upon completion, CMake will integrate with vcpkg to download, compile, and link external libraries specified in the vcpkg.json manifest when building the project.
This project enables Address Sanitizer (ASan) for debug builds. On Linux, this should already be available when using a modern version of GCC or Clang with C++20 support. On Windows, ASan needs to be installed separately which is documented here.
The simplest way to build the project is to use an IDE with CMake integration. Alternatively, the project can be built from the command line using CMake presets. To use the windows-release preset, run:
cmake --preset windows-release
cmake --build --preset windows-release
A list of available configuration and build presets can be displayed by running cmake --list-presets and cmake --build --list-presets respectively. At this time, only x64 builds are supported. Note that on Windows, cl and ninja are expected to be available in your environment path which are available by default when using the Developer Command Prompt for Visual Studio.
This project uses Google Test for unit testing which can be run with CTest after building the project. To run tests with the windows-release preset, run:
ctest --preset windows-release
To see what test presets are available, run ctest --list-presets. Alternatively, tests can be run from the separate tests executable which is built with the project.
Once built, the program executable can be found in out/build/<preset>/src. After running the program, the mesh can be simplified by pressing the S key. The mesh also can be translated and rotated about an arbitrary axis by left or right clicking and dragging the cursor across the screen. Lastly, the mesh can be uniformly scaled using the mouse scroll wheel.