Technique and system for the real-time generation of perspective images

• US 5,550,959 A
• Filed: 05/27/1993
• Issued: 08/27/1996
• Est. Priority Date: 05/27/1993
• Status: Expired due to Term

• Current Assignee: Novalogic Incorporated
• Original Assignee: Novalogic Incorporated
• Inventors: Freeman, Kyle G.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): Fetting, Anton W.
• Application Number:
  US08/068,428
• Time in Patent Office: 1,188 Days
• Field of Search: 395/127, 395/119, 395/120, 395/135, 395/123, 395/130, 395/121, 395/139
• US Class Current: 345/427
• CPC Class Codes: G06T 15/20 Perspective computation

Abstract

A technique and system for the real-time computation of visual scenes reduces the three-dimensional computation to two additions and further reduces the need for three-dimensional computations by displaying several screen pixels per three-dimensional computation. The approach when implemented in hardware or software significantly speeds up scene generation time. From a two-dimensional array of elevations a series of cross-sections perpendicular to the observer are constructed. For each elevation within the cross-section, a series of screen pixels is drawn. The next array element in the cross-section is found by adding a value to both indexes in the two-dimensional array.

Claims

1. A method of realtime generation of perspective visual scenes reflective of a virtual observer'"'"'s movement through a gaming area generated from a visual data base, comprising:

generating a series of overlapping perspective cross-sections perpendicular to a virtual observer'"'"'s line of sight, including;

(a) determining a desired horizontal scale, vertical scale, position, heading and height of the virtual observer relative to the visual data base, a desired number of perspective cross-sections and distance of each respective perspective cross-section from the heading, position and height of the virtual observer;

(b) identifying a sampling point for the first perspective cross-section in the perspective visual scene of the gaming area;

(c) computing a two-dimensional scale vector with direction perpendicular to the observer'"'"'s line of sight and with magnitude scaled according to the distance of the respective perspective cross-section from the virtual observer;

(d) for each display column to the virtual observer'"'"'s left of the virtual observer'"'"'s line of sight, adding the scale vector to the sampling point;

(e) obtaining elevation data at said sampling point from a visual data base;

(f) for each display column, scaling the elevation data stored at a respective point in said data base and drawing a line to the scaled elevation;

(g) repeating steps (d), (e) and (f) until all display columns to the virtual observer'"'"'s left have been drawn;

(h) for each display column to the virtual observer'"'"'s right of the virtual observer'"'"'s line of sight, adding the negative of said scale vector to said sampling point;

(i) obtaining elevation data from the visual data base;

(j) for each display column, scaling the elevation data stored at a respective point in said data base and drawing a line to the scaled elevation;

(k) repeating steps (h), (i) and (j) until all display columns to the virtual observer'"'"'s left have been drawn;

(l) repeating steps (b) through (k), inclusive until all of the overlapping series of perspective cross-sections have been generated; and

displaying the display columns of the overlapping cross-sections that are not overdrawn by the display columns of an overlapping cross-section.

2. The method of claim 1 in which said step of determining the desired horizontal scale, vertical scale, number of perspective cross-sections desired, and distance of each respective perspective cross-section from the virtual observer comprises applying algorithmic functions to the virtual observer'"'"'s position, heading and height.

3. A method for generating perspective visual scenes during computer game play, comprising:

generating a series of overlapping perspective cross-sections perpendicular to a virtual observer'"'"'s line of sight, including;

(a) determining desired horizontal scale, vertical scale, number of perspective cross-sections desired, and distance of each respective perspective cross-section from the virtual observer;

(b) computing a center point for the first perspective cross-section;

(c) computing a two-dimensional scale vector with direction perpendicular to the virtual observer'"'"'s line of sight and with magnitude scaled according to the distance of the respective perspective cross-section from the observer;

(d) determining the length of an increment by adding the scale vector to the centerpoint for positions to the left of the centerpoint and adding the negative of the scale vector to the centerpoint for positions to the right of the centerpoint;

(e) stepping a single increment from said center point along a line determined by the angle and direction of said scale vector and said predetermined distance of the respective perspective cross-section from the virtual observer;

(f) drawing a display column on the perspective cross-section at the position determined in step (e), comprising;

obtaining elevation data from a visual data base; and

scaling the elevation data stored at a respective point in said data base and drawing a line to the scaled elevation;

(g) repeating steps (d) through (f), inclusive, until all display columns on the perspective cross-section have been drawn;

(h) repeating steps (b) through (g), inclusive, until all of the perspective cross-sections have been computed and drawn; and

displaying the display columns of the overlapping cross-sections that are not overdrawn by the display columns of an overlapping cross-section.

4. The method of claim 3 in which said step of determining the desired horizontal scale, vertical scale, number of perspective cross-sections desired, and distance of each respective perspective cross-section from the virtual observer comprises applying algorithmic functions to the virtual observer'"'"'s position, heading and height.

5. An apparatus for generating and displaying real-time visual images of perspective scenes, comprising:

a memory;

a display for displaying the perspective scenes; and

a processor that;

(a) determines, in real-time, position and heading data of a virtual observer relative to a visual data base stored in the memory,

(b) determines a perspective visual scene visible to the virtual observer from the position and heading data,

(c) divides the visual scene into a series of overlapping perspective cross-sections, with each perspective cross-section being perpendicular to the position and heading of the virtual observer and located at a greater distance from the position of the virtual observer than the preceding perspective cross-section,

(d) determines a scale for each perspective cross-section according to the distance of each of the perspective cross-sections to the virtual observer,

(e) determines a sampling point for each perspective cross-section,

(f) computes a two-dimensional scale vector for each perspective cross-section with direction perpendicular to the virtual observer'"'"'s line of sight and with magnitude scaled according to the distance of the respective perspective cross-section from the observer,

(g) determines the position of each display column by adding the scaled vector to the sampling point for each display column to the left of the sampling point and adding the negative of the scale vector to the sampling point for each display column to the right of the sampling point,

(h) obtains elevation data from the visual data base and scales the elevation data as a function of the position of each display column and the scale of the perspective cross-section,

(i) generates column draw signals associated with each display column of the scaled perspective cross-section, the column draw signals being a function of the position of each display column and the scaled elevation data, and

(j) provides the column draw signals to the display for controlling the display to draw a scaled display column on the display, wherein the portion of the scaled display column not overdrawn by the scaled display column of another perspective cross-section is displayed.

6. The apparatus of claim 5, further comprising:

address means responsive to virtual observer position and heading data and incremental X- and Y-steps for generating a value corresponding to a data base address of elevation data in the visual data base;

memory means responsive to said value corresponding to the data base address of the elevation data for generating instantaneous terrain elevation data;

wherein the processor further determines virtual observer height data relative to the visual data base stored in the memory;

subtractor means responsive to said terrain instantaneous elevation data and virtual observer height data for generating a value corresponding to the difference between virtual observer height and terrain elevation; and

vertical scaling means responsive to said value corresponding to the difference between virtual observer height and terrain elevation for supplying the column-draw signal to the display.

7. The apparatus of claim 6, further comprising memory means responsive to virtual observer position and heading data and incremental X- and Y-steps for generating color data.

8. A method of generating perspective visual scenes reflective of a virtual observer'"'"'s movement through a gaming area generated from a visual data base, comprising:

generating a series of overlapping perspective cross-sections perpendicular to a virtual observer'"'"'s line of sight, horizontally and vertically scaling each of the series of overlapping cross-sections dependent upon a distance from the virtual observer, including;

(a) determining a desired horizontal scale, vertical scale, position, heading and height of the visual observer relative to the visual data base, a desired number of perspective cross-sections and distance of each respective perspective cross-section from the heading, position and height of the virtual observer;

(b) identifying a sampling point in the perspective visual scene of the gaming area by computing a center point for each perspective cross-section;

(c) computing a two-dimensional scale vector for each perspective cross-section with direction perpendicular to the observer'"'"'s line of sight and with magnitude scaled according to the distance of the respective perspective cross-section from the virtual observer;

(d) drawing a line in each display column of each perspective cross-section, including;

(i) determining the position of the display column by adding the scale vector to the sampling point for display columns to the left of the virtual observer'"'"'s line of sight and adding the negative of the scale vector to the sampling point for display columns to the right of the virtual observer'"'"'s line of sight;

(ii) obtaining elevation data at said sampling point from a visual data base;

(iii) scaling the elevation data stored at a respective point in said data base and drawing a line to the scaled elevation;

(iv) repeating steps (i), (ii) and (iii) until all the display columns of the perspective cross-sections of the visual scene have been drawn.

9. The method of claim 8 in which said step of determining the desired horizontal scale, vertical scale, number of perspective cross-sections desired, and distance of each respective perspective cross-section from the virtual observer comprises applying algorithmic functions to the virtual observer'"'"'s position, heading and height.