Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorGeraerts, R.J.
dc.contributor.authorVermeulen, J.L.
dc.date.accessioned2017-04-24T17:03:20Z
dc.date.available2017-04-24T17:03:20Z
dc.date.issued2017
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/25765
dc.description.abstractIn crowd simulation, a navigation mesh of an environment is typically generated to allow efficient path planning. Some methods for navigation mesh generation require as input a representation of the walkable environment, that is, the parts of the environment that a human would be able to walk across. In a previous Master's thesis, Polak developed a filtering pipeline that extracts such a walkable environment from a 3D environment. A shortcoming of this method is that the result often contains gaps; for instance, stairs will yield a series of free-floating steps, with no information indicating that it is possible to walk from one step to the next. In this thesis, we provide an algorithm extending the existing pipeline that tries to solve this. We detect gaps, up to a given size, between pairs of boundary edges of the walkable environment, and fill them with a quad. For connections between different cycles of boundary edges, we make a heuristic choice based on projected distance when there are multiple destinations for a given segment of a boundary edge. For connections between boundary edges in the same cycle, we project all the quads onto the ground plane and take their union, lifting the result back to 3D to fill the gap. We compare our algorithm to two voxel-based methods of navigation mesh generation: Recast and NEOGEN. We find that our method gives more accurate results in many environments: it retains the exact representation of the walkable environment, semantically separates the gaps from the walkable areas, and requires no tweaking of parameters to obtain optimal results. However, there are some open problems that still need to be solved for our method to work fully automatically in practice, such as dealing with obstacles and the interaction of more than two cycles of boundary edges.
dc.description.sponsorshipUtrecht University
dc.format.extent61939660
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titleBridging gaps in walkable environments
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsCrowd simulation, Navigation mesh, Walkable environment, Gaps
dc.subject.courseuuGame and Media Technology


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record