CoChat

Volumetric Hierarchical Approximate Convex Decomposition

· 2016 · Game Engine Gems 3
Cited by 65

The DOI matches its Crossref record.

Abstract

ECD aims at partitioning a polyhedron P into a minimum set of convex polyhedra. In [Chazelle 1984], the authors prove that ECD is NP-hard and discuss various heuristics to address it. [Lien and Amato 2004] claim that ECD algorithms produce intractable convex decompositions with a high number of clusters (shown in Figure 11.2) and propose computing an approximate convex decomposition instead. The main idea is to relax the exact convexity constraint by allowing the clusters to be almost convex. More precisely, ACD aims at decomposing a polyhedron P into a minimum number of polyhedra  Γ | 0, , 1i i N  such that the concavity of each polyhedron Γi is lower than a predefined threshold ε . (The definition of concavity is discussed later.) The convex approximation  | 0, , 1iC i N  associated with the convex decomposition  Γ | 0, , 1i i N  is defined as  Γi iC CH , (11.3) where  ΓiCH is the convex hull of Γi. In order to avoid the higher computational complexity associated with volumetric representations, the convex decomposition algorithms described in [Chazelle 1984] and [Lien and Amato 2004] operate on the polyhedral surface S of P instead of computing a convex decomposition of the volume defined by P. Here, the surface S is decomposed into convex or near-convex patches  Ψ | 0, , 1i i N  , as shown in Figure 11.2. The convex approximation  Π | 0, , 1i i N  associated with the approximate convex decomposition  Ψi of S is given by  Π Ψi iCH , (11.4) where  ΨiCH is the convex hull of Ψi. Note that  Π i is guaranteed to include the surface S (i.e., 10 ΠN iiS   ) but not necessarily the entire volume of P, which is usually sufficient for collision detection purposes. Several approximate convex decomposition algorithms have been recently proposed [Lien and Amato 2007, Ghosh et al. 2013, Attene et al. 2008, Kreavoy et al. 2007, Mamou 2010, Ren et al. 2011], and some implementations are publicly available.2 The hierarchical approximate convex decomposition (HACD) algorithm has been very popular and was adopted by various physics libraries (e.g., Bullet and PhysX) and game engines (e.g., Unreal Engine). As in [Lien and Amato 2004], 2 https://sourceforge.net/projects/hacd/ Original mesh (20K tri.) ECD [Chazelle 1984] (2043 patches) ACD [Mamou 2010] (13 patches) ACD-based convex approximation (13 convex hulls) Figure 11.2. ECD, ACD, and ACD-based convex approximation.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1201/b21177-15

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cited by

See all 65

Metadata

Venue
Game Engine Gems 3
Published
2016-02-24
Pages
155-172
OpenAlex
W3032127812
Cited by
65
References
0
FWCI
17.75
Type
book chapter
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Volumetric Hierarchical Approximate Convex Decomposition. https://app.cochat.ai/papers/10.1201/b21177-15
The paper
Volumetric Hierarchical Approximate Convex Decomposition. (2016). Game Engine Gems 3. https://doi.org/10.1201/b21177-15

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.