Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Approximate Convex Decomposition

Project Personnel:Mukulika Ghosh,Nancy Amato

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

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.

  • More results 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)
  • More information can be found here: Approximate Convex Decomposition

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)
  • More information can be found here: Approximate Convex Decomposition

ACD described above uses a greedy recursive approach to decompose an input model into approximately convex pieces. Hence in this proposed work, the decomposition is improved by selection of multiple segmentation boundaries for decomposition from a set of possible segmentation boundaries. Also instead of using the user-defined threshold over an absolute measure of concavity, it is used as a tolerance over a relative concavity measure to result in more natural looking decomposition.

ACD
FACD at two levels

More details can be found here: Fast Approximate Convex Decomposition

Skeletonization

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 is shown below.

  • 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

Motion Planning of Deformable Objects

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

Fast Approximate Convex Decomposition Using Relative Concavity, Mukulika Ghosh, Nancy M. Amato, Yanyan Lu, Jyh-Ming Lien, Computer Aided-Design, 45(2):494 - 504, 2013. Also, In Proc. ACM Solid and Physical Modeling Symp. (SPM), France, Oct 2012.
Journal(pdf, abstract) Proceedings(pdf, abstract)

Nearly Uniform Sampling on Surfaces with Applications to Motion Planning, Mukulika Ghosh, Cindy (Hsin-Yi) Yeh, Shawna Thomas, Nancy M. Amato, Technical Report, TR13-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Apr 2013.
Technical Report(pdf, abstract)

Fast Approximate Convex Decomposition, Mukulika Ghosh, Masters Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA, Aug 2012.
Masters Thesis(pdf)

Alpha decomposition of Polygons, Yanyan Lu, Jyh-Ming Lien, Mukulika Ghosh, Nancy M. Amato, Computers & Graphics, 36(5):466 - 476, 2012. Also, In Proc. of Shape Modeling International (SMI), College Station, TX, US, May 2012.
Journal(pdf, abstract) Proceedings(pdf, abstract)

Approximate Convex Decomposition of Polyhedra, Jyh-Ming Lien, Nancy M. Amato, Computer Aided Geometric Design, 25(7):503-522, Oct 2008. Also, In Proc. ACM Solid and Physical Modeling Symp. (SPM), pp. 121-131, New York, NY, USA, Jun 2007. Also, Technical Report, TR06-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2006. Also, Technical Report, TR05-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2005.
Journal(pdf, abstract) Proceedings(pdf, abstract) Technical Report(pdf, abstract) Technical Report(ps, pdf, abstract)

Approximate Convex Decomposition and Its Applications, Jyh-Ming Lien, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Dec 2006.
Ph.D. Thesis(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 and Engineering, 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 and Engineering, Texas A&M University, Jan 2003.
Proceedings(ps, pdf) Technical Report(ps, pdf, abstract)

Supported by NSF

Project Alumni:Jyh-Ming Lien