“Approximate convex decomposition for 3D meshes with collision-aware concavity and tree search” by Wei, Liu, Ling and Su

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.

1. Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. 1998. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM) 45, 6 (1998), 891–923.Google ScholarDigital Library
2. Marco Attene, Michela Mortara, Michela Spagnuolo, and Bianca Falcidieno. 2008. Hierarchical convex approximation of 3D shapes for fast region selection. In Computer graphics forum, Vol. 27. Wiley Online Library, 1323–1332.Google Scholar
3. Chanderjit L Bajaj and Tamal K Dey. 1992. Convex decomposition of polyhedra and robustness. SIAM J. Comput. 21, 2 (1992), 339–364.Google ScholarDigital Library
4. Chandrajit L Bajaj and Valerio Pascucci. 1996. Splitting a complex of convex polytopes in any dimension. In Proceedings of the twelfth annual symposium on Computational geometry. 88–97.Google ScholarDigital Library
5. Gino van den Bergen. 1999. A fast and robust GJK implementation for collision detection of convex objects. Journal of graphics tools 4, 2 (1999), 7–25.Google ScholarDigital Library
6. Jose Luis Blanco and Pranjal Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN, a library for Nearest Neighbor (NN) with KD-trees. https://github.com/jlblancoc/nanoflann.Google Scholar
7. Gareth Bradshaw and Carol O’Sullivan. 2004. Adaptive medial-axis approximation for sphere-tree construction. ACM Transactions on Graphics (TOG) 23, 1 (2004), 1–26.Google ScholarDigital Library
8. Stéphane Calderon and Tamy Boubekeur. 2017. Bounding proxies for shape approximation. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–13.Google ScholarDigital Library
9. Bernard Chazelle. 1984. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comput. 13, 3 (1984), 488–507.Google ScholarDigital Library
10. Bernard Chazelle, David P Dobkin, Nadia Shouraboura, and Ayellet Tal. 1997. Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry 7, 5–6 (1997), 327–342.Google ScholarDigital Library
11. Bernard M Chazelle. 1981. Convex decompositions of polyhedra. In Proceedings of the thirteenth annual ACM symposium on Theory of computing. 70–79.Google ScholarDigital Library
12. Zhiqin Chen, Andrea Tagliasacchi, and Hao Zhang. 2020. Bsp-net: Generating compact meshes via binary space partitioning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 45–54.Google ScholarCross Ref
13. Boyang Deng, Kyle Genova, Soroosh Yazdani, Sofien Bouaziz, Geoffrey Hinton, and Andrea Tagliasacchi. 2020. Cvxnet: Learnable convex decomposition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 31–44.Google ScholarCross Ref
14. Andreas Fabri and Sylvain Pion. 2009. CGAL: The computational geometry algorithms library. In Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. 538–539.Google ScholarDigital Library
15. Matheus Gadelha, Giorgio Gori, Duygu Ceylan, Radomir Mech, Nathan Carr, Tamy Boubekeur, Rui Wang, and Subhransu Maji. 2020. Learning generative models of shape handles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 402–411.Google ScholarCross Ref
16. Mukulika Ghosh, Nancy M Amato, Yanyan Lu, and Jyh-Ming Lien. 2013. Fast approximate convex decomposition using relative concavity. Computer-Aided Design 45, 2 (2013), 494–504.Google ScholarDigital Library
17. Elmer G Gilbert, Daniel W Johnson, and S Sathiya Keerthi. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE Journal on Robotics and Automation 4, 2 (1988), 193–203.Google ScholarCross Ref
18. Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. 2018. Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905 (2018).Google Scholar
19. John E Hershberger and Jack S Snoeyink. 1998. Erased arrangements of lines and convex decompositions of polyhedra. Computational Geometry 9, 3 (1998), 129–143.Google ScholarDigital Library
20. Jingwei Huang, Hao Su, and Leonidas Guibas. 2018. Robust watertight manifold surface generation method for shapenet models. arXiv preprint arXiv:1802.01698 (2018).Google Scholar
21. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), 78.Google ScholarDigital Library
22. Barry Joe. 1994. Tetrahedral mesh generation in polyhedral regions based on convex polyhedron decompositions. Internat. J. Numer. Methods Engrg. 37, 4 (1994), 693–713.Google ScholarCross Ref
23. Levente Kocsis and Csaba Szepesvári. 2006. Bandit based monte-carlo planning. In European conference on machine learning. Springer, 282–293.Google ScholarDigital Library
24. Lingxiao Li, Minhyuk Sung, Anastasia Dubrovina, Li Yi, and Leonidas J Guibas. 2019. Supervised fitting of geometric primitives to 3d point clouds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2652–2660.Google ScholarCross Ref
25. Jyh-Ming Lien and Nancy M Amato. 2004. Approximate convex decomposition. In Proceedings of the twentieth annual symposium on Computational geometry. 457–458.Google ScholarDigital Library
26. Jyh-Ming Lien and Nancy M Amato. 2007. Approximate convex decomposition of polyhedra. In Proceedings of the 2007 ACM symposium on Solid and physical modeling. 121–131.Google ScholarDigital Library
27. Jyh-Ming Lien and Nancy M Amato. 2008. Approximate convex decomposition of polyhedra and its applications. Computer Aided Geometric Design 25, 7 (2008), 503–522.Google ScholarDigital Library
28. Jyh-Ming Lien, John Keyser, and Nancy M Amato. 2006. Simultaneous shape decomposition and skeletonization. In Proceedings of the 2006 ACM symposium on Solid and physical modeling. 219–228.Google ScholarDigital Library
29. Guilin Liu, Zhonghua Xi, and Jyh-Ming Lien. 2016. Nearly convex segmentation of polyhedra through convex ridge separation. Computer-Aided Design 78 (2016), 137–146.Google ScholarDigital Library
30. Hairong Liu, Wenyu Liu, and Longin Jan Latecki. 2010. Convex shape decomposition. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 97–104.Google ScholarCross Ref
31. Minghua Liu, Minhyuk Sung, Radomir Mech, and Hao Su. 2021. DeepMetaHandles: Learning Deformation Meta-Handles of 3D Meshes with Biharmonic Coordinates. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 12–21.Google ScholarCross Ref
32. Rong Liu, Hao Zhang, and James Busby. 2008. Convex hull covering of polygonal scenes for accurate collision detection in games.. In Graphics Interface. 203–210.Google Scholar
33. Khaled Mamou and Faouzi Ghorbel. 2009. A simple and efficient approach for 3D mesh approximate convex decomposition. In 2009 16th IEEE international conference on image processing (ICIP). IEEE, 3501–3504.Google ScholarCross Ref
34. Khaled Mamou, E Lengyel, and AK Peters. 2016. Volumetric hierarchical approximate convex decomposition. In Game Engine Gems 3. AK Peters, 141–158.Google Scholar
35. Brian Mirtich. 1998. V-Clip: Fast and robust polyhedral collision detection. ACM Transactions On Graphics (TOG) 17, 3 (1998), 177–208.Google ScholarDigital Library
36. Kaichun Mo, Paul Guerrero, Li Yi, Hao Su, Peter Wonka, Niloy Mitra, and Leonidas J Guibas. 2019. Structurenet: Hierarchical graph networks for 3d shape generation. arXiv preprint arXiv:1908.00575 (2019).Google Scholar
37. Tongzhou Mu, Zhan Ling, Fanbo Xiang, Derek Yang, Xuanlin Li, Stone Tao, Zhiao Huang, Zhiwei Jia, and Hao Su. 2021. ManiSkill: Learning-from-Demonstrations Benchmark for Generalizable Manipulation Skills. arXiv e-prints (2021), arXiv-2107.Google Scholar
38. Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2013. Real time dynamic fracture with volumetric approximate convex decompositions. ACM Transactions on Graphics (TOG) 32, 4 (2013), 1–10.Google ScholarDigital Library
39. Joseph O’Rourke and Kenneth Supowit. 1983. Some NP-hard polygon decomposition problems. IEEE Transactions on Information Theory 29, 2 (1983), 181–190.Google ScholarDigital Library
40. Despoina Paschalidou, Luc Van Gool, and Andreas Geiger. 2020. Learning unsupervised hierarchical part decomposition of 3d objects from a single rgb image. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 1060–1070.Google ScholarCross Ref
41. Despoina Paschalidou, Ali Osman Ulusoy, and Andreas Geiger. 2019. Superquadrics revisited: Learning 3d shape parsing beyond cuboids. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 10344–10353.Google ScholarCross Ref
42. Karl Pearson. 1901. LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science 2, 11 (1901), 559–572.Google Scholar
43. Zhou Ren, Junsong Yuan, Chunyuan Li, and Wenyu Liu. 2011. Minimum near-convex decomposition for robust shape representation. In 2011 International Conference on Computer Vision. IEEE, 303–310.Google Scholar
44. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Workshop on Applied Computational Geometry. Springer, 203–222.Google ScholarCross Ref
45. Dmitriy Smirnov, Matthew Fisher, Vladimir G Kim, Richard Zhang, and Justin Solomon. 2020. Deep parametric shape predictions using distance fields. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 561–570.Google ScholarCross Ref
46. Jack Snoeyink. 2017. Point location. In Handbook of discrete and computational geometry. Chapman and Hall/CRC, 1005–1028.Google Scholar
47. Chun-Yu Sun, Qian-Fang Zou, Xin Tong, and Yang Liu. 2019. Learning adaptive hierarchical cuboid abstractions of 3d shape collections. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–13.Google ScholarDigital Library
48. Jean-Marc Thiery, Émilie Guy, and Tamy Boubekeur. 2013. Sphere-meshes: Shape approximation using spherical quadric error metrics. ACM Transactions on Graphics (TOG) 32, 6 (2013), 1–12.Google ScholarDigital Library
49. Daniel Thul, L’ubor Ladický, Sohyeon Jeong, and Marc Pollefeys. 2018. Approximate convex decomposition and transfer for animated meshes. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–10.Google ScholarDigital Library
50. Shubham Tulsiani, Hao Su, Leonidas J Guibas, Alexei A Efros, and Jitendra Malik. 2017. Learning shape abstractions by assembling volumetric primitives. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2635–2643.Google ScholarCross Ref
51. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear subspace design for real-time shape deformation. ACM Transactions on Graphics (TOG) 34, 4 (2015), 1–11.Google ScholarDigital Library
52. René Weller. 2013. A brief overview of collision detection. New Geometric Data Structures for Collision Detection and Haptics (2013), 9–46.Google ScholarDigital Library
53. Martin Wicke, Mario Botsch, and Markus Gross. 2007. A finite element method on convex polyhedra. In Computer Graphics Forum, Vol. 26. Wiley Online Library, 355–364.Google Scholar
54. Chuhua Xian, Hongwei Lin, and Shuming Gao. 2012. Automatic cage generation by improved obbs for mesh deformation. The Visual Computer 28, 1 (2012), 21–33.Google ScholarDigital Library
55. Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanxiao Jiang, Yifu Yuan, He Wang, et al. 2020. Sapien: A simulated part-based interactive environment. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 11097–11107.Google ScholarCross Ref
56. Yang Zhou, Kangxue Yin, Hui Huang, Hao Zhang, Minglun Gong, and Daniel Cohen-Or. 2015. Generalized cylinder decomposition. ACM Trans. Graph. 34, 6 (2015), 171–1.Google ScholarDigital Library
57. Chuhang Zou, Ersin Yumer, Jimei Yang, Duygu Ceylan, and Derek Hoiem. 2017. 3d-prnn: Generating shape primitives with recurrent neural networks. In Proceedings of the IEEE International Conference on Computer Vision. 900–909.Google ScholarCross Ref