July 2004

TOP

References:

• J. Giesen and M. John, "Surface Reconstruction Based on a Dynamical System." Proceedings of the 23rd Annual Conference of the European Association for Computer Graphics (Eurographics), Computer Graphics Forum 21, (2002) 363-371.
• J. Giesen and M. John, The Flow Complex: A Data Structure for Geometric Modeling. Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2003) 285-294.

Other references here.

Main "idea:"

• Study the critical points of the distance function (using the Voronoi diagram and dual Delaunay tesselation of point sets) --- Theorem 1:
  • The critical points of the distance function h (from points of the input dataset) are the intersection of Voronoi objects and their dual Delaunay objects.

Motivation:

• Study critical points of Morse functions as studied by Edelsbrunner et al. (aka Alpha-shapes and computational topology).

Use of Voronoi/Delaunay objects:

• For point samples, critical points are characterized at the intersection of Voronoi objects with their dual Delaunay objects.
   
• Driver of a point x: Consider the lowest dimensional Voronoi object which contains x; let sigma be the dual Delaunay object. The driver of x is then the closest point to x on sigma.
   
  • Examples:
    1. x is part of a Voronoi cell, sigma is the dual Delaunay vertex, i.e., a sample point p. The driver of x is the sample p.
    2. x is part of a Voronoi face or shock sheet, sigma is the dual Delaunay edge: the driver of x is the A_1^2-2 locus.
    3. x is part of a Voronoi edge or shock curve, sigma is the dual Delaunay triangle (thru the 3 samples sharing the Voronoi edge): the driver of x is the A_1^3-2 locus.
    4. x is part of a Voronoi vertex, sigma is the dual Delaunay tetrahedron; the driver of x is x for a regular tet.
        
• Stable manifold of a critical point s of the vector distance function h (to the boundary, inputs): is given by the integral curves ending at s (i.e., the set of all ponts that flow into s).
   
  1. Stable manifold of a critical point of index 0 (minimum) is the critical point itself (e.g., a sample input point).
      
  2. Stable manifold of a critical point of index 1 (saddle point at the intercept of a Delaunay edge and Voronoi face; i.e., an A_1^2-2 shock sheet source) is the Delaunay edge.
      
     NB: The union of all such stable manifolds is what they call the (3D) Gabriel graph, different from the definition of Petitjean and Boyer, but directly equivalent to the 2D definition.
      
  3. Stable manifold of a critical point of index 2 (saddle point at the intercept of a Delaunay face F and Voronoi edge; i.e., an A_1^3-2 shock curve source for acute triangle configurations) is constructed as a polygon contained in the Delaunay faces F which all flow into s.
      
  4. Stable manifold of a critical point of index 3 (local maximum, a sink for the flow; i.e., an A_1^4-4) is a region bounded by multiple adjacent stable manifolds of index 2, bounded by a circuit of Delaunay edges, i.e., stable manifolds of index 1.
      

NB: There is an error in the above right figure: one saddle point is missing for the central Delaunay edge.

NB: The green dot on the LHS of the blue s is not correct as drawn, since its associated triplet of generators form an acute triangle.

Flow complex:

• Given a finite set of points in R^3, the stable flow complex of the point set is given by the simplicial complex built by the Gabriel graph (Delaunay edges) and the triangulated surface whose points flow into index 2 saddles.

Theorem 2:

• The stable manifolds of the local maximum of the distance function h associated with a finite set of points P in R^3 are the bounded regions of the flow complex.

Notes (re-interpretation in the language of shock graphs and scaffolds):

• Step 3: Computes the set of A_1^3-2's (i.e., isolated sources of shock curves).
   
• Step 5: Acute triangle interpolant associated to a shock curve with a valid shock source.
   
• Step 13: This is a valid shock source for a sheet, i.e., an A_1^2-2
   
• Steps 13 and 14: Produce a triangle with vertices given by a pair of input points (which share a Delaunay edge, i.e., for which there is a well-defined A_1^2-2) and the Delaunay triangle circumcenter (the A_1^3-2).
   
• Steps 15 to 24: Produce a triangle (or polygon) for input pairs which do not have a well-defined critical point (i.e., without an A_1^2-2 shock source), by iteratively triangulating neighboring Delaunay faces via associated shock curve sources for obtuse configurations (i.e., with one outward sheet flow towards s).
   

With this procedure, we end-up with a complex which is typically larger than the desired mesh, M*.

NB: The above is a sytematic triangulation process; there are no constraints derived from sampling conditions or from surface-related configurations (e.g., more the two stable manifolds may be attached to the same Delaunay edges).

Reduced flow-complex:

Iteratively remove parts of the flow complex which locally are non-manifold: i.e., such that the associated Gabriel (Delaunay) edge has more than 2 surface patches (3 or more stable manifolds of index 2) through it.

• Ordered removal: For a given edge with 3 or more surface patches thru it, remove the one which has minimum distance between its index 2 critical point s and its associated index 3 maximum (i.e., with minimum distance between the A_1^3-2 and its closest A_1^4-4 sink).
• Stop removals when all Delaunay edges have at most 2 surface patches throu them.

Remaining "problem:" resolve topological non-regularities.

NB: Nearby patches which are connected: separate these (heuristic based? unclear in the paper how this is done).

Extension to shape partitioning and matching in:

• T.K. Dey, J. Giesen and S. Goswami, "Shape Segmentation and Matching with Flow Discretization." Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2748, (2003) 25-36.

Relationships with alpha-shapes:

• T. K. Dey, J. Giesen and M. John, "Alpha-Shapes and Flow Shapes are Homotopy Equivalent." Proceedings of the 35rd Annual ACM Symposium on the Theory of Computing (STOC), (2003) 493-502

Extension to the power diagram in:

• J. Giesen and M. John, "Computing the Weighted Flow Complex." Proceedings of the 8th International Fall Workshop Vision, Modeling, and Visualization (VMV), (2003) 235-243.
  • Theorem 1: The critical points of h = Min pi_p(x) are the intersection points of the power objects and their dual Delaunay objects (where pi_p(x) = |x-p|² - r², the power distance).

• This work is very close in spirit to the work on shock graphs and scaffold. Although they do not mention medial axes, we can consider that this work is related to two of the previous classes: distance based (level-sets) and partition-based (Voronoi/Delaunay).

NB: I met Giesen last year at the Workshop on surface meshing at DIMACS and told him that their work was very closely related to ours. He did not know of shock graphs and scaffold at the time. In their most recent papers they do mention one of our papers (shock scaffolds, IWVF 2001), but only as a method to compute the MA, and they seem unaware of previous work on 2D shapes.

TOP

Last Updated: July 8, 2004