Separating a polygonal environment into a multi-layered environment.

Abstract

Path planning is the field of computer science devoted to finding efficient and/or realistic methods used to navigate characters through virtual environments. The Explicit Corridor Map [21] is a navigation mesh which has recently been extended to scenes that consist of multiple 2D layers which are connected by so called transfers [42]. Obtaining such a layered 2D environment from a 3D polygonal environment has been studied by Saaltink [40]. Saaltink employed a brute-force algorithm, as well as a graph-based algorithm. In this study we continue searching for other algorithms employing a graph encoding of the 3D polygonal environment. In this graph encoding each polygon is represented by a vertex. Whenever two polygons are next to each other, an edge connecting the corresponding vertices is added to the graph. Lastly, a special kind of edge called an overlap is added between to vertices in the graph whenever the corresponding polygons overlap when they are projected on the xz-plane. We show that finding a multi-layered environment using this graph encoding is an NP-Hard problem by a reduction from 3-SAT. Methods are described that can significantly reduce the size of the graph encoding of the 3D polygonal environment. Furthermore, we have implemented a range of different heuristic methods. The first heuristic method employs shortest path algorithms to quickly search and cut all paths connecting overlapping polygons. The second heuristic method clusters polygons based on height information. In addition to these two methods, different local search algorithms are implemented, as well as a genetic algorithm. Since none of these methods are guaranteed to find an optimal solution, we have also implemented an integer linear programming that employs Branch & Price. The results of all these different methods are listed and evaluated. For these tests, nine environments were used. The height-based clustering and an implementation of local search outperform all other methods, both in quality of the solution as well as in execution time.