signed-heat-3d (3D volumetric domains)

Documentation is at nzfeng.github.io/signed-heat-docs

C++ demo for "A Heat Method for Generalized Signed Distance" by Nicole Feng and Keenan Crane, presented at SIGGRAPH 2024.

This library implements the Signed Heat Method (SHM) on 3D volumetric domains, solving for (generalized) signed distance to triangle meshes, polygon meshes, and point clouds. No assumptions are placed on the input, besides that it be consistently oriented.

Check out the sample project to get started with a build system and a GUI.

Check out the docs at nzfeng.github.io/signed-heat-3d.

More resources:

• Python bindings have been released as the signed-heat-method package on PyPI. Checkout the documentation for install instructions.
• If you're interested in using the Signed Heat Method in 2D surface domains, go to this Github repository which demonstrates the geometry-central implementation on (2D) surface meshes and point clouds.
• Project page with links to paper, pseudocode, supplementals, & videos: link

Performance

1. To improve performance, operators and spatial discretizations are only built as necessary, and re-used in future computations if the underlying discretization hasn't changed. This means future computations can be significantly faster than the initial solve (which includes, for example, tet mesh construction and matrix factorization.)

2. Linear solves are (optionally) accelerated using the algebraic multigrid library AMGCL, which (unfortunately) requires Boost. If you do not want to use Boost, use cmake -DSHM_NO_AMGCL=On to compile to a program without AMGCL but with solve times ~5x slower (more or less for larger/smaller problems). Force use of AMGCL via cmake -DSHM_NO_AMGCL=Off. Boost can be installed on macOS using brew install boost, and the necessary modules on Ubuntu using

sudo apt-get -y update
sudo apt-get -y install libboost-dev libboost-test-dev libboost-program-options-dev libboost-serialization-dev

Windows users should probably follow the instructions on the Boost website.

User tips

1. There are still several further obvious areas of performance improvement, which haven't been implemented yet:

• In 3D domains, Step 1 of the Signed Heat Method (vector diffusion) can be done by convolution; the integral is evaluted simply by direct summation, even though this summation is trivially parallelizable.
• One could optimize loop order when iterating over source/domain elements (whichever is smaller) for better cache behavior.
• More performance-critical implementations could also implement hierarchical summation.

2. Be aware of the method's dependency on meshing: for example, the resulting SDF will probably not look great if you only use a 2 x 2 x 2 grid (that's only 8 samples total of the SDF --- not enough to capture beyond the coarsest of details.)

3. Relatedly, note that adaptive grid-based meshing has not yet been implemented, though the tetrahedral meshing is adaptive (may be relevant if using this library for surface reconstruction in particular).

To gain an understanding of what this entails: in the above figure, the tet mesh discretization of the volumetric domain yields more faithful reconstruction than using a grid with a similar number of degrees of freedom (DOFs), since its DOFs are adapted to the input. A tet mesh can also be made to be constrained to the input shape boundary, enabling exact enforcement of zero set constraints. (On the other hand, the far-field accuracy of the SDF on the tet mesh is lower where tets are coarser.) Contributions to signed-heat-3d are welcome.

4. The library also only uses standard marching cubes and marching tets to contour (extract) level set surfaces of the resulting SDF. Better reconstruction can be obtained by using e.g. dual contouring --- though it's totally possible to feed the results to any contouring algorithm of your choice, and contributions to the library itself are also welcome!

Citation

If this code contributes to academic work, please cite as:

@article{Feng:2024:SHM,
    author = {Feng, Nicole and Crane, Keenan},
    title = {A Heat Method for Generalized Signed Distance},
    year = {2024},
    issue_date = {July 2024},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    volume = {43},
    number = {4},
    issn = {0730-0301},
    url = {https://doi.org/10.1145/3658220},
    doi = {10.1145/3658220},
    journal = {ACM Trans. Graph.},
    month = {jul},
    articleno = {92},
    numpages = {19}
}