| dc.description.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. | |
