Approximate Convex Decomposition


Jyh-Ming 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:

Software
Download the code from the Software page

ACD and it's 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
    		•

    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.
    Full text: 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.
    Full text: Ph.D. Thesis (pdf)

    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.
    Full text: Proceedings (pdf) Technical Report (ps, pdf)

    Approximate Convex Decomposition of Polygons, Jyh-Ming Lien, Nancy M. Amato, Computational Geometry: Theory & Applications. 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.
    Full text: 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.
    Full text: Proceedings (ps, pdf) Technical Report (ps, pdf)

    Benchmarks

    List of MASC Research Pages
    Computer Science @ George Mason University