Approximate convex decomposition for 3D meshes with collision-aware concavity and tree search
Authors:
Open Access
- 22 July 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 41 (4) , 1-18
Abstract
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.Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- Bounded biharmonic weights for real-time deformationACM Transactions on Graphics, 2011
- Approximate convex decomposition of polyhedra and its applicationsComputer Aided Geometric Design, 2008
- Adaptive medial-axis approximation for sphere-tree constructionACM Transactions on Graphics, 2004
- A Fast and Robust GJK Implementation for Collision Detection of Convex ObjectsJournal of Graphics Tools, 1999
- V-ClipACM Transactions on Graphics, 1998
- Erased arrangements of lines and convex decompositions of polyhedraComputational Geometry, 1998
- Strategies for polyhedral surface decomposition: An experimental studyComputational Geometry, 1997
- Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositionsInternational Journal for Numerical Methods in Engineering, 1994
- A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Journal on Robotics and Automation, 1988
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983