PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Xinyue Wei, Minghua Liu, Zhan Ling, Hao Su

arXiv:2205.02961v1cs.GRcs.CGcs.CVcs.RO

TL;DR

Existing approximate convex decomposition methods can lose fine-grained structures that matter for object functionality. This paper combines collision-aware concavity, direct mesh cutting, and multi-step tree search, and reports decompositions closer to the original shape with fewer components, supporting delicate and efficient interaction.

  • Problem

    Existing approaches may fail to preserve fine-grained 3D structures even though such details are important for retaining object functionality in interactive environments.

  • Method

    The method measures concavity from both shape boundary and interior, directly cuts meshes with 3D planes, and uses multi-step tree search to select cutting planes.

  • Results

    The method generates decompositions closer to the original shape with fewer components, while better preserving collision conditions and fine-grained structures.

  • Takeaways & Limitations

    The resulting decompositions support delicate and efficient object interaction in downstream applications.

  • Takeaways & Limitations

    Decomposition quality and runtime involve a trade-off because longer search can increase search time.

Abstract

from arXiv · show

Approximate convex decomposition aims to decompose a 3D shape into a set of almost convex components, whose convex hulls can then be used to represent the input shape. It thus enables efficient geometry processing algorithms specifically designed for convex shapes and has been widely used in game engines, physics simulations, and animation. While prior works can capture the global structure of input shapes, they may fail to preserve fine-grained details (e.g., filling a toaster's slots), which are critical for retaining the functionality of objects in interactive environments. In this paper, we propose a novel method that addresses the limitations of existing approaches from three perspectives: (a) We introduce a novel collision-aware concavity metric that examines the distance between a shape and its convex hull from both the boundary and the interior. The proposed concavity preserves collision conditions and is more robust to detect various approximation errors. (b) We decompose shapes by directly cutting meshes with 3D planes. It ensures generated convex hulls are intersection-free and avoids voxelization errors. (c) Instead of using a one-step greedy strategy, we propose employing a multi-step tree search to determine the cutting planes, which leads to a globally better solution and avoids unnecessary cuttings. Through extensive evaluation on a large-scale articulated object dataset, we show that our method generates decompositions closer to the original shape with fewer components. It thus supports delicate and efficient object interaction in downstream applications. We will release our implementation to facilitate future research.

1 INTRODUCTION

Approximate convex decomposition reduces complex 3D shapes to almost-convex components, but existing methods can miss fine details and rely on limited metrics and greedy decisions. The paper introduces collision-aware concavity, direct mesh cutting, and multi-step tree search to produce closer decompositions with fewer components.

  • Motivation: Convex decomposition simplifies geometry processing by representing complex shapes with components suited to efficient convex-shape algorithms.Applications include point location, mesh intersection, and minimum-distance computation.
  • Prior approaches: Exact convex decomposition is NP-hard, while approximate convex decomposition reduces component counts by relaxing strict convexity.ACD uses convex hulls of approximately convex components to approximate the original shape.
  • Limitations: Existing ACD methods define concavity metrics and then greedily decompose meshes, but their metrics and one-step decisions have important corner cases.These corner cases can require additional heuristic terms as workarounds.
  • Contribution: The method combines collision-aware concavity, direct 3D-plane mesh cutting, and Monte Carlo tree search to address prior limitations.The concavity examines both boundary and interior samples; direct cutting avoids voxelization defects; tree search evaluates multiple future actions.
  • Results: Evaluation on V-HACD and PartNet Mobility shows better preservation of collision conditions and fine-grained structures with fewer convex components.Examples include drawer handles, kettle spouts, scissor inner rings, and toaster slots.

2 RELATED WORK

Convex-shape algorithms support many geometry-processing and interactive applications, motivating approximate convex decomposition as a practical alternative to exact decomposition. Related methods use concavity thresholds and partitioning strategies, but learning-based approaches may fail to preserve detailed structures and generalize poorly.

  • Applications: Convex inputs accelerate collision detection, point location, and downstream tasks including skeleton extraction, tetrahedral meshing, deformation, and animation.These applications span physics simulation, virtual reality, game engines, rendering, and animation.
  • Convex decomposition: Exact convex decomposition is NP-hard and typically produces many components, motivating approximate convex decomposition with almost-convex components.ACD relaxes strict convexity to improve practical usability.
  • ACD pipeline: ACD methods measure component-to-convex-hull concavity and iteratively partition or cluster shapes until each component meets a threshold.The literature includes multiple families of concavity metrics.
  • Learning-based methods: Learning-based methods assemble convex polyhedra from global shape embeddings but may fail to preserve input structures and generalize poorly to novel shapes.These limitations have hindered extensive practical use.
  • Algorithm setup: The paper frames its algorithm around a solid 2-manifold mesh, a concavity threshold, and an approximate convex decomposition output.The listed algorithm takes a 2-manifold solid mesh and threshold as input.

3 PROBLEM DEFINITION AND METHOD OVERVIEW

The method recursively cuts a solid mesh into non-overlapping almost-convex components whose convex hulls approximate the original shape. Its three design choices combine collision-aware concavity, direct plane-based cutting, and multi-step search for globally better decompositions.

  • Problem definition: The objective is to minimize the number of almost-convex components while keeping each component’s concavity below threshold 𝜖.Components may meet at boundaries, and their convex hulls approximate the original shape.
  • Recursive decomposition: Components whose concavity exceeds 𝜖 are recursively split with cutting planes until all components satisfy the constraint.A post-processing step then merges generated components to further reduce their number.
  • Collision-aware concavity: Both interior and boundary measures are needed because shell openings and deep holes produce different discrepancies from the convex hull.The figure contrasts cases where Hi(S) greatly exceeds Hb(S) and where Hb(S) greatly exceeds Hi(S).
  • Geometric design: Directly cutting meshes with 3D planes avoids discretization errors and supports precise, efficient decomposition without voxelizing the input.The resulting approach also targets intersection-free convex hulls.
  • Search strategy: Multi-step tree search replaces one-step greedy action selection to seek globally better decompositions.The search evaluates future actions rather than relying only on one-step results.

4 COLLISION-AWARE CONCAVITY METRIC

The proposed collision-aware concavity metric combines boundary and interior distances to detect approximation errors that can alter collision conditions. It uses sampled Hausdorff distances, with an efficient volume-based surrogate for interior distance when direct calculation is costly.

  • Motivation: Existing boundary- and volume-based metrics can produce functionally damaging decompositions by filling hollow interiors or small-volume holes.Boundary-only metrics may fill shell-like structures, while volume-based metrics may overlook thin planar errors; such failures can disrupt object interaction.
  • Concavity definition: The proposed metric examines both the boundary surface and interior of a shape relative to its convex hull using a unified formulation.Boundary and interior point sets are sampled, and their Hausdorff distances define complementary terms for measuring shape difference.
  • Concavity definition: Concavity(S) = max(Hb(S), Hi(S)) combines boundary and interior Hausdorff distances so shell-like and boundary-surface errors are both penalized.Using only Hb(S) can miss hollow interiors, whereas using only Hi(S) can miss differences between boundary surfaces.
  • Collision awareness: The collision-aware metric penalizes convex-hull regions far from the original shape, making it sensitive to fine-grained and thin approximation errors that change collision conditions.The threshold can be interpreted as the degree to which the original shape becomes thicker, unlike a volume-difference threshold.
  • Efficient concavity calculation: A volume-derived surrogate Rv(S) accelerates interior-error estimation by replacing dense interior sampling, while a coefficient k less than 1 compensates for its practical overestimation.Rv(S) is based on the volume difference between the convex hull and input shape and can bound the proposed concavity through Hb(S) and Rv(S).

5 SHAPE DECOMPOSITION BY CUTTING MESHES

The method directly cuts manifold triangle meshes with 3D planes instead of grouping triangles or voxelizing shapes. This preserves flat boundaries, keeps convex hulls intersection-free, and avoids discretization artifacts and over-decomposition of convex parts.

  • Triangle-grouping methods can create zigzag component boundaries whose convex hulls intersect.
  • Voxel-based methods introduce discretization artifacts and may fail to recognize already convex components.
  • The method recursively splits manifold meshes by directly cutting them with 3D planes, producing manifold parts with flat boundaries.
  • Direct mesh cutting ensures that convex hulls of decomposed components are intersection-free.
  • The method samples m equally spaced candidate planes along each axis-aligned direction, then refines the selected plane’s position.
  • A lightweight cutting implementation is about 100x faster than CGAL’s implementation.

6 MONTE CARLO TREE SEARCH FOR CUTTING PLANE

The method replaces one-step greedy plane selection with Monte Carlo tree search that evaluates future cuttings. This addresses short-sighted choices and unnecessary components while selecting and refining decomposition planes.

  • Each intermediate component with concavity above threshold ε is split using candidates restricted to m equally spaced axis-aligned planes.
  • One-step greedy search can choose short-sighted cutting planes that produce globally worse decompositions and more components.
  • In the illustrated example, the optimal decomposition has exactly four square parts, whereas greedy middle cutting produces more components.
  • The method uses Monte Carlo tree search to simulate multiple future cuttings and favor planes leading to globally better decompositions.
  • Multiple-step search removes the need for additional heuristic terms to handle various corner cases.
  • Search-tree nodes represent decomposed component sets, and each child corresponds to a candidate cut of the component with largest concavity.
  • TreePolicy balances exploration and exploitation, while DefaultPolicy completes playouts with greedy cuttings to evaluate expanded nodes.
  • Evaluating intermediate results helps distinguish paths with similar final outcomes and select paths that achieve good results earlier.

7 EVALUATIONS

Evaluations show that the method preserves fine-grained shape details while producing fewer components than key baselines, and that tree search improves decomposition quality. Ablations further expose trade-offs among detail, component count, search quality, and runtime, while downstream drawer-opening results favor the method’s collision shapes.

  • Evaluation setup: 2,346 shapes in PartNet-Mobility provide a large-scale articulated-object benchmark with complex inner structures and delicate details for fine-grained interaction.The V-HACD dataset contains 61 shapes, whereas PartNet-Mobility covers 2,346 indoor articulated objects.
  • Evaluation setup: Our method uses separate comparison protocols for HACD, V-HACD, and Animation because their termination rules, component targets, and concavity definitions differ.For HACD and V-HACD, the authors compare component counts; for Animation, they match component counts and compare concavity scores.
  • Comparisons with existing methods: Our method outperforms HACD and V-HACD in component count on both datasets, while also achieving lower mean concavity scores; against Animation, it produces similar component counts with lower concavity.Runtime is similar to HACD and V-HACD, whereas Animation is faster because its implementation uses optimized industrial code.
  • Comparisons with existing methods: Collision-aware concavity preserves fine-grained structures such as scissors’ inner rings, toaster slots, kettle spouts, and drawer-handle holes that baselines may fill.Boundary- or volume-based metrics can ignore interior structures or introduce thin planar components that fill holes.
  • Ablation studies: Multi-step tree search generates fewer components than one-step greedy cutting by evaluating future consequences and avoiding unnecessary divisions.The tree-search version is also faster than the greedy baseline because it reduces the number of rounds and uses simplified concavity calculations during search.
  • Ablation studies: Lowering the concavity threshold increases component count and detail preservation, while increasing it yields fewer components and a coarser approximation; larger search settings improve solutions but increase runtime.More candidate planes, greater search depth, and more iterations generally improve decomposition quality, with d = 2 providing the most significant depth-related gain.
  • Ablation studies: Refinement becomes less beneficial as candidate-plane sampling increases because adjacent candidates become closer, while post-processing merging reduces redundant divisions.The application study trains SAC agents on 49 drawers from 25 cabinets; collision shapes from our method produce a much higher success rate than V-HACD shapes.

8 DISCUSSION

The method combines collision-aware concavity, direct mesh cutting, and multi-step tree search to preserve detail while reducing unnecessary decomposition.

  • 8 DISCUSSION: Collision-aware concavity examines both component boundaries and interiors to preserve fine-grained shape structures.It is designed to support delicate object interaction in downstream applications.
  • 8 DISCUSSION: Efficient mesh cutting produces intersection-free components and avoids discretization artifacts.
  • 8 DISCUSSION: Multi-step tree search finds globally better cutting planes and leads to fewer decomposed components.
  • 8 DISCUSSION: Runtime considerations motivate simplifications, while future work includes parallelization, neural evaluation, smarter cutting directions, and adaptive thresholds.

A PROOF FOR THEOREM 1

The proof establishes a relationship between interior and boundary Hausdorff distances by analyzing sampled points and exhaustively considering the locations of the maximizing pair.

  • A PROOF FOR THEOREM 1: The proof uses Hausdorff distance between samples from the solid shape S and its convex hull CH(S).The distance uses nearest-point Euclidean distances, with P and Q sampled from the interiors of S and CH(S), respectively.
  • A PROOF FOR THEOREM 1: The proof assumes the interior includes the boundary surface and that sampling covers all points in each set.
  • A PROOF FOR THEOREM 1: Because S is contained in CH(S), the directed distance from P to Q is zero, so Hi(S) is determined by a maximizing pair p* and q*.
  • A PROOF FOR THEOREM 1: The maximizing pair is analyzed through four cases based on whether p* and q* lie inside or on the boundaries of S and CH(S).Cases include q* inside S, p* off S's boundary, both points on relevant boundaries, and q* inside CH(S) but outside S.
  • A PROOF FOR THEOREM 1: The theorem concludes by bounding Hi(S) through the relevant boundary and interior terms, with the boundary-contact case giving Hi(S) = Hb(S).

B DETAILED VERSION OF TABLE 1

The detailed comparison evaluates the method against HACD, V-HACD, and Animation using dataset-wide statistics and a better-ratio measure.

  • C DETAILED VERSION OF TABLE 1: The evaluation reports complete quantitative comparisons for all objects in the V-HACD dataset and selected statistics for PartNet-Mobility.
  • C DETAILED VERSION OF TABLE 1: For HACD and V-HACD, the comparison fixes lower concavity scores and compares the numbers of decomposed components.
  • C DETAILED VERSION OF TABLE 1: For Animation, the comparison matches the numbers of decomposed components and compares concavity scores.
  • C DETAILED VERSION OF TABLE 1: Average, median, and better-ratio statistics summarize performance, with better ratio measuring the percentage of cases where the method outperforms a baseline.

C DEFAULT VALUE OF HYPER-PARAMETERS

The experiments use fixed default hyper-parameters and apply UCB-based tree-node selection, whose exploration parameter controls the balance between exploration and exploitation.

  • C DEFAULT VALUE OF HYPER-PARAMETERS: The default hyper-parameters are m = 20, t = 500, d = 4, and k = 0.3.The method samples 3,000 points per unit area when computing Hb, and experiments generally include the merging stage.
  • C DEFAULT VALUE OF HYPER-PARAMETERS: Tree search selects nodes for expansion using an Upper Confidence Bound term.
  • C DEFAULT VALUE OF HYPER-PARAMETERS: The parameter c balances exploration and exploitation in UCB-based selection.At c = 0, exploration disappears and MCTS nearly becomes one-step greedy search, increasing the number of components.

E HOW WELL DOES Rv APPROXIMATES Hi?

The section evaluates whether max(Hb,𝑘Rv) is a practical approximation of max(Hb, Hi), reporting small absolute or relative errors across most PartNetM shapes.

  • The evaluation experimentally verifies that Theorem 1 holds for all shapes on both datasets.
  • max(Hb,𝑘Rv) approximates max(Hb, Hi) well in practice with a small absolute or relative error.
  • More than 94% of PartNetM’s 13,536 shapes satisfy either an absolute error ≤0.02 or a ratio between 0.8 and 1.2.The comparison is between max(Hb,𝑘Rv) and max(Hb, Hi).
Loading 2205.02961v1…