Approximate Convex Decomposition
JyhMing Lien and Nancy Amato
Overview
One common strategy for dealing with large, complex models is to partition them into pieces that are easier to handle. Many problems can be solved more efficiently when the input is convex. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and often result in representations with an unmanageable number of components. We propose an alternative partitioning strategy that decomposes a given model (in 2D or 3D) into approximately convex pieces.Here are some benefits of ACD over the traditional exact convex decomposition:
 For many applications, the approximately convex components of this decomposition provide similar benefits as convex components.
 The resulting decomposition is both significantly smaller and can be computed more efficiently.
 An approximate convex decomposition can more accurately represent the important structural features of the model by providing a mechanism for ignoring insignificant features, such as wrinkles and other surface texture.
 It produces an elegant hierarchical representation
Software
Download the code from the Software pageACD and it's applications
ACD of Polygons Animations and images of 2D ACD can be found here: 

ACD of Polyhedra Animations and images of 3D ACD can be found here:



Application: Skeleton extraction 


Application: Mesh generation

Publications
Approximate Convex Decomposition of Polyhedra, JyhMing Lien, Nancy M. Amato, In Proc. of the ACM Symposium on Solid and Physical Modeling (SPM), Beijing, China, June 2007, to appear. Also, Technical Report, TR06002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2006.
Full text: Proceedings (pdf) Technical Report (pdf)
Approximate Convex Decomposition and Its Applications,
JyhMing Lien, Ph.D. Thesis, Department of Computer Science, Texas A&M University, Dec 2006.
Full text: Ph.D. Thesis (pdf)
Simultaneous Shape Decomposition and Skeletonization, JyhMing Lien, John Keyser, Nancy M. Amato, In Proc. ACM Solid and Physical Modeling Symp. (SPM), pp. 219228, Cardiff, Wales, UK, Jun 2006. Also, Technical Report, TR05015, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2005.
Full text: Proceedings (pdf) Technical Report (ps, pdf)
Approximate Convex Decomposition of Polygons, JyhMing Lien, Nancy M. Amato, Computational Geometry: Theory & Applications. Also, In Proc. ACM Symp. Comput. Geom., pp. 1726, Brooklyn, New York, Jun 2004. Also, Technical Report, TR03008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2003. Also, Technical Report, TR03008, Department of Computer Science, Texas A&M University, Texas, Jun 2003.
Full text: Journal (ps, pdf) Proceedings (ps, pdf)
Approximate Convex Decomposition, JyhMing Lien, Nancy M. Amato, In Proc. ACM Symp. Comput. Geom., pp. 457458, Brooklyn, New York. Video Abstract, Jun 2004. Also, Technical Report, TR03001, Department of Computer Science, Texas A&M University, Jan 2003.
Full text: Proceedings (ps, pdf) Technical Report (ps, pdf)
Benchmarks
List of MASC Research Pages