View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Separating a polygonal environment into a multi-layered environment.

        Thumbnail
        View/Open
        thesis.pdf (19.14Mb)
        Publication date
        2012
        Author
        Hillebrand, A.
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/12273
        Collections
        • Theses
        Utrecht university logo