Jordi L. Vermeulen

Autonomous agents typically need a navigation mesh of a 3D virtual environment to allow efficient path planning. This mesh needs as input a continuous representation of the walkable areas. However, the walkable environment (WE), i.e. the parts of the 3D environment that an agent can walk on, may contain gaps. These may be due to the filtering steps performed to compute the WE, because of modelling errors in the 3D model, or simply be part of the geometry of the environment. We provide an algorithm that identifies and fills these gaps. We detect gaps, up to a given distance, between pairs of boundary edges of the walkable environment, and fill them with polygons. We employ a heuristic for choosing which pairs of edges should be connected. We compare our algorithm to Recast [10], a voxel-based method for navigation mesh generation. 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 good results. However, our method is currently slower than Recast, and requires more memory.

Thek‐nearest neighbour (kNN) problem appears in many different fields of computer science, such as computer animation and robotics. In crowd simulation,kNN queries are typically used by a collision‐avoidance method to prevent unnecessary computations. Many different methods for finding these neighbours exist, but it is unclear which will work best in crowd simulations, an application which is characterised by low dimensionality and frequent change of the data points. We therefore compare several data structures for performingkNN queries. We find that the nanoflann implementation of ak‐d tree offers the best performance by far on many different scenarios, processing 100,000 agents in about 35 ms on a fast consumer PC.