Approximate Convex Decomposition for 3D Meshes with Collision-Aware Concavity and Tree Search

Introduction

• Convex decomposition supports geometry processing because many tasks that are expensive for general shapes can use efficient convex optimization algorithms for convex polyhedra [Snoeyink 2017; Bergen 1999; Liu et al. 2008; Mirtich 1998; Gilbert et al. 1988].Examples include point-in-mesh tests, mesh intersection checks, and minimum-distance calculations.Source: §1 · pp. 1–2
• ACD relaxes exact convexity to produce fewer components than exact convex decomposition, whose minimum-component formulation is NP-hard.The components’ convex hulls approximate the original shape and can speed downstream applications; V-HACD is widely adopted in game engines and physics simulation SDKs.Source: §1 · p. 2
• Existing ACD methods may fill collision-sensitive gaps, create intersecting hulls or voxelization artifacts, and make short-sighted cuts that increase component counts.Boundary- and volume-based concavity measures can miss changes in collision conditions, such as toaster slots being filled; greedy methods can also require heuristic workarounds for corner cases.Source: §1 · p. 2
• The method combines collision-aware concavity, direct 3D plane cuts, and Monte Carlo tree search to address three shortcomings of existing decomposition approaches.Its concavity metric samples boundary and interior points using Hausdorff distance; direct cuts yield flat component boundaries and intersection-free convex hulls without voxelization defects, while mesh cutting is reported as 100x faster than off-the-shelf libraries. Multi-step search considers future cuts and avoids extra heuristic terms for corner cases.Source: §1 · p. 2
• On V-HACD and PartNet Mobility, the method better preserves collision conditions and fine structures while using fewer convex components.Examples include drawer handles, kettle spouts, scissor inner rings, and toaster slots; the resulting decompositions support delicate and fast object interaction.Source: §1 · p. 2

2.1 Application of Convex Shapes

• Convex components enable efficient collision detection, point location, skeleton extraction, tetrahedral meshing, mesh deformation, and real-time animation.Collision detection is used in physics simulation, virtual reality, game engines, and animation; convex inputs can also accelerate point location.Source: §2.1 · p. 2

2.2 Convex Decomposition

• Exact convex decomposition is NP-hard and can produce many components, motivating approximate decomposition, which permits almost-convex parts [Chazelle et al. 1997; O’Rourke and Supowit 1983; Lien and Amato 2004, 2007].Approximate methods iteratively partition or cluster shapes until each component’s concavity falls below a predefined threshold.Source: §2.2 · pp. 2–3
• Boundary-distance metrics [Lien and Amato 2004, 2007, 2008; Ghosh et al. 2013; Liu et al. 2016; Mamou and Ghorbel 2009] can be intricate and insufficient, while visibility metrics [Liu et al. 2010; Ren et al. 2011] can be biased and costly.Boundary methods compare the shape boundary with its convex hull; visibility methods measure ratios of mutually visible surface-point pairs inside the shape.Source: §2.2 · p. 3
• Volume-based methods [Attene et al. 2008; Mamou et al. 2016; Thul et al. 2018] are efficient, but volume difference alone may not penalize implausible decompositions, such as filling toaster slots.V-HACD voxelizes meshes and greedily cuts voxels with axis-aligned planes; it is widely used for its open-source code and general-case performance.Source: §2.2 · p. 3
• Learning-based methods [Chen et al. 2020; Deng et al. 2020] generate components from global shape embeddings, risking lost structures and limited generalization to novel shapes.These methods represent meshes as assemblies of convex polyhedra.Source: §2.2 · p. 3

2.3 Shape Abstraction

• Shape abstraction represents global structure with primitives such as cuboids, superquadrics, and sphere-trees, but their low-dimensional expressibility limits fine-grained detail [Calderon and Boubekeur 2017; Paschalidou et al. 2020, 2019; Bradshaw and O’Sullivan 2004].Other primitive families include sphere-meshes, generalized cylinders, and combinations of primitives.Source: §2.3 · p. 3

3 PROBLEM DEFINITION AND METHOD OVERVIEW

• The objective is to minimize component count while keeping each component’s concavity below threshold ε, with the component union equivalent to the input solid.The input is assumed to be a 2-manifold solid mesh; imperfect meshes can be converted with an off-the-shelf algorithm [Huang et al. 2018].Source: §3 · p. 3
• Components exceeding ε are recursively split by a selected plane until all meet the constraint, then post-processing merges components to reduce their number.The method uses a divide-and-conquer strategy.Source: §3 · pp. 3–4
• Unlike V-HACD, the method uses collision-aware concavity that detects approximation errors more sensitively; both interior and boundary measures are needed.The figure illustrates cases where the interior measure Hi(S) or boundary measure Hb(S) is much greater than the other.Source: §3 · p. 4, Figure 2 · p. 4
• It cuts meshes directly with 3D planes rather than voxelizing them, avoiding discretization errors and enabling more precise and efficient decomposition.Source: §3 · p. 4
• Instead of greedily choosing locally optimal actions from one-step results, it uses multi-step tree search to achieve globally better decomposition.Source: §3 · p. 4

4.1 Concavity Definition

• Boundary-distance metrics can fill hollow interiors, while volume-based metrics can close deep holes with thin planar components, compromising object functionality.Examples include losing the ability to grasp scissors by their circles, pour from a kettle, or interact with a refrigerator water dispenser.Source: §4.1 · p. 4, Figure 3 · p. 4, Figure 4 · p. 5
• The metric combines sampled boundary and interior Hausdorff distances, using the worst-case point pair to penalize extra convex-hull volume that changes collision conditions.The boundary term captures deep holes, while the interior term detects hollow structures whose openings have small boundary distances.Source: §4.1 · p. 5
• The metric makes the threshold interpretable as how much thicker the original shape becomes, and it targets fine-grained or thin structures even when their volume is small.It focuses on the farthest point pair rather than an overall average, guarding against severe local errors.Source: §4.1 · p. 5

4.2 Efficient Concavity Calculation

• To reduce the cost of sampling interiors for Hi(S), the method uses Rv(S), the radius of a sphere with volume equal to the convex-hull volume difference, as a surrogate.Because Rv(S) often overestimates Hi(S), the method uses a coefficient k less than 1; the resulting calculation avoids interior sampling and its nearest-neighbor computation while retaining a bound with Hb(S) and Rv(S).Source: §4.2 · p. 6

• Triangle grouping can create zigzag boundaries and intersecting convex hulls, while voxelization introduces artifacts, can misclassify convex parts, and requires many voxels for precision.Source: §5 · p. 6, Figure 6 · p. 6, Figure 7 · p. 6
• Direct 3D plane cuts split manifold meshes into recursively decomposable parts with flat boundaries, intersection-free convex hulls, preserved fine details, and no voxelization-driven over-decomposition.The method follows.Source: §5 · p. 6
• A lightweight cutting routine is about 100x faster than CGAL, partitioning and splitting triangles, triangulating cut surfaces, and removing redundant triangles.The cut surfaces use constrained Delaunay triangulation, with intersecting edges as boundary constraints.Source: §5 · p. 7

6.1 Search Space

• For each component above the concavity threshold, the search samples m equally spaced axis-aligned planes per direction, optionally aligning directions with the input’s principal axes.The discretized candidates make the search feasible and avoid irregular cuts; the selected plane is later refined in its continuous neighborhood.Source: §6.1 · p. 7

6.2 One-Step Greedy vs. Multi-Step Search

• MCTS simulates future cuttings to avoid short-sighted greedy choices, find globally better decompositions, and eliminate auxiliary heuristics for corner cases.In the cube example, greedy cuts tie in cost and lead to more components, while MCTS finds the proper first cut and decomposes the shape into exactly four square parts.Source: §6.2 · pp. 7–8, Figure 9 · p. 7

6.3 Search Tree Structure

• Each tree node represents decomposed components, and actions cut the component with the largest concavity; UCB balances exploration and exploitation during node selection.Each cut adds one component, and each node has at most 3m children; expansion randomly selects an untried candidate plane.Source: §6.3 · p. 8

6.4 Tree Node Evaluation

• A default-policy rollout completes each evaluation to d + 1 components, and the score considers intermediate decompositions as well as the final result.The rollout greedily cuts the highest-concavity component from the middle along three axis-aligned directions, retaining the best one-step concavity reduction.Source: §6.4 · pp. 8–9

6.5 Plane Refinement and Component Merging

• The method refines the highest-scoring root plane by ternary search, then merges adjacent components when their combined concavity is within ε.For speed, MCTS uses Rv as concavity; outside MCTS, max(Hb(S), kRv(S)) determines whether components meet the concavity constraint and need further cuts.Source: §6.5 · p. 9

7.1 Comparing with Existing Methods

• The evaluation covers 61 V-HACD shapes and 2,346 PartNet-Mobility shapes; each PartNet-Mobility part was decomposed individually, with comparisons tailored to each baseline’s termination criteria.HACD and V-HACD were run for fine-grained decompositions and matched by concavity threshold; Animation was matched to the method’s component count.Source: §7.1 · pp. 9, 11
• The method uses fewer components than HACD and V-HACD on both datasets, with lower mean concavity, and achieves lower concavity than Animation at nearly equal component counts.Animation was compared quantitatively only on V-HACD; runtime was similar to HACD and V-HACD, while Animation was faster.Source: Table 1 · p. 9, §7.1 · p. 11
• On PartNet-Mobility, collision-aware concavity preserves more input structure than baselines: HACD often fills interior space, while V-HACD and Animation can still fill holes or add thin planar components.Preserving structures such as scissor rings, toaster slots, and kettle spouts supports object functionality; the method also uses fewer components than HACD and V-HACD.Source: Figure 11 · p. 10, §7.1 · p. 11

7.2 Ablation studies

• At the same concavity threshold, multi-step tree search produces fewer components and runs faster than one-step greedy search, avoiding shortsighted cuts in the torus and bottle-cap examples.The greedy baseline used the proposed concavity metric; the quantitative comparison was on V-HACD at threshold 0.05.Source: §7.2 · p. 11, Table 2 · p. 11
• Lowering the concavity threshold yields more components and closer shape approximations, while raising it yields fewer components but can lose detail; the distance-based threshold represents how much the shape thickens.The change is more pronounced at relatively small concavities.Source: §7.2 · p. 11, Figure 13 · p. 12, Figure 14 · p. 12
• More sampled planes, greater search depth, and more tree-search iterations generally improve decomposition quality but increase runtime; looking two steps ahead provides the largest depth-related gain.Increasing the number of plane candidates also leads to fewer components.Source: §7.2 · pp. 11–12, Figure 13 · p. 12
• Cut refinement improves candidate cut locations, but its benefit shrinks as candidate planes become denser; post-processing merges more redundant divisions at smaller thresholds, and choosing good or PCA axes can reduce components.Cutting directions can substantially affect results in some cases.Source: §7.2 · pp. 12–13, Figure 15 · p. 13

7.3 Application

• In the 49-drawer task, agents achieved a much higher success rate with the method’s collision shapes, which preserve handle holes that V-HACD fills.An opening counted as success if achieved within five trials; one SAC agent was trained from scratch per drawer.Source: Table 3 · p. 13, §7.3 · p. 13

• Collision-aware concavity examines shapes at both the boundary and interior to preserve fine-grained structures and support delicate object interaction.Source: §8 · p. 13
• Directly cutting meshes produces intersection-free components while avoiding discretization artifacts.Source: §8 · p. 13
• Multi-step tree search finds globally better cutting planes, leading to fewer decomposed components.Source: §8 · p. 13
• Runtime considerations motivate current simplifications; future work includes parallelization, neural-network evaluation, smarter cutting directions, and adaptive thresholds.Source: §8 · p. 13

A PROOF FOR THEOREM 1

• The proof defines Hi(S) using samples from the interiors of S and CH(S), assumes samples cover all points, and simplifies the distance because S is contained in its convex hull.It uses the Hausdorff distance, with d(x,Y) defined as the infimum of Euclidean distances from x to points in Y; the proof includes the boundary in the interior convention.Source: A PROOF FOR THEOREM 1 · p. 15
• The four-case analysis establishes the theorem: the interior distance is zero when the hull point lies inside S, equals Hb(S) in a boundary case, and is bounded using Rv(S) and Hb(S) otherwise.In the remaining case, the proof bounds the relevant distance using a maximum inscribed sphere and the nearest boundary point of S.Source: A PROOF FOR THEOREM 1 · pp. 15–16
• In the remaining case, the closest-point pair lies in the same connected region between S and CH(S), where an inscribed sphere centered at the hull point has radius r and Rv(S) ≥ r.If the sphere meets the convex-hull boundary, the proof uses its intersection point, the nearest point on S, and the tangent plane to relate the distance to Hb(S).Source: A PROOF FOR THEOREM 1 · pp. 15–16

B DETAILED VERSION OF TABLE 1

• Table 5 reports the complete V-HACD dataset comparison, while Table 4 gives selected statistics for the larger PartNet-Mobility dataset [Xiang et al. 2020].The method is compared separately with each baseline algorithm.Source: B DETAILED VERSION OF TABLE 1 · p. 16
• For Animation, the method matches component counts and compares concavity scores.Results include averages, medians, and the “better ratio.”Source: B DETAILED VERSION OF TABLE 1 · p. 16

C DEFAULT VALUE OF HYPER-PARAMETERS

• Defaults are m=20, t=500, d=4, and k=0.3, with 3,000 points sampled per unit area for computing Hb.Hyper-parameters are consistent across datasets and experiments except during ablations; all methods include merging unless noted otherwise.Source: C DEFAULT VALUE OF HYPER-PARAMETERS · p. 16
• UCB selects tree nodes for expansion, balancing the value function Q(n) against exploration through c.At c=0, search becomes nearly one-step greedy and component counts rise; very large c makes search inefficient and sub-optimal.Source: C DEFAULT VALUE OF HYPER-PARAMETERS · p. 16
• The empirically chosen c is Concavity(S)/d, using each input component’s concavity score and tree-search depth, and generally produces good results.The influence of c is studied on the V-HACD dataset and reported in Figure 20.Source: C DEFAULT VALUE OF HYPER-PARAMETERS · p. 16

E HOW WELL DOES Rv APPROXIMATES Hi?

• Experiments verify that Theorem 1 holds for all shapes on both datasets.Source: E HOW WELL DOES Rv APPROXIMATES Hi? · p. 16
• In practice, max(Hb, kRv) approximates max(Hb, Hi) well, with small absolute or relative error.Source: E HOW WELL DOES Rv APPROXIMATES Hi? · p. 18
• More than 94% of 13,536 PartNetM shapes satisfy |max(Hb, kRv) − max(Hb, Hi)| ≤ 0.02 or 0.8 ≤ max(Hb, kRv) / max(Hb, Hi) ≤ 1.2.The comparison evaluates the two metrics using either an absolute-error threshold of 0.02 or a relative ratio between 0.8 and 1.2.Source: E HOW WELL DOES Rv APPROXIMATES Hi? · p. 18