4 - Surface Reconstruction

Summary

In the previous chapter we learned that the restricted Delaunay triangulation is a good approximation of a densely sampled surface Σ from both topological and geometric view point. Unfortunately, we cannot compute this triangulation because the restricted Voronoi diagram Vor P|_Σ cannot be computed without knowing Σ. As a remedy we approximate the restricted Voronoi diagram and compute a set of triangles that is a superset of all restricted Delaunay triangles. This set is pruned to extract a manifold surface which is output as an approximation to the sampled surface Σ.

Algorithm

First, we observe that each restricted Voronoi cell V_p|_Σ = V_p ∩ Σ is almost flat if the sample is sufficiently dense. This follows from the Normal Variation Lemma 3.3 as the points in V_p|_Σ cannot be far apart if ε is small. In particular, V_p|_Σ lies within a thin neighborhood of the tangent plane τ_p at p. So, we need two approximations: (i) an approximation to τ_p or equivalently to n_p and (ii) an approximation to V_p|_Σ based on the approximation to n_p. The following definitions of poles and cocones are used for these two approximations.

Poles and Cocones

Definition 4.1 (Poles). The farthest Voronoi vertex, denoted p⁺, in V_pis called the positive pole of p.