Browse Prior Art Database

Three-Dimensional Intervisibility Algorithm

IP.com Disclosure Number: IPCOM000120987D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 6 page(s) / 259K

Publishing Venue

IBM

Related People

Glickstein, IS: AUTHOR [+2]

Abstract

This article describes an algorithm which determines visibility of each cell in a three-dimensional (3-D) problem space from one or more observation points. Given a 3-D digital terrain map and multiple above ground level (AGL) sheets at specified heights above the terrain, the algorithm determines the visibility of each grid cell on each AGL sheet from each of a number of observation points (OPs). Each OP is located in the problem space, at a given map cell, at a given mean sea level (MSL) altitude, and has a given maximum visibility distance. This algorithm determines the visibility - true or false - from each observation point to each cell in each AGL sheet. This is done iteratively, by passing precomputed messages to adjacent cells.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 33% of the total text.

Three-Dimensional Intervisibility Algorithm

      This article describes an algorithm which determines
visibility of each cell in a three-dimensional (3-D) problem space
from one or more observation points.  Given a 3-D digital terrain map
and multiple above ground level (AGL) sheets at specified heights
above the terrain, the algorithm determines the visibility of each
grid cell on each AGL sheet from each of a number of observation
points (OPs). Each OP is located in the problem space, at a given map
cell, at a given mean sea level (MSL) altitude, and has a given
maximum visibility distance. This algorithm determines the visibility
- true or false - from each observation point to each cell in each
AGL sheet.  This is done iteratively, by passing precomputed messages
to adjacent cells.

      A fundamental concept of this algorithm is that information is
exchanged between map/grid cells.  We have termed this information
exchange "message passing."  It is inherently a parallel concept, and
for a parallel processing implementation each map cell is represented
by a processor. Saying that a message is sent from map cell i to map
cell j means that the processor representing cell i generates an
output which is received as an input by the processor representing
cell j.  In a serial implementation map/grid cells are represented as
array elements.  In this case saying that a message is sent from map
cell i to map cell j means that the value of the array element
representing cell i is used to alter the value of the array element
representing cell j.

      The message passing (MP) array models the line-of-sight
geometry based on an a priori knowledge of which cells can
potentially block the visibility between a given observation point
and any other cell on the map.  This geometric relationship data is
unique for a single octant, and the other 7 octants are easily mapped
onto this reference octant via symmetry.  Fig. 1 is a graphic
representation of the relationship between (a) the original map, (b)
the reference octant, and (c) the MP array.

      Consider map cell 75 which is along the line-of-sight (LOS)
illustrated in Fig. 1(a).  If the octant containing this LOS is
mapped onto octant 1 using symmetry operations - in this case by
substituting -y for y - cell 75 can now be treated as the cell which
is 2 cells up and 1 cell over from the OP (Fig. 1(b)).  In the
MP array cell 75 appears 3 times because it is along lines-of-sight
from the OP to cells 132, 133, and 134 (Fig. 1(c)).  In a similar
way, the MP array provides a complete representation of all possible
lines-of-sight.

      The values in the MP array are determined before the algorithm
begins.  This is accomplished as follows:
 1.  Each element in the bottom row of MP receives data which
points/refers to the element at octant 1, row 1, column 1 (cell 46,
in this example, which contains the OP)
      2.  All elements in the first half of MP row 2 rece...