Data block processing for fast image generation

• US 4,855,937 A
• Filed: 08/08/1984
• Issued: 08/08/1989
• Est. Priority Date: 08/08/1984
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: General Electric Company
• Inventors: Heartz, Robert A.
• Primary Examiner(s): Cangialosi, Salvatore
• Application Number:
  US07/638,708
• Time in Patent Office: 1,826 Days
• Field of Search: 364/900 MS File, 364/200 MS File, 364/522, 364/700, 364/731, 364/521
• US Class Current: 345/421
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 15/20 Perspective computation

Abstract

An improvement for the real-time computer generation of visual scenes based on an algorithm that reduces the processing of elevation data to simple repetitive accumulations and a compare operation to generate occult data using grid elevation data bases is disclosed. The improvement reduces the size of the on-line, high speed, random access, data base memory required in image generation from grid data bases and reduces image generation time. The grid data base is divided into an array of data blocks. The data blocks are sequentially transferred to on-line ping-pong buffer memories (14), and each data block is processed through to final display by a view ray processor (16). The order of block selection is such that the sweep data remains continuous. When a sweep leaves a block, exit processing parameters are stored in a sweep horizon memory (18) as sweep parameters. When the sweep is again continued in a future block, the sweep parameters are transferred to the view ray processor (16) and an X,Y address generator (20) as initial conditions.

Claims

1. In a method of real-time computer generation of visual scenes comprising the steps of storing a grid data base of elevation posts are predetermined intervals for the visual scene to be generated, defining a horizontal field of view as a predetermined number of sweeps 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 sweep, 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 an increment of Δ

RTanφ

_m where m refers to the m^th view ray, and for each range increment Δ

R, increasing the distance between sweeps by the increment Δ

RΔ

Tanφ

, comparing at each range increment Δ

R 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, the improvement comprising the steps of

dividing said grid data base into an array of data blocks;

sequentially transferring said data blocks to an on-line memory in an order to allow processing such that the sweep data remains continuous;

when a sweep leaves a data block, storing the exit processing parameters in a sweep table as sweep parameters; and

when the sweep is again continued in a further data block, reading the sweep parameters in said sweep table as initial conditions for the processing of said future data block.

2. The improvement in the method of real-time computer generation of visual scenes according to claim 1 wherein the method of determining which view ray strikes an elevation post is performed by a view ray processor and said on-line memory is a ping-pong memory is composed of two random access memories and said step of sequentially transferring is performed by writing data into one of said random access memories from said data base while data is being read from the other of said random access memories to said view ray processor.

3. The improvement in the method of real-time computer generation of visual scenes according to claim 1 further comprising the steps of

checking said X,Y data base address to determine if the address is a horizon point and if it is, then checking the sweep to determine if it is within the block being processed, otherwise checking to determine if said X,Y data base address is within the block being processed,

if the X,Y data base address is a horizon point and the sweep is not within the block being processed, then calling the next data block to be processed, but if the X,Y data base address is not a horizon point or the sweep is within the block being processed, then checking the address to determine if it is within the block being processed,

if the X,Y data base address is not within the block being processed, then commencing the next sweep, otherwise determining if the current view ray strikes an elevation post, and

if the current view ray is occulted, when incrementing to the next point, otherwise writing the data for the current view ray as a pixel to said display means and then determining if the next view ray strikes an elevation post.

4. In a real-time computer image generating system comprising data base means for storing a grid data base of elevation posts at predetermined intervals for the visual scene to be generated and a view ray processor including sweep generation means for defining a horizontal field of view as a predetermined number of sweeps perpendicular to a boresight at a view point, range incrementing means for changing the range from the view point and for each sweep, defining the changes in Δ

X and Δ

Y in said grid data base, address means for accumulating Δ

X and Δ

Y to generate an X,Y data base address for extracting the elevation for that sweep element, said sweep generation means being responsive to said range incrementing means for stepping a view ray down by an increment of Δ

Rtanφ

_m for each range increment Δ

R where m refers to the m^th view ray and increasing the distance between sweeps by the increment Δ

RΔ

tanφ

, comparing means for comparing the accumulated elevation value of the view ray at each range increment φ

R with the elevation extracted from said means for storing with said X,Y data base address, and means responsive to said comparing means for reading data for that post to a display means if the view ray strikes the post or reading the elevation data for the next elevation post from said storage means if the view ray does not strike the post, the improvement wherein said grid data base is divided into an array of data blocks within said storage meaas and said computer image generator means further comprises;

an on-line memory;

means for sequentially transferring said data blocks to said on-line memory in an order to allow processing such that the sweep data remains continuous;

block edge detection means responsive to said address generation means for detecting the edge of a data block currently being processed; and

sweep memory means responsive to said block edge detection means for storing the exit processing parameters as sweep parameters, said sweep parameters being read out of said sweep memory means as initial conditions for the processing of the next data block said view ray processor.

5. The improvement in the real-time computer image generator system as recited in claim 4 wherein said on-line memory is composed of two random access memories arranged such that while data is being read from one to said view ray processor, data is being written into the other from said data base storage means.

6. The improvement in the real-time computer image generator as recited in claim 4 further comprisng a block detection selection means for storing the block selection order and the maximum and minimum sweep tangents that intersect each data block, said data base means being responsive to said block detection selection means for reading data into said on-line memory.