Constructing shape skeletons of 3D objects using generalized Voronoi diagrams

Claim 3

The method of claim 1, wherein the simplices comprise Delaunay tetrahedra.

Claim 4

The method of claim 1, further comprising the step of removing at least some of any simplices that are external to a boundary of the object.

Claim 5

The method of claim 1, wherein the centers of the circumspheres whose simplices share a common face are connected to form the approximate skeleton, said step of connecting forming a plurality of closed Voronoi cells.

Claim 6

The method of claim 4, further comprising the step of removing connections between the centers of circumspheres that do not form closed Voronoi cells.

Claim 7

The method of claim 5, further comprising the step of forming a connectivity graph based on common cell edges, said connectivity graph being traversed to identify Voronoi cells that comprise patches, said patches collectively approximating the skeleton.

Claim 8

The method of claim 1, wherein the step of adjusting includes the step of adjusting at least one of: (a) a disposition of the vertices of the simplices; (b) a radius of a circumsphere; and (c) a disposition of the circumsphere to create a maximal inscribed sphere, a circumsphere being a maximal inscribed sphere if the vertices of said 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.

Claim 9

The method of claim 1, wherein the step of adjusting includes the step of adjusting 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.

Claim 12

The method of claim 9, wherein a circumsphere is a maximal inscribed sphere if the vertices of the tetrahedra that the circumsphere circumscribes lie on a boundary of the object and are disposed where the circumsphere is tangent to the boundary of the object.

Claim 13

The method of claim 9, wherein the surface point data have sufficient density so that a maximum distance between adjacent points is smaller than any surface feature to be represented by the skeleton.

Claim 14

The method of claim 9, further comprising the step of removing spurious tetrahedra that occur apart from any portion of the object associated with an edge point of the skeleton.

Claim 15

The method of claim 9, further comprising the step of subdividing the Voronoi cells into triangles by introducing internal edges.

Claim 16

The method of claim 9, further comprising the step of constructing a connectivity graph, wherein the approximate skeleton is formed by traversing the connectivity graph to identify patches that collectively comprise the approximate skeleton.

Claim 17

Apparatus for constructing a skeleton representing an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory for storing machine instructions that comprise a computer program; and (b) a processor, coupled to the memory, said processor executing the computer program and thereby implementing a plurality of functions, including: (i) producing simplices having vertices at surface data points that sample a boundary of the object; (ii) forming circumspheres comprising hyperspheres that circumscribe the simplices; (iii) connecting centers of the circumspheres to form an approximate skeleton; and (iv) adjusting the circumspheres so as to minimize an error in the disposition of the vertices of the approximate skeleton and thereby producing an accurate skeleton of the object.

Claim 18

Apparatus for constructing a skeleton representing an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory for storing machine instructions that comprise a computer program; and (b) a processor, coupled to the memory, said processor executing the computer program and thereby implementing a plurality of functions, including: (i) producing simplices having vertices at surface data points that sample a boundary of the object; (ii) forming circumspheres comprising hyperspheres that circumscribe the simplices; (iii) connecting centers of the circumspheres to form an approximate skeleton; and (iv) adjusting the circumspheres so as to minimize an error in the disposition of the vertices of the approximate skeleton and thereby producing an accurate skeleton of the object.

Claim 19

Apparatus for constructing a skeleton for an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory for storing machine instructions that comprise a computer program; and (b) a processor, coupled to the memory, said processor executing the computer program and thereby implementing a plurality of functions, including: (i) performing a Delaunay triangulation of surface point data that sample a boundary of the object at a plurality of points to produce tetrahedra having vertices at the points, said tetrahedra not containing any of the points and comprising a complex hull of the surface point data; (ii) removing at least some of any tetrahedra that lie outside the boundary of the object; (iii) constructing circumspheres that circumscribe the tetrahedra disposed within the boundary; (iv) connecting centers of adjacent circumspheres circumscribed about tetrahedra that share a common face, and forming Voronoi cells using connections that are created thereby; (v) identifying closed Voronoi cells and removing centers of circumspheres that are not part of any closed Voronoi cell and connections to said centers, producing an approximation of the skeleton; (vi) adjusting positions of interior vertices of the approximate skeleton by adjusting at least one of: dispositions of the vertices, lengths of radii, and dispositions of centers of the circumspheres, to produce maximal inscribed spheres; and (vii) adjusting positions of edge vertices of the skeleton to correspond to centers of other maximal inscribed spheres that are tangent to the boundary at single points of transverse maxima of a maximum principal curvature, yielding an accurate skeleton of the object.

Claim 20

Apparatus for constructing a skeleton for an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory for storing machine instructions that comprise a computer program; and (b) a processor, coupled to the memory, said processor executing the computer program and thereby implementing a plurality of functions, including: (i) performing a Delaunay triangulation of surface point data that sample a boundary of the object at a plurality of points to produce tetrahedra having vertices at the points, said tetrahedra not containing any of the points and comprising a complex hull of the surface point data; (ii) removing at least some of any tetrahedra that lie outside the boundary of the object; (iii) constructing circumspheres that circumscribe the tetrahedra disposed within the boundary; (iv) connecting centers of adjacent circumspheres circumscribed about tetrahedra that share a common face, and forming Voronoi cells using connections that are created thereby; (v) identifying closed Voronoi cells and removing centers of circumspheres that are not part of any closed Voronoi cell and connections to said centers, producing an approximation of the skeleton; (vi) adjusting positions of interior vertices of the approximate skeleton by adjusting at least one of: dispositions of the vertices, lengths of radii, and dispositions of centers of the circumspheres, to produce maximal inscribed spheres; and (vii) adjusting positions of edge vertices of the skeleton to correspond to centers of other maximal inscribed spheres that are tangent to the boundary at single points of transverse maxima of a maximum principal curvature, yielding an accurate skeleton of the object.

Claim 21

An article of manufacture for use with a computer to construct a skeleton representing an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory media, adapted to be used with a computer; and (b) a plurality of machine instructions stored on the memory media, said machine instructions, when executed by the computer, effecting a plurality of functions, including: (i) producing simplices having vertices at surface data points that sample a boundary of the object; (ii) forming circumspheres comprising hyperspheres that circumscribe the simplices; (iii) connecting centers of the circumspheres to form an approximate skeleton; and (iv) adjusting the circumspheres so as to minimize an error in the disposition of the vertices of the approximate skeleton and thereby producing an accurate skeleton of the object.

Claim 22

An article of manufacture for use with a computer to construct a skeleton representing an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory media, adapted to be used with a computer; and (b) a plurality of machine instructions stored on the memory media, said machine instructions, when executed by the computer, effecting a plurality of functions, including: (i) producing simplices having vertices at surface data points that sample a boundary of the object; (ii) forming circumspheres comprising hyperspheres that circumscribe the simplices; (iii) connecting centers of the circumspheres to form an approximate skeleton; and (iv) adjusting the circumspheres so as to minimize an error in the disposition of the vertices of the approximate skeleton and thereby producing an accurate skeleton of the object.

Claim 23

An article of manufacture for use with a computer to construct a skeleton for an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory media, adapted to be used with a computer; and (b) a plurality of machine instructions stored on the memory media, said machine instructions, when executed by the computer, effecting a plurality of functions, including: (i) performing a Delaunay triangulation of surface point data that sample a boundary of the object at a plurality of points to produce tetrahedra having vertices at the points, said tetrahedra not containing any of the points and comprising a complex hull of the surface point data; (ii) removing at least some of any tetrahedra that lie outside the boundary of the object; (iii) constructing circumspheres that circumscribe the tetrahedra disposed within the boundary; (iv) connecting centers of adjacent circumspheres circumscribed about tetrahedra that share a common face, and forming Voronoi cells using connections that are created thereby; (v) identifying closed Voronoi cells and removing centers of circumspheres that are not part of any closed Voronoi cell and connections to said centers, producing an approximation of the skeleton; (vi) adjusting positions of interior vertices of the approximate skeleton by adjusting at least one of: dispositions of the vertices, lengths of radii, and dispositions of centers of the circumspheres, to produce maximal inscribed spheres; and (vii) adjusting positions of edge vertices of the skeleton to correspond to centers of other maximal inscribed spheres that are tangent to the boundary at single points of transverse maxima of a maximum principal curvature, yielding an accurate skeleton of the object.

Claim 24

An article of manufacture for use with a computer to construct a skeleton for an object, said object being defined by boundary data that represent a surface of the object, comprising: (a) a memory media, adapted to be used with a computer; and (b) a plurality of machine instructions stored on the memory media, said machine instructions, when executed by the computer, effecting a plurality of functions, including: (i) performing a Delaunay triangulation of surface point data that sample a boundary of the object at a plurality of points to produce tetrahedra having vertices at the points, said tetrahedra not containing any of the points and comprising a complex hull of the surface point data; (ii) removing at least some of any tetrahedra that lie outside the boundary of the object; (iii) constructing circumspheres that circumscribe the tetrahedra disposed within the boundary; (iv) connecting centers of adjacent circumspheres circumscribed about tetrahedra that share a common face, and forming Voronoi cells using connections that are created thereby; (v) identifying closed Voronoi cells and removing centers of circumspheres that are not part of any closed Voronoi cell and connections to said centers, producing an approximation of the skeleton; (vi) adjusting positions of interior vertices of the approximate skeleton by adjusting at least one of: dispositions of the vertices, lengths of radii, and dispositions of centers of the circumspheres, to produce maximal inscribed spheres; and (vii) adjusting positions of edge vertices of the skeleton to correspond to centers of other maximal inscribed spheres that are tangent to the boundary at single points of transverse maxima of a maximum principal curvature, yielding an accurate skeleton of the object.