Computation of 3D skeletons using a generalized Delaunay triangulation technique

Jayachandra M. Reddy, George Turkiyyah

Research output: Contribution to journalArticlepeer-review

59 Scopus citations

Abstract

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, 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.

Original languageEnglish (US)
Pages (from-to)677-694
Number of pages18
JournalComputer-Aided Design
Volume27
Issue number9
DOIs
StatePublished - Jan 1 1995

Keywords

  • Delaunay triangulation
  • Voronoi diagrams
  • medial axis transforms

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'Computation of 3D skeletons using a generalized Delaunay triangulation technique'. Together they form a unique fingerprint.

Cite this