Constructing Shape Skeletons of 3D Objects Using Generalized Voronoi Diagrams

The present invention generally relates to computer-aided modeling of objects, and more specifically, to the use of a computer for generating shape skeletons for objects described by solid models.

Shape skeletons are powerful geometry 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 synthesis. In this context, the skeleton of an object consists of the closure of a locus of spheres that are maximally inscribable in the object so that points on the skeleton are minimally equidistant from at least two points on the boundary of the object. Skeletons of solids generically comprise a collection of two-dimensional (2D) surface patches, but can also contain one-dimensional (1D) curve components (or even zero dimensional points, if the object is composed of disjoint spheres).

The skeleton concept was formally introduced by H. A. Blum as a tool for shape description (described in "A Transformation for Extracting New Descriptors of Shape," Models for the Perception of Speech and Visual Form, ed. W. Wathen-Dunn, MIT Press, 1967, pp. 362-381) and has since been extended to three dimensions by others. The mathematical properties of skeletons and some of their curvature properties are known in the art. The importance of skeletons for the applications mentioned above has led to an extensive body of related literature describing algorithms and implementations for skeleton generation.

The techniques for generating skeletons can be classified into five categories. The first category includes algorithms that employ the exact mathematical description of the object without relying on discretization of either the object or the embedding space. The prior art discusses 2D and 3D algorithms for continuous skeleton generation. For example, one such reference presents a skeleton generation method for convex polyhedra. While these methods are appealing because they produce exact skeletal curves and surfaces, the algebraic manipulations involved for computing geometric intersections currently limit their applicability to low degree curves and surfaces.

The second category involves discretization of the space in which an object for which a skeleton is being constructed lies, using quadtrees, octrees, etc., and employs thinning procedures for the skeleton generation. This approach has become popularized by the computer vision community because of the discrete image input typical of vision processing. While space discretization is very effective in 2D applications, the size of the 3D grids required for non-trivial solids becomes prohibitive. U.S. Pat. No. 5,390,291 discloses how skeletons are applied for shape interpolation in a voxel based setting, but the skeletons are computed for 2D image data (using a thinning algorithm) and not for the 3D voxel description of a solid.

The third category involves tracing algorithms to traverse skeleton curves. This approach is effective for general 2D objects and 3D polyhedra, but extensions to non-polyhedral objects have not appeared in the prior art.

The fourth category involves transforming skeleton generation into the numerical solution of variational problems or PDEs to track the propagation of a moving front. Specific prior art approaches include the use of active contours (or snakes) and modified eikonal equations. Although these methods can exploit sophisticated numerical techniques, the computational requirements exceed current hardware capabilities for non-trivial 3D objects.

The fifth category employs discretization or sampling of the object's boundary and uses Voronoi diagrams as the basis for skeleton generation. These discretization methods produce a polygonal approximation that converges to the skeleton as the sampling becomes very dense, but the convergence is slow, especially near the edge of the skeleton of an object bounded by curved surfaces.

From the foregoing discussion, it will be apparent that a more efficient, accurate technique for producing skeletons would be useful in modeling objects. Of the five approaches discussed above, a variation of the fifth appears to offer the desired effectiveness. Details of this technique are discussed by Munikumar S. Vimawala in a Master's Thesis entitled, "Computational Procedures for Topological Shape Design," which was published in 1994. However, a more accurate determination of the skeleton of 3D objects is required than is disclosed in this prior art reference, since the disclosed approach produces only approximate skeletons having significant errors.

In accordance with the present invention, a polygonal approximation to the skeleton of an object with a piecewise curvature continuous boundary is created. The invention involves adjustment steps to improve the accuracy of the approximate skeleton, and the accuracy improvement is especially significant near the edge of the skeleton. More specifically, a method is defined for using a computer to construct a skeleton representing an object, where the object is defined by boundary data that represent a surface of the object. The method includes the step of producing simplices having vertices at surface data points that sample a boundary of the object. Circumspheres comprising hyperspheres are constructed so as to circumscribe the simplices. Centers of the circumspheres are connected to form an approximate skeleton. The circumspheres are then adjusted to minimize an error in the disposition of the vertices of the approximate skeleton, thereby producing an accurate skeleton of the object.

The simplices preferably comprise Delaunay tetrahedra. The method also includes the step of removing at least some of any simplices that are external to a boundary of the object. To form the approximate skeleton, the centers of the circumspheres whose simplices share a common face are connected. This step forms a plurality of closed Voronoi cells. In addition, the method provides for removing connections between the centers of circumspheres that do not form closed Voronoi cells. A connectivity graph is created, based on common cell edges, and is traversed to identify Voronoi cells that comprise patches. These patches collectively approximate the skeleton.

The step of adjusting modifies either the disposition of the vertices of the simplices, or the radius of a circumsphere, or the disposition of the circumsphere, to create a maximal inscribed sphere. A circumsphere is a maximal inscribed sphere if the vertices of the simplices circumscribed by the circumsphere lie on the boundary of the object and are disposed where the circumsphere is tangent to the boundary of the object.

Further, the step of adjusting provides for moving the centers of the circumspheres to correspond to centers of maximal inscribed spheres that are tangent to the boundary of the object at transverse maxima of a maximum principal curvature for the object.

A further aspect of the invention is directed to apparatus for constructing a skeleton representing an object, where the object is defined by boundary data that represent a surface of the object. The apparatus includes a memory for storing machine instructions that comprise a computer program. A processor, coupled to the memory, executes the computer program and thereby implements a plurality of functions. These functions are generally consistent with the steps of the method discussed above.

A still further aspect of the present invention is directed to an article of manufacture for use with a computer to construct a skeleton for an object. The article comprises a memory media on which are stored a plurality of machine instructions. When executed on a computer, the machine instructions cause the computer to implement functions that are consistent with the steps of the method discussed above.

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIGS. 1A and 1B are a block diagram or flow chart illustrating the steps of a procedure for constructing a more accurate polygonal approximation to the skeleton of an object described by a solid model;

FIG. 2 is a graph illustrating a principal curve of transverse maxima of curvature and the points considered during adjustment of the skeleton edge geometry;

FIG. 3 illustrates a portion of a pruned Voronoi cell approximation to the skeleton of an object having a super ellipsoidal shape, in which significant jaggedness is observed near the skeleton edges;

FIG. 4 shows an image of the super ellipsoidal shape referenced in FIG. 3;

FIGS. 5A, 5B, and 5C are isometric views of Voronoi cell approximations to a skeleton of a block for 500 sample points, 1000 sample points, and 2000 sample points, respectively;

FIG. 5D is an isometric view of the skeleton of the super ellipsoidal shape of FIGS. 3 and 4, after the skeleton has been adjusted in accord with the present invention to minimize errors in the interior and along the edge;

FIG. 6 shows the error of an internal portion of an approximate skeleton relative to a corresponding portion of the skeleton that is adjusted to minimize errors;

FIG. 7 illustrates three geometric classes of tetrahedra in regard to merging or coalescing vertices of the tetrahedra; and

FIG. 8 is a schematic illustration of a personal computer or workstation suitable for use in implementing the present invention.

The basic idea of the skeleton generation process is to construct the topology and initial geometry of the skeleton from the Delaunay triangulation of a suitable discretization of the boundary of the object, and then to adjust the geometry of the skeleton interior and edge points to reduce errors in the skeleton. Given an object .OMEGA. and points on its surface .differential..OMEGA., the Delaunay triangulation of this set of points is computed and the Delaunay centers, i.e., the centers of the spheres circumscribed about each Delaunay simplex, are evaluated. Under certain conditions, as the density of the point sampling on .differential..OMEGA. increases, the Delaunay spheres corresponding to the interior Delaunay simplices approach tangency to .differential..OMEGA.. Therefore, the Delaunay spheres approximate the maximal spheres covering the object's interior, and the closed Voronoi cells connecting the centers of these spheres-a subset of the Voronoi diagram-converge towards the skeleton.

Creating an Initial Approximate Skeleton

FIGS. 1A and 1B identify the steps of the procedure for constructing accurate polygonal skeletons. The process begins by sampling the boundary to obtain a set of surface data points. Alternatively, as indicated in a block 10 in FIG. 1A, surface data points defining a solid model of the object for which a skeleton is to be constructed can be provided as an input to the process. These surface data points can be obtained using a variety of available polygonization procedures such as the one presented by Bloomenthal (in "An Implicit Surface Polygonizer," Graphics Gems IV, ed. P. S. Heckbert, AP Professional, Cambridge, Mass., 1994, pp. 324-349). The sample is evaluated to determine the sample spacing, i.e., the maximum distance between a point and its nearest neighbor. Resampling is performed until the sample is boundary conforming, and the sample spacing is smaller than the size of the smallest surface feature to be accounted for, i.e., to ensure boundary discretization as provided in a block 12. Once the boundary has been appropriately sampled, yielding a set of densely sampled data points as noted in a block 14, Delaunay triangulation is performed to produce a set of tetrahedra having vertices at the data points and no data point in the interior of any of the tetrahedra; this step is indicated in a block 16. As provided in a block 18, the Delaunay tetrahedra cover a convex hull of data for the object.

Of the tetrahedra produced by the Delaunay triangulation, those lying outside the object are identified and removed from the set, in the step of a block 20. The set of tetrahedra noted in block 18 may also contain spurious tetrahedra that lie very close to the object boundary, but which do not properly correspond to a skeleton edge. Spurious tetrahedra can be maintained in the set until an adjustment is made to minimize edge errors, at which time they are identified by the absence of a nearby surface point satisfying the skeleton edge identification criterion. Alternatively, a heuristic approach may be applied to remove tetrahedra whose inscribed centers lie outside a slightly shrunken version of the object. The heuristic approach may eliminate a few valid tetrahedra, but the adjustment procedure described below corrects the geometry so that the final skeleton produced is still accurate.

Once an appropriate set of Delaunay tetrahedra has been obtained as noted in a block 22, the corresponding circumspheres are constructed around the Delaunay tetrahedra, and the centers of the circumspheres are connected across each face shared by two Delaunay tetrahedra so that Delaunay center connectivity is determined by Delaunay tetrahedra face adjacency. These steps are referenced in a block 24. The Delaunay centers of all Delaunay tetrahedra sharing a common edge are thereby connected to form a closed loop referred to as a Voronoi cell. Collectively, as indicated in a block 26, the Voronoi cells comprise a Voronoi diagram. Connections between the centers of circumspheres that do not form a closed cell are removed. The closed Voronoi cells are retained, as noted in a block 28, and a cell connectivity graph based on common cell edges is formed. The connectivity graph is traversed to identify collections of cells that form the patches or sheets that collectively approximate the object's skeleton. Sheet boundaries are composed of skeleton edges (i.e., Voronoi edges belonging to only one cell that exist at the extremities of the skeleton), and seams comprising Voronoi edges belonging to more than two Voronoi cells where multiple sheets meet. The Voronoi cells are subdivided into triangles. By the introduction of internal edges, creating the initial polygonal approximation of the skeleton, as referenced in a block 30 of FIG. 1B, these triangles remain plane as their vertex locations are adjusted (as described below).

While the polygon set described above approximates the skeleton, and the approximation converges to the object's skeleton for very dense sampling, the accuracy of the approximation improves slowly with increased sample density, as demonstrated by FIGS. 5A, 5B, and 5C. These Figures respectively show Voronoi cell skeleton approximations for a block obtained from 500, 1000, and 2000 surface points. It will be noted that the convergence to the skeleton interior points is relatively rapid for regions on the "rectangular" middle patch. However, near the edges of the skeleton, larger errors appear. Even for the dense sampling of 2000 surface points, the errors remain noticeable and the skeleton edge approximation is also noticeably jagged.

Improving the Accuracy of the Skeleton Interior

To improve the polygonal skeleton approximation, adjustment procedures are employed in a block 32 of FIG. 1B to identify, with greater accuracy, the location of a skeleton point near each vertex of the initial polygonal approximation. The skeleton point is identified as the center of a maximal inscribed sphere, and the maximal inscribed sphere is found by adjusting the vertices, center, and/or radius of a circumsphere until a maximal inscribed sphere is prescribed. For the adjusted circumsphere to be maximal, each of the (adjusted) vertices must lie on the object boundary, be equidistant from the adjusted center, and lie at a tangency of the circumsphere with the boundary. After these adjustments are completed, the result is a refined polygonal approximation of the skeleton, with an accurate interior geometry, as indicated in a block 34.

FIG. 6 represents a simple example showing how an adjustment is made to the vertices, radius, and disposition of a circumsphere 204 to minimize an error in the interior portion of a skeleton. In this example, the circumsphere and skeleton are shown in only two dimensions to more clearly illustrate the adjustment technique. The initial approximate skeleton for this portion of the object is represented by a line 200 that connects the centers of the circumspheres previously created. Circumsphere 204 extends through vertices, P.sub.1, P.sub.2, P.sub.3, P.sub.4, of the Delaunay tetrahedron about which it was formed, and x indicates the center of that Delaunay tetrahedron. Further, x' and r (not shown) respectively denote the center and radius of an adjusted circumsphere 206, and P'.sub.1, P'.sub.2, P'.sub.3, and P'.sub.4 are the adjusted contact points (not all of which will be distinct) for this circumsphere. More generally, the vectors n.sub.f (P'.sub.i) and n.sub.s (P'.sub.i)=(P'.sub.i -x) are the respective normals to a boundary 210 and the circumsphere at the point P'.sub.i. The local problem to adjust the position of a vertex of a Voronoi cell is then stated as follows:

Find {P'.sub.1, P'.sub.2, P'.sub.3,, P'.sub.4,, x', r} so as to minimize .parallel.x'-x.parallel..sup.2 (the error corresponding to line 202) subject to the constraints that P'.sub.i lies on the boundary: ##EQU1## and the surface normal vector evaluated at the point is parallel to the normal to the circumsphere centered at the point: ##EQU2##

In this form, the position of each interior point on the approximate skeleton is adjusted as the result of a local adjustment problem involving 16 scalar variables and 12 constraints. The result is a refined portion of the skeleton represented by a dash line 212. In the preferred embodiment, a projected Lagrangian method, Sequential Quadratic Programming (SQP), is employed to solve these problems. The adjustment process moves all vertices to surface contact points. Since skeleton interior points typically have only two distinct contact points, some of the vertices coalesce during the adjustment, and the vertices that start closest together are most likely to coalesce. For example, in FIG. 6, vertices P.sub.1 and P.sub.2 coalesce into a new vertex O.sub.1 during the adjustment of circumsphere 204 to form new circumsphere 206.

Because finding the distinct contact points is sufficient to determine the maximal sphere and the corresponding skeleton point at its center, the formulation above is often more general than required. A heuristic approach in which vertices lying closest together are merged is employed to produce smaller adjustment problems that are less expensive to solve. Heuristics can be used to identify vertices that are likely to coalesce, thereby reducing the dimensionality of the adjustment problem that must be solved for each tetrahedron. For interior points, the simplified problem includes ten variables (locations of the two contact points and the center and radius of the maximal inscribed sphere), with five constraints (contact points on the boundary, tangent to the sphere, and equidistant from the center). An initial guess for the values of these variables depend on the geometry of the tetrahedron involved.

In FIG. 7, three relevant geometric classes of tetrahedra are illustrated, including a class 236 that has a face with vertices on one of a bottom 232 and a top 234 (or other surfaces) of an object 230, a class 238 that has one or more line segments on a surface of the object, and a class 240 that has only points on the two surfaces of the object. Initial guesses for the boundary point locations are obtained as the ends of a line segment generated by merging the vertices of the tetrahedron, and the initial guess for the center is the center of the circumsphere. Based on the class of the tetrahedra, the initial guesses are generated and used to determine the ten variables required to define a skeleton point. For example, in class 236, a small face is defined by vertices T.sub.1, T.sub.2, and T.sub.3, which are likely to coalesce and are therefore merged a priori so that an adjustment is made starting with the two end points of the resulting line segment that extends between bottom 232 and top 234. Similarly, the tetrahedra in class 238 have two short edges between pairs of vertices (T.sub. T.sub.2, and B.sub.1 B.sub.2) that are likely to coalesce and can be merged to produce initial guesses. In the preferred embodiment, the merging is accomplished by determining D, the maximum average edge length associated with a vertex. If the shortest edge has a length less than D/5, its vertices are merged to produce a triangle to which the same merging criterion is applied. If these heuristics are not satisfied for a tetrahedron, the 16 variable problem is solved to produce the required skeleton point. For seam points, which occur for tetrahedra in class 240, the 16 variable model is used to generate the adjusted maximal inscribed spheres that possess three and four distinct contact points.

Improving the Accuracy of the Skeleton near Its Edges

In practice, the most significant inaccuracies are typically concentrated near the edge of the skeleton. Referring again to FIG. 1B, a block 36 provides for adjusting the position of skeleton edge vertices to minimize the errors of the refined skeleton. The result of this adjustment is a final accurate polygonal approximation of the skeleton, as indicated in a block 38. Since the edge of the skeleton arises as a result of the closure of the set of maximal inscribed spheres possessing distinct boundary tangency points, the maximal inscribed spheres associated with the skeleton edge possess only a single boundary tangency. Since distinct boundary tangencies do not exist, the optimization described above for adjusting the location of the interior vertices of the skeleton approximation will not be effective. An alternative approach is used to improve the location of the skeleton edge vertices. For sharp edges of the object (where the surface normal changes discontinuously), the skeleton extends to the boundary of the object, and the approximate skeleton vertex is moved to the nearest point on the sharp boundary edge. For smooth regions of the boundary, the skeleton edge does not extend to the boundary of the object. Skeleton edge points lie in the interior of the object and are centers of maximal spheres that contact the boundary at a single point where the two distinct tangency points of nearby maximal spheres effectively coalesce. This single tangency point is distinguished as a location of maximum value of principal curvature as the surface is traversed in the direction of maximal curvature. The edge optimization procedure can be summarized as follows:

Let x be a center of a circumsphere around a Delaunay tetrahedra at the edge of the skeleton. The problem is then to find a boundary point P to minimize .parallel.x'-x.parallel., where x' is the location of the center of the maximal circumsphere tangent to the boundary at O' subject to the constraints that P lies on the boundary and .gradient.K.sub.1 .multidot.u.sub.1 =0, K.sub.1 is the maximal principal curvature at P, and u.sub.1 is the direction vector associated with maximal principal curvature at P.

The edge vertex optimization involves three scalar variables and two constraints and is solved in the current embodiment by the SQP algorithm. Some care is appropriate in the selection of starting points for the optimization since nearby inflection points of the maximum curvature may cause convergence to a minimum rather than a maximum of K.sub.1. To attain reliable results, it is best to begin the optimization with a point on the curve of surface tangency points corresponding to the skeleton edge. This curve of associated tangency points for the skeleton edge is a principal curve associated with the direction of minimum curvature and is illustrated for the example of FIG. 2. A curve-tracing method, stepping in the direction of minimum curvature and searching transversely to find the local maxima of maximum principal curvature, is employed to follow this curve and sequentially generate starting points for the edge optimization.

In the example of FIG. 2, the skeleton edge was previously defined by a circumsphere center at x. Curves 50 and 52 represent the actual shape of the surface of the object at spaced-apart transverse points along the surface. The principal curve of transverse maxima of curvature is represented by a line 58. Starting at a vertex P.sub.1, which is a surface point, the process traverses along a curve 56 until it reaches the principal curve of transverse maxima of principal curvature represented by line 58. This point then is used to define a circumsphere centered at x* that is tangent to the surface at 0*, which lies on line 58. Additional circumspheres tangent to line 58 are then formed that meet the conditions noted above. The line through the centers of the these circumspheres then accurately defines the skeletal edge of the object. For example, the sphere centered at x' is tangent to the surface at 0'.

FIG. 3 shows a portion of a pruned Voronoi cell approximation 70 to the skeleton of a super ellipsoid 76, shown in FIG. 4. This approximation is based on 20,000 sampled surface points, and significant jaggedness is still observed near an edge 72 of the skeleton.

In FIG. 5D, the skeleton of the super ellipsoidal shape of FIGS. 3 and 4 is illustrated after the present invention has been employed to minimize errors in the interior and along at the edges of the skeleton. The benefits of the adjustment process used to minimize these errors will be readily apparent to those of skill in this art.

System for Implementing the Creation of a Skeleton

With reference to FIG. 8, a generally conventional personal computer 300 is illustrated, which is suitable for use in connection with practicing the present invention. Alternatively, a corresponding workstation on a local area network may be used for executing machine instructions comprising a computer program that causes the present invention to be executed. Personal computer 300 includes a processor chassis 302 in which are mounted a floppy disk drive 304, a hard drive 306, a motherboard populated with appropriate integrated circuits (not shown), and a power supply (also not shown), as are generally well known to those of ordinary skill in the art. A monitor 308 is included for displaying graphics and text generated by software programs that are run by the personal computer, and for graphically representing models of objects produced by the present invention. A mouse 310 (or other pointing device) is connected to a serial port (or to a bus port) on the rear of processor chassis 302, and signals from mouse 310 are conveyed to the motherboard to control a cursor on the display and to select text, menu options, and graphic components displayed on monitor 308 by software programs executing on the personal computer. In addition, a keyboard 313 is coupled to the motherboard for user entry of text and commands that affect the running of software programs executing on the personal computer.

Personal computer 300 also optionally includes a compact disk-read only memory (CD-ROM) drive 317 into which a CD-ROM disk may be inserted so that executable files and data on the disk can be read for transfer into the memory and/or into storage on hard drive 306 of personal computer 300. Other types of mass memory storage devices may also be provided. The machine instructions comprising the software program that causes the CPU to implement the functions of the present invention that have been discussed above will likely be distributed on floppy disks or CD-ROMs or other memory media and stored in the hard drive until loaded into random access memory (RAM) for execution by the CPU.

Although the present invention has been described in connection with the preferred form of practicing it, those of ordinary skill in the art will understand that many modifications can be made thereto within the scope of the claims that follow. Accordingly, it is not intended that the scope of the invention in any way be limited by the above description, but instead be determined entirely by reference to the claims that follow.