Home research People General Info Seminars Resources Intranet

Jyh-Ming Lien, Nancy M. Amato, "Approximate Convex Decomposition of Polyhedra," Technical Report, TR05-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2005.
Technical Report(ps, pdf, abstract)

One common strategy for dealing with large, complex models is to partition them into pieces that are easier to handle. 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 in R2 or R3 into "approximately convex" pieces that may provide similar bene ts as convex components, while the resulting decomposition is both significantly smaller and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition can more accurately represent the important structural features of the model by providing a mechanism for ignoring less signi cant features, such as wrinkles and other surface texture. Recently, a method for approximate convex decomposition (ACD) of polygons with zero or more holes has been proposed and shown both theoretically and experimentally to efficiently produce high quality decompositions. In this paper, we identify and address several challenges in extending the approach to three-dimensions and provide evidence that ACD of polyhedra can provide similar advantages as for polygons. We also demonstrate several of its applications.