Approximate convex decomposition of polyhedra

Jyh Ming Lien, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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)
Title of host publicationProceedings - SPM 2007
Subtitle of host publicationACM Symposium on Solid and Physical Modeling
Pages121-131
Number of pages11
DOIs
StatePublished - 2007
Externally publishedYes
EventSPM 2007: ACM Symposium on Solid and Physical Modeling - Beijing, China
Duration: Jun 4 2007Jun 6 2007

Publication series

NameProceedings - SPM 2007: ACM Symposium on Solid and Physical Modeling

Conference

ConferenceSPM 2007: ACM Symposium on Solid and Physical Modeling
Country/TerritoryChina
CityBeijing
Period6/4/076/6/07

Keywords

  • Concavity measurement
  • Convex decomposition

ASJC Scopus subject areas

  • Computer Science Applications
  • Software
  • Modeling and Simulation

Fingerprint

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

Cite this