A Practical Approach for Planar Visibility Maintenance

A. Zarei ; M. Ghodsi

Journal for geometry and graphics, Tome 13 (2009) no. 1, pp. 75-9.

Résumé

We propose a method for maintaining the region visible from a moving point observer inside a planar scene. In this method, we check the observer position in discrete time-stamps to detect and apply changes to the visible or illuminated region of a moving point observer q, or VP(q). We efficiently maintain a list C(q) of edges in VP(q) which are subject to change during the motion. In each time-stamp that VP(q) is to be updated, we only refine and redraw the view against the edges of C(q) that indicate the positions of the visibility changes. We build an enriched representation of the visibility graph in a preprocessing step to apply the required updates on C(q) efficiently and ready to be used in the next time-stamp. Using these structures, the exact visible regions are updated in each time-stamp in O(|C(q)|) for sufficiently small values of time-stamp intervals. This is the best possible and superior to the current solutions. Although the time-stamp intervals are small enough in real applications, our method will still remain superior even if the intervals were relatively long in cases with high-speed observer or in dense scenes. The results of our implementation prove efficiency of our method in practice.

Détail

Classification : 68U05, 65D18
Mots-clés : Computational geometry, exact visibility maintenance, moving observer, planar polygonal scene, visibility polygon