Subgrid Marching Tetrahedra
Conditionally accepted to SIGGRAPH 2026
Hossein BaktashCarnegie Mellon University
Mark GillespieInria (IP Paris) & University of Utah
Keenan CraneCarnegie Mellon University & Roblox
Contouring algorithms like marching cubes and marching tetrahedra are a fundamental tool in geometry processing, needed to convert from implicit representations (like signed distance functions) to explicit representations (namely, polygon meshes). However, they suffer from an equally fundamental challenge of signal processing, namely aliasing: unless the implicit function is sufficiently-well sampled onto a grid, the extracted mesh will have missing features, holes, etc. Moreover, these methods assume that the surface has a definite inside and outside—making them unsuitable for surfaces with boundary. The conventional solution is simply to increase grid resolution, but due to Nyquist-Shannon, this resolution may have to be made prohibitively large in order to capture very fine features in an implicit function; moreover, one most often does not even have an a priori bound on the smallest feature size. A common workaround is to use spatially adaptive marching methods, but here one encounters significant complexity in data structures and implementation—and still suffers from the lack of an a priori bound. We adopt a fundamentally different approach: rather than adapt the grid to the feature size, we change the information stored on the grid to capture (in spirit) information about the frequency of geometric features within each cell. More precisely, we encode geometry using a generalization of Haken's normal coordinates from geometric topology, which count the number of surface intersections for each edge, plus the intersection locations (as 1D barycentric coordinates). Our key contribution, then, is a procedure for reconstructing manifold, intersection-free geometry from these generalized normal coordinates. Unlike other marching procedures, we do not require a distinct inside/outside—nor do we even require consistently-oriented surface patches. This procedure is a strict generalization of the one used for marching tetrahedra, and shares all of its attractive properties. E.g., reconstruction can be performed in parallel across all cells, while still guaranteeing compatibility with neighbors. Moreover, unlike classic marching algorithms, we do not need to build a large table of possibilities, but can instead just run a simple deterministic algorithm. We evaluate our method on two applications: contouring signed distance functions with thin features, and converting polygon soup to manifold, intersection-free meshes. In practice, we see that, for equal grid resolution, the surface fidelity achieved via contouring is dramatically closer to the true surface. More importantly, with our method there is no lower bound on the feature size that we can encode on a fixed grid (apart from floating precision), meaning that we do better even than an adaptive method, for any fixed maximal degree of refinement.