An implementation of Surface Simplification using Quadric Error Metrics in Vulkan and C++.
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 sort edges by 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 CMake 3.27 and a compiler that supports the C++23 language standard. To assist with CMake configuration, building, and testing, CMake Presets are used with ninja as a build generator.
This project requires a graphics driver with Vulkan 1.3 support. While not required for release builds, this project requires the Vulkan SDK for debug builds which enable validation layers by default.
This project uses vcpkg to manage external dependencies. To get started, run git submodule update --init to clone vcpkg as a git submodule. 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 version of GCC or Clang with C++23 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-releaseA 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 after building the project with CTest. To use the windows-release preset, run:
ctest --preset windows-releaseTo 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.
The program executable can be found in the out/build/<preset>/src directory. Once running, the mesh can be simplified by pressing the S key. The mesh can also be viewed from different angles by left clicking and dragging the cursor across the screen.