Constructing shape skeletons of 3D objects using generalized Voronoi diagrams
US6133921A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | May 23, 1997 |
| Grant date | Oct 17, 2000 |
| Priority date | — |
| Expiry date | May 23, 2017 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/20
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.