Digital visual and sensor simulation system for generating realistic scenes

• US 5,317,689 A
• Filed: 08/10/1990
• Issued: 05/31/1994
• Est. Priority Date: 09/11/1986
• Status: Expired due to Fees

• Current Assignee: L-3 Communications Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: Yang, Chao, McMillen, Robert J., Rosman, Andrew, Landis, Gary N., Nack, Myron L., Ellis, Thomas O., Moise, Norton L.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/565,864
• Time in Patent Office: 1,390 Days
• Field of Search: 364/521, 364/518, 364/522, 364/162, 364/163, 364/164, 364/165, 340/747, 340/750, 340/798, 340/799, 345/127, 345/131
• US Class Current: 345/505
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G09B 9/301 by computer-processed or -generated image

Abstract

A system using a ray-tracing algorithm and a hierarchy of volume elements (called voxels) to process only the visible surfaces in a field of view. In this arrangement, a dense, three-dimensional voxel data base is developed from the objects, their shadows and other features recorded, for example, in two-dimensional aerial photography. The rays are grouped into subimages and the subimages are executed as parallel tasks on a multiple instruction stream and multiple data stream computer (MIMD). The use of a three-dimensional voxel data base formed by combining three-dimensional digital terrain elevation data with two-dimensional plan view and oblique view aerial photography permits the development of a realistic and cost-effective data base. Hidden surfaces are not processed. By processing only visible surfaces, displays can now be produced depicting the nap-of-the-earth as seen in low flight of aircraft or as viewed from ground vehicles. The approach employed here is a highly-parallel data processing system solution to the nap-of-the-earth flight simulation through a high level of detail data base. The components of the system are the display algorithm and data structure, the software which implements the algorithm and data structure and creates the data base, and the hardware which executes the software. The algorithm processes only visible surfaces so that the occulting overload management problem is eliminated at the design level. The algorithm decomposes the image into subimages and processes the subimages independently.

Claims

1. A parallel processing computer image generation system for generating encoded image signals representing a scene as viewed by the human eye or sensors on a moving vehicle, comprising:

a plurality of subimage data processing devices for independently computing different images of terrain, static objects on the terrain and the sky;

object data processing devices for computing images of dynamic objects, points, lines, targets and special effects such as dynamic sea and dynamic atmospheric effects;

an image data processing device that generates the encoded image signals representing said scene;

means coupling said subimage data processing devices and said object data processing devices in parallel to supply image signal data to said image data processing device for simultaneous processing thereby to generate said encoded image signals representing said scene;

data sources coupled to said subimage data processing devices and to said object data processing devices to supply image data for processing; and

means for controlling coupled to said subimage data processing devices, to said object data processing devices and to said data sources for said subimage and object data processing devices for;

(a) decomposing the scene into a plurality of different subimages, corresponding to the plurality of subimage data processing devices, each subimage comprising a rectangular array of adjacent pixels;

(b) controlling said subimage data processing devices and object data processing devices with respect to current image data; and

(c) controlling said data sources for said subimage data processing devices with respect to image data which will be next needed for image generation.

2. The system according to claim 1 in which said data sources comprise:

object memories for said object data processing devices;

global physical memories coupled to said subimage data processing devices, containing subsets of data base needed for current image data processing;

global virtual memories containing at least a large terrain data base; and

interconnection networks coupling said global virtual memories to said global physical memories to supply data thereto.

3. The system of claim 1 in which said means for controlling comprises:

a motion computation system for producing current and predicted indications of vehicle positions and attitudes; and

means for coupling said motion computation system to said subimage data processing devices and said object data processing devices for providing control with respect to current image data and for coupling said motion computation system to provide control with respect to data which will be next needed for image processing and display.

4. A parallel processing computer image generation system for generating encoded image signals representing a scene as viewed by the human eye or sensors on a moving vehicle, comprising:

a plurality of subimage data processing devices for independently computing different images of terrain, static objects on the terrain and the sky;

object data processing devices for computing images of dynamic objects, points, lines, targets and special effects such as dynamic sea and dynamic atmospheric effects;

an image data processing device that generates the encoded image signals representing said scene;

means coupling said subimage data processing devices and said object data processing devices in parallel to supply image signal data to said image data processing device for simultaneous processing thereby to generate said encoded image signals representing said scene;

object memories coupled to said object data processing devices to supply image signal data thereto;

global physical memories coupled to said subimage data processing devices to supply current image signal data thereto;

global virtual memories containing at least a large terrain data base;

interconnection networks coupling said global virtual memories to said global physical memories; and

means for controlling coupled to said subimage data processing devices, to said object data processing devices and to said global virtual memories for;

(a) decomposing the scene into a plurality of different subimages, corresponding to the plurality of subimage data processing devices, each subimage comprising a rectangular array of adjacent pixels;

(b) controlling said subimage data processing devices and object data processing devices with respect to current image data; and

(c) controlling said global virtual memories with respect to image data which will be next needed for image generation.

5. The system according to claim 4 in which said means for controlling comprises:

a motion computation system for producing current and predicted indications of vehicle positions and attitudes; and

means for coupling said motion computation system to said subimage data processing devices and to said object data processing devices for providing control with respect to current image data and for coupling said motion computation system to said global virtual memories for providing control with respect to data which will be next needed for image generation.

6. A computer image generation system for generating encoded image signals representing a selected scene, comprising:

storage means providing a three-dimensional surface data base of discrete volume elements individually representative of different subimages of said scene;

means for accessing said data base for retrieving the data of all of the subimages comprising said selected scene;

a plurality of processors, each for processing data using a three dimensional visible surface technique with ray tracing for a corresponding subimage of said selected scene independently and in parallel with other subimages of said selected scene; and

image generation means coupled to said means for processing the data for simultaneously processing the data for all of said subimages to generate encoded image signals representing said selected scene.

7. A computer image generation system for generating encoded image signals representing a selected scene, comprising:

storage means for providing a three-dimensional surface data base of discrete volume elements individually representative of a different subimage of said scene, a separate software task being created for each subimage, the code or logic in each task being identical but the input parameters for each subimage vary whereby the data processed from said data base varies with each task;

means for each software task for accessing said data base in accordance with said input parameters for each subimage for retrieving the data of all of the subimages comprising said selected scene;

a plurality of processors, each processor for processing data using a three-dimensional visible surface technique with ray tracing for a corresponding subimage of said selected scene independently and in parallel with other subimages of said selected scene; and

image generation means coupled to said means for simultaneously processing the data for all of said subimages for generating encoded image signals representing said selected scene.

8. The system according to claim 7 in which said three dimensional data base comprises data base structures of volume elements of differing resolutions providing a hierarchical resolution data structure.

9. The system according to claim 8 in which a data base of high resolution is embeded in a data base of lesser resolution.

10. A three dimensional visible surface computer image generation system for generating encoded signals representing a selected scene, comprising:

storage means comprising a three-dimensional surface data base of discrete volume elements individually representative of different subimages of said scene, each volume having a location of said data base corresponding to the X, Y address in the plane of that portion of the scene represented by the volume element and being accessed by first and second step position vector components into said data base respectively representative of the X and Y values of said address, and a third step position vector components which is compared with elevation data stored in said data base in association with that address, stopping terminating when said third step position vector component is less than or equal to said elevation data;

means for accessing volume elements of said data base for retrieving the data of the subimages comprising said selected scene;

means for processing the data using a three-dimensional visible surface technique with ray tracing for each subimage of said selected scene independently and in parallel with other images of said selected scene; and

image generation means coupled to said means for simultaneously processing the data for all of said subimages for generating encoded image signals representing said selected scene.

11. The system according to claim 10 in which said data base comprises a hierarchy of resolutions.

12. The system according to claim 10 in which said data base comprises a hierarchy of resolutions and maximum values of elevation data are stored at lesser elevation resolution values than the X, Y address values in each hierarchy of resolutions and stepping continues at low resolution values when said third step position vector component is above the low resolution value of said elevation data.

13. The system according to claim 12 in which stepping at the next higher resolution takes place only when said third step position vector component is less than or equal to the low resolution value of said elevation data.

14. The system according to claim 10 in which said selected image is decomposed into vertical scan lines and said data base is accessed for all elevation data associated with each volume element.

15. The system according to claim 10 in which said image is decomposed into a grid of square subimages each of which is decomposed into a sequence of concentric square annuli and said data base is accessed beginning with that portion representing the outermost square annulus and sequentially progressing in said data base to that portion representing the innermost square annulus.

16. In a computer image generation system, the method for generating encoded image signals representing a three dimensional image of a selected scene, comprising:

developing a data base of groups of signal states, each group of signal states forming a data base volume element the signal states of which represent a surface three-dimensional subimage of said scene, each volume element having a location of said data base identified with the grid point location of the subimage of the scene represented by that volume element;

accessing said volume elements in said data base in steps corresponding to simultaneous steps along individual rays from a viewing point projected into said scene;

processing the data using a plurality of processors, each processor using a three-dimensional visible surface technique with ray tracing from each accessed volume element for a corresponding subimage of said selected scene independently and in parallel with the data for other subimages of said selected scene; and

thereafter simultaneously processing the data for all of said subimages for generating said encoded image signals.

17. In a computer image generating system the method of storing and accessing information in a computer data base, comprising:

providing a data base having a hierarchy of data resolutions, high, medium and low data resolutions;

storing the average of high data resolution at data base locations of medium data resolution;

storing the average of medium data resolution at data base locations of low data resolution; and

accessing said data base locations beginning with locations of low data resolutions and accessing locations of higher resolution if the viewing range is less than certain precomputed threshold ranges.

18. In a computer image generating system the method for generating encoded image signals in real-time and non real-time representing a selected scene, comprising:

providing data bases of discrete volume elements individually representative of a different subimage of said scene;

providing a separate task for each subimage in which the logic for each task is identical;

employing different input parameters for each task for accessing data from said data bases which varies with each task;

executing said tasks and processing the data in a highly parallel mode to provide a high throughput of data for a real-time image; and

executing said tasks and processing the data in a less parallel mode to provide a lesser data throughput for non-real time images.