Approximate Convex Decomposition 2005 Tech Report

 Convex solid decomposition (Full size image) The leftmost image shows an Exact Convex Decomposition. The size and time of ACD without (top images) and with (bottom images) feature grouping are shown for a range approximation values tau. Convex surface decomposition (Full size image) The leftmost figure shows a result of the exact decomposition. The others are results of the approximate decomposition.

Genus reduction

 Genus reduction is a process of finding sets of edges (called handle cuts) whose removal will reduce the number of homological loops on the surface of a polyhedron. Our approach is based on the intuition that the bridges that share the same pocket tell us approximate locations of the handles, i.e., these bridges can serve as entrances to and exits from the enclosed handles. The figure on the left shows the handle cuts (in red curves) of the David model.

Shape decomposition
The components of an ACD can also be used for shape representation. We argue that in many cases the significance of a feature depends on its volumetric proportion to its "base". For example, a 5 cm stick on a ball with 5 cm radius is a more significant feature than a 5 cm stick on a ball with 5 km radius. This intuition can be captured by the concept of convexity. Unlike concavity, convexity is independent of the size of a model and always has a value between 0 and 1.

 Bear top: ACD components bottom: the convex hulls of the ACD components 71,372 triangles take 6.9 sec to decompose result in 6 components Dragon top: ACD components bottom: the convex hulls of the ACD components 871,414 triangles take 386.2 sec to decompose result in 43 components Horse top: ACD components bottom: the convex hulls of the ACD components 39,694 triangles take 15.4 sec to decompose result in 17 components Deformed Horse (a skeletal deformation of the Horse model) top: ACD components bottom: the convex hulls of the ACD components 39,694 triangles take 16.1 sec to decompose result in 22 components