Dynamic and Robust Local Clearance Triangulations

作者：Kallmann Marcelo^*

来源：ACM Transactions on Graphics, 2014, 33(5): 161.

DOI：10.1145/2580947

• Algorithms
• Path planning
• navigation meshes
• character navigation

The Local Clearance Triangulation (LCT) of polygonal obstacles is a cell decomposition designed for the efficient computation of locally shortest paths with clearance. This article presents a revised definition of LCTs, new theoretical results and optimizations, and new algorithms introducing dynamic updates and robustness. Given an input obstacle set with n vertices, a theoretical analysis is proposed showing that LCTs generate a triangular decomposition of O(n) cells, guaranteeing that discrete search algorithms can compute paths in optimal times. In addition, several examples are presented indicating that the number of triangles is low in practice, close to 2n, and a new technique is described for reducing the number of triangles when the maximum query clearance is known in advance. Algorithms for repairing the local clearance property dynamically are also introduced, leading to efficient LCT updates for addressing dynamic changes in the obstacle set. Dynamic updates automatically handle intersecting and overlapping segments with guaranteed robustness, using techniques that combine one exact geometric predicate with adjustment of illegal floating-point coordinates. The presented results demonstrate that LCTs are efficient and highly flexible for representing dynamic polygonal environments with clearance information.

• 出版日期2014-8