Patent Description:
Intervisibility analysis may be performed on a central processing unit (CPU) of a computer. The CPU may be programmed to radially traverse an altitude database and store results (visible, not visible) in an array. The array is then loaded into texture memory of a graphics processing unit for visual display.

However, intervisibility analysis is computationally intensive. Consequently, real time analysis is difficult to achieve, especially for threats located in dense terrain.

<NPL>) relates to a GPU Stream Computing Approach to Terrain database integrity monitoring and states in its abstract "Synthetic Vision Systems (SVS) provide an aircraft pilot with a virtual <NUM>-D image of surrounding terrain which is generated from a digital elevation model stored in an onboard database. SVS improves the pilot's situational awareness at night and in inclement weather, thus reducing the chance of accidents such as controlled flight into terrain. A terrain database integrity monitor is needed to verify the accuracy of the displayed image due to potential database and navigational system errors. Previous research has used existing aircraft sensors to compare the real terrain position with the predicted position. We propose an improvement to one of these models by leveraging the stream computing capabilities of commercial graphics hardware. "Brook for GPUs", a system for implementing stream computing applications on programmable graphics processors, is used to execute a streaming ray-casting algorithm that correctly simulates the beam characteristics of a radar altimeter during all phases of flight.

<CIT> in its abstract states "A system and method for efficient intervisibility determination. The intervisibility determination method of the present invention provides a multiple threat processing capability within a specified area of terrain using a common database. Computation is simplified through the method of processing data posts in the terrain elevation database. By taking integer steps and incrementing distance, x or y, and a predicted elevation value at each step, a small number of operations may be performed. Recomputing a change in elevation value may be reduced. An umbra database provides an enhanced look-up capability for displaying and updating the intervisibility display information. The systems and methods of the present invention may be suitable for use on a vehicle and in mission management activities.

According to another embodiment herein, a vehicle comprises a graphics processing unit having a plurality of shader units programmed to determine intervisibility of an object in an environment with respect to the vehicle.

The invention involves a method that includes supplying textures and location information to a graphics processing unit, the textures representing elevation data of obstructions in an environment, the location information indicating locations of an object in the environment and a reference point; and using a plurality of shader units of the graphics processing unit in parallel to process the texture to determine intervisibility between the object and the reference point. The obstructions may include terrain; and wherein the textures are accessed from a real time terrain database. The textures may be within a locus of the reference point. The method may further include using sensors to sense the location of the object in real time. The textures are processed to determine whether a line of sight between the reference point and the object is obstructed by the environment. The graphics processing unit outputs a composite texture indicating the line of sight. The reference point may corresponds to a weapons system; and wherein the line of sight is projected from the weapons system towards the object. The line of sight may be projected from the object towards the reference point. At least one of lethality and detection range of a weapons system is supplied to the graphics processing unit; and wherein at least one of lethality and detection range are represented in the line of sight. The method can also include visually displaying the composite texture, and updating the composite texture as the reference point moves across the environment. The reference point may correspond to a vehicle moving across the environment. The reference point may correspond to an airborne platform moving above the environment. The method may also include using the determination of intervisibility to perform at least one of collision avoidance, mission planning, dynamic route planning, situational awareness, search and rescue coverage analysis, optimal troop movement through a minimally visible path, and cell tower placement with maximal intervisibility, and road planning.

These features and functions may be achieved independently in various embodiments or may be combined in other embodiments. Further details of the embodiments can be seen with reference to the following description and drawings.

Reference is made to <FIG>, which illustrates a method of determining intervisibility between a reference point and an object in an environment. Intervisibility refers to mutually visible sight. The reference point may be within or outside the environment. The reference point may move across the environment as the method is being performed. The reference point may correspond, for example, to a person, a vehicle or component thereof, an Intelligence base, or an operations center.

The environment may include one or more objects. In a tactical environment, the object might be a target or it might be a friend or foe. To simplify the description of <FIG>, only a single reference point and a single object will be described.

The environment may contain natural and artificial obstructions, which can obstruct the line of sight between the reference point and the object. Natural obstructions may include fixed obstructions (e.g., mountains and other terrain) and transitory obstructions. Artificial obstructions may include be fixed obstructions (e.g., buildings) and transitory obstructions.

Intervisibility may be determined as follows. At block <NUM>, information about the environment within a locus of the reference point is accessed. In some embodiments, terrain and other fixed obstructions in the environment may have been previously scanned (e.g., during reconnaissance, mapping) and stored. Transitory obstructions may be determined from current sensor information. This information may be encoded as textures that can be processed by a graphics processing unit. Textures may include numerical values representing elevation data, such as elevation data of terrain and other obstructions. The textures may be stored in a real time terrain database, and textures within the locus of the reference point may be accessed from the real time terrain database.

Information about the reference point may be determined in real time. For example, if the reference point corresponds to an airborne platform, position and attitude about the airborne platform may be provided by onboard sensors (e.g., GPS) or remote sensors.

Also at block <NUM>, information about the object is accessed. The object information may include location and type of the object. This information may have already been determined (e.g., during reconnaissance, mapping) or it may be obtained in real time. Sensors (e.g., visible and infrared imaging devices, digital communications, RADAR, LADAR) may be used to reveal the position and altitude of the object in the environment. Image recognition software may be used to identify the type of object. The image recognition may also be used to identify the object as friend or foe.

At block <NUM>, the information about the environment, the object and the reference point are supplied to a graphics processing unit. The information about the environment may be supplied as textures.

At block <NUM>, ancillary information is supplied to the graphics processing unit. For example, if the object includes a weapons system or if the reference point corresponds to a vehicle armed with a weapons system, the ancillary information includes at least one of lethality and detection range of the weapons system. Other ancillary information may include colors for depiction of detection, lethality or hidden surfaces, and a minimum range with starting and ending angles.

At block <NUM>, a plurality of shader units of the graphics processing unit are used in parallel to determine intervisibility between the object and the reference point. The shader units are programmed to determine whether a line of sight between the reference point and the object is obstructed by the environment. An output of the graphics processing unit includes a composite texture indicating line of sight between the object and the reference point.

Ancillary additional information such as lethality and detection range of a weapons system are also supplied to the graphics processing unit, the shader units is programmed to compute intervisibility from the reference point (see <FIG>) or object (see <FIG>) to every point in the environment within a maximum of the lethality or detection range and classify it as lethality or detection. Color coding is applied to the composite texture based on lethality and detection range of the weapons system, whether the weapons system is hidden, etc. Examples of composite textures showing lethality and detection ranges are illustrated in <FIG> and <FIG>.

<FIG> shows composite texture <NUM> with respect to an aircraft <NUM> (reference point) flying over terrain (environment) <NUM>. The aircraft <NUM> is equipped with missiles having a known lethality and detection range. The composite texture <NUM> includes a wedge <NUM> of approximately <NUM> degrees. The wedge <NUM>, which projects outward from the aircraft <NUM>, represents a missile launch radii from the aircraft <NUM>. A minimum range is used to depict that the aircraft's pilot cannot see through the fuselage to the ground below; hence the distance from the aircraft <NUM> to the wedge <NUM>.

The wedge <NUM> is represented with minimum range, detection, lethality and hidden colors. The mid-gray region <NUM> within the wedge <NUM> represents the lethality range, and the light gray region <NUM> represents the detection range. The dark gray region <NUM> represents pixels that are obstructed by the terrain <NUM>. From the perspective of the aircraft <NUM> displayed below the wedge <NUM>, the shaded regions <NUM>-<NUM> are what the pilot can see at the current aircraft location and attitude.

<FIG> shows a composite texture <NUM> representing a ground threat (object) <NUM> with respect to an aircraft (not shown). An outer circle <NUM> represents detection range of a ground-based weapons system, and the inner circle <NUM> represents lethality of the weapons system. In some embodiments, the graphics processing unit could use coloration of the circles <NUM> and <NUM> and shading <NUM> within to represent threats. For example, yellow coloration may indicate the threat as a warning, orange coloration may indicate that the aircraft has penetrated the detection range of the threat, and red coloration may indicate the aircraft has penetrated the lethality range of the threat.

Reference is once again made to <FIG>. At block <NUM>, the composite intervisibility texture is communicated to a user. For example, the composite texture <NUM> of <FIG> may be visually displayed to an operator of the aircraft. By visually identifying a threat that the operator can see with respect to the terrain, the composite texture <NUM> provides real time situational awareness.

As the reference point moves across the environment, the graphics processing unit updates the composite texture by returning control to block <NUM>. The composite texture may be updated as frequently as needed. For example, if the composite texture is being displayed on a monitor having a refresh rate of <NUM>, the composite texture may be updated at a rate of <NUM>. More generally, the refresh rate of the composite texture may be a function of GPU performance, memory bandwidth, and the number of available shader units in the graphics processing unit.

In practice, more than one object may be in the environment. The method of <FIG> may be used to determine intervisibility between the reference point and each object, and represent each line of sight in the composite texture.

At block <NUM>, an action may be taken in response to the composite texture. For an airborne platform, an operator may take evasive action.

Other possible actions include collision avoidance, mission (tactical) planning, situational awareness, dynamic route planning, and search and rescue coverage. Still other possible actions include, without limitation, police surveillance, optimal troop movement through a minimally visible path, cell tower placement with maximal intervisibility, and road planning.

Reference is made to <FIG>, which illustrates an example of a system <NUM> for determining intervisibility between a reference point and an object in an environment. The system <NUM> includes a central processing unit (CPU) <NUM> and at least one graphics processing unit (GPU) <NUM>. The CPU <NUM> may be programmed to receive sensor data about the reference point and the object and retrieve textures representing the environment within a locus of the reference point. The CPU <NUM> is further programmed to supply some or all of the following inputs to the GPU <NUM>: (<NUM>) textures; (<NUM>) reference point location (e.g., position, altitude and orientation); (<NUM>) object locations (e.g., position and elevation); (<NUM>) detection and/or lethality ranges of the objects; and (<NUM>) ancillary data, such as colors for depiction of detection, lethality, and hidden surfaces.

Each GPU <NUM> may have a number N of multiprocessors, each of which executes in parallel with the others. Each multiprocessor may have a group of M stream processors or cores. Thus, the GPU <NUM> may have a total of NxM cores that can be executed in parallel.

Each core is assigned a group of pixels. These NxM cores enable the GPU <NUM> to process independent vertices and fragments in parallel.

The GPU <NUM> outputs a composite texture. The composite texture may be visually displayed on a monitor <NUM>.

General-purpose computing on graphics processing units (GPGPU) enables the GPU <NUM> to perform computations that would otherwise be handled by the CPU <NUM>. The GPU <NUM> may be programmed with a shader program <NUM> to that causes the shader units to execute an intervisibility algorithm. A shader program in general is an executable set of instructions written in a high level programming language that is loaded on a GPU and executes on vertex and texture data sent to the GPU for visualization and computation. The shader units may also be programmed to compute color and other attributes of each pixel.

Additional reference is made to <FIG>, which illustrates an example of a shader program for determining intervisibility between a reference point and an object in an environment. At block <NUM>, an area between the reference point and the object is computed. For example, the area may include a wedge extending from the reference point towards the object. The wedge may be defined by a distance and arc limits with respect to the reference point.

At block <NUM>, locations of fragments are identified. Each core will process a fragment. As part of block <NUM>, offsets into the input textures are derived for the reference point and the fragments. These offsets enable elevation at a point to be determined. Distance between points on the elevation texture may also be determined at block <NUM>.

Each fragment is iterated by the GPU <NUM> to calculate intervisibility over the entire area. The processing of a fragment includes computing an angle in the z-axis from the reference point to the fragment location (block <NUM>), and iterating incrementally from the reference point to the fragment location, calculating a slope from the reference point to each iterated location (block <NUM>). Slope may be calculated, for instance, as the arc-tangent of the change in elevation divided by the distance. If the slope of each iteration is greater than the angle, then the fragment is classified as visible; otherwise, it is classified as not visible (block <NUM>).

Classification of lethality and detection may be performed (block <NUM>) by calculating the distance from the reference point to the fragment. If the distance is within the lethality range and visible, the fragment is colored with the lethality color. If the distance is within the detection range and visible, the detection color is used.

The system <NUM> may be implemented in one or more computers having a CPU <NUM> and at least one GPU <NUM>. Multiple graphics cards in one computer, or large numbers of graphics chips, further parallelizes the processing. The computer(s) may be at the reference point or at a remote location.

The system <NUM> unloads the processing burden from the CPU <NUM> onto the shader units of the GPU <NUM>. By tapping the parallel processing power of the GPU <NUM>, intervisibility analysis can be performed in real time. The system is especially useful for analyzing intervisibility of reference points that correspond to fast-moving vehicles such as airborne platforms traveling over dense terrain.

Claim 1:
A method comprising:
supplying to a graphics processing unit, information about an environment as textures representing elevation data of obstructions in the environment, the obstructions including terrain, wherein the textures are accessed from a real time terrain database;
supplying to the graphics processing unit location information comprising object position and object altitude of an object in the environment, and reference point position, reference point altitude and reference point orientation of a reference point, the reference point corresponding to a vehicle moving across the environment or an airborne platform moving above the environment;
using a plurality of shader units of the graphics processing unit in parallel to process the textures to determine in real time intervisibility between the object and the reference point, intervisibility comprising whether a line of sight between the reference point and the object is obstructed by the environment;
outputting by the graphics processing unit a composite intervisibility texture to a user indicating the line of sight; and
updating by the graphics processing unit the outputted composite intervisibility texture when the reference point moves across the environment;
wherein the object includes a weapons system or the reference point corresponds to a vehicle armed with a weapons system; and wherein
ancillary information is further supplied to the graphics processing unit, the ancillary information including at least one of lethality and detection range of the weapons system, wherein
the shader units are further programmed to compute intervisibility from the reference point or object to every point in the environment within the maximum of the lethality or detection range and classify it as lethality or detection and wherein
color coding is applied to the composite texture based on lethality and detection range of the weapons system and whether the weapons system is hidden.