Apparatus and method for three-dimensional terrain rendering

• US 6,433,792 B1
• Filed: 02/23/2000
• Issued: 08/13/2002
• Est. Priority Date: 09/29/1997
• Status: Expired due to Term

• Current Assignee: Skyline Acquisition Corp.
• Original Assignee: Skyline Software Systems Incorporated (Aecom Incorporated)
• Inventors: Shor, Ofer, Yaron, Ronnie
• Primary Examiner(s): BRIER, JEFFERY A
• Application Number:
  US09/511,140
• Time in Patent Office: 902 Days
• Field of Search: 345/427, 345/428, 345/557, 345/667, 345/668, 345/669, 711/136, 711/137
• US Class Current: 345/669
• 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 of storing a terrain image in a data structure for subsequent display at a selected resolution, the method comprising the steps of:

(a) providing said terrain image in a plurality of said resolutions;

(b) dividing each image into a plurality of tiles;

(c) dividing each of the plurality of tiles into a plurality of picture elements;

(d) storing the picture elements for subsequent display of the terrain image in at least one resolution; and

(e) providing at least one pointer from a parent tile to a first of said plurality of said resolutions to a child tile of a second of said plurality of said resolutions, wherein said first of said plurality of said resolutions is of lesser detail than said second of said plurality of said resolutions.

2. A method according to claim 1 and further comprising storing either of a color attribute and an elevation attribute for each of said picture elements.

3. A method according to claim 1 wherein said dividing step comprises providing said tile with a fixed number of said picture elements.

4. A method according to claim 1 wherein said first of said plurality of said resolutions has four times more detail than said second of said plurality of said resolutions.

5. A method of storing terrain image tiles in a memory, the method comprising:

determining a currently viewed tile;

reading at least one near tile contiguous to said currently viewed tile into said memory;

dividing said currently viewed tile into a plurality of sections;

determining a currently viewed section of said currently viewed tile; and

reading at least one far tile not abutting said currently viewed tile into said memory, wherein said far tile is at a predetermined orientation relative to said currently viewed section.

6. A method according to claim 5 wherein said reading at least one near tile step comprises reading eight tiles wherein each of said eight tiles abuts said currently viewed tile.

7. A method according to claim 5 wherein said dividing step comprises dividing said currently viewed tile into four sections comprising top-left, top-right, bottom-left, and bottom-right sections.

8. A method according to claim 7 wherein said reading at least one far tile step comprises reading a row of tiles parallel to an outer edge of said currently viewed section, wherein said currently viewed section is intermediate to said row and another of said sections.

9. A method according to claim 7 wherein said reading at least one far tile step comprises reading a column of tiles parallel to an outer edge of said currently viewed section, wherein said currently viewed section is intermediate to said column and another of said sections.

10. A method according to claim 7 wherein said reading at least one far tile step comprises:

reading a row of tiles parallel to an outer edge of said currently viewed section, wherein said currently viewed section is intermediate to said row and another of said sections; and

reading a column of tiles parallel to an outer edge of said currently viewed section, wherein said currently viewed section is intermediate to said column and another of said sections.

11. A method according to claim 10 wherein either of said reading a row step and said reading a column step comprises reading three tiles.

12. A method according to claim 10 and further comprising reading a corner tile intersecting said row and said column.

13. A method according to claim 5 wherein any of said steps are performed for a plurality of resolution levels.

14. A method according to claim 5 wherein any of said reading steps comprises reading into a disk cache memory.

15. A method of managing terrain image tiles in a memory, the method comprising:

maintaining an index comprising a coordinate of each of a plurality of stored tiles and a pointer to each of said plurality of stored tiles;

searching said index for an index entry matching a coordinate of a requested tile;

incrementing a plurality of use counters for a rendering cycle, each of said plurality of use counters corresponding to a one of said plurality of stored tiles;

if said coordinate of said requested tile is found in said index;

returning said pointer to said stored tile wherein said coordinate of said stored tile matches said coordinate of said requested tile; and

zeroing said use counter corresponding to said stored tile wherein said coordinate of said stored tile matches said coordinate of said requested tile; and

if said coordinate of said requested tile is not found in said index;

determining a least recently used stored tile whose use counter is highest among said plurality of use counters; and

reading said requested tile into said memory, whereby said least recently used stored tile is replaced with said requested tile.

16. A method according to claim 15 wherein said maintaining an index step comprises maintaining an index of at least one bit of each of said coordinates of said plurality of stored tiles.

17. A method according to claim 15 wherein said maintaining an index step comprises maintaining an index of 5 least-significant bits of each of said coordinates of said plurality of stored tiles.

18. A method according to claim 15 wherein said searching step comprises searching using at least one bit of said coordinate of said requested tile.

19. A method according to claim 15 wherein:

said maintaining an index step comprises maintaining an index of at least one bit of each of said coordinates of said plurality of stored tiles;

wherein said searching step comprises searching using at least one bit of said coordinate of said requested tile; and

if said at least one bit of coordinate of said requested tile is found in said index, further comprising verifying that a full coordinate of said requested tile matches a full coordinate of said stored tile corresponding to said index entry.

20. A method according to claim 15 and, if said coordinate of said requested tile is not found in said index, further comprising:

searching a disk cache memory for said requested tile and wherein said reading step comprises reading said requested tile from said disk cache memory.