Conventional intervisibility determination algorithms traverse the line of sight from one endpoint to the other, checking intervening polygons (or their edges) for intersection with the line of sight. We present an intervisibility algorithm based on a completely different approach. Consider a minimal axis-parallel bounding box for the line of sight; the box is called the sieve. The algorithm is based on the insight that only those polygons that overlap the sieve along all three coordinate axes can possibly block the line of sight. A direct access data structure known as a "bucket list" is used to efficiently select the polygons with projections along the coordinate axes that overlap those of the sieve. Only those polygons need be tested for intersection with the line of sight.
Our performance experiment with an initial implementation of the sieve
algorithm, conducted using the ModSAF Computer Generated Forces system,
found that it was measurably faster that that system's current
intervisibility algorithm, but required more memory. We expect to
improve both speed and memory requirements in future versions. For more
information, see: Petty, M. D. and Mukherjee, A. (1997). "The Sieve
Overlap Algorithm for Intervisibility Determination", Proceedings of the
1997 Spring Simulation Interoperability Workshop, Orlando FL, March 3-7
1997.
To select locations for the individual entities of the unit within that
unit's position, the terrain geometry must be considered in terms of
cover, concealment, and intervisibility. The field of fire for an
entity is the terrain area that is visible and within effective weapon
range from that entity's location. Define a unit's fire zone as the
terrain area a unit is assigned to defend by coverage with direct fire
from its entities. The task is to find a set of locations for the
individual entities of the unit that maximizes the cumulative inclusion
of portions of the unit's fire zone within its entities' fields of fire
without excessive exposure of the unit's entities to enemy fire from
within the fire zone.
Our algorithm for this task has four steps:
We will compare the performance of this algorithm with an existing CGF
algorithm as well as human subject matter experts performing the same
task.
HLA Data Distribution
The High Level Architecture (HLA) is a standard for constructing
distributed simulations. The Data Distribution component of HLA reduces
the amount of data delivered to a simulation by allowing communications
connections to be based on simulations' expressions of data production
and requirements. At the core of determining which connections to make
is a geometric problem: finding the dynamic intersection of
d-dimensional rectilinear hyperrectangles in d-space. Four different
algorithms for solving that problem, including a new one developed
through application of theoretical results from computational geometry,
are being compared in an experiment designed to reveal how well they
perform in the specific context of the data distribution application.
Both intersection performance and connectivity efficiency results are
being analyzed.
Fire Zone Defense
A military unit (platoon, company, or battalion) that is being generated
by a Computer Generated Forces (CGF) system will consist of some number
of entities (typically 3 to 40). A useful CGF capability would be to be
able to order that unit to take up a defensive position and have a
terrain reasoning algorithm within the CGF system determine optimum
locations for each of the individual entities of that unit. The CGF
system could then move the entities to the selected locations.