Journal for Geometry and Graphics 13 (2009), No. 1, 075--090
Copyright Heldermann Verlag 2009
A Practical Approach for Planar Visibility Maintenance
Alireza Zarei
Computer Engineering Department, Sharif University of Technology, IPM School of Computer Science, Tehran, Iran
zarei@mehr.sharif.edu
Mohammad Ghodsi
Computer Engineering Department, Sharif University of Technology, IPM School of Computer Science, Tehran, Iran
ghodsi@sharif.edu
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.
Keywords: Computational geometry, exact visibility maintenance, moving observer, planar polygonal scene, visibility polygon.
MSC: 68U05; 65D18
[ Fulltext-pdf (186 KB)] for subscribers only.