July 2004

BACK

Main goal:

• Deal with (1) surfaces of arbitrary topology, allowing (2) non-uniform sampling, and (3) producing models with provable guarantees on the basis of the point samples only.

Summary (main ideas):

1. DMA: A discrete version of the MA is proposed to define the regularity of interpolants (essentially, how far surface polygons are from the MA):
    
   • The proposed DMA boils down to Blum's MA without the medial structure that intersects or touches the surface interpolants.
      
   • NB: This requires we first get a surface interpolant ... (somewhat a circular statement).
      
2. Regularity: an (closed) interpolant (like a triangle) is regular if the granularity (i.e., maximum local radius of the interpolants incident at each sample point p) is smaller than the local thickness (i.e., Euclidean distance to the DMA).
    
   • Granularity is equivalent to the maximum radius for the A_1^3-2's associated to p used to build interpolants incident at p.
      
   • In contra-distinction to Amenta et al. the notion of regularity introduced here is based on a discrete analogue to the MA and it can be checked directly from the sample point set.
      
3. Local characterization of 3D regular point sets: "Suitable extension of the Gabriel graph to 3D point set."
    
   • NB: Recipe in 2D: of all Gabriel neighbors at p (pairs with an A_1^2-2), keep only the 2 nearest ones.
      
   • For 3 points adjacent in a regular interpolant O, Pi, Pj, Pk, consider a ball touching them and such that its center is also the circumcenter of the circumcircle through these 3 points. If this ball is maximal (empty of other points) then construct a 2-simplex (triangle) and triple of 1-simplex (edges) with vertices Pi, Pj, Pk; this is called the 3D Gabriel complex (3DGC).
      
   • The 3DGC is a subcomplex of the Delaunay tessellation of P.
      
     • NB: The set of centers of maximal balls of the 3DGC corresponds to the set of A_1^3-2 shock sources.
        
   • The interpolant set O is a subcomplex of the 3DGC.
      
4. Minimal granularities: Construction of a regular mesh by propagation:
    
   • Given an edge Pi Pj in O, pick Pk and Pl such that the associated 2 triangles have smallest circumcircles.
      
   • Start with a known edge in O (e.g., the shortest edge in the Delaunay tessellation).
      
5. Non-regular sets remain problematic: if two surface patches are such that the DMA is closer than the local granularities, we run into problems with the above (it leaves holes in the mesh).
    

NEXT

Last Updated: July 15, 2004