| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News

Algorithms & Applications Group
Fast Approximate Convex Decomposition

Fast Approximate Convex Decomposition
Mukulika Ghosh and Nancy M. Amato
Project Alumni: Jyh-Ming Lien

It is an extension of Approximate Convex Decomposition algorithm of Amato and Lien. It partitions a given input model into "approximately convex" pieces while emphasizing structurally important parts of the model in decomposition.
Although optimal solution for decomposition is difficult to obtain, we propose an algorithm which predicts a set of decomposition boundaries and finds a good solution from this set. Unlike constructing a single cut at each step in the recursion, multiple non-crossing cuts are constructed and a subset of these cuts is selected using dynamic programming approach to decompose the model.
We also introduced a new measure associated with each cut which quantifies the impact of the cut on the concavity of the model. This measure is known as relative concavity of a cut which priortizes structural concavities over surface noise or texture.

Contribution over ACD:

• Absolute concavity measure is replaced by relative concavity to decompose the input model along "important" structural concavities.
• No greedy approach is used to resolve concavity. Instead of selecting a single cut at each recursive step, multiple cuts are selected from a set of possible independent cuts.

Relative vs. Absolute Concavity

Certain concavities of model might have low absolute concavity value. Using the user-defined tolerance over this absolute measure might overlook such concavities during decomposition. Whereas lowering the tolerance might cause decomposition along unnecessary regions. Hence in this work, we use the user-defined tolerance over relative concavity. It is the ratio of concavity of the model before and after application of a cut. A cut is known as "important" if it's relative concavity is above the user-defined tolerance. As shown in the figure below, the small structural concavities like hoofs and ears of the horse model is emphasized without causing oversegmentation in the torso and legs.

Salient features of relative concavity:

• Emphasizes sudden change in concavity over gradual increase or decrease in concavity of the model.
• A relative and localized measure associated with segmentation boundary or cut.
• Distinguishes surface undulation, texture or noise from structural concavity.

Multiple cuts selection

In original ACD, a single cut that contains the vertex of maximum concavity is used to decompose the input model into two components, both of which are processed recursively. To avoid recursive application, multiple non-crossing cuts are applied to decompose the model in a single iteration. In particular, a set of non-crossing cuts are selected that will decompose the model into set of components each of which meets the required threshold.
This is done by identifying a set of non-crossing (independent) cuts, known as potential cuts, in the model. If all the potential cuts are applied on the model, they will divide the model into set of primary components. The primary components and the potential cuts are placed in a "cut-graph" where the edges represent the potential cuts and the vertices indicate these primary component. The final set of cuts used to decompose the model is then selected using a dynamic programming approach. The cut-graph is used to define a linear ordering of the primary components which are the initial sub-problems in the dynamic programming. The objective function maximizes the relative concavity of important splitting cuts in the sub-problem. This reduces the depth of recursion and along with certain optimization techniques (as described below) improves the efficiency of the decomposition algorithm.

Merging of Convex Hulls

This is a sub-problem addressed to improve the complexity using re-usability. Measuring concavity of a model involves building its convex hull. We propose a novel method to build the convex hull of two intersecting models from their existing convex hulls.
It is an incremental algorithm which finds the intersection in the existing convex hulls and merges them along the traced intersection. The hull of the merged structure is then constructed by iteratively merging pair of facets (in 3D) or edges (in 2D) starting from those along the intersection till the resulting structure is convex.
For more details refer Merging of Intersecting Convex Hulls

Results

Related Projects

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)

 Parasol Home | Research | People | General info | Seminars | Resources   Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science and Engineering Engineering TAMU Web Accessibility Policy and Law - Web Accessibility and Usability Standards  -   Contact Webmaster