July 2004

BACK

Reference:

• Nina Amenta, Sunghee Choi, Tamal Dey and Naveen Leekha, "A simple algorithm for homeomorphic surface reconstruction," ACM Symposium on Computational Geometry, 2000, pages 213-222. Submitted to the International Journal of Computational Geometry and its Applications.

Goal:

• Guarantee that the output surface M* is homeomorphic (a continuous deformation exists preserving the topology) to the object original surface M.
  • Claim to fame: 1st published result with such a guarantee.

(old) Assumptions of the previous crust algorithm:

1. M is smooth (twice-differentiable) manifold without boundary (closed: topologically like a sphere).
    
2. Sampling is dense and uniform enough so that no sample point is too far (not too close) from the MA; i.e., the distance between samples is proportional (factor r ) to the (minimum) distance to the MA.

A simpler one-pass algorithm is proposed with the above guarantee as a theorem.

(new) Assumptions: Let T be the set of final triangles for M*

1. T contains all (Delaunay) triangles whose dual Voronoi edges intersect M
   --> ensures that T contains a piecewise-linear manifold homeomorphic to M (T is usually larger).
    
2. Each triangle is small: i.e., the radius of its circumcircle is much smaller than the distance to the MA at its vertices.
    
3. Triangles in T are flat: i.e., a triangle normal makes a small angle with the surface normals at their vertices.
    
   Together, conditions 2 and 3 are used to show that any piecewise-linear manifold extracted from T which spans all samples s must be homeomorphic to M.
    
4. Samples are in general position (no degenerate situations, like co-spherical or co-linear).
    

Co-cones:

Candidate triangles are selected using the cocone at each sample point:

• Consider the farthest Voronoi vertex associated to a sample p: this is its 1st pole p+.
   
• The line through p and p+ is the estimated normal N to M at p.
   
• For an angle theta (parameter) the co-cone is defined as the cone complement of the double cone with apex p making an angle pi/2 - theta with N.
   
• Determine the set of Voronoi edges in Vp that intersect the co-cones at all 3 of the samples inducing an edge.
  • The dual triangles of such edges are part of the candidate set T.

Problems with practical data, due to undersampling, noise, non-smoothness:

• The estimated "normals" then may not be in the correct direction, leading to a wrong choice of triangles.
   
• Procedure BOUNDARY: detect Voronoi cells which are not long and thin along the estimated normals.
  Removing these triangles leaves holes in the mesh.
   
• Tight cocone attempts to fill such holes by labeling Delaunay tetrahedra as in or out, based on the initial approximation of the surface. Remove all out tetrahedra, and take the boundary of the in tetrahedra to get a surface M* (which is then "water tight", i.e., closed). Works well if the undersampling is local.

TOP

Last Updated: June 30, 2004