Incremental terrain image generation

• US 4,583,185 A
• Filed: 10/28/1983
• Issued: 04/15/1986
• Est. Priority Date: 10/28/1983
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Heartz, Robert A.
• Primary Examiner(s): Krass, Errol A.
• Assistant Examiner(s): Herndon, Heather R.
• Application Number:
  US06/546,599
• Time in Patent Office: 900 Days
• Field of Search: 364/521, 364/522, 340/700, 340/711, 340/825.7, 358/903
• US Class Current: 345/421
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G09B 9/302 the image being transformed by computer processing, e.g. updating the image to correspond to the changing point of view

Abstract

An algorithm for the real-time computer generation of visual scenes reduces the processing of elevation data to simple repetitive accumulations and a compare opertion to generate occult data using grid elevation data bases. The approach, when implemented as a software or firmware program, significantly speeds up scene generation time, and when implemented in hardware, significantly reduces the amount of hardware required. Accumulator (16) or counter (38) accumulates increments in tangent of the view angle, while accumulator (18) or counter (40) accumulates increments in range. Depending on the outcome of the compare operation of comparator (32), the accumulated tangent of the view angle or the accumulated range is used to compute in subtractor (26) the elevation of the view ray at each range increment of a sweep. This computed elevation is compared in comparator (32) with the corresponding elevation data for that point in the grid data base.

Claims

1. A method of real-time computer generation of visual scenes comprising the steps of

storing a grid data base of elevation posts at predetermined intervals for the visual scene to be generated,

defining a horizontal field of view as a predetermined number of sweep increments perpendicular to a boresight at a view point,

incrementing the change in range Δ

R from the view point and for each sweep, defining the changes Δ

X and Δ

Y in said grid data base,

accumulating Δ

X and Δ

Y to generate an X,Y data base address for extracting the elevation for that sweep element,

for each range increment Δ

R, stepping a view ray down by a increment of Δ

R Tan φ

_m, where m refers to the m^th view ray,

for each range increment Δ

R, increasing the distance between sweeps by the increment Δ

RΔ

Tan φ

,

comparing at each range increment the accumulated elevation value of the view ray with the elevation extracted with said X,Y data base address, and

if a view ray strikes an elevation post, reading the data for that post to a display means, otherwise reading the elevation data for the next elevation post from the data base.

2. The method according to claim 1 wherein the step of storing further includes storing corresponding color data for each of said elevation posts.

3. A computer image generator that is capable of generating in real time visual images of perspective scenes, comprising:

first register means for storing a value corresponding to Δ

RΔ

Tan φ

, where Δ

R is an incremental change in range and Δ

Tan φ

is an incremental change in the tangent of the view angle;

first accumulator means connected to said first register means for accumulating a value corresponding to n R Tan which is the increment value resulting in incrementing the tangent of the view angle n times;

second accumulator means connected to said first register means for accumulating a value corresponding to Δ

R Tan φ

_min -mΔ

RΔ

Tan φ

which is the increment value resulting in incrementing the range, said second accumulator means being preloaded with the value Δ

R Tan φ

_min where φ

_min is the angle defining the edge of the vertical field of view;

third accumulator means connected to said first and second accumulator means to receive as its input the output of a selected one thereof, said third accumulator means being preloaded with a value corresponding to h, the elevation of the view point, and accumulating a value corresponding to h-Z'"'"'_nm, where Z'"'"'_nm is the view ray projection of the n^th range increment and the m^th increment of the view angle tangent;

first memory means for storing a Z grid data base of elevation posts of predetermined intervals for the visual scene to be generated;

addressing means for generating an X,Y address for said Z grid data base corresponding to N^th range increment and the m^th increment of the view angle tangent; and

comparing means connected to said third accumulator means and said memory means for providing a first output if the value of the output of said third accumulator means is greater than or equal to the addressed value in said memory means and a second output if the value of the output of said third accumulator means is less than the addressed value in said memory means, said first output causing selection of the output of said first accumulator means as the input to be supplied to said third accumulator means and causing said second accumulator means to be decremented, and said second output causing selection of the output of the said second accumulator means as the input to be supplied to said third accumulator means, causing the addressed data in said first memory means to be read out to said third accumulator means and causing said first accumulator to be incremented.

4. The computer image generator as recited in claim 3 further comprising second memory means for storing intensity data corresponding the elevation posts of the data base stored in said first memory means, said second memory means also being addressed by said addressing means and responsive to the first output of said comparing means for reading out addressed intensity data.

5. The computer image generator as recited in claim 3 wherein said first accumulator means comprises second register means, first and second gate means and first summing means, said first gate means being responsive to said second output of said comparing means for supplying the output of said second register means to one input of said first summing means, the second input of said first summing means being connected to said first register means, and said second gate means being responsive to said first output of said comparing means to supply the output of said second register means to said third accumulator means, and wherein said second accumulator means comprises third register means, third and fourth gate means and second summing means, said third gate means being responsive to said first output of said comparing means for supplying the output of said third register means to one input of said second summing means, the second input of said second summing means being connected to said first register means, and said fourth gate means being responsive to said second output of said comparing means for supplying the output of said third register means to said third accumulator means.

6. The computer image generator according to claim 3 wherein said first accumulator means comprises range counter means which is incremented in response to the second output of said comparing means and read out to said third accumulator means in response to the first output of said comparing means and wherein said second accumulator means comprises view ray counter means which is decremented in response to the first output of said comparing means and read out to said third accumulator means in response to the second output of said comparing means.