Terms

• Terrain means elevation. Ignore surface features for now.
• Use a grid (matrix) of elevations (in this talk; I implemented TINs in 1973).
• Visibility Index: How much can a particular observer see?
• Viewshed: What, specifically, can a particular observer see?
• Sample viewsheds

Multiple Observer Siting

Given some terrain...

Choose the smallest set of observers that will cover as much terrain as possible.

Applications:

• Cell phone towers
• Radio relays on the moon (no ionosphere or stable orbits), and Mars (weak ionosphere).
• Tourism attractions.
• Conversely, visual nuisances to be hidden from the tourists(forest clearcuts, park garbage dumps, private vacation homes).
• Military observers, concealment from observers, route planning, route updating as the observers vanish.
• Maybe connectivity of visible (or hidden) region is important.

Notes

• No interest in toy demos on small datasets, which don't scale up.
• A sufficient quantitative speedup will cause a qualitative change.
• Computing power is not necessarily growing as fast as the data size. (cf PDA)
• Use 1201x1201 DEM cells.
• Ignore earth's curvature, since it can be corrected. Ignore vegetation.

Detailed Process

• VIX: Find approx visibility index of each point in cell. (Use sampling.)
• FINDMAX: Select a sample set of points that have hi vix and also are spaced out.
• VIEWSHED: Find the viewshed of each sample point. (Run lines of sight out.)
• SITE: Select a subset of those viewsheds to cover the cell as well as possible.

VIX - Find Approx Visibility Index of Each Point

• 1,442,401 points (aka observers): speed is essential.
• Choose a parameter, T, say T=10.
• Other parameters: observer ht, target ht, radius of interest.
• For each observer, select T targets at random. Run a line of sight to see if the target is visible.
• Number of targets visible by that observer: its approx visibility index.
• Program coded carefully. Each LOS test averages 8 microseconds on a 600 MHz Pentium.

Findmax - Select Observer Subset

• From the 1442401 points, select the best 1000.
• Best: highest visibility index and also well spaced (to correct for clusters of good points).

VIEWSHED

To determine which points within R, the radius of interest of the observer, are visible.

• Define a 2R by 2R square about the observer.
• Iterate around its perimeter.
• For each point on the perimeter, run a line of sight from the observer to it.
• See which points on that LOS are visible.
• The execution time per observer is proportional to R².
• If we had run LOSs to each point, instead of to each point on the perimeter, the time would have been much worse: R³.

Site - Find a good set of observers

We have a set of possible observers, with their viewsheds (stored as bitmaps). Now, select a subset that covers the terrain cell.

• This is a greedy algorithm.
• As we progress, we know the set of observers chosen so far, and C, the region that they cumulatively see (stored as a bitmap).
• To add another observer to the set:
  • Temporarily unite each remaining observer's viewshed with C, and calculate its area.
  • Pick the observer that results in the largest resulting area.
  • However, remember how much new area each possible observer would have added. In the next round, perhaps do not even consider this observer. This saves time.
• Update everything.

Lake Champlain W Cell Experiment

Terrain	Visibility

Surprising Observations - 1

• Except at the start, the order that an observer is added is unrelated to its visibility.
• After 50 observers added, almost every new observer is itself already visible.
• After 180 observers added, none of the 828 other potential observers added even one new target.

Surprising Observations - 2

• 
  Area of Last Inserted Viewshed (*30), and Cumulative Visible Area, as Observers are Inserted

• Cumulating Viewsheds

• Other results are in paper.

Future: What do we really know about visibility?

• Small changes in the input cause large changes in the input.
• Some viewshed images are partly (mostly?) fiction.
• However certain regions are definitely hidden, and others are definitely visible.
• Find them.
• Note the nonlinearity: visibility is a step function.

Just good enough computation

If...

• The input elevations are noisy, and
• The output visibilities are very sensitive to the input,

Then...

• A much quicker, less accurate, computation might produce just as good output.
• A serious quantitative speed increase will translate into a qualitative improvement in what can be done.

Multilevel Game Theory

1. Red side places observers to cover as much terrain as possible.
2. Blue side, knowing the red observers, finds areas guaranteed to be hidden.

Data Mining

• Visibility is multidimensional:
• Observer height, target height, radius of interest, number of test samples used, ...
• How visibility index depends on height:
• Can the function be simplified?

Acknowledgements

Productivity was greatly helped by:

• Linux
• LaTeX
• xemacs
• xv
• g++

National Science Foundation

How it all fits together