
Fast Approximate Convex Decomposition
Mukulika Ghosh and
Nancy M. Amato
Project Alumni: JyhMing 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 noncrossing 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:
Relative vs. Absolute Concavity
Certain concavities of model might have low absolute concavity value. Using the userdefined 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 userdefined 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 userdefined 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:
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 noncrossing cuts are applied to decompose the model in a single iteration. In particular, a set of noncrossing 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 noncrossing (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 "cutgraph" 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 cutgraph is used to define a linear ordering of the primary components which are the initial subproblems in the dynamic programming. The objective function maximizes the relative concavity of important splitting cuts in the subproblem. 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 subproblem addressed to improve the complexity using reusability. 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
Approximate Convex Decomposition
Merging of Intersecting Convex Hulls
Fast Approximate Convex Decomposition Using Relative Concavity, Mukulika Ghosh, Nancy M. Amato, Yanyan Lu, JyhMing Lien, Computer AidedDesign, 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 (HsinYi) Yeh, Shawna Thomas, Nancy M. Amato, Technical Report, TR13005, 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, JyhMing 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, JyhMing Lien, Nancy M. Amato, Computer Aided Geometric Design, 25(7):503522, Oct 2008. Also, In Proc. ACM Solid and Physical Modeling Symp. (SPM), pp. 121131, New York, NY, USA, Jun 2007. Also, Technical Report, TR06002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jan 2006. Also, Technical Report, TR05001, 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, JyhMing 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, JyhMing Lien, Nancy M. Amato, Computational Geometry: Theory & Applications, To appear:2005. Also, In Proc. ACM Symp. Comput. Geom., pp. 1726, Brooklyn, New York, Jun 2004. Also, Technical Report, TR03008, Parasol Laboratory, Department of Computer Science, Texas A&M University, Dec 2003. Also, Technical Report, TR03008, 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, JyhMing Lien, Nancy M. Amato, In Proc. ACM Symp. Comput. Geom., pp. 457458, Brooklyn, New York. Video Abstract, Jun 2004. Also, Technical Report, TR03001, 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 778433112 parasoladmin@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 