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. Benefits of ACD: 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 ACD and its applications ACD of Polygons We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (re- solving) the most significant non-convex feature (notch). Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or, if the polygon has no holes, takes O(nr^2) time. Animations and images of 2D ACD can be found here: Videos from Approximate Convex Decomposition (SoCG04 video&MM) Images from Approximate Convex Decomposition for Polygons. (SoCG04) Images from Approximate Convex Decomposition (Tech. Report TR03-001) ACD of Polyhedra There are several challenges faced when extending ACD to polyhedra. One operation that we use to address some of these issues is to group certain types of adjacent features and to process them as a unit. As we have shown, this can help us to both reduce computational costs and to improve the quality of the resulting decomposition. Animations and images of 3D ACD can be found here: Images from Approximate Convex Decomposition of Polyhedra (Tech. Report TR05-001) Videos from Approximate Convex Decomposition (SoCG04 video&MM) Videos and images from Approximate Convex Decomposition (Tech. Report TR03-001) Application: Skeleton extraction A skeleton of the model is extracted from the convex hulls of these nearly convex components. The process of shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. An example of the extracted skeleton and the deformed models using the extracted skeleton are shown on the left. Animation using the extracted skeleton and motion capture data: boxing (avi [divx] 6.2 MB, mov [quicktime] 19 MB) sexy walk (avi [divx] 4.2 MB, mov [quicktime] 6.8 MB) push a box (avi [divx] 2.0 MB, mov [quicktime] 3.1 MB) More information can be found here: Skeleton extraction Application: Mesh generation Tetrahedral meshes can be easily generated from the convex hulls of the ACD components. These meshes, which tightly enclose and approximate the shape of the input model, can be used to provide visually realistic deformations. We have applied this strategy for efficiently planning motion of deformable objects. Videos: (avi [dvix], 2Mb) (mov [quicktime], 13Mb) More videos and images can be found here Software acd2d_gui version 0.5 download binary: all platforms, models: polygons Note: You may need to have glut library if you want to visualize the results. You can get glut from freeglut for linux and from this page for win32. Source code (in C++) is available on request Report bugs to jmlien@cs.gmu.edu We are working toward the first release of acd3d. Please check back later. Publications Approximate Convex Decomposition of Polyhedra, Jyh-Ming 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, TR06-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2006. Proceedings (pdf) Technical Report (pdf) Approximate Convex Decomposition and Its Applications, Jyh-Ming Lien, Ph.D. Thesis, Department of Computer Science, Texas A&M University, Dec 2006. Ph.D. Thesis(pdf) Simultaneous Shape Decomposition and Skeletonization, Jyh-Ming Lien, John Keyser, Nancy M. Amato, In Proc. ACM Solid a nd Physical Modeling Symp. (SPM), pp. 219-228, Cardiff, Wales, UK, Jun 2006. Also, Technical Report, TR05-015, Parasol Laboratory, Depa rtment of Computer Science, Texas A&M University, Dec 2005. Proceedings (pdf) Technical Report (ps, pdf) Approximate Convex Decomposition of Polygons, Jyh-Ming Lien, Nancy M. Amato, Computational Geometry: Theory & Applications, To appear:2005. Also, In Proc. ACM Symp. Comput. Geom., pp. 17-26, Brooklyn, New York, Jun 2004. Also, Technical Report, TR03-008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2003. Also, Technical Report, TR03-008, Department of Computer Science, Texas A&M University, Texas, Jun 2003. Journal (ps, pdf) Proceedings (ps, pdf) Approximate Convex Decomposition, Jyh-Ming Lien, Nancy M. Amato, In Proc. ACM Symp. Comput. Geom., pp. 457-458, Brooklyn, New York. Video Abstract, Jun 2004. Also, Technical Report, TR03-001, Department of Computer Science, Texas A&M University, Jan 2003. Proceedings (ps, pdf) Technical Report (ps, pdf) Benchmarks 2D & 3D Geometric Decomposition Benchmarks