Volumetric Hierarchical Approximate Convex Decomposition
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.
Integrity signals
Registry
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.
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
Objaverse: A Universe of Annotated 3D Objects
Deitke, M., Schwenk, D., Salvador, J., Weihs, L., Michel, O., VanderBilt, E., Schmidt, L., Ehsanit, K., Kembhavi, A., & Farhadi, A. (2023) · 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52729.2023.01263 · Cited by 725
“We then generate colliders using V-HACD [43] to support rigid-body interactions.”
MethodJacquard: A Large Scale Dataset for Robotic Grasp Detection
Depierre, A., Dellandrea, E., & Chen, L. (2018) · 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2018.8593950 · Cited by 490
SAPIEN: A SimulAted Part-Based Interactive ENvironment
Xiang, F., Qin, Y., Mo, K., Xia, Y., Zhu, H., Liu, F., Liu, M., Jiang, H., Yuan, Y., Wang, H., et al. (2020) · 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr42600.2020.01111 · Cited by 406
Where2Act: From Pixels to Actions for Articulated 3D Objects
Mo, K., Guibas, L., Mukadam, M., Gupta, A., & Tulsiani, S. (2021) · arXiv · doi:10.48550/arxiv.2101.02692 · Cited by 132
Approximate convex decomposition for 3D meshes with collision-aware concavity and tree search
Wei, X., Liu, M., Ling, Z., & Su, H. (2022) · ACM Transactions on Graphics · doi:10.1145/3528223.3530103 · Cited by 80
Metadata
- Venue
- Game Engine Gems 3
- Publisher
- A K Peters/CRC Press
- 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.