Approximating Visibility

Varying Radius and Height - Visibilities

H= 1, 2, 5, 10

R=2, H=1	R=2, H=2	R=2, H=5	R=2, H=10
R=5, H=1	R=5, H=2	R=5, H=5	R=5, H=10
R=10, H=1	R=10, H=2	R=10, H=5	R=10, H=10
R=20, H=1	R=20, H=2	R=20, H=5	R=20, H=10
R=50, H=1	R=50, H=2	R=50, H=5	R=50, H=10
R=100, H=1	R=100, H=2	R=100, H=5	R=100, H=10

H = 10, 20, 50, 100

R=2, H=10	R=2, H=20	R=2, H=50	R=2, H=100
R=5, H=10	R=5, H=20	R=5, H=50	R=5, H=100
R=10, H=10	R=10, H=20	R=10, H=50	R=10, H=100
R=20, H=10	R=20, H=20	R=20, H=50	R=20, H=100
R=50, H=10	R=50, H=20	R=50, H=50	R=50, H=100
R=100, H=10	R=100, H=20	R=100, H=50	R=100, H=100

Varying Radius and Height - Histograms of Visibilities

H = 1, 2, 5, 10

R=2, H=1	R=2, H=2	R=2, H=5	R=2, H=10
R=5, H=1	R=5, H=2	R=5, H=5	R=5, H=10
R=10, H=1	R=10, H=2	R=10, H=5	R=10, H=10
R=20, H=1	R=20, H=2	R=20, H=5	R=20, H=10
R=50, H=1	R=50, H=2	R=50, H=5	R=50, H=10
R=100, H=1	R=100, H=2	R=100, H=5	R=100, H=10

H = 10, 20, 50, 100

R=2, H=10	R=2, H=20	R=2, H=50	R=2, H=100
R=5, H=10	R=5, H=20	R=5, H=50	R=5, H=100
R=10, H=10	R=10, H=20	R=10, H=50	R=10, H=100
R=20, H=10	R=20, H=20	R=20, H=50	R=20, H=100
R=50, H=10	R=50, H=20	R=50, H=50	R=50, H=100
R=100, H=10	R=100, H=20	R=100, H=50	R=100, H=100

Varying Radius and Height - 100 Most Visible Points

H = 1, 2, 5, 10

R=2, H=1	R=2, H=2	R=2, H=5	R=2, H=10
R=5, H=1	R=5, H=2	R=5, H=5	R=5, H=10
R=10, H=1	R=10, H=2	R=10, H=5	R=10, H=10
R=20, H=1	R=20, H=2	R=20, H=5	R=20, H=10
R=50, H=1	R=50, H=2	R=50, H=5	R=50, H=10
R=100, H=1	R=100, H=2	R=100, H=5	R=100, H=10

H = 10, 20, 50, 100

R=2, H=10	R=2, H=20	R=2, H=50	R=2, H=100
R=5, H=10	R=5, H=20	R=5, H=50	R=5, H=100
R=10, H=10	R=10, H=20	R=10, H=50	R=10, H=100
R=20, H=10	R=20, H=20	R=20, H=50	R=20, H=100
R=50, H=10	R=50, H=20	R=50, H=50	R=50, H=100
R=100, H=10	R=100, H=20	R=100, H=50	R=100, H=100

Longterm Strategy

• Operate on terrain elevation data.
• Competing representations on large datasets:
  • TINs,
  • grid (matrix),
  • contour
• Operations:
• Format conversion
• Compression
• Visibility
• Drainage (future)
• Integrate into a system

How the Parts Fit Together

Theme

•  Experimental Computational Cartography
•  Interface between the theoreticians and the computer
•  Design then implement algorithms and data structures
• efficiently
• on the largest (not toy sized!) datasets
• then
• observe results and
• suggest new research problems
• use general purpose data structures and algorithms,
• benefit from larger community effort
• like using Open Source Software instead of proprietary packages.
• Notable special-purpose failures: Lisp machines, floating point processors, database engines, special graphics engines, and most parallel machines.

Why Visibility?

• Terrain visibility determination is very important.
• ... but very compute intensive.
• Let`s make this more efficient
• ... by studying relative importance of various factors.
• Looking at real data is always surprising.

Applications

• Siting cellphone towers.
• Locating a forest clearcut to be invisible to tourists driving along a highway that is itself sited to give a good view.
• Military observers.

Terminology

• Viewshed: What specific points can an observer see?
• Visibility index: How many points can this observer see?

Sample terrain from South Korea, color-coded by elevation	Visibility indices of every point, colored similarly

• Confidence intervals:
1. Unshaded (): almost certainly visible.
2. Lightly shaded (): probably visible.
3. Darkly shaded (): probably hidden.
4. Black (): almost certainly hidden.



Unexpected observation: small relation of height to visibility



Siting Observers


Programs viewshed and vix may be used to find a set of observers that jointly can see every point as follows.

1. Use vix to list all the points by visibility index, and hence, to find the most visible point. Place the first observer, O₁, there.
2. Use viewshed to find the points that O₁ cannot see.
3. Filter the sorted list of points to delete points that O₁ can see.
4. Find the most visible point that O₁ cannot see; that is the second observer, O₂.
5. Repeat until the set of observers can see every point.

Visibility Design Details

• Use a raster terrain elevation database. Why?
  • Simpler
  • Approximate, but...
  • Exact visibility computation on a TIN is so slow, so approximation is needed here also.
• An observer: O.
• Radius of interest: R.
• Observer height above the terrain.
• Target height. Assumed to be a fixed distance above each point of the terrain.
• Viewshed: specific terrain within R of O that is visible from O.
• Visibility Index of O is the fraction of the disk of radius R centered on O that is visible from O.
  • Often computed for every point.
  • Perhaps we want just the most visible points.
  • Identifying them may be more important than calculating their exact visibility indices.
  • Statistical estimation: Choose T random targets within R of R, and counting the number visible.
• Visibility Map: an image representing the visibility index of each original point by a color.

Visibility Map is Compute-intensive

• Consider a 1201x1201 DEM with R=100. Ignoring edge effects, there are 3.14159 x 1201² 100² = 4.5e10 observer-target pairs.
• Question: What most affects the visibility map?
• The proper approach:Start with a formal model of terrain, and theoretically analyze it.
• No useful formal model of terrain exists.

Aside: Fractal `landscape` is not even `moonscape`

• Mandelbrot`s images are pretty, but are unreal to anyone who works with real data.
• The major force for landscape generation is water erosion, causing long-range drainage patterns.
• Also, terrain is scale-variant.
• Up and down are not equivalent.
• Many local maxima but few local minima (above sea level).
• Of course, if enough parameters are added, then any methodology can do anything quite well. Ptolemaic epicycles modeled planetary orbits fine.

Interim solution: test real data

• Korea

Korea

• 232x232 section of a level-1 DEM.
• Compute all 36 combinations of
  • R (radius of interest) =20,50, 100
  • H (observer and target ht) =20, 50, 100, and
  • T (number of random targets per R,H) =10, 30, 100, 300.
• Future: interactive website letting user compare.
• Now: every combo of R and H for T=300.

  R=20, H=20	R=20, H=50	R=20, H=100
  R=50, H=50	R=50, H=50	R=50, H=100
  R=100, H=100	R=100, H=50	R=100, H=100

Observations:

• H has little effect. That simplifies things.
• R has a large effect. E.g., the bottom central ================================================================

  Proposed Future Work

  Short Term

  • Multiple observers covering a region.
  • Fast graphics cards?
  • Test the largest DEM datasets available.
  • Study other serendipitous questions that will arise.

  Medium Term

  • Leverage from array operations tools, like Matlab?
  • Output sensitivity to input?
  • If visibility indices and viewsheds are sensitive to small input perturbations, then
  • Try to establish error bounds on the output.
  • Faster and less accurate output when input is inaccurate?
  • Feature recognition: feed into constrained TIN.

  Long Term

  1. Investigate the general question of the proper representation of terrain elevation data.
  2. If using TINs, use triangular splines, not just piecewise multilinear flat triangles.
  3. Consider the idea of a conceptually deeper representation, based on the geomorphological forces that created the terrain. Devise a basis set of operators, such as uplift, downcut, etc. Deduce the operators that created the particular terrain under consideration, and store them.
  4. Slightly differently, represent the terrain by the features that people would use to describe it. This idea is many decades old. Can we get it to work? The problem is that you can't just say that there is a hill over there, you have to specify the hill in considerable detail, which would seem to take more space than simply listing all the elevations with a grid or TIN.
  5. Extend to geological data structures. Plan excavation strategy for open pit mine.
  6. The major creative force for terrestrial terrain is water erosion. This does not apply to the moon, Venus, and, to the same extent, to Mars. Therefore those surfaces might be statistically different. What impact, if any, would this have on the speed and output distribution of our algorithms and data structures?

  How the Parts Fit Together

  
  

  ---