July 2004

BACK

Reference:

• "Regular and Non-Regular Point Sets: Properties and Reconstruction,", S. Petitjean and Edmond Boyer, Computational Geometry-Theory and Application, volume 19, number 2-3, pp. 101-126, 2001. Elsevier.

Paper is available here: http://www.loria.fr/~petitjea/publications.html

Critique of methods based on LFS (and smoothness):

• Requires sufficiently dense samplings (which is rarely met in practice).
   
• 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, i.e., distance to the unknown MA).
   
• 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).
   
  NB: Dey et al. assume for CAD models that ridges are known and the the surfaces are closed to compute MA of such CAD models.

Goal:

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

Assumptions:

1. The sampling S is from an actual surface M.
    
2. The sampling is "proper", i.e., there is enough samples points in high curvature areas, and try to avoid oversampling in low curvature areas.
    

Contributions:

1. Regular interpolants: Define a discrete equivalent of r-sampling, based on an analogue for piecewise-linear objects of the MA.
    
2. Regularity of a point set can then be decided via the points alone.
    
3. When applied to non-regular point sets, one needs to iteratively determine locally regular configurations of simplices.
    
   • Then, more simplices are recovered than needed.
   • An a posteriori stage based on heuristics is designed to recover the "interesting part".

Simplex: Convex hull of a set of affine independent points (e.g., a vertex, an edge, a triangle, a tetrahedron, etc.).

Star of a vertex p: set of simplices incident on p.

NB: These are like the maximal (Delaunay) balls of each shock curve source (A_1^3-2's in 3D) associated to p.

Discrete MA:

• Definition of the MA of an interpolant ("None of the previously defined MA of piecewise-linear surfaces, mostly based on the Voronoi diagram, are entirely satisfactory.")

Notes:

• This is Blum's MA without the medial medial structure that intersects or touches the surface interpolants. On the right above, the dark triangles represent surface interpolants (i.e., the samples P,Q,R do not share an interpolant in this particular configuration).
   
• The DMA is a "good indicator of the ability of an interpolant to reconstruct an unknown shape."
   

  2 examples in 2D of how the DMA may differ from the continous MA.

   

  

  

  N.B.:

  • Local thickness is related to the LFS(p) of Amenta et al. (the Euclidean distance from p to the nearest point of the MA).
     
  • In the above examples, C1 and C2 are not part of the interpolant O.
     

  

  

  NB:

  • 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.

   

  ---

  General Properties

   

  Let O be a regular interpolant of P.

  

  Thus O is a subset of the Delaunay tessellation of P.

   

  

   

  ---

  Regular 2D Point Sets

  Assume O is a regular 2D point set.

  

  

  Thus, an edge Pi Pj of a regular interpolant belongs to the Gabriel graph of the point set, which itself is a subset of the Delaunay tessellation, such that pairs of points are connected if the ball having them for diameter is empty (maximal).

  NB: The set of centers of maximal balls of the Gabriel graph in 2D corresponds to the set of A_1^2-2 shock sources.

   

  

  NB:

  • For regular interpolants, the local granularity at a sample p is equivalent to the maximum distance between p and any other point in its neighborhood, i.e., it is a measure of the size of the neighborhood.
     
  • Not all edges of the Gabriel graph correspond to edges of O.
     

  The following proposition permits to discriminate which edges are needed.

  

  Recipe in 2D: of all Gabriel neighbors, keep only the 2 nearest ones.

  

   

  ---

  Regular 3D Point Sets

  Assume O is a regular 3D point set.

  

  "Suitable extension of the Gabriel graph to 3D point set:"

  • For 3 points, 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.
     
  • The interpolant set O is a subcomplex of the 3DGC.
     

  NB: The set of centers of maximal balls of the 3DGC corresponds to the set of A_1^3-2 shock sources.

   

  

  Thus, given an edge Pi Pj, pick Pk and Pl such that the associated 2 triangles have smallest circumcircles.

  

  Remember: Local thickness is the minimum distance to the DMA.

  

   

  ---

  Non-Regular Point Sets

  Problem in 3D: The tangent plane at hyperbolic sampled patches (or negative curvature surfaces) intersects the mesh locally. leading to a tendency to have flat 4-point configurations --> non-regularity.

  Minimal Interpolants (heuristic):

  1. The (m-1)-simplex s2 neighboring an already computed (m-1)-simplex s1 on O is s.t. the granularities at the vertices of s1 AND s2 are minimal (i.e., the circumballs have minimal radii).
      
  2. s1 and s2 belong to the Gabriel complex of P.
      

  NB:

  • This ensures the resulting interpolant is a subcomplex of the Gabriel complex of P, but it typically leaves holes in the mesh.
     
  • Implicit idea: the Gabriel complex contains enough simplices (e.g., triangles) for reconstruction.
     

  

   

  Post-processing:

  • The resulting meshing is not always made of a single manifold (i.e., some edges have more than two interpolant through them). Use some heuristics to simplify the mesh (partial results).

   

  Conclusion (future steps):

  • Establish a parallel between the DMA and the continuous MA.

   

  ---

  NEXT: Summary

   

  Last Updated: July 15, 2004