PaperlayerView exact revision on arXiv

Source-linked AI summary

CuACD: A Fully GPU-Resident Approximate Convex Decomposition

Ruoxi Shi, Xinyue Wei, Fanbo Xiang, Zexiang Xu, Hao Su

arXiv:2609.28731v1cs.CGcs.GR

TL;DR

Approximate convex decomposition is a costly preprocessing step, and major ACD costs such as search, cutting, and hull construction have remained CPU-bound. CuACD makes the pipeline fully GPU-resident using warp-centric design and device-side allocation. It reports more than an order of magnitude of speedup over CoACD at matched or better quality across three benchmarks.

  • Problem

    ACD’s expensive candidate-plane search and CPU-bound cutting and hull construction make decomposition costly in game pipelines and large-scale robot-learning datasets.

    Source: §1 · p. 2

  • Method

    CuACD redesigns search-based ACD around warp-centric kernels and a device-side heap allocator to run the full pipeline on the GPU.

    Source: §1 · p. 2, §3.2 · p. 4

  • Results

    More than an order of magnitude of speedup over CoACD at matched or better quality across three benchmarks.

    Source: §1 · p. 3, §6 · p. 9

  • Takeaways & Limitations

    CuACD’s reusable CUDA geometry components are released as standalone modules for existing search-based ACD pipelines.

    Source: §1 · p. 2

    CuACD retains hand-designed search heuristics, and its heap does not compact across arenas after fragmentation or return freed memory to the system allocator.

    Source: §6 · p. 9

Abstract

from arXiv · show

Approximate convex decomposition (ACD) converts triangle meshes into small sets of convex parts and is a standard preprocessing step for physics simulation, collision detection, and large-scale robot learning. The majority of modern ACD methods produce high-quality decompositions through an expensive search over candidate cutting planes, with per-mesh runtimes of tens of seconds that force game pipelines into overnight bakes and keep articulated-object datasets on CPU clusters for days. Prior work has accelerated isolated stages, most recently VisACD's GPU-based visibility metric, yet the dominant costs -- search, mesh cutting, and convex hull construction -- have remained on the CPU because their natural decomposition into many small homogeneous phases trails off in a fading last wave at every kernel boundary, and the variable-sized output of each phase forces a host round trip simply to allocate the next launch's input. We address these obstacles by adopting the warp, rather than the thread or thread block, as the unit of algorithm design, an idea introduced in the graph-processing community for a different pathology and which we adapt here to fuse the many heterogeneous phases of a computational-geometry pipeline into single warp-resident kernels, paired with a device-side heap allocator that lets the buffers between fused phases be sized and allocated on the device. Building on this template, we present CuACD (CUDA ACD), the first fully GPU-resident ACD system, together with a suite of reusable GPU components, released as open-source standalone CUDA modules that drop into any search-based ACD pipeline. On the V-HACD benchmark, PartNet-Mobility, and an Objaverse subset, CuACD achieves more than an order of magnitude of speedup over CoACD at matched or better quality.

1 Introduction

CuACD addresses the expensive search and CPU-bound cutting and hull stages that limit approximate convex decomposition, a preprocessing primitive for simulation and graphics. It redesigns the pipeline around warp-level work and device-side allocation, reporting orders-of-magnitude speedups over CoACD with better decomposition quality.

1 Introduction

  • ACD’s candidate-cut search repeatedly evaluates concavity by building convex hulls and measuring surface deviation, making cutting and hull construction computational hot spots.The inner loop executes hundreds of thousands of times per decomposition; VisACD accelerates visibility queries but leaves intersection tests and hull construction on the CPU.Source: §1 · p. 2
  • Splitting irregular ACD work into separate CUDA kernels creates fading tails of idle lanes and requires host round trips to size and allocate each next phase’s input.These costs accumulate at kernel boundaries and can undermine the savings sought from GPU execution.Source: §1 · p. 2
  • CuACD adopts the warp as the algorithm-design unit and pairs warp-resident pipeline work with a device-side heap allocator for variable-sized intermediate buffers.A warp is a 32-lane SIMD processor; the paper contrasts roughly 10^4 independent threads with roughly 10^2 resident warps.Source: §1 · p. 2, Figure 2 · p. 2
  • CuACD releases reusable CUDA components—including heap allocation, warp-level sorting, mesh-plane clipping, hull construction, connected components, and Hausdorff distance—for existing search-based ACD pipelines.The paper describes this as the first fully GPU-resident ACD system.Source: §1 · p. 2
  • Orders of magnitude faster than CoACD while achieving better decomposition quality, CuACD runs the ACD pipeline fully on the GPU.The paper also describes its quality as matched or better across three benchmarks.Source: §1 · pp. 2–3

2 Related Work

Prior ACD methods trade among decomposition quality, speed, and task-specific constraints, while GPU geometry work has accelerated individual primitives rather than the full ACD pipeline. Learning-based approaches offer a complementary route through neural proposals or representations.

Approximate convex decomposition

  • V-HACD trades some accuracy for robustness and speed, CoACD [Wei et al. 2022] improves quality at longer runtime, and VisACD [Fokin and Savva 2026] leaves cutting, hull construction, and outer search on the CPU.NavACD constrains decomposition to preserve inferred navigable free space, producing fewer and larger hulls for navigation uses.Source: §2 · p. 3

Geometry processing on the GPU

  • GPU geometry work has accelerated primitives such as rasterization, spatial indexing, hierarchy building, and traversal, while prior GPU hull algorithms target one large point cloud rather than many small concurrent hulls.CuACD extends GPU geometry processing to the full ACD pipeline, including hull construction and lookahead tree search.Source: §2 · p. 3

Learning-based convex decomposition

  • Learning-based methods propose cutting planes, represent shapes as differentiable convex unions, or cluster learned feature fields; CuACD instead accelerates classical hand-designed search, and the strategies are complementary.The cited learning-based work includes Luo et al. [2025], Deng et al. [2020], and Yang et al. [2026].Source: §2 · p. 3

3 A Warp-Centric View of Geometry Processing

CuACD treats a warp, rather than a thread or block, as the unit of algorithm design, matching the GPU’s concurrency to the active ACD worklist. Warp-level primitives handle irregular candidate evaluation, while a device-side heap lets phases fuse without returning to the host.

3 A Warp-Centric View of Geometry Processing

  • At warp granularity, the GPU schedules about 10^2 resident warps, matching the 10^2–10^3 active parts in an ACD worklist and its candidate pool.CuACD uses these as coarse-grained tasks, with each candidate evaluation running within a 32-lane warp.Source: §3 · p. 3

3.1 Fine Layer: Evaluating One Candidate as a Warp

  • One candidate’s irregular, variable-size evaluation is organized as a 32-lane warp using array traversal, sorting and set operations, symmetric work, and divide and conquer.Divide and conquer is listed last because its data-dependent branches may not keep all warp lanes useful.Source: §3.1 · p. 4
  • The mesh-plane clipper maps to filtering and sort-and-dedup, hull construction to divide and conquer with symmetric merging, and the concavity surrogate to warp reduction.These stages instantiate the warp-level primitives used to evaluate a candidate.Source: §3.1 · p. 4

3.2 Device-Resident Fusion: The Heap Allocator

  • A device-side heap enables fused, device-resident phases when intermediate buffer sizes are known only after the producing kernel runs.This avoids the host round-trip required to size and allocate variable-sized mesh, hull, and BVH buffers between phases.Source: §3.2 · p. 4
  • The heap uses binned free lists and a bitmap to find a fitting sub-bin in one bitwise operation; boundary tags coalesce neighboring freed blocks in O(1).The on-device allocations include cut-generated vertex arrays, hull edge and face arrays, and Hausdorff-query BVH scratch.Source: §3.2 · p. 5

4 The CuACD Algorithm

CuACD follows a search-based decomposition loop, redesigning its cutting, hull, and concavity stages for GPU execution. It then applies connected-component splitting and greedy hull merging as post-processing.

4.1 The CuACD Pipeline

  • The pipeline selects parts above concavity threshold τ, searches candidate cuts, and returns resulting parts to the worklist; after the loop, greedy hull merging reduces part count without regressing quality.Candidate planes are proposed from axis-aligned samples and concave edges, then evaluated with bounded look-ahead; the cheaper kR_v surrogate is used during search and the full metric at termination.Source: Figure 4 · p. 5, §4.1 · p. 5

4.2 Mesh–Plane Clipper

  • The mesh-plane clipper intersects the mesh with a plane, splits triangles by vertex sign, recovers boundary edges, closes the cut with caps, and writes two output meshes.It finds boundary edges by sorting edge keys from the smaller part and isolating unpaired keys, then classifies loops and ear-clips the caps.Source: §4.2 · pp. 5–6

4.3 Convex Hull and Concavity Evaluation

  • The exact divide-and-conquer hull uses integer predicates and a warp-cooperative 3D algorithm, sorting points into 16 two-lane sub-hulls before balanced pairwise merging.The implementation is based on Preparata and Hong’s O(n log n) algorithm.Source: §4.3 · p. 6
  • At n=65,536 on V-HACD, the direction-extreme prefilter removes about 70% of points and is over 12× faster than the plain D&C GPU path; below n=1024, callers use D&C directly.The prefilter retains 80 extreme witnesses, builds their hull, and drops points interior to that hull before the final D&C call.Source: §4.3 · p. 6
  • The Hausdorff evaluator assigns one warp to each mesh–hull pair, samples points on each mesh, and uses an LBVH for distance queries to triangles.The concavity metric requires bidirectional Hausdorff distance between a part’s mesh and its hull.Source: §4.3 · p. 6

4.4 Post-processing

  • Before parts enter the worklist and after each accepted cut, CuACD splits disconnected components with a lock-free warp-parallel union-find; its final greedy pass merges pairs whose joint hull stays below τ.Union-find uses read-only parent-chain finds and best-effort rank updates; the merge pass reuses the hybrid hull and Hausdorff evaluator.Source: §4.4 · p. 6

5 Results

Across three benchmarks, CuACD substantially outpaces prior systems at matched or better decomposition quality. The results also examine component performance, scalability across thresholds and mesh sizes, and a full-scene application.

5.1 Implementation Details

  • Experiments use an RTX 4090 and compare three benchmarks, with baselines threshold-swept toward CoACD’s default mean concavity of 0.05.The benchmarks are V-HACD, 14,085 PartNet-Mobility per-link meshes, and a 1,000-mesh Objaverse subset; PaMO preprocessing is excluded from timings.Source: §5 · p. 6, §5.1 · p. 6, §5.2 · pp. 6–7

5.2 Comparison with Baselines

  • 78×, 80×, and 104× faster than CoACD on V-HACD, PartNet-Mobility, and Objaverse, respectively, at matched or lower mean concavity and comparable or fewer parts.The comparison targets CoACD’s default mean concavity of 0.05; residual concavity differences reflect threshold granularity.Source: Table 1 · p. 7, §5.2 · p. 7
  • At matched mean concavity, CuACD’s cuts align with meaningful features on representative meshes, on par with or cleaner than CPU baselines.Figure 5 compares CoACD, NavACD, VisACD, and CuACD on V-HACD and PartNet-Mobility examples.Source: §5.2 · p. 7, Figure 5 · p. 8

5.3 GPU Gains Versus Algorithmic Gains

  • A 94-candidate root pool, including 64 concave-edge planes, reduces part count at fixed threshold; deeper branching has minimal observed impact.CuACD outperforms CoACD in quality with nominally weaker D=2 and W_sub=5 settings, versus 4 and 60.Source: §5.3 · p. 7
  • 20.85 s per mesh for the matched CPU port versus 0.23 s for CuACD, with near-matched V-HACD part counts and maximum concavities.The CPU port averages 33.7 parts and 0.0481 maximum concavity; CuACD averages 33.6 parts and 0.0488.Source: §5.3 · p. 7

5.4 Reusable Component Performance

  • The allocator leads CUDA malloc/free by 5× without contention and 10–11× when arenas are oversubscribed; the hybrid hull method exceeds Bullet by 300× and plain GPU divide-and-conquer by 12× at n=65,536.The warp-cooperative quick-sort also scales beyond 10^3 elements where CUB’s kernels do not.Source: §5.4 · p. 7

5.5 Scalability and Threshold Sensitivity

  • At τ=0.01, mean part count rises from ∼34 to ∼194 and runtime from 0.23 s to ∼0.5 s, while peak memory grows from 1.4 to 1.6 GiB.CuACD also reaches ∼10^6-triangle inputs in the multi-second regime within a single RTX 4090’s 24 GiB envelope.Source: §5.5 · pp. 7, 9, Figure 8 · p. 9

5.6 Application: Scene-Scale Decomposition

  • At τ=0.005, CuACD decomposes the 1,043,077-triangle Amazon Lumberyard Bistro interior in 18.73 s using 2355.6 MiB peak GPU memory on one RTX 4090.The scene contains 585,299 vertices.Source: §5.6 · p. 9, Figure 9 · p. 9

6 Conclusion and Discussion

CuACD adapts warp-as-unit design from graph traversal to computational geometry and presents a fully GPU-resident ACD system. Its hand-designed search and allocator behavior, along with register-limited occupancy, remain limitations and motivate future work.

6 Conclusion and Discussion

  • CuACD adapts the warp-as-unit view of Hong et al. [2011] to computational geometry, presenting the first fully GPU-resident ACD system with orders-of-magnitude speedups over CoACD across three benchmarks at matched or better quality.The work also contributes reusable GPU components.Source: §6 · p. 9
  • Search remains based on hand-designed CoACD-lineage heuristics; heap fragmentation is not compacted across arenas, freed memory is not returned, and register pressure limits occupancy to 25–50%.Learned cut quality, improved memory management, and register-aware scheduling are left to future work.Source: §6 · p. 9

A Hyperparameter Reference

CuACD exposes parameters for concavity, geometric tolerances, look-ahead search, and concave-edge proposals; τ=0.05 preserves direct concavity comparisons with CoACD.

A Hyperparameter Reference

  • τ and k define the concavity metric; ε_axis and ε_conc set plane-placement tolerances; W_top, W_sub, and D govern look-ahead tree shape; N_ce and I_ce control concave-edge proposals.N_ce bounds the proposal budget per part, while I_ce sets the number of outer iterations in which that proposal family is active.Source: A Hyperparameter Reference · p. 11

B Ablation of Search Hyperparameters

The search ablations identify a root candidate-pool setting that stays near the quality plateau at lower cost, while other knobs expose runtime–part-count trade-offs. Per-mesh outcomes vary widely with input geometry, so matched-mesh means are the appropriate basis for system comparison.

B Ablation of Search Hyperparameters

  • At (Wtop=30, Nce=16), output part count is within noise of the quality plateau at a small fraction of the cost of larger root pools.The ablation sweeps mean per-mesh runtime and mean output part count on V-HACD; this setting is used throughout the paper.Source: B Ablation of Search Hyperparameters · p. 11, Figure 10 · p. 11
  • Running CC-Split after every cut reduces part count by roughly seven and slightly shortens runtime; reducing Ice from 10 to 3 cuts runtime by about 17% for roughly two extra parts.Raising Ice to 20 yields no measurable improvement.Source: B Ablation of Search Hyperparameters · p. 11
  • Wsub=3 matches the default within noise, while Wsub=15 roughly triples look-ahead leaves for less than one part of gain, making Wsub=5 the clear operating point.The Wsub=5 conclusion is stated in the continuation of the ablation discussion.Source: B Ablation of Search Hyperparameters · p. 11
  • Depth 3 leaves mean part count essentially unchanged from depth 2 (32.89 vs. 33.57) while nearly doubling runtime (0.41 s vs. 0.23 s).The ablation identifies depth 2 as the sweet spot.Source: B Ablation of Search Hyperparameters · p. 11
  • CuACD’s V-HACD per-mesh part counts range from 3 to 165, runtimes remain below half a second, and maximum concavity stays within sampling error of the 0.05 threshold.The passage attributes the spread to input geometry and favors matched-mesh means for cross-system comparison.Source: B Ablation of Search Hyperparameters · p. 11, Table 5 · p. 11

C Warp-Cooperative Sort: Component Benchmark

The component benchmark evaluates warp-cooperative quick-sort against CPU and GPU sorting methods on batches of variable-sized sequences. Its partition uses warp-wide masks and prefix counts to assign unique output slots without shared-memory traffic.

C Warp-Cooperative Sort: Component Benchmark

  • The warp-cooperative quick-sort is the only GPU method feasible at the largest tested sizes, uses 24 bytes of shared memory, accepts dynamic inputs, and stays within a small constant factor of CUB merge where feasible.The benchmark compares batches of 1,000 int4 sequences from 10^2 to 10^5 elements; CUB block functions exceed shared-memory capacity beyond 10^3.Source: C Warp-Cooperative Sort: Component… · p. 12

D Warp-Cooperative Sort: Algorithm and Mechanics

  • For each 32-element chunk, lanes classify values against a pivot using warp-wide masks; prefix popcounts assign unique destinations, and the interior is filled with the pivot.The partition produces (< p | = p | > p) in O(n) loads with zero auxiliary shared memory.Source: D Warp-Cooperative Sort: Algorithm and… · p. 12
  • The partition relies on ballot, population-count, and shuffle intrinsics, each executing in one instruction without shared-memory traffic.The ballot collects predicate bits, popcount supplies lane prefix indices, and shuffle broadcasts a register value across the warp.Source: D Warp-Cooperative Sort: Algorithm and… · p. 12

E Heap Allocator Internals

The device-side allocator uses warp-level locking, boundary tags, and binned free lists to allocate and coalesce memory blocks. Its pool grows by slabs when no bin can satisfy a request.

E Heap Allocator Internals

  • Only lane 0 of each warp holds an arena’s spin-lock, and boundary tags locate neighboring blocks in O(1) pointer chases for coalescing on free.The allocator requires no offline compaction pass.Source: E Heap Allocator Internals · p. 12
  • Each arena’s 32 power-of-two bins are split into sub-bins indexed by a bitmap; a single find-first-set operation locates a feasible free-list head.When no bin fits, the allocator obtains a fresh slab from the underlying linear pool; the pool size stabilizes after the first decomposition call.Source: E Heap Allocator Internals · pp. 12–13

F Mesh–Plane Clipper Internals

The clipper closes boundary loops by ear-clipping: it triangulates a cap by repeatedly removing a convex vertex whose neighbor triangle contains no other polygon vertex. A warp cooperates on the point-in-triangle test, while lane 0 advances and updates the polygon list.

F Mesh–Plane Clipper Internals

  • Inner loops are bridged into enclosing outer loops after ray-casting classification, turning the cap into a simple polygon for triangulation.The ear-clipping procedure repeats until three vertices remain.Source: F Mesh–Plane Clipper Internals · p. 13
  • The cap warp parallelizes each ear’s point-in-triangle test across lanes, while lane 0 scans candidate vertices and splices accepted ears from the linked list.Degenerate zero-area ears are emitted when the cross product magnitude is at most epsilon, keeping the cap watertight at T-junctions and collinear split edges.Source: F Mesh–Plane Clipper Internals · p. 13

G Convex Hull Internals

CuACD builds convex hulls through divide-and-conquer splitting and warp-cooperative gift-wrapping merges. It also triangulates cap loops with warp-cooperative ear clipping.

G Convex Hull Internals

  • During merging, two lanes search from opposite bridge endpoints and use a warp shuffle to advance the endpoint with the larger turning angle until the rotation closes a ring.The initial cross-edge spans the two extreme points along the merge axis.Source: G Convex Hull Internals · p. 13
  • For cap triangulation, warp lanes test candidate ears in parallel; an occupied candidate is rejected, while an empty one is emitted and removed from the polygon list.In the illustrated loop, D rejects the ear at A, while the test at B passes and triangle ABC is written.Source: Figure 12 · p. 13
  • The divide-and-conquer hull splits points along the longest bounding-box axis, hulls each half independently, then merges the child hulls by gift-wrapping.Figure 13 illustrates the split and a bridge edge rotating around the child-hull boundaries.Source: Figure 13 · p. 13

H Inefficiencies of the Per-Phase CUDA Decomposition

The conventional per-phase CUDA clipper incurs underfilled kernel tails and host round trips for variable-sized outputs. Warp-centric templates provide cooperative patterns for array and set operations, paired work, and divide-and-conquer hull construction.

H Inefficiencies of the Per-Phase CUDA Decomposition

  • The conventional mesh–plane clipper expands to roughly seven kernel launches per cut, with data-dependent output counts across edge collection, intersections, split triangles, and boundaries.Boundary chaining and ear clipping may run on the host or underfill the GPU; adjacent kernels require synchronization, a host-side size read, and a sized launch.Source: H Inefficiencies of the Per-Phase CUDA… · pp. 13–14
  • When phase work shrinks near a kernel boundary, only a trailing fraction of warps remains active, leaving most of the GPU idle; repeated boundaries accumulate this underfill.The clipper, hull prefilter, and tree search are examples of phases whose work can taper or prune.Source: H Inefficiencies of the Per-Phase CUDA… · p. 14, Figure 14 · p. 14
  • Variable output sizes force the host to read each completed phase's output size before launching the next, adding synchronization and transfer latency across repeated cuts.CUDA Graphs do not remove this dependency because changing output sizes alter consuming launch shapes and require graph rebuilding.Source: H Inefficiencies of the Per-Phase CUDA… · p. 14, Figure 14 · p. 14

I Warp-Centric Primitive Templates

  • Warp array primitives combine stride-32 scans, five-shuffle reductions, and dense ballot/popcount filtering; sparse filtering instead assigns slots with a shared-counter atomicAdd.Each lane visits array index 32r + ℓ; dense survivors receive packed output slots.Source: I Warp-Centric Primitive Templates · p. 14
  • Sorting, deduplication, and membership queries use warp-cooperative quicksort, a neighbor scan to drop adjacent duplicates, and a 32-lane binary search requiring five comparison rounds.The sort's three-way partition uses the vote-plus-popcount dense-filter pattern.Source: I Warp-Centric Primitive Templates · p. 14
  • For paired entities, each warp forms 16 two-lane groups that process endpoints or linked-list neighbors together, exchanging register values with one warp shuffle.CuACD uses this pattern for convex-hull bridge-edge merging.Source: I Warp-Centric Primitive Templates · pp. 14–15, Figure 16 · p. 15
  • The hull's divide-and-conquer template splits input points 16 ways, hulls chunks in paired-lane groups, then merges sub-hulls up a tree; divergent branch control can erode SIMD benefit.The pattern is most effective when branches are short and structurally similar.Source: I Warp-Centric Primitive Templates · p. 15
Loading 2609.28731v1…