“Navigation-driven Approximate Convex Decomposition”
Conference:
Type(s):
Title:
- Navigation-driven Approximate Convex Decomposition
Presenter(s)/Author(s):
Abstract:
We introduce a new approach to approximate convex decomposition based on protecting the space around input shapes that objects in a game or simulation must be able to navigate. Our method is efficient, customizable, and provides novel guarantees that the resulting decompositions will meet application-specific requirements when used for collision.
References:
[1]
Srikanth Bandi and Daniel Thalmann. 1998. Space Discretization for Efficient Human Navigation. Computer Graphics Forum 17, 3 (1998), 195?206. https://doi.org/10.1111/1467-8659.00267
[2]
Jules Bloomenthal. 1994. An implicit surface polygonizer. In Graphics Gems IV, Paul S. Heckbert (Ed.). Academic Press Professional Inc., San Diego, CA, 324?349.
[3]
Bernard M. Chazelle. 1981. Convex Decompositions of Polyhedra. In Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (Milwaukee, Wisconsin, USA) (STOC ?81). Association for Computing Machinery, New York, NY, USA, 70?79. https://doi.org/10.1145/800076.802459
[4]
Zhiqin Chen, Andrea Tagliasacchi, and Hao Zhang. 2020. BSP-Net: Generating Compact Meshes via Binary Space Partitioning. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, Los Alamitos, CA, USA, 42?51. https://doi.org/10.1109/CVPR42600.2020.00012
[5]
Mark de Berg, Otfried Cheong, Marc Kreveld, and Mark Overmars. 2008. Robot Motion Planning. Springer Berlin Heidelberg, Berlin, Heidelberg, 283?306. https://doi.org/10.1007/978-3-540-77974-2_13
[6]
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. https://doi.org/10.1080/10867651.1999.10487502
[7]
Boyang Deng, Kyle Genova, Soroosh Yazdani, Sofien Bouaziz, Geoffrey Hinton, and Andrea Tagliasacchi. 2020. CvxNet: Learnable Convex Decomposition. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, Los Alamitos, CA, USA, 31?41. https://doi.org/10.1109/CVPR42600.2020.00011
[8]
Dave Eberly. 2020. Robust and Error-Free Geometric Computing. CRC Press, Boca Raton, FL, USA.
[9]
Epic Games. 2023. Add a Collision Hull to a Static Mesh Using the Auto Convex Collision Tool. https://docs.unrealengine.com/5.3/en-US/add-a-collision-hull-to-a-static-mesh-using-the-auto-convex-collision-tool-in-unreal-engine/
[10]
Jyh-Ming Lien and Nancy M. Amato. 2004. Approximate convex decomposition of polygons. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (Brooklyn, New York, USA) (SCG ?04). Association for Computing Machinery, New York, NY, USA, 17?26. https://doi.org/10.1145/997817.997823
[11]
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 (Beijing, China) (SPM ?07). Association for Computing Machinery, New York, NY, USA, 121?131. https://doi.org/10.1145/1236246.1236265
[12]
William E. Lorensen and Harvey E. Cline. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques(SIGGRAPH ?87). Association for Computing Machinery, New York, NY, USA, 163?169. https://doi.org/10.1145/37401.37422
[13]
Tom?s Lozano-P?rez. 1990. Spatial Planning: A Configuration Space Approach. In Autonomous Robot Vehicles, Ingemar J. Cox and Gordon T. Wilfong (Eds.). Springer New York, New York, NY, 259?271. https://doi.org/10.1007/978-1-4613-8997-2_20
[14]
Khaled Mamou. 2016. Volumetric hierarchical approximate convex decomposition. In Game Engine Gems 3, Eric Lengyel (Ed.). A K Peters / CRC Press, Boca Raton, FL, USA, 141?158.
[15]
Khaled Mamou and Faouzi Ghorbel. 2009. A simple and efficient approach for 3D mesh approximate convex decomposition. In Proceedings of the 16th IEEE International Conference on Image Processing (Cairo, Egypt) (ICIP?09). IEEE Press, 3465?3468.
[16]
neemoh and John W. Ratcliff. 2023. V-HACD GitHub issue 149: V4.1 Always producing m_maxConvexHulls. https://github.com/kmammou/v-hacd/issues/149
[17]
James A. Sethian. 1999. Optimality and First Arrivals. In Level Set Methods and Fast Marching Methods. Cambridge University Press, Cambridge, UK, 286?315.
[18]
Greg Snook. 2000. Simplified 3D Movement and Pathfinding Using Navigation Meshes. In Game Programming Gems, Mark DeLoura (Ed.). Charles River Media, 288?304.
[19]
Daniel Thul, L?ubor Ladick?, Sohyeon Jeong, and Marc Pollefeys. 2018. Approximate convex decomposition and transfer for animated meshes. ACM Trans. Graph. 37, 6, Article 226 (dec 2018), 10 pages. https://doi.org/10.1145/3272127.3275029
[20]
Xinyue Wei, Minghua Liu, Zhan Ling, and Hao Su. 2022. Approximate convex decomposition for 3D meshes with collision-aware concavity and tree search. ACM Trans. Graph. 41, 4, Article 42 (jul 2022), 18 pages. https://doi.org/10.1145/3528223.3530103
[21]
Fanbo Xiang, Yuzhe Qin, Kaichun Mo, Yikuan Xia, Hao Zhu, Fangchen Liu, Minghua Liu, Hanxiao Jiang, Yifu Yuan, He Wang, Li Yi, Angel X. Chang, Leonidas J. Guibas, and Hao Su. 2020. SAPIEN: A SimulAted Part-Based Interactive ENvironment. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Computer Society, Los Alamitos, CA, USA, 11094?11104. https://doi.org/10.1109/CVPR42600.2020.01111
