Home research People General Info Seminars Resources Intranet

Jyh-Ming Lien, Nancy M. Amato, "Approximate Convex Decomposition of Polyhedra," In Proc. ACM Solid and Physical Modeling Symp. (SPM), pp. 121-131, New York, NY, USA, Jun 2007.
Proceedings(pdf, 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 decom- positions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we ex- plore 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 provid- ing a mechanism for ignoring less significant features, such as sur- face texture. We describe a technique for computing ACD s 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 show- ing that comparable or better results can be obtained using ACD de- compositions in place of exact convex decompositions ( ECD ) that are several orders of magnitude larger. CR Categories: I.3.5 [COMPUTER GRAPHICS]: Computa- tional Geometry and Object Modeling—Geometric algorithms, lan- guages, and systems Keywords: concavity measurement, convex decomposition