FIELD OF THE INVENTION

This invention generally relates to a system and technique for the generation of images on a display device, and more particularly to real-time computer simulation of visual images of perspective scenes such as landscapes and seascapes.

BACKGROUND OF THE INVENTION

The principle application area for computer image generation (CIG) has been that of visual training simulators which present scenes to an observer or trainee to allow the observer to practice some task, such as flying an airplane. In a flight simulator, a three-dimensional model of the desired "gaming area" is prepared and stored on magnetic disk or similar bulk storage media. This model is called the visual data base. The visual simulator combines an image generator with an electro-optical display system such as a cathode ray tube (CRT) or similar display. The image generator reads in blocks of three-dimensional data from the disk and transforms this data into two-dimensional scene descriptions. The two-dimensional data are converted to analog video that is presented to the operator or trainee via the display. The generated imagery is meant to be representative of the true scenes that the operator would see if the operator were actually performing the task being simulated. The generation of the display images is said to be in "real time" which is normally taken to mean 30 frames per second, as in the U.S. television standard. CIG systems are described in detail in the book entitled Computer Image Generation edited by Bruce J. Schacter and published by Wiley-Interscience (1983).

Computer generation of visual representations of objects whose various vertices, edges and planes are defined by data bases referenced to a system of axes is described in U.S. Pat. Nos. 3,602,702 to Warnock, 3,621,214 to Romney et al., and 3,665,408 to Erdahl et al. These teach general means for converting such data into a two-dimensional perspective view, with tests for determining which of several overlapping objects will be visible and conceal the others. The scan employed for presentation of the visual image on a cathode-ray tube (CRT) is a conventional horizontally scanned raster. U.S. Pat. No. 3,671,729 to Lux teaches means to cause a mechanical plotter to draw curves or profiles (provided as electrical input signals giving elevation and range for successive radial scans) in which the profile parts which would be out of the field of view of an elevated observer are omitted. The device is not indicated as having any application to electronic image generation, nor does it appear that it could be so applied. U.S. Pat. No. 3,736,564 to Watkins teaches the conversion of electrical signals defining surfaces of a three-dimensional object onto a two-dimensional image or view plane defined by a raster scan device such as a CRT. The converted signals defining the surfaces to be displayed are determined by comparing the relative depths of segments of the surfaces along each scan line of the display and selectively subdividing the scan lines according to the visual characteristics of the segments when necessary. Signals defining the visible segments are then utilized to control the intensity of the display.

The real-time computer generation of visual images of landscapes and seascapes find particular use in aircraft or ship simulators. U.S. Pat. No. 3,769,442 to Heartz et al. describes a process for producing a compressed data base for a radar land mass simulator. U.S. Pat. No. 4,017,985 to Heartz describes a process for the generation of a perspective scene in which the tangent of the view angle is computed for each range element along a sweep. This process requires a high speed multiply and divide to compute the tangent which is then compared to a stored maximum to determine if the element is seen. If it is seen, it is compared to the last value to fill in skipped pixels. U.S. Pat. No. 4,343,037 to Bolton describes a visual display system in which a pipeline processor is used to compute in real-time the perspective transformation from the textured ground surface plane to the display plane. Application Ser. No. 527,809 filed Aug. 30, 1983, by M. Bunker et al. and assigned to the assignee of this application discloses techniques to reduce dynamic aliasing problems in real time images generated from a textured grid data base. These techniques may be applied to the invention disclosed herein in order to refine the images produced.

Real-time generation of visual scenes is at best a difficult computational problem. The more realistic the scene, the more complex the computational problem seems to become. This in turn imposes a severe requirement on the hardware design. What is needed is a technique for simplifying the computations required for the real-time generation of visual displays without sacrifice of realism to the displayed scene.

SUMMARY OF THE INVENTION

It is therefore an object of the present invention to provide a unique computer generated real-time display wherein the hardware requirements are greatly simplified.

It is another object of the invention to provide an algorithm for the real-time computer generation of visual scenes that uses a few simple mathematical functions resulting in a significant speed-up of scene generation time.

The objects of the invention are accomplished by a process that replaces the multiply and divide operations normally performed with simple, repetitive accumulate operations. Seen elements and pixel fill-in are implemented by a single compare. The range elements of the sweep are scanned by progressively incrementing a delta view angle tangent. Occulting is determined by comparing the projection on the Z axis of delta view angle tangent at the element range to the altitude minus element elevation. If the projection is greater than altitude minus element elevation, the point is seen and the delta tangent view angle is incremented. Otherwise, the point is hidden and the range element is incremented. The invention uses an X-Y grid data base as opposed to vector schemes used in the prior art. Since only simple addition operations performed with an accumulator and a compare operation are used, the mathematical processing is greatly simplified in contrast with the multiplication and division operations resorted to by the prior art. This approach, when implemented as a software or firmware program, significantly speeds up scene generation time. When implemented in hardware, the amount of hardware required for real-time scene generation is significantly reduced. In fact, the simplicity of the hardware implementation lends itself to current gate array devices which would significantly reduce hardware requirements.

BRIEF DESCRIPTION OF THE DRAWINGS

The objects, advantages, and other aspects of the invention will be better understood from the following detailed description of the invention together with the drawings, in which:

FIG. 1 is a diagramatic illustration of a 512.times.512 element CRT display wherein the number of elements corresponds to the grid data base;

FIG. 2 is a graphical representation of the horizontal sweeps from the view point;

FIG. 3 is a graphical representation of the vertical sweeps from the view point;

FIG. 4 is a graphical illustration of the view ray processing according to the invention;

FIG. 5 is a block diagram of a direct hardware implementation of the inventive view ray processing technique;

FIG. 6 is a block diagram of a simplified hardware implementation of the invention which takes advantage of certain redundancies inherent in the FIG. 5 implementation; and

FIG. 7 is a simplified flow diagram of a software or firmware implementation of the view ray processing technique according to the invention.

DETAILED DESCRIPTION OF THE INVENTION

Terrain occulting, that is what is hidden from a specific viewpoint, is a key calculation to all image generators. The invention provides a fast summation algorithm for generating occult data or perspective scenes using grid elevation data bases. Such grid data bases are produced, for example, by the Defense Mapping Agency (DMA). A DMA terrain elevation data base is typically a 512.times.512 array of elevation posts that are 300 feet apart. A corresponding planimetric grid data base defines feature colors such as for lakes, forests, snow caps, fields and so forth. The ray processing technique according to the invention is best illustrated by reference to FIGS. 1, 2, 3 and 4. First, a vertical column of the output image, i.e. a vertical raster, is defined as a sweep which is composed of 512 view ray elements, as shown in FIG. 1. The horizontal field of view (FOV) is defined as plus and minus 256 sweeps which are defined by equal increments perpendicular to the boresight. Any sweep is transformed to the grid data base as shown in FIG. 2. The processing starts incrementing .DELTA.R from the view point. .DELTA.R is shown as equal steps, but in practice, the .DELTA.R steps are expanded as they move away from the view point. For any sweep, a .DELTA.X and .DELTA.Y can be defined. The accumulation of .DELTA.X and .DELTA.Y is the X,Y data base address which is used to extract the elevation and color for that sweep element.

For a given sweep, the vertical view rays are shown in FIG. 3. Again, the field of view is defined as plus or minus 256 equal steps normal to the view ray. The view ray processing is illustrated in FIG. 4. For each range increment, the view ray steps down by an increment of .DELTA.RTan.phi..sub.min. A simple compare at each range increment determines if the view ray strikes an elevation post. If the view ray is above the elevation post, the next elevation post and color is read from the data base. If the view strikes the post, the color for that post is read to the CRT display via a refresh memory.

Considering FIG. 4 in more detail, the edge of the vertical field of view is .phi..sub.min. The first view ray projection (point 1) on the Z axis is .DELTA.R Tan .phi..sub.min. Since .DELTA.R Tan .phi..sub.min is less than (h-Z.sub.1), Z.sub.1 does not intersect the field of view, and therefore we increment to the next elevation, Z.sub.2. The projection of the view ray at Z.sub.2 is 2.DELTA.R Tan .phi..sub.min. This is greater than (h-Z.sub.2) which means that Z.sub.2 is seen. The tangent of the view angle is incremented to point 3 and, again, Z.sub.2 is seen. The tangent of the view angle is incremented until its projection on the Z axis is greater than (h-Z.sub.2), then we increment to the next elevation point and so forth. It is therefore evident that if a view ray strikes an elevation post, that point is seen and remains seen until the view ray is incremented to a point above the elevation post. If a view ray is above an elevation post, then the point is occulted.

The following equation is the view ray projection, Z'.sub.nm, of the n.sup.th range increment and the m.sup.th increment in the view angle tangent:

Z'.sub.nm =n.DELTA.R(Tan .phi..sub.min -m.DELTA. Tan .phi.)

Incrementing the tangent of the view angle results in the following equation:

Z'.sub.n(m+1) =n.DELTA.R(Tan .phi..sub.min -(m+1).DELTA. Tan .phi.)

Note that this equation can be expressed as the previous equation value plus an increment as follows: ##EQU1## Similarly, if range is incremented, the following equation results:

Z'.sub.(n+1)m =(n+1).DELTA.R(Tan .phi..sub.min -m.DELTA. Tan .phi.)

This equation can also be expressed as the first equation value plus an increment as follows: ##EQU2##

FIG. 5 is a block diagram of a pipeline implementation of the occult algorithm according to the invention. As will be observed, this implementation is a simple gate array of registers and accumulators. Register 10 supplies a value corresponding to .DELTA.R.DELTA. Tan .phi.to adder 12 and subtractor 14. The output of adder 12 is stored in register 16 which accumulates a value corresponding to n.DELTA.R.DELTA. Tan .phi. which is the increment value resulting in incrementing the tangent of the view angle. The output of subtractor 14 is stored in register 18 which accumulates a value corresponding to .DELTA.R Tan .phi..sub.min -m.DELTA.R.DELTA. Tan .phi. which is the increment value resulting in incrementing the range. Note that register 18 is preloaded with a value corresponding to .DELTA. R Tan .phi..sub.min. Whether the tangent of the view angle or the range is incremented is controlled by gates 20 and 22. Gate 20, when enabled, couples the output of register 16 to the other input of adder 12. Similarly, gate 22, when enabled, couples the output of register 18 to the other input of subtractor 14. Those skilled in the art will understand that register 16 in combination with adder 12 constitute an accumulator and register 18 in combination with subtractor 14 constitute another accumulator.

In the pipeline implementation shown in FIG. 5, there is another accumulator constituted by the register 24 and the subtractor 26. The register 24 is preloaded with the value of h, the elevation of the view point. The output of register 24 is supplied to one input of subtractor 26 while the other input is supplied from either register 16 or register 18 via gates 28 or 30, respectively, depending on whether the range or the tangent of the view angle is incremented. The output of this accumulator is the output of subtractor 26 which is stored in register 24 and supplied to input A of comparator 32. Input B of the comparator 32 is supplied from the Z grid data base 34. This data base like the I or intensity data base 36 is addressed by the X,Y coordinates of the sweep. The output of the I data base 36 is supplied to the CRT refresh memory. The data bases 34 and 36 are gated depending on whether the range or the tangent of the view angle is to be incremented.

Comparator 32 defines the next operation. If A<B, then range is incremented as denoted by en#1. If A.gtoreq.B, then the tangent of the view angle is incremented as denoted by en#2. Table I shows the actions required for generating a perspective scene.

                  TABLE I
    ______________________________________
    PERSPECTIVE SCENE GENERATION
    Operation - En#1 Operation - En#2
    ______________________________________
    Increment Range  Increment Tan View Angle
    Read next Z      Write Pixel to Display
    Increment N.increment.R.increment.Tan.phi.
                     Increment M.increment.R.increment.Tan.phi.
    Read M.increment.R.increment.Tan.phi.
                     Read N.increment.R.increment.Tan.phi.
    Summations       Summations
    Compare          Compare
    ______________________________________

                  TABLE II
    ______________________________________
    PROGRAM OPERATIONS
    ______________________________________
    A        Declaration of the variables.
    B        Read data bases into memory.
    C        Write sky color to output memory.
    D        Get viewpoint parameters.
    E        Compute viewpoint constants.
    F        Find coordinates of the nearest block to the
             viewpoint.
    G        Compute and store the coordinates of each
             64 .times. 64 data block in the order that they
             will be processed.
    H        Compute and store the minimum and maximum
             sweep numbers which intersect each block.
             If a block is outside the field of view, set
             minimum and maximum sweep numbers to zero.
    I        Initialize sweep and horizon tables.
    J        Block processing - Read 64 .times. 64 block into
             memory if some or all of it may be visible.
             Sweep processing (Address generator) - Check
             if new address is still inside block.
             Update sweep table with new address.
             Lookup elevation and intensity at this
             address. Compare elevation with
             h - Z.sub.nm : (1) Elevation post is seen.
             Check if this pixel address will be
             visible on view window. Increment view
             angle, update tables Z <  (h - Z.sub.nm).
             (2) Elevation post is not seen. Incre-
             ment range and update tables.
    K        Transpose output array.
    L        Write output file.
    M        End of program.
    ______________________________________