Approximate Convex Decomposition (ACD)
supported by NSF
Jyh-Ming Lien and Nancy M. Amato

(This page is no longer maintained, please visit this webpage for now updates.)

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 it 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(nr2) 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

Benchmarks

• 2D & 3D Geometric Decomposition Benchmarks

Papers

Related Projects

Skeleton Extraction

Papers

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, abstract)

Simultaneous Shape Decomposition and Skeletonization, Jyh-Ming Lien, John Keyser, Nancy M. Amato, In Proc. ACM Solid and Physical Modeling Symp. (SPM), pp. 219-228, Cardiff, Wales, UK, Jun 2006. Also, Technical Report, TR05-015, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2005.
Proceedings(pdf, abstract) Technical Report(ps, pdf, abstract)

Approximate Convex Decomposition of Polyhedra, Jyh-Ming Lien, Nancy M. Amato, Technical Report, TR06-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2006.
Technical Report(pdf, abstract)

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, abstract) Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

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, abstract)

Parasol Home | Research | People | General info | Seminars | Resources   Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  Contact Webmaster      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science Engineering TAMU