Alternative algorithms for computing Explicit Corridor Maps using exact and topology-oriented paradigms.

Abstract

Abstract

In the last two decades, games and real-time applications have known an exponential growth in terms of complexity, becoming more and more able to simulate realistic environments. For these complex systems efficient path planning and crowd simulation algorithms are fundamen- tal. Consequently, a lot of research has been done to design the right data structures, which would improve the realism of a simulation within real-time performance. The Explicit Corridor Map (ECM) is an efficient navigation mesh that can represent free space exactly in a given 2D environment. The ECM is based on the medial axis, an efficient descriptor of polygonal shapes similar to the generalized Voronoi diagram. Due to its low time and space complexities, together with other path planning algorithms, it can simulate large crowds in real-time. To obtain the Explicit Corridor Map, current solutions use the graphics card. Ergo, the quality of the ECM is dependent on the maximum resolution supported by the graphics process- ing unit (GPU). On the other hand, this Master Thesis proposes alternative algorithms based on the exact and topology-oriented paradigms. Doing so, we would obtain a more precise and resolution independent result. The algorithm was implemented using two software packages for computing segment Voronoi Diagram, namely VRONI (the topology-oriented candidate) and the Segment Delaunay Graph from CGAL (the exact candidate). The aim was to identify the strengths and weaknesses of each algorithm in terms of precision, robustness and computation time. Running our tests, we found that the solution implemented with VRONI is the most robust and outperforms the other variants in terms of precision and robustness. On the other hand, we found the behavior of CGAL quite unstable, regardless of the number format used for com- putation. To our surprise, using double number types yields more precise results than using exact number types. Finally, precision is an issue for the gpu, since it is dependent on the resolution of the framebuffer. Even using the maximum admited resolution, still its precision lags behind the other two algorithms a few orders of mangnitude.