ACM Transactions On Graphics (SIGGRAPH 2024)
We introduce a method for approximating the signed distance function (SDF) of geometry corrupted by holes, noise, or self-intersections. The method implicitly defines a completed version of the shape, rather than explicitly repairing the given input. Our starting point is a modified version of the heat method for geodesic distance, which diffuses normal vectors rather than a scalar distribution. This formulation provides robustness akin to generalized winding numbers (GWN), but provides distance function rather than just an inside/outside classification. Our formulation also offers several features not common to classic distance algorithms, such as the ability to simultaneously fit multiple level sets, a notion of distance for geometry that does not topologically bound any region, and the ability to mix and match signed and unsigned distance. The method can be applied in any dimension and to any spatial discretization, including triangle meshes, tet meshes, point clouds, polygonal meshes, voxelized surfaces, and regular grids. We evaluate the method on several challenging examples, implementing normal offsets and other morphological operations directly on imperfect curve and surface data. In many cases we also obtain an inside/outside classification dramatically more robust than the one obtained provided by GWN.
Acknowledgements
This work was funded by an NSF CAREER Award (IIS 1943123), NSF Award IIS 221229, a Packard Fellowship, and gifts from Adobe Research. The authors also thank Alec Jacobson for helpful conversations about winding numbers and the pseudonormal.The signed distance function (SDF) of a shape
SDFs form an essential building block of many algorithms across graphics, geometry processing, vision, robotics, and more. However, the meaning of "inside"/"outside" — and hence signed distance — is not well-defined whenever the source geometry
So we introduce the Signed Heat Method (SHM) for computing signed distance to broken geometry. The generalized signed distance functions computed by our method are robust across a wide variety of errors in the input, and generalize signed distance to cases not previously considered by past distance algorithms. Our method in principle applies to all discretizations and all dimensions, and we show many such examples in the paper:
Our algorithm is simple and efficient, consisting of three basic steps. First we diffuse the normals of the source geometry
Our algorithm makes use of the remarkable fact that parallel transport along shortest geodesics (shortest paths) can be computed using short-time vector diffusion [Berline et al. 1992, Thm. 2.30]. We aren’t the first to make use of this fact in geometry processing — that would be The Vector Heat Method by Sharp et al. 2019 — but we recognized its implications for computing signed distance. In particular, the theorem guarantees that for small diffusion time, diffused normal vectors of
Our method is robust on broken geometry, because diffusion effectively interpolates normals from nearby points, and extends limited information about orientation to the rest of the domain. Because our method is based purely on PDEs, it generalizes to curved surfaces, different spatial discretizations, and allows one to easily incorporate constraints. Our particular discretization (using edge-based functions to encode vector fields) enables a purely intrinsic formulation, allowing for additional robustness via intrinsic Delaunay refinement; it also lets the method apply directly to non-manifold and self-intersecting meshes.
We show that our method is robust to defects in the source geometry...
...as well as to errors in the domain:
Our method works on non-orientable surfaces:
We show results on a variety of surface discretizations beyond triangle meshes:
And also a variety of volumetric discretizations:
With generalized signed distance established as a basic tool, like generalized morphological operations that can simplify high-frequency features of broken shapes as if they were whole ("dilation"/"erosion"):
In addition to generalized signed distance, our method can compute unsigned distance to curves and point sources, subsuming past heat methods. We can compute distance fields that combine all of these types of distance:
We also show that the SHM is more accurate than past heat methods while having the same asymptotic cost, while being an order of magnitude faster than other state-of-the-art algorithms for geodesic distance [Belyaev & Fayolle 2020].
While we began this project with signed distance in mind, we found that vector diffusion also yields more faithful surface reconstruction than winding numbers/Poisson Surface Reconstruction (which essentially use scalar diffusion). The latter methods fill in holes with flat or saddle-like patches, behavior which is endemic to their underlying PDE and thus independent of the observed surface. In contrast, vector diffusion interpolates observed normal vectors, so we fill in holes with patches that more closely align with the curvature of the surrounding surfaces:
Our experiments were also a reminder that contouring winding number is really difficult. Regardless of what contouring strategy we tried, there were inevitably a significant number of cases on our benchmark where contouring failed miserably at classifiying inside/outside. Here's an example comparing the generalized signed distance function produced by our method, vs. contouring first using winding number, then computing distance to the contoured curve:
Contouring has been a noted Achilles' heel for winding number since its introduction to graphics; Jacobson et al. 2013 ("Robust Inside-Outside Segmentation using Generalized Winding Numbers", Section 5) had noted that simply contouring according to the 0.5 levelset is often insufficient and proposed a graph cut optimization, though it isn't clear the latter is any better (it isn't implemented in the official release in libigl).
I had also encountered the challenges of contouring winding number during our previous surface winding numbers project, where I had developed a contouring procedure that at least worked better than previous methods. Still, our experiments show that contouring winding numbers is far from "automatic". In this project, I ended up trying two methods for contouring winding number functions on surfaces: (1) the method from our surface winding numbers paper, and (2) contouring according to the average function value along one side of the curve. Both methods yield pretty inconsistent inside/outside classification on a benchmark of 220 examples, where both methods failed terribly on ~10% of examples (where "terrible" = more than 50% of surface area was misclassified):
For the least-squares optimization
Finally, deriving the representation of point sources involved taking the limit as the radius
To implement this project, I ended up implementing the complex-valued Crouzeix-Raviart connection Laplacian on triangle meshes, polygon Laplacians, and barycentric vectors. These features are now implemented in geometry-central (pending a Github pull request), in addition to the signed heat method itself.
For polygon Laplacians, there had been two recent papers with different constructions ("Discrete differential operators on polygonal meshes" by De Goes et al. 2020, and "Polygon Laplacian Made Simple" by Bunge et al. 2020) and I wasn't sure of their respective advantages, so I just implemented both.The first step of our method involves solving a discrete Poisson question with a particular source term. Following the "standard" finite element procedure, we represent this source term in a particular basis, which in our case involves integrating this source term against (vector) Crouzeix-Raviart basis functions. This leads to an expression weighted by a scalar Crouzeix-Raviart basis function, though in practice we found that we obtained more accurate results by omitting this scaling factor. Could it be that since Crouzeix-Raviart functions are non-conforming, that our approach yields the correct behavior by using piecewise constant vector bases (instead of piecewise linear)? It's not entirely clear to me what's going on from a function space perspective.
Similar to the unsigned heat method, we observe empirically that the unsigned distance produced by our method behaves like graph distance as
However, it's not immediately clear to me why. Crane et al.'s proof (Crane et al., Appendix A) relies on Varadhan's formula involving scalar heat flow, whereas our method depends on vector heat flow. Given some time, I'd like to derive a similar proof using the relevant asymptotic relationships.
The accuracy of our signed distance gradient approximation relies on the asymptotic behavior of the vector heat kernel as