July 2004

BACK

NB:

• Claim to fame: 1st algorithm in 3D with provable guarantees of reconstruction (interpolation through the right vertices).
• Intuitive notion: featureless areas (remote from the MA) can be reconstructed with fewer samples.

Since some Voronoi vertices can be arbitrarily close to the surface M irrespective of the sampling density, poles are introduced. It is shown that as density augments, for a smooth continuous surface (no boundaries), poles will remain away from the surface (alternatively close the theoretical MA).

The (crust) algorithm in a nutshell, 1998:

Pass 1: Compute the 3D Voronoi diagram of the sample points, S.   Poles: For each sample point s, pick the farthest vertex v of its Voronoi cell, and the farthest vertex v' such that angle vsv' exceeds 90 degrees.   Pass 2: Compute the Delaunay tessellation of the sample points augmented with the poles, the Voronoi vertices chosen in the second step.   (Voronoi filtering) Keep a triangle only if the 3 vertices are sample points s in S. NB: Will work if the poles were well situated on each side of the unknown surface M.   (Normal filtering) Remove a triangle T if the angle difference between the normal to T and the vector to the pole p+ at a vertex of T is too large (parameter theta).   (Trimming) Orient triangles and poles (inside and outside) consistently to retrieve a piecewise-linear manifold without boundary.

Alternatives to steps 3, 4 and 5, 2000:

1. Using co-cones:
    
   • A co-cone defines an umbrella for a sample point made of small Delaunay triangles defining a relatively flat disk-like neighborhood centered at the sample point.
      
2. The power crust and power shape:
    
   • Label poles as outer or inner poles and output the power diagram faces separating the cells of outer and inner poles == power crust == approximate surface mesh M*
      
   • Output the triangulation faces connecting inside poles == power shape == approximate interior MA
      

NB: Power distance of point x in R^3 from a (weighted) point p: pi_p(x) = | x - p|² - r² , where r is a weight (here taken as the radius of the associated polar ball (maximal or Delaunay ball).

Example here

Sampling criterion based on the distance to MA:

• Let the Local Feature Size at a point p on M, denoted LFS(p), be the Euclidean distance from p to the nearest point of the MA.
   
  • LFS(p) <= smallest radius of MA associated to p.
  • LFS(p) is 1-Lipschitz: i.e., LFS(p) <= LFS(q) + |pq| , for any 2 points p and q on M.
     
• Set S is an r-sample of M if no point p on M is farther than "r . LFS(p)" from a point of S.
   
  • This is valid only for regular (smooth) manifolds, i.e., r should be positive and in practice cannot be too small.
     
  • Works well in 2D: in particular a smooth curve is perfectly reconstructed (interpolated) for r <= 0.25 .
     
  • Breaks down in 3D because Voronoi vertices can be arbitrarily close to the surface: this is why poles are introduced. Then, the crust is guaranteed to be topologically equivalent to M if r <= 0.06 .
     

Key element of the algorithm(s) : distinguish outer from inner poles:

• Done iteratively starting with those for which a high confidence is available (triangular face part of the convex hull for example: i.e., Voronoi cell shooting off to infinity).
   
• Inner and outer polar balls should intersect shallowly.

• Near sharp corners this criterion may fail: a test on how skinny (elongated) a voronoi cell is permits to avoid rounding off corners (user-supplied parameter).

• Noisy sampling: when points lie near but not on the surface, not all Voronoi cells are well shaped (i.e., elongated or skinny).

Examples and details: http://www.cs.utexas.edu/users/amenta/powercrust/welcome.html

Notes:

• Petitjean and Boyer, 2001: Regular and non-regular point sets
   
  • Requires sufficiently dense samplings.
     
  • Regularity of a point set should be decided on the basis of points alone, not the a priori unknown shape (e.g., via the LFS).
     
  • Theoretical values of r are not useful in practical applications' particularly for CAD-like objects with sharp edges which would require infinite density (to avoid a heuristic like above).
     
• Dey et al., 2003: Tight cocone: A water-tight Surface reconstruction
   
  • Output of the power crust is not a triangulated surface (i.e., made of polygons) and it may introduce extra points (near corners).
     
  • It fails when the sampling is not uniform and dense.
     
  • Construct an approximate MA once a closed (tight) surface is built (using the cocone algorithm and a hole detection and filling algorithm).

NEXT: CoCone algorithm.

Last Updated: June 30, 2004