Combining high and low resolution speeds up viewshed computation
Best of Two Worlds: Combining High and Low Resolution to Compute Viewsheds on terrains
Data Structures and Algorithms
Summary
Figuring out which points you can see from a spot on a digital map of land can take a long time. The paper shows a way to speed this up by first looking at a simpler map with bigger blocks to quickly rule out invisible areas. Then, it carefully checks only the potentially visible small blocks in detail to get the exact answer. The authors prove their method is faster and tested it to show it can be over ten times quicker than older methods, without losing accuracy.
What this means in practice
- •For geospatial analysts: Accelerate detailed visibility analysis on large terrain data by filtering out invisible regions using a multi-resolution approach.
- •For game developers: Improve rendering efficiency by quickly determining visible terrain areas in large virtual worlds without approximation.
Authors
Laura Toma
Abstract
The viewshed of a point $v$ on a grid terrain $T$, viewshed$_T(v)$, is defined as the set of grid points in $T$ that are visible from $v$. We describe a novel algorithm for computing viewshed$_T(v)$ using a multi-resolution approach: Given a parameter $k >1$ that represents the block size, we create a grid $T'$ which is a lower-resolution version of $T$, such that each point in $T'$ corresponds to a block of $\lceil \sqrt k \rceil $-by-$\lceil \sqrt k \rceil$ points in $T$. The key of our approach is using $T'$ to speed up the computation of viewshed$_T(v)$ while not introducing approximation. We compute viewshed$_T(v)$ in two steps: First we compute the viewshed of $v$ on $T'$, while maintaining the invariant that any block in $T'$ that is labeled as invisible may not contain any visible points. Thus, the first step's role is to use $T'$ to filter out blocks in $T$ that are guaranteed to be invisible. The second step considers the blocks that were labeled as visible in $T'$ and computes the visibility of their points with full accuracy using the data in $T$. Overall the algorithm runs in $O(n + \frac nk \lg \frac nk + k \lg k + l \cdot \lg n)$, where $l$ is the total size of visible blocks in $T'$. When $k = Ω(1)$ and $l = o(n) $, the running time of our algorithm improves on the previous best bound of $O(n \lg n)$. Our experimental results show the performance of the new algorithm in practice and a speedup of more than an order of magnitude compared to previous algorithms.