Automatically-generated Convex Region Decomposition for Real-time Spatial Agent Navigation in Virtual Worlds
Automatically-generated Convex Region Decomposition for Real-time Spatial Agent Navigation in Virtual Worlds
复制标题
自动生成凸区域分解，用于虚拟世界中的实时空间代理导航
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Priyesh N. Dixit
中科院分区：
文献类型：
--
作者：
D. Hale;G. Youngblood;Priyesh N. Dixit
本文提出了一种新的方法来分解复杂的几何环境中的导航网格表示的边界几何和连接图的实时代理在虚拟世界中的使用。这是通过生成一组定义明确且覆盖率高的凸可导航区域以及它们之间的连接网关来实现的。本文的重点是一个新的自动化算法开发的世界空间的2D表示分解成任意边的高阶多边形。DEACCON（Decomposition of Environments for the Creation of Convex-region Navigation-meshes）算法的工作原理是用一系列四边形为世界空间的2D多边形表示播种。然后，每个四边形都有机会在遇到障碍物之前生长到最大程度。DEACON实现了一个自动细分系统，将四边形转换为高阶多边形，同时仍然保持凸属性。这允许生成具有高覆盖度的导航网格，同时仍然允许使用大的导航区域，从而在虚拟世界中提供更容易的代理导航。与空间填充网格分解和Hertel-Mehlhorn导航网格分解方法相比，DEACCON提供了更完整的覆盖范围，可控的网格大小，以及更好的整体算法控制，以达到所需的分解质量，并由于更好的分解而提高了代理导航速度。
This paper presents a new method for decomposing environments of complex geometry into a navigation mesh represented by bounding geometry and a connectivity graph for real-time agent usage in virtual worlds. This is accomplished by the generation of a well-defined and high-coverage set of convex navigable regions and the connected gateways between them. The focus of this paper is a new automated algorithm developed for decomposing a 2D representation of world-space into arbitrary sided high-order polygons. The DEACCON (Decomposition of Environments for the Creation of Convex-region Navigation-meshes) algorithm works by seeding a 2D polygonal representation of world-space with a series of quads. Each quad is then provided with the opportunity to grow to its maximum extent before encountering an obstruction. DEACCON implements an automatic subdividing system to convert quads into higher-order polygons while still maintaining the convex property. This allows for the generation of navigation meshes with high degrees of coverage while still allowing the use of large navigation regions, providing for easier agent navigation in virtual worlds. Compared to the Space-filling Volumes and Hertel-Mehlhorn navigation mesh decomposition methods, DEACCON provides more complete coverage, controllable mesh sizes, and better overall algorithmic control to desired decomposition quality with an improvement in agent navigation speed due to better decompositions.