Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1997-05-23
2000-10-17
Zimmerman, Mark K.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
345441, G06T 1700
Patent
active
061339210
ABSTRACT:
Starting with a solid model of a 3D object, an accurate skeleton is produced by minimizing internal and edge errors of an initial approximate skeleton. To produce the initial approximate skeleton, the boundary of the solid is densely sampled to obtain a set of surface data points. Delaunay triangulation is performed on the surface data points and exterior and spurious tetrahedra are removed, leaving substantially interior tetrahedra. Circumspheres are constructed that enclose the tetrahedra, and the centers of the circumspheres are connected based on tetrahedra adjacency, to form a Voronoi diagram. Closed Voronoi cells are identified comprising the initial approximate skeleton. The position of skeleton interior vertices are then adjusted to minimize their error, producing a refined polygonal approximation of the skeleton interior geometry. Positions of the skeleton edge vertices are adjusted to minimize the edge error, yielding an accurate polygonal approximation of the skeleton.
REFERENCES:
patent: 4933889 (1990-06-01), Meshkat et al.
patent: 5522019 (1996-05-01), Bala et al.
patent: 5542036 (1996-07-01), Schroeder et al.
patent: 5559935 (1996-09-01), Itoh et al.
patent: 5617322 (1997-04-01), Yokota
patent: 5774696 (1998-06-01), Akiyama
Turner, J; Accurate Solid Modeling Using Polyhedral Approximations; IEEE Computer Graphics & Applications; pp. 14-28, 1988.
Herman, G. et al.; Shape-based Interpolation; IEEE Computer Graphics & Applications; pp. 69-79, May 1992.
Lavender, D. et al.; Voronoi Diagrams of Set-Theoretic Solid Models; IEEE Computer Graphics & Applications; pp. 69-77, Sep. 1992.
Zhou, J.M. et al.; Automatic Creation of 3D Meshes for Complicated Solids; IEEE Transactions on Magnetics, vol. 28, No. 2; pp. 1759-1762, Mar. 1992.
Sequeira, R. et al.; Disctrete Voronoi Diagrams and the SKIZ Operator: A Dynamic Algorithm; IEEE Transactions on Pattern Analysis and Machine Intellegence, vol. 19, No. 10; pp. 1165-1170, Oct. 1997.
Pai T.W., et al; Boundary-Constrained Morphological Skeleton Minimization and Skeleton Reconstruction; IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, No. 2; pp. 201-208, Feb. 1994.
Chen Hao
Ganter Mark A.
Storti Duane W.
Turkiyyah George M.
Anderson Ronald M.
Lee Albert K.
University of Washington
Zimmerman Mark K.
LandOfFree
Constructing shape skeletons of 3D objects using generalized Vor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Constructing shape skeletons of 3D objects using generalized Vor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing shape skeletons of 3D objects using generalized Vor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-473962