Visibility computations in 2D polygonal scenes

摘要

The core part of computer programs such as visualization softwares, rendering engines or robotics path planners lies in visibly computations. Although the corresponding algorithms are only a small part of the whole application, they are responsible for most of the running time and their efficiency is therefore crucial. Traditional visibility computation algorithms have two drawbacks: They perform useless computations on invisible objects, and recompute everything from scratch for every single query, even if the changes undergone by two successive solutions are minor. We show how to remedy these problems in the context of polygonal scenes in the plane by using the visibility complex data structure, which encodes all the visibility relations between objects of the scene. First, we present an optimal algorithm for computing the visibility complex. Second, we show how to use this data structure to compute visibility polygons and to maintain views around a moving point in the scene. Both the theoretical complexity and the practical performances of our algorithms are presented. Finally, we explain how to handle the degeneracies and numerical imprecisions caused by real-world data sets.