VisACD: Visibility-Based GPU-Accelerated Approximate Convex Decomposition Volume: 45 Issue: 2

Egor Fokin 1 Manolis Savva 1 1 Simon Fraser University 3dlg-hcvc.github.io/visacd · 2026

Read VisACD: Visibility-Based GPU-Accelerated Approximate Convex Decomposition Volume: 45 Issue: 2 by Egor Fokin 1 Manolis Savva 1 1 Simon Fraser University 3dlg-hcvc.github.io/visacd (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04244.txt.

Introduction

Egor Fokin and Manolis Savva built VisACD, a visibility-based, rotation-equivariant, intersection-free algorithm for approximate convex decomposition with GPU acceleration. Collision detection trades accuracy against speed, and primitive colliders like bounding boxes are fast while raw meshes are costly. Prior methods give high-quality results but need many convex parts and react to mesh orientation. VisACD yields high-quality splits with fewer parts, ignores shape facing, and runs more efficiently than prior work.

Catalog record

CREATOREgor Fokin 1 Manolis Savva 1 1 Simon Fraser University 3dlg-hcvc.github.io/visacd
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16357
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04244

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

VisACD: Visibility-Based GPU-Accelerated Approximate Convex Decomposition Volume: 45 Issue: 2 Egor Fokin 1 Manolis Savva 1 1 Simon Fraser University 3dlg-hcvc.github.io/visacd Abstract Physics-based simulation involves trade-offs between performance and accuracy. In collision detection, one trade-off is the granularity of collider geometry. Primitive-based colliders such as bounding boxes are efficient, while using the original mesh is more accurate but often computationally expensive. Approximate Convex Decomposition (ACD) methods strive for a balance of efficiency and accuracy. Prior works can produce high-quality decompositions but require large numbers of convex parts and are sensitive to the orientation of the input mesh. We address these weaknesses with VisACD, a visibility-based, rotation-equivariant, and intersection-free ACD algorithm with GPU acceleration. Our approach produces high-quality decompositions with fewer convex parts, is not sensitive to shape orientation, and is more efficient than prior work. \ShortPresentation [backend=biber,bibstyle=eg/EG,citestyle=alphabetic,backref=true,mincitenames=1,maxcitenames=2,natbib=true]biblatex ccs Computing methodologies Collision detection ccs Computing methodologies Mesh geometry models ccs Computing methodologies Mesh models ccs Computing methodologies Parallel algorithms † † year: 2026 † † year: 2026 † † editors: B. Masia and J. Thies † † editors-short: I. Lim and P. Musialski † † editors-star: A. Bönsch and N. Umetani † † editors-tutorial: R. Chaine and A. Vaxman † † editors-education: B. Heinemann and B. Wünsche † † editors-poster: T. Gerrits and M. Teschner † † editors-dc: N.N. † † subject: EUROGRAPHICS CGF Vol No † † teaser: We present VisACD, a visibility-based GPU-accelerated intersection-free approximate convex decomposition (ACD) algorithm. VisACD is rotation-equivariant and thus not sensitive to input mesh orientation. Our experiments show that VisACD outperforms prior methods producing accurate decompositions with fewer parts (indicated by numbers). 1 Introduction Representing shapes as a set of convex hulls is an acceleration technique used widely in physics and game engines. This representation enables efficient algorithms such as checking whether a point lies inside the mesh [ 20 ] , computing distances between two objects [ 8 ] or checking whether two meshes intersect [ 4 ] . In practice, sets of convex hull ‘colliders’ are authored by content creators through fitting primitives such as boxes or capsules to a mesh asset. This is a time-consuming process, and the resulting colliders can differ substantially from the original mesh asset. Multiple algorithms were created to automate this process and produce more accurate convex decompositions. Exact convex decomposition [ 5 ] attempts to decompose a shape into convex hulls such that the shape of the decomposition is exactly the same as the input mesh. Such algorithms are slow and produce thousands of parts negating the intended efficiency gains. A different approach is Approximate Convex Decomposition (ACD) [ 14 ] , which decomposes objects into parts that approximately match the initial shape. This relaxed condition allows algorithms that are faster and produce decompositions with orders of magnitude fewer parts. In this paper, we present a) VisACD, a method that produces convex decompositions closer to the initial mesh and with lower part numbers, that is not sensitive to mesh orientation and that is more efficient, compared to baselines from prior work. b) A concavity metric tailored for efficient cutting plane computation. c) A parallelization of our algorithm using NVidia OptiX and CUDA. 2 Related Work Applications for ACD methods. Recent works [ 13 , 9 ] use ACD to create colliders for different objects in robot grasping simulations. NERF-Texture [ 10 ] uses CoACD as volume-preserving smoothing. V-HACD [ 18 ] was adapted by Unreal Engine 4 for automatic collider creation of 3D objects. The quality of the decompositions directly impacts the accuracy and efficiency in the mentioned applications. Concavity measures for ACD. ACD algorithms use a concavity measure that they minimize and use in evaluation. Some methods use surface-based metrics to measure concavity. These metrics include distances between the mesh surface and its convex hull [ 14 , 7 ] , or between the shortest geodesic path on the mesh and the convex hull [ 15 ] . HACD [ 17 ] projects the vertices onto the convex hull and measures the distances between the points and their projections. [ 22 ] show that these metrics fail to capture differences of volume properties. Other methods use volume-based metrics, such as volume ratio between a mesh and its hull [ 3 , 18 , 21 ] , and CoACD [ 22 ] uses a mixture of volume-based and surface-based metrics. Another family of metrics uses pairwise visibility of surface points (two points are considered visible to each other if the segment between them lies fully outside the mesh). Some works [ 11 , 2 ] use a percentage of pairs that are mutually visible. Other works [ 16 , 19 ] calculate the distance between those connections and the surface of the mesh. This metric can be easily computed and has useful properties that we discuss later. Our method uses an efficient visibility-based metric at its core, computing the total combined length of all segments between mutually visible vertices. Prior work on ACD algorithms. [ 14 ] introduced a surface-based approach that cuts meshes at regions of high concavity, with later works improving concavity measures [ 7 ] , cut paths [ 15 ] , or using triangle merging [ 17 , 12 ] . However, surface-based methods struggle to preserve volume, especially in meshes with holes or cavities. To address this, volumetric ACD methods were proposed, including tetrahedral merging [ 3 ] , point-patch clustering [ 11 ] , spectral clustering [ 2 ] , and Reeb-graph-based approaches [ 16 , 19 ] . While these methods better preserve volume, they do not prevent convex hull intersections, limiting their applicability in animation and simulation. More recent works utilize cutting planes as a main tool of decomposition to prevent convex hull intersections. V-HACD [ 17 ] uses axis-aligned cutting planes to decompose a voxelized representation of the mesh. CoACD [ 22 ] improves on this by using an MCTS algorithm instead of a greedy one and by employing a regular mesh representation together with a volumetric concavity measure to preserve volume properties. [ 21 , 1 ] additionally sample planes that contain edges of maximum concavity. Such methods evaluate the cutting planes by performing the cut and computing the concavity of resulting pieces, which is highly inefficient, limiting the number of planes that can be sampled at every iteration. Figure 1: Sensitivity of axis-aligned plane methods to orientation. Our approach also uses cutting planes. However, by using visibility-based concavity we can compute a plane value without cutting the mesh, which allows us to sample thousands of planes per iteration and achieve better results. Our plane sampling strategy also makes the method rotation-equivariant, eliminating sensitivity to mesh orientation in axis-aligned plane methods ( Figure 1 ). 3 Method 3.1 Visibility-Based Concavity Metric We use the definition of weak convexity proposed by [ 2 ] and define visibility edges e_{i} as edges between two mesh vertices that lie outside of the mesh and do not intersect it. An important property is that a convex mesh has zero visibility edges and the more concavities there are in a mesh, the more visibility edges. One way to measure the concavity of the mesh is to use the number of such

Read the complete text