Dual Contouring

2 min read•1 page

Marching Cubes is a primal method that puts vertices directly on grid edges. Dual Contouring is a dual method that places exactly one vertex inside each cell containing a surface crossing, reconstructing sharp corners and edges.

Hermite Data Elements:

1. Primal Chamfering: Marching Cubes cuts off sharp features because vertices are restricted to lie strictly along grid edges. 2. Hermite Intersection: Captures both the point of intersection and the surface normal. 3. Dual Vertex: The single vertex generated inside the cell can sit anywhere, allowing it to adapt to sharp features.

python

1class HermiteData:
2    def __init__(self, point, normal):
3        self.point = point    # Exact intersection coordinate on grid edge
4        self.normal = normal  # Normal vector of surface at intersection
5
6def dual_contouring_cell(cell):
7    # Collect Hermite data along all 12 cell edges
8    points, normals = [], []
9    for edge in cell.edges:
10        if edge.is_intersected:
11            points.append(edge.intersection_pt)
12            normals.append(edge.intersection_normal)
13
14    # Solve QEF to place one vertex inside the cell
15    dual_vertex = solve_qef(points, normals)
16    return dual_vertex

Mesh Reconstruction Mode

2 min read•1 page

To find the ideal position for the dual vertex, we minimize the sum of squared distances to the tangent planes at each edge intersection point. This is formulated as a linear least squares problem $A v = b$ and solved using pseudo-inverses.

QEF Mathematics:

1. Objective Function: $E(v) = \sum (n_i \cdot (v - p_i))^2$, representing distance to tangent planes. 2. Least Squares Form: $A$ is the matrix of normal vectors $n_i$, and $b_i = n_i \cdot p_i$. 3. Feature Alignment: The solver places the vertex exactly at the intersection of the tangent planes, capturing sharp corners.

python

1import numpy as np
2
3def solve_qef(intersection_points, normals):
4    # Formulate Ax = b system
5    # A contains normals, b contains dot product (normal * point)
6    A = np.array(normals)
7    b = np.array([np.dot(n, p) for n, p in zip(normals, intersection_points)])
8    
9    # Solve linear least squares system
10    # minimizes sum((n_i * (x - p_i))^2)
11    x, _, _, _ = np.linalg.lstsq(A, b, rcond=None)
12    return x

Angle between Normals (Degrees)

90.00