Apparatus and method for three-dimensional terrain rendering

• US 6,111,583 A
• Filed: 09/29/1997
• Issued: 08/29/2000
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Skyline Software Systems Incorporated (Aecom Incorporated)
• Original Assignee: Skyline Software Systems Incorporated (Aecom Incorporated)
• Inventors: Shor, Ofer, Yaron, Ronnie
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US08/939,948
• Time in Patent Office: 1,065 Days
• Field of Search: 345/421, 345/426, 345/424
• US Class Current: 345/421
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method for rendering a three-dimensional terrain, the method including providing at least one previous display pixel having a previous ray from a point of view through the at least one previous display pixel to a previous terrain unit intersecting an axis of the previous ray, the previous ray having a length, and computing a subsequent ray from the point of view through a subsequent display pixel, whereby the subsequent ray has a length equal to the length of the previous ray.

Claims

1. A method for rendering a three-dimensional terrain, the method comprising:

providing a plurality of previous display pixels, each of said plurality of previous display pixels having a previous ray with a length from a point of view through said previous display pixel to a previous terrain unit intersecting an axis of said previous ray;

determining a starting value of a length of a subsequent ray from said point of view through a subsequent display pixel to a subsequent terrain unit intersecting an axis of said subsequent ray, said determining step comprising setting said starting value to the shortest of said lengths of at least two of said previous rays; and

repeatedly increasing or decreasing said starting value until said length of said subsequent ray is reached or reached with a predetermined tolerance, each of said repeated increasing and decreasing includes using, at least once, an increment equal to V_r +2^d where V_r is equal to a unit vector value of said subsequent ray and d is equal to Log₂ of said length of said subsequent ray.

2. The method of claim 1 wherein said providing step comprises tracing each of said previous rays through one of said plurality of previous display pixels.

3. The method of claim 1 wherein said providing step comprises previously computing each of said previous rays'"'"' lengths.

4. The method of claim 1 wherein said determining step further comprises setting said starting value to the shortest of said lengths of two of said previous rays that are associated with two of said plurality of previous display pixels that are adjacent to said subsequent display pixel.

5. A method according to claim 1 and further comprising the step of maintaining any of said lengths in a Z-buffer, and wherein said providing step comprises retrieving any of said lengths from said Z-buffer.

6. The method of claim 1 wherein said repeated increasing comprises:

(a) increasing said starting value by a factor; and

(b) incrementing said factor by said increment subsequent to said step (a).

7. The method of claim 1 wherein said repeated decreasing comprises decreasing said starting value by said increment.

8. Three-dimensional terrain rendering apparatus comprising:

a display including a plurality of display pixels;

a memory for storing information about a plurality of previous ones of the display pixels, each of said previous display pixels having a previous ray with a length from a point of view through said previous display pixel to a previous terrain unit intersecting an axis of said previous ray; and

apparatus for accessing said memory and computing a length of a subsequent ray from said point of view through a subsequent one of said display pixels to a subsequent terrain unit intersecting an axis of said subsequent ray, wherein said computing includes setting a starting value of said length of said subsequent ray to the shortest of said lengths of at least two of said previous rays and said computing further includes repeatedly increasing or decreasing said starting value until said length of said subsequent ray is reached or reached with a predetermined tolerance wherein each of said repeated increasing and decreasing includes using, at least once, an increment equal to V_r +2^d where V_r is equal to a unit vector value of said subsequent ray and d is equal to Log₂ of said length of said subsequent ray.