Line-of-sight problem

The basic principle of visibility computation is based on the line-of-sight (LOS) problem. The problem of determining the LOS between a viewpoint V and an observed point P is illustrated in the next figure. Note that the viewpoint is raised by a height hV, which relates to the height of an observer or a watchtower. The profile between V and P needs to be tested for obstructions, which might break the LOS.

The LOS is broken:

if either any point between V and P has a vertical viewing angle $γ_{i}$ which is larger than the vertical angle $γ_{LOS}$ of the LOS.
or if the height HLOS of the LOS at any point is lower than the elevation Hi of that point.

The line-of-sight (LOS) problem.

Algorithms to solve the LOS problem (LOS checks) depend on the data structure used to represent the DTM. While the basic principle of visibility is valid in any case, an implicit spatial order, as it is inherent for gridded DTM’s, greatly simplifies the determination of visibility.

Line-of-sight check for grids

A line-of-sight check requires a terrain profile between a viewpoint and a target point. An LOS check is performed for each new vertex inferred. The computation can be terminated as soon as an LOS blockage is found or the target point is reached. For a viewshed analysis the LOS between the viewpoint and each other point has to be tested and is therefore quite demanding. There are examples for a line-of-sight and an entire viewshed in the next two figures.

Line-of-sight through a grid. a) View from above. b) Profile view. Red sections are invisible, blue sections are visible from the viewpoint in the southwest. (Swisstopo 1991)

Viewshed from one observer point in the center of the map. (Swisstopo 1991)

Line-of-sight check for TIN’s

The solution of the visibility problem for TIN’s is substantially more complex than for grids because of two facts:

An implicit spatial order is not established in TIN’s. Thus, any LOS calculation involves a fair amount of TIN traversal.
In contrast to grids, TIN’s are made up of irregular facets of different size and shape. While in the case of grids, it is considered sufficient to sample the visibility by checking the visibility of individual grid cells, each TIN facet needs to be checked whether it is fully, partially, or not at all visible from the viewpoint in order to obtain a complete solution.

In principle, any so-called object-space hidden surface algorithm, see Sutherland et al. (1974) and Foley et al. (1992), which is used to determine the visible parts of arbitrary 3-D objects, could be applied to extract visibility regions on a TIN. However, as TIN’s represent more specific structures (they are 2.5-D, and facets are restricted to triangles), simpler algorithms can be designed based on heuristics. For instance, backface culling (see below) significantly reduces the number of triangles that have to be tested for visibility, which is quite an effort. Such heuristics are particularly useful if the number of visibility analyses required is very big, e.g. if moving viewpoints occur.

Backface culling

As visibility computations in TIN’s are very demanding, clever algorithms try to somehow reduce the amount of work to be done. Backface culling accelerates visibility analyses by making use of the following logical implication:

Any triangle facing away from the viewer can immediately be rejected as invisible.

Triangles facing away can be found by calculating the normal vector for each TIN facet on the profile along the line-of-sight (figure below). If the angle between the normal and the vector to the viewpoint is larger than 90° it is certain that the facet is invisible (figure below b)).

Triangles facing away from the sun (b)) don’t have to be tested for visibility.

Depending on the position of the viewpoint and on the terrain type, it is not uncommon that the number of triangles, which must further be checked (figure above a)) is reduced by 50 per cent. An algorithm based on such heuristics has been presented by De Floriani et al. (1986).