Homepage of Roland Geraerts

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Computing High-Quality Paths in Weighted Regions

A high-quality indicative route in a heterogeneous environment.

Abstract

The Weighted Region Problem is defined as the problem of finding a cost-optimal path in a weighted planar polygonal subdivision. Searching for paths on a grid representation of the scene is fast and easy to implement. However, grid representations do not capture the exact geometry of the scene. Hence, grid paths can be inaccurate or might not even exist at all. Methods that work on an exact representation of the scene can approximate an optimal path up to an arbitrarily small epsilon-error. However, these methods are computationally inefficient and thus not well-suited for real-time applications. In this paper, we analyze the quality of optimal paths on a 8-neighbor-grid. We prove that the costs of such a path in a scene with weighted regions can be arbitrarily high in the general case. If all regions are aligned with the grid, we prove that the costs are at most 4 + Sqrt(4 - 2 Sqrt(2)) times the costs of an optimal path. In addition, we present a new hybrid method called Vertex-based Pruning (VBP). VBP computes paths that are epsilon-optimal inside a pruned subset of the scene. Experiments show that VBP paths can be computed at interactive rates, and are thus well-suited as an input for advanced path-following strategies in robotics, crowd simulation or gaming applications.

References

Norman S. Jaklin, Mark tibboel and Roland Geraerts. Computing High-Quality Paths in Weighted Regions. In ACM SigGraph Conference on Motion in Games (MIG 2014), pp. 77-86, 2014.
Norman S. Jaklin, Mark Tibboel and Roland Geraerts. Path-cost Analysis and Real-Time Path Computation in Weighted Regions. In ICT.OPEN 2015 (ICT.OPEN 2015).