TY - GEN
T1 - Approximate convex decomposition of polyhedra
AU - Lien, Jyh Ming
AU - Amato, Nancy M.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Concavity measurement
KW - Convex decomposition
UR - http://www.scopus.com/inward/record.url?scp=35348823676&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35348823676&partnerID=8YFLogxK
U2 - 10.1145/1236246.1236265
DO - 10.1145/1236246.1236265
M3 - Conference contribution
AN - SCOPUS:35348823676
SN - 1595936661
SN - 9781595936660
T3 - Proceedings - SPM 2007: ACM Symposium on Solid and Physical Modeling
SP - 121
EP - 131
BT - Proceedings - SPM 2007
T2 - SPM 2007: ACM Symposium on Solid and Physical Modeling
Y2 - 4 June 2007 through 6 June 2007
ER -