An accelerated triangulation method for computing the skeletons of free-form solid models

George Turkiyyah*, Duane W. Storti, Mark Ganter, Hao Chen, Munikumar Vimawala

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


Shape skeletons are powerful geometric 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 design. As a result there has been significant interest in the development of effective methods for skeleton generation of general free-form solids. In this paper we describe a method that combines Delaunay triangulation with local numerical optimization schemes for the generation of accurate skeletons of 3D implicit solid models. The proposed method accelerates the slow convergence of Voronoi diagrams to the skeleton, which, without optimization, would require impractically large sample point sets and resulting meshes to attain acceptable accuracy. The Delaunay triangulation forms the basis for generating the topological structure of the skeleton. The optimization step of the process generates the geometry of the skeleton patches by moving the vertices of Delaunay tetrahedra and relocating their centres to form maximally inscribed spheres. The computational advantage of the optimization scheme is that it involves the solution of one small optimization problem per tetrahedron and its complexity is therefore only linear (O(n)) in the number of points used for the skeleton approximation. We demonstrate the effectiveness of the method on a number of representative solid models.

Original languageEnglish (US)
Pages (from-to)5-19
Number of pages15
JournalCAD Computer Aided Design
Issue number1
StatePublished - Jan 1 1997


  • Delaunay triangulation
  • Implicit solid models
  • Medial axis
  • Skeleton generation
  • Surface curvature

ASJC Scopus subject areas

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


Dive into the research topics of 'An accelerated triangulation method for computing the skeletons of free-form solid models'. Together they form a unique fingerprint.

Cite this