Dual Marching Cubes

Dual marching cubes extracts the dual of the marching cubes mesh (Nielson [2004]). The chosen marching cubes variant triangulates each cell, every connected piece of that triangulation becomes one vertex, and every crossed grid edge yields a quad connecting the vertices of the four cells around it. A cell crossed by several surface sheets gets one vertex per sheet, which avoids dual contouring’s pinches, and the topology follows the variant’s tables. Method Comparisons compares the methods in detail.

import torch
import isoext
from isoext import viewer
from isoext.sdf import CuboidSDF, RotationOp, get_sdf_normal, project_to_surface

Basic Usage

vertices, faces = isoext.dual_marching_cubes(grid, level=0.0, method="vega")

  • grid: A UniformGrid or SparseGrid with values set

  • level: The iso-value to extract (default: 0.0)

  • method: The marching cubes variant that triangulates the cells ("vega", "lewiner", "nagae", or "lorensen")

  • intersection: Optional edge crossings from get_intersection; attach normals to them for sharp features

grid = isoext.UniformGrid([64, 64, 64])
grid.set_values(grid.get_points().norm(dim=-1) - 0.8)  # Sphere

vertices, faces = isoext.dual_marching_cubes(grid)
print(f"{vertices.shape[0]:,} vertices, {faces.shape[0]:,} triangles")
viewer.embed(vertices, faces, color="crimson")

11,954 vertices, 23,904 triangles

Sharp Features

Vertex placement works like dual contouring’s: without normals, each vertex is the centroid of its patch’s edge crossings; with normals, it is the QEF minimizer, which lands on sharp edges and corners. The recipe is the same as on the Dual Contouring page:

cube = RotationOp(sdf=CuboidSDF(size=[1.0, 1.0, 1.0]), axis=[1, 1, 0], angle=30)
grid = isoext.UniformGrid([48, 48, 48])
grid.set_values(cube(grid.get_points()))

its = isoext.get_intersection(grid)
points = project_to_surface(cube, its.get_points())
its.set_points(points)
its.set_normals(get_sdf_normal(cube, points))

vertices, faces = isoext.dual_marching_cubes(grid, intersection=its)
print(f"max vertex error: {cube(vertices).abs().max():.4f}")
viewer.embed(vertices, faces, color="crimson", flat_shading=True)

max vertex error: 0.0073

Patches

A patch is one connected piece of a cell’s triangulation. Most cells have one. A cell crossed by two sheets has two, and gets two vertices, so the sheets stay separate. The smallest field that shows this has two inside samples at opposite corners of the center cell: the mesh comes out as two pieces, each the dual of the octahedron marching cubes would extract, and the center cell contributes one vertex to each:

t = 1 / 3
blobs = isoext.UniformGrid([4, 4, 4])
p = blobs.get_points()
centers = torch.tensor([[-t, -t, -t], [t, t, t]], device="cuda")
blobs.set_values((p[..., None, :] - centers).norm(dim=-1).amin(-1) - 0.5)

vertices, faces = isoext.dual_marching_cubes(blobs)
print(f"{vertices.shape[0]} vertices, {faces.shape[0]} triangles")
viewer.embed(vertices, faces, color="crimson", flat_shading=True, height=340, grid=blobs)

16 vertices, 24 triangles

References

[1]

Gregory M. Nielson. Dual marching cubes. In IEEE Visualization 2004, 489–496. 2004. doi:10.1109/VISUAL.2004.28.