Last update: July 23, 2002

BACK

References for Computational Geometry & CAD - Voronoi Diagrams & Skeletons - by G. Turkiyyah, D. Storti, et al. :

• A Skeletal/Metaball Shape Representation to Support Deformable Solid Modeling, 2000.
• Skeleton-based Three-dimensional Geometric Morphing, 2000.
• A Skeletal-Based Solid Editor, 1999.
• Skeleton-Based Modeling Operations on Solids, 1997.
• An Accelerated Triangulation Method for Computing Skeletons of Free-form Solid Models, 1997.
• Computation of 3D Skeletons by a Generalized Delaunay Triangulation Approach, 1995.

BibTeX references

In this paper, we describe a method for generating geometric morphs between general 3D solid models. The method is based on the Euclidean skeleton and is capable of generating morphs between shapes that possess different feature sets and different topology. The essential concept that enables the morphing method is utilization of the trimmed skeleton of the symmetric difference as an intermediate shape. The intermediate shape is a valid solid model whose boundary does not self-intersect and is everywhere equidistant from the boundaries of the source shapes. We apply the skeleton-based intermediate shape generation procedure recursively to produce a sequence of shapes, referred to as a morph history, that gradually transform between the initial and target shapes. The method is sufficiently robust to handle significant changes in geometry and topology, such as the creation and annihilation of protrusions, indentations, internal holes and handles, and produces intuitive morph histories.

The skeleton also establishes a correspondence between points on the boundaries of the source and target objects. Interpolation between corresponding points is performed to enable fast generation of a morph history consisting of a sequence of valid solid models. For source and target models that are sufficiently close, this interpolative morphing scheme generates results comparable to those obtained by the recursive skeletonization procedure, but with improved computational efficiency. The boundary point correspondence generated by the skeleton enables morphing with surface attributes (e.g., color, texture, surface roughness, and transparency). The skeleton-based procedure also allows for morphing between open curves or surfaces. A modification of the basic procedure allows the user to control the morph by specifying corresponding feature sets on the initial and final objects. Examples are presented to demonstrate the capabilities of the methods described.

Author Keywords: Morphing; Skeletons; Medial axis; Shape interpolation.

Shape skeletons are powerful geometric abstractions that provide useful intermediate representations for a number of geometric operations on solid models including feature recognition, shape decomposition, finite element mesh generation, and shape design. As a result there has been significant interest in the development of effective methods for skeleton generation of general free-form solids. In this paper we describe a method that combines Delaunay triangulation with local numerical optimization schemes for the generation of accurate skeletons of 3D implicit solid models. The proposed method accelerates the slow convergence of Voronoi diagrams to the skeleton, which, without optimization, would require impractically large sample point sets and resulting meshes to attain acceptable accuracy. The Delaunay triangulation forms the basis for generating the topological structure of the skeleton. The optimization step of the process generates the geometry of the skeleton patches by moving the vertices of Delaunay tetrahedra and relocating their centres to form maximally inscribed spheres. The computational advantage of the optimization scheme is that it involves the solution of one small optimization problem per tetrahedron and its complexity is therefore only linear (O(n)) in the number of points used for the skeleton approximation. We demonstrate the effectiveness of the method on a number of representative solid models.

Keywords: skeleton generation; medial axis; Delaunay triangulation; surface curvature; implicit solid models

Index Terms: Computer aided design; Bodies of revolution; Optimization; Three dimensional computer graphics; Curve fitting; Mathematical morphology; Mathematical models; Algorithms; Skeleton generation; Delaunay triangulation; Free form solid models; Voronoi diagrams

Three main steps:

1. Boundary discretization & skeleton topology construction:
   • via Delaunay triangulation: retrieve Voronoi vertices.
2. Generation of interior patch geometry
   • move/adjust the circumsphere.
3. Generation of edge geometry:
   • Locate contact points with maximal principal curvature along maximal curvature direction, and move along the inward gradient direction a distance equal to the minimum radius of curvature.

Let h define the sample spacing, which is assumed small w/r to any surface feature, including the radius of curvature. Then O(h) defines closeness (adjacency), while O(l) defines separate distinct points (non-adjacent).

3 types of Delaunay tetrahedra:

1. All 4 vertices are distinct (i.e., separated by a distance O(l)).
2. 1 or 2 pairs of vertices are close (i.e., separated by a distance O(h)), but these pairs remain distinct from each other.
3. A triplet of vertices are close, while the 4th is distinct.

Convergence of triangulations toward the skeleton

Convergence rate is driven by p = 1/(1-cos t) , where t is the angle at the centre of a maximal sphere with respect to 2 contact points (rays).

Convergence of interior skeleton points

The centre of an arbitrary Delaunay tetrahedron, from 4 boundary samples, with at least one O(l) edge length corresponds to the centre of a maximally inscribed sphere w/r to the original bounding surface.

However, Delaunay centres do NOT converge to skeleton points associated with non-G1 contact points, e.g., at necks with discontinuous (tangents) pair of points.

Convergence at edge points

The centre of an arbitrary Delaunay tetrahedron, from 4 boundary samples, with only O(h) edge lengths, corresponds to the centre of a maximally inscribed sphere w/r to the original bounding surface at an edge point.

The convergence rate p above is very small as we get near the edge, since t vanishes (or becomes undeterminate).

Convergence of edge points requires G2 (curvature) smoothness. E.g., at cusps the Delaunay spheres may not converge to skeletal points.

Extraction of skeleton patch topology

Discretization & triangulation

Continue retriangulation (point addition) until no Delaunay facets intersects the boundary. This should ensure that the Voronoi diagram is a superset of the skeleton.

This may create some spurious tetrahedra (very flat, near planar sections of the boundary). These may be detected by checking if the inscribed centre is outside a slightly shrunken version of the original boundary (offset).

Cell traversal

A cell-connectivity graph is built on the basis of common cell-edges, and traversed to obtain skeleton patches.

Optimization of the skeleton interior geometry

As sampling density augments, the Voronoi diagram remains jagged near boundary edges (convergence is very slow, or there is no convergence if the boundary does not have G2 continuity).

A local optimization problem is set to move the Voronoi vertices faster toward the centers of maximally inscribed spheres. The loci of quadruplets of points defining a tetrahedron are iteratively moved, from their initial position, minimizing the distance between the old centre and the new one, subject to geometric constraints enforcing the maximality of the inscribed sphere.

NB: Not all 4 vertices need be included in the optimization process above in practice. At least 2 distinct vertices prove sufficient in most cases (a pair of close vertices tend to coalesce). The selection of 2 vertices can be based on identifying which of the 2 types of Delaunay tetrahedron is at hand.

NB: Single tangency points, where all 4 points coalesce, may not constitute a maximal sphere, because high-order contact is not specifically enforced in the above local optimization process; hence, the need for an edge optimization model, as summarized below.

Optimization of the skeleton edge geometry

Contact points along an edge form a principal curve (a ridge or valley) that is everywhere perpendicular to the transverse direction. For the transverse principal curve, find the locus of maximal (minimal) curvature. The latter provides the new constraint for the local optimization search (based on the gradient of pricipal curvatures). An implicit function, f, is used (the zero level set is the boundary of the object), and formula derived for the optimization process in terms of the gradient and Hessian of f.

NB: Near hyperbolic points or umbilics, this approach will likely fail.

The skeletal representation of 3D solids based on the medial axis transform has many applications in engineering. However, these applications are seldom realized, owing to the lack of viable computational techniques for generating skeletons. Such a computational technique, based on a notion of the generalized Voronoi diagram of a set of mixed-dimensional entities [i.e., vertices, edges & faces], is presented. It is shown that the generalized Voronoi diagram of a set of specific mixed dimensional set derived from the set of boundary entities of a polyhedron is, in fact, the exact skeleton of the polyhedron. Rather than the generalized Voronoi diagram being directly computed, its dual, an abstract Delaunay triangulation, is computed, from which the skeleton can be derived. An approach based on the Voronoi diagram of a well chosen representative point set on the boundary is also discussed as a special case; it is shown that the limitations of this approach are overcome by the generalization developed. Overall, it is argued that this generalization of the Voronoi diagram and the notion of the abstract generalized Delaunay triangulation are useful, and that they provide a viable approach to the computation of skeletons. Finally, details of the implementation, results, and an evaluation are presented.

Keywords: medial axis transforms; Voronoi diagrams; Delaunay triangulation.

Introduction

Skeleton features:

1. Uniqueness
2. Invertibility
3. Dimensional reduction
4. Topological equivalence
5. Provides various levels of details as required, from abstract topology to complete geometry ("most attractive feature" according to the authors).

Skeleton = Union of nonredundant midsurfaces defined by a set of entities on the boundary of the object - two such entities are considered: a representative point set on the boundary and the set of all vertices, edges & faces.

Generalized Voronoi Diagrams of Mixed-Dimensional Entities

Bounded edge: Straight line of finite lenght, bounded by two vertices.

Bounded face: Plane of finite area bounded by a set of bounded edges and vertices.

Oriented face: Bounded face with an associated direction, given by its normal.

Projection Pr(q,E): Projection of point q onto an entity E. It is the intersection of E and the perpendicular to E through q. If E is a point (vertex) than Pr(q,E)=q.

OrientSet(Ei): Set of points s.t. :

• Ei is a face, then OrientSet(Ei) = all the points that are in the halfspace defined by the positive orientation of Ei. If Ei is not oriented, then OrientSet(Ei) = all points.
• Ei is an edge, then OrientSet(Ei) = intersection of all OrientSet(Ej), where Ej are adjacent faces of Ei. If there are no adjacent faces, then OrientSet(Ei) = all points.
• Ei is an vertex, then OrientSet(Ei) = intersection of all OrientSet(Ej), where Ej are adjacent edges of Ei. If there are no adjacent faces, then OrientSet(Ei) = all points.

Mixed-dimensional set, Sg: consists of vertices, bounded edges, or bounded faces (oriented or not), and it satisfies the following 3 conditions:

1. A bounding face belongs to Sg, so does its bounding edges.
2. A bounding edge belong to Sg, so does its two bounding vertices.
3. No element of Sg is interior to another element of Sg.

Generalized Voronoi diagram of a mixed dimensional set, GV(Sg):

• Given Sg = {E1, ..., En}, GV(Sg) is the sequence of Voronoi cells {GV1, ..., GVn}, where the metric is given by the normal distance from Ei to a point q.

Generalized Delaunay triangulation of a mixed dimensional set, GT(Sg):

• Every facet of in GT(Sg) is defined by 3 nodes which are elements of Sg.
• Dual to GV(Sg):
  • Each facet of GV(Sg) has a Delaunay edge in GT(Sg). Each such facet defines a midsurface of 2 elements that are the nodes of the dual Delaunay edge. These facets are called Voronoi surface (they are not necessarily planar).
  • Each edge of GV(Sg) has a dual Delaunay facet in GT(Sg). Each such edge is equidistant from 3 elements of the set Sg. These edges are called Voronoi axis (they are not necessarily straight).
  • Each vertex of GV(Sg) has a dual Delaunay tetrahedron in GT(Sg), and is equidistant to 4 elements of the set Sg. Hence a Voronoi vertex has a special geometric meaning. This is not the case of Delaunay vertices.

Skeletons as Generalized Voronoi Diagrams

Skeleton of polyhedron P, SA(P)

External skeleton, SA'(P): skeleton of the complement of P, P'.

Critical point of SA(P): has 4 or more nearest point on the boundary of P.

Critical axis of SA(P): Loci of points which have 3 or more nearest points on the boundary of P.

Skeleton from boundary point sets:

The union of all the Voronoi facets whose dual edges are classified as interior make an approximate SA(P).

Boundary Point Set, BPSg : Point set on the boundary of which is:

1. Valid: none of edges of the Delaunay triangulation of this set intersect the boundary of P (e.g.: add points where there are concavities or deep cavities in order to preserve their boundary).
2. Well-chosen: the circumspheres of the Delaunay tetrahedra are close to being maximal interior spheres.

Skeleton from mixed-dimensional boundary elements

This is an approximation to the medial axis (axis do not reach curvature extrema, or ridges, in this definition; i.e., axis are not reaching the boundary). It distinguishes outside from inside skeletons. All Voronoi faces crossing the boundary of the polyhedron P are not kept in either skeletons.

Computation of Skeleton

A direct computation of GV involves several computations of intersections of quadric patches. Instead the authors computed the dual GT which does not have such intersections.

Start with Delaunay triangles and looks for 4th element to construct a tetrahedron, iteratively.

BACK

Page created & maintained by Frederic Leymarie, 2000.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu