Approximate convex decomposition of polyhedra and its applications

Jyh Ming Lien, Nancy M. Amato

Research output: Contribution to journalArticlepeer-review


Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (acd) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing acds of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using acd decompositions in place of exact convex decompositions (ecd) that are several orders of magnitude larger.

Original languageEnglish (US)
Pages (from-to)503-522
Number of pages20
JournalComputer Aided Geometric Design
Issue number7
StatePublished - Oct 2008
Externally publishedYes


  • Concavity measurement
  • Convex decomposition
  • Feature grouping

ASJC Scopus subject areas

  • Modeling and Simulation
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Approximate convex decomposition of polyhedra and its applications'. Together they form a unique fingerprint.

Cite this