Method and system for rendering two-dimensional views of a three-dimensional surface

• US 5,781,195 A
• Filed: 04/16/1996
• Issued: 07/14/1998
• Est. Priority Date: 04/16/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Marvin, John
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/632,847
• Time in Patent Office: 819 Days
• Field of Search: 395/357, 395/358, 345/428, 345/429, 345/430, 345/419
• US Class Current: 345/428
• CPC Class Codes: G06T 11/00 2D [Two Dimensional] image generation

Abstract

A method and system for rendering a two-dimensional image of a three-dimensional surface in real time directly from surface-feature data stored in computer-readable format. A two-dimensional screen display may therefore be rendered "on the fly" for any view point, altitude, and orientation in three-dimensional space. Changing the view point enables panning, changing the altitude allows zooming, and changing the orientation allows spinning of the image. Successive two-dimensional renderings from an initial field of view are rendered to present a sequence of screen displays that effectively pan, zoom, or spin the image of the three-dimensional surface. The rendering methods are sufficiently fast when implemented on preferred personal computer systems so as to enable panning, zooming, and spinning at a satisfactory rate in response to user commands. To the user, the surface features appears to pan, zoom, or spin in real time. Two-dimensional views may be rendered of any three-dimensional structure such as an airplane, power plant, anatomical organ, atomic particle, etc. In particular, two-dimensional views of maps of the surface of the Earth are rendered in connection with a multimedia world atlas computer program.

Claims

1. A method for rendering a two-dimensional view of a three-dimensional surface, comprising the steps of:

receiving a user command defining a field of view portion of said three-dimensional surface;

selecting a sequence of memory blocks comprising a reduced-detail three-dimensional surface corresponding to said field of view, each said memory block comprising a group of spatially-contiguous pixels of said reduced-detail three-dimensional surface, said sequence of memory blocks comprising a spatially-contiguous section of said reduced-detail three-dimensional surface;

retrieving said section from sequentially-addressed locations within a mass-storage computer memory;

computing a two-dimensional projection of said section; and

displaying said two-dimensional projection of said section on a display device.

2. The method of claim 1, wherein said step of receiving user commands defining a field of view comprises interpreting said user commands as a view point vector and an orientation vector.

3. The method of claim 1, wherein said reduced-detail three-dimensional surface comprises color-coded topographical and bathological map data.

4. The method of claim 1, wherein said step of selecting a sequence of memory blocks comprises identifying said memory blocks in hybrid-quad-tree format.

5. The method of claim 1, wherein said step of retrieving said section comprises retrieving at least one memory block comprising at least about 128 spatially-contiguous pixels.

6. The method of claim 1, wherein said step of computing a two-dimensional projection of said section comprises computing a two-dimensional orthographic projection of said section.

7. The method of claim 1, wherein said step of displaying said two-dimensional projection of said section comprises painting a computer screen comprising at least about 300,000 pixels.

8. The method of claim 1, further comprising the steps of:

after displaying said two-dimensional projection of said section on said display device, checking for an interrupt condition; and

if said interrupt condition has not occurred, displaying a first detail layer corresponding to said field of view on said display device.

9. The method of claim 8, further comprising the step of, if said interrupt condition has occurred, discontinuing the rendering of said two-dimensional view of said three-dimensional surface.

10. The method of claim 9, further comprising the steps of:

after displaying said first detail layer, checking for said interrupt condition;

if said interrupt condition has occurred, discontinuing the rendering of said two-dimensional view of said three-dimensional surface; and

if said interrupt condition has not occurred, displaying a second detail layer corresponding to said field of view on said display device.

11. The method of claim 10, wherein:

said step of displaying a first detail layer comprises displaying an area object; and

said step of displaying a second detail layer comprises displaying a line object.

12. A method for rendering a panning sequence of two-dimensional views of a three-dimensional surface, comprising the steps of:

(a) receiving a user command defining a field of view comprising said panning sequence;

(b) selecting a sequence of memory blocks comprising a reduced-detail three-dimensional surface corresponding to said field of view, each said memory block comprising a group of spatially-contiguous pixels of said reduced-detail three-dimensional surface, said sequence of memory blocks comprising a spatially-contiguous section of said reduced-detail three-dimensional surface;

(c) retrieving said section from sequentially-addressed locations within a mass-storage computer memory;

(d) computing a two-dimensional projection of said section;

(e) displaying said two-dimensional projection of said section on a display device;

(f) checking for an interrupt condition; and

(g) if said interrupt condition has not occurred, repeating steps (b)-(g) hereof.

13. The method of claim 12, further comprising the step of:

if said interrupt condition has occurred

displaying a first detail layer corresponding to said field of view,

after displaying said first detail layer, checking for said interrupt condition, and

if said interrupt condition has not occurred, displaying a second detail layer corresponding to said field of view on said display device.

14. In a computer characterized by a central processing unit (CPU), a cache memory, a mass-storage computer memory, an input device for providing user commands to said CPU, and an output device for providing displaying two-dimensional views of a three dimensional surface, and a program module running on said computer, said program module operable for:

receiving a first user command defining a first field of view portion of said three-dimensional surface;

selecting a first sequence of memory blocks comprising said first field of view;

checking said cache memory to determine whether said memory blocks comprising said first field of view are present within said cache memory;

if said memory blocks comprising said first field of view are not present within said cache memory, reading an extended first field of view from said mass-storage computer memory into said cache memory, said extended first field of view comprising said first field of view and areas of said three-dimensional surface that are spatially-contiguous with said first field of view;

computing a two-dimensional projection comprising said first field of view;

displaying said two-dimensional projection comprising said first field of view on a display device;

receiving a second user command defining a second field of view portion of said three-dimensional surface;

selecting a second sequence of memory blocks comprising said second field of view;

checking said cache memory to determine whether said memory blocks comprising said second field of view are present within said cache memory; and

if said memory blocks comprising said second field of view are present within said cache memory, using said memory blocks comprising said second field of view within said cache memory to display a two-dimensional projection comprising said second field of view on said display device.

15. A storage medium for a computer program used in a computer system, said storage medium comprising a computer program providing a method for rendering a two-dimensional view of a three-dimensional surface, comprising the steps of:

receiving a user command defining a field of view portion of said three-dimensional surface;

selecting a sequence of memory blocks comprising a reduced-detail three-dimensional surface corresponding to said field of view, each said memory block comprising a group of spatially-contiguous pixels of said reduced-detail three-dimensional surface, said sequence of memory blocks comprising a spatially-contiguous section of said reduced-detail three-dimensional surface;

retrieving said section from sequentially-addressed locations within a mass-storage computer memory;

computing a two-dimensional projection of said section;

displaying said two-dimensional projection of said section on a display device;

after displaying said two-dimensional projection of said section on said display device, checking for an interrupt condition;

if said interrupt condition has not occurred, displaying a first detail layer corresponding to said field of view on said display device.

16. The storage medium of claim 15, wherein said method further comprises the steps of:

after displaying said first detail layer, checking for said interrupt condition;

if said interrupt condition has occurred, discontinuing the rendering of said two-dimensional view of a three-dimensional surface; and

if said interrupt condition has not occurred, displaying a second detail layer corresponding to said field of view on said display device.

17. A storage medium for a computer program used in a computer system, said storage medium comprising a computer program providing a method for rendering a panning sequence of two-dimensional views of a three-dimensional surface, comprising the steps of:

(a) receiving a user command defining a field of view comprising said panning sequence;

(b) selecting a sequence of memory blocks comprising a reduced-detail three-dimensional surface corresponding to a field of view corresponding to said panning sequence, each said memory block comprising a group of spatially-contiguous pixels of said reduced-detail three-dimensional surface, said sequence of memory blocks comprising a spatially-contiguous section of said reduced-detail three-dimensional surface;

(c) retrieving said section from sequentially-addressed locations within a mass-storage computer memory;

(d) computing a two-dimensional projection of said section;

(e) displaying said two-dimensional projection of said section on a display device;

(f) checking for an interrupt condition;

(g) if said interrupt condition has not occurred, repeating steps (b)-(g) hereof; and

(h) if said interrupt condition has occurred

displaying a first detail layer corresponding to said field of view,

after displaying said first detail layer, checking for said interrupt condition, and

if said interrupt condition has not occurred, displaying a second detail layer corresponding to said field of view on said display device.

18. A storage medium for a computer program used in a computer system, said storage medium comprising a computer program providing a method for rendering two-dimensional views of a three-dimensional surface, comprising the steps of:

receiving a first user command defining a first field of view portion of said three-dimensional surface;

selecting a first sequence of memory blocks comprising said first field of view;

checking a cache memory to determine whether said memory blocks comprising said first field of view are present within said cache memory;

if said memory blocks comprising said first field of view are not present within said cache memory, reading an extended first field of view from a mass-storage computer memory into said cache memory, said extended first field of view comprising said first field of view and areas of said three-dimensional surface that are spatially-contiguous with said first field of view;

computing a two-dimensional projection comprising said first field of view;

displaying said two-dimensional projection comprising said first field of view on a display device;

after displaying said two-dimensional projection of said section on said display device, checking for an interrupt condition;

if said interrupt condition has not occurred, displaying a first detail layer corresponding to said field of view on said display device;

after displaying said first detail layer, checking for said interrupt condition;

if said interrupt condition has occurred, discontinuing the rendering of said two-dimensional view of said three-dimensional surface;

if said interrupt condition has not occurred, displaying a second detail layer corresponding to said field of view on said display device; and

if said interrupt condition has occurred

receiving a second user command defining a second field of view portion of said three-dimensional surface,

selecting a second sequence of memory blocks comprising said second field of view,

checking a cache memory to determine whether said memory blocks comprising said second field of view are present within said cache memory, and

if said memory blocks comprising said second field of view are present within said cache memory, using said memory blocks comprising said second field of view within said cache memory to display a two-dimensional projection comprising said second field of view on said display device.

19. A storage medium for a computer program used in a computer system, said storage medium comprising a computer program providing a method for rendering two-dimensional views of a three-dimensional surface, comprising the steps of:

defining a reduced-detail database corresponding to said three-dimensional surface;

defining a detail database corresponding to said three-dimensional surface;

dividing said reduced-detail database into a plurality of memory blocks, each said memory block comprising a group of spatially-contiguous pixels;

grouping said memory blocks into a plurality of spatially-contiguous sections of said reduced-detail three-dimensional surface;

storing each said section in a plurality of sequentially-addressed locations within a mass-storage computer memory;

defining a plurality of layers comprising said detail database; and

storing each said layer within said mass-storage computer memory.

20. The method of claim 19, wherein said reduced-detail database comprises color-coded topographical and bathological map data.