“Dynamic and Robust Local Clearance Triangulations” by Kallmann

  • ©Marcelo Kallmann




    Dynamic and Robust Local Clearance Triangulations

Session/Category Title: Layout Building & Scenes




    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.


    1. J. Berg, M. Lin, and D. Manocha. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. In Proceedings of the International Conference on Robotics and Automation (ICRA’08). IEEE.
    2. P. Bhattacharya and M. Gavrilova. 2008. Roadmap-based path planning – Using the Voronoi diagram for a clearance-based shortest path. IEEE Robot. Autom. Mag. 15, 2, 58–66.
    3. B. Chazelle. 1982. A theorem on polygon cutting with applications. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 339–349.
    4. L. P. Chew. 1985. Planning the shortest path for a disc in o (n2logn) time. In Proceedings of the ACM Symposium on Computational Geometry.
    5. M. De Berg, O. Cheong, and, M. Van Kreveld. 2008. Computational Geometry: Algorithms and Applications. Springer.
    6. D. Demyen. 2007. Efficient triangulation-based pathfinding. https://skatgame.net/mburo/ps/thesis_demyen_2006.pdf.
    7. D. Demyen and M. Buro. 2006. Efficient triangulation-based pathfinding. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI’06). AAAI Press, 942–947.
    8. O. Devillers and S. Pion. 2003. Efficient exact geometric predicates for Delaunay triangulations. In Proceedings of the 5th Workshop Algorithm Engineering and Experiments. 37–44.
    9. O. Devillers, S. Pion, and M. Teillaud. 2001. Walking in a triangulation. In Proceedings of the ACM Symposium on Computational Geometry. 106–114.
    10. M. L. Gavrilova, H. Ratschek, and J. G. Rokne. 2000. Exact computation of Delaunay and power triangulations. Reliab. Comput. 6, 1, 39–60.
    11. R. Gayle, A. Sud, E. andersen, S. J. Guy, M. C. Lin, and D. Manocha. 2009. Interactive navigation of heterogeneous agents using adaptive roadmaps. IEEE Trans. Visual. Comput. Graph. 15, 34–48.
    12. R. Geraerts. 2010. Planning short paths with clearance using explicit corridors. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’10).
    13. P. E. Hart, N. J. Nilsson, and B. Raphael. 2007. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybernet. 4, 2, 100–107.
    14. M. Held. 2001. Vroni: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Comput. Geom. 18, 2, 95–123.
    15. J. Hershberger and J. Snoeyink. 1994. Computing minimum length paths of a given homotopy class. Comput. Geom. Theory Appl. 4, 2, 63–97.
    16. J. Hershberger and S. Suri. 1997. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28, 2215–2256.
    17. K. E. Hoff III, T. Culver, J. Keyser, M. Lin, and D. Manocha. 2000. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of the ACM Symposium on Computational Geometry.
    18. C.-J. Jorgensen and F. Lamarche. 2011. From geometry to spatial reasoning: Automatic structuring of 3D virtual environments. In Proceedings of the 4th International Conference on Motion in Games (MIG’11). Springer, 353–364.
    19. M. Kallmann. 2010. Shortest paths with arbitrary clearance from navigation meshes. In Proceedings of the Eurographics/SIGGRAPH Symposium on Computer Animation (SCA’10).
    20. M. Kallmann, H. Bieri, and D. Thalmann. 2003. Fully dynamic constrained Delaunay triangulations. In Geometric Modeling for Scientific Visualization, G. Brunnett, B. Hamann, H. Mueller, and L. Linsen, Eds., Springer, 241–257.
    21. S. Kapoor, S. N. Maheshwari, and J. S. B. Mitchell. 1997. An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane. Discr. Comput. Geom. 18, 4, 377–383.
    22. S. Koenig and M. Likhachev. 2002. D* lite. In Proceedings of the AAAI Conference on Artificial Intelligence. 476–483.
    23. J. J. Kuffner and J.-C. Latombe. 1999. Fast synthetic vision, memory, and learning models for virtual humans. In Proceedings of the IEEE International Conference on Computer Animation (CA’99).
    24. F. Lamarche. 2009. Topoplan: A topological path planner for real time human navigation under floor and ceiling constraints. Comput. Graph. Forum 28, 2, 649–658.
    25. F. Lamarche and S. Donikian. 2004. Crowd of virtual humans: A new approach for real time navigation in complex and structured environments. Comput. Graph. Forum 23, 3, 509–518.
    26. D. T. Lee and F. P. Preparata. 1984. Euclidean shortest paths in the presence of rectilinear barriers. Netw. 3, 14, 393–410.
    27. M. Likhachev, G. Gordon, and S. Thrun. 2003. ARA*: Anytime a* search with provable bounds on sub-optimality. In Neural Information Processing Systems., MIT Press.
    28. Y. H. Liu and S. Arimoto. 1995. Finding the shortest path of a disk among polygonal obstacles using a radius-independent graph. IEEE Trans. Robot. Autom. 11, 5, 682–691.
    29. T. Lozano-Perez and M. A. Wesley. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Comm. ACM 22, 10, 560–570.
    30. R. A. Metoyer and J. K. Hodgins. 2003. Reactive pedestrian path following from examples. In Proceedings of the 16th International Conference on Computer Animation and Social Agents (CASA’03). IEEE Computer Society.
    31. J. S. B. Mitchell. 1993. Shortest paths among obstacles in the plane. In Proceedings of the 9th Annual Symposium on Computational Geometry. ACM Press, New York, 308–317.
    32. N. Nilsson. 1969. A mobile automaton: An application of artificial intelligence techniques. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI’69). 509–520.
    33. H. Noser and D. Thalmann. 1995. Synthetic vision and audition for digital actors. Proc. Eurograph. 14, 3, 326-336.
    34. R. Oliva and N. Pelechano. 2013. Neogen: Near optimal generator of navigation meshes for 3D multi-layered environments. Comput. Graph. 37, 5, 403–412.
    35. M. H. Overmars and E. Welzl. 1988. New methods for computing visibility graphs. In Proceedings of the 4th Annual Symposium on Computational Geometry. ACM Press, New York, 164–171.
    36. W. Shao and D. Terzopoulos. 2005. Autonomous pedestrians. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’05). ACM Press, New York, 19–28.
    37. J. R. Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Proceedings of the Workshop on Applied Computational Geometry: Towards Geometric Engineering (FCRC’96). M. C. Lin and D. Manocha, Eds., Lecture Notes in Computer Science, vol. 1148, Springer, 203–222.
    38. J. R. Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discr. Comput. Geom. 18, 3, 305–363.
    39. S. Singh, M. Kapadia, P. Faloutsos, and G. Reinman. 2009. SteerBench: A benchmark suite for evaluating steering behaviors. Comput. Animat. Virtual Worlds 20, 56, 533–548.
    40. J. A. Storer and J. H. Reif. 1994. Shortest paths in the plane with polygonal obstacles. J. ACM 41, 5, 982–1012.
    41. A. Sud, E. Andersen, S. Curtis, M. C. Lin, and D. Manocha. 2008. Real-time path planning in dynamic virtual environments using multiagent navigation graphs. IEEE Trans. Vis. Comput. Graph. 14, 526–538.
    42. R. Wein, J. van den Berg, and D. Halperin. 2007. The visibility-Voronoi complex and its applications. Comput. Geom. Theory Appl. 36, 1, 66–78.

ACM Digital Library Publication: