Method and apparatus for determining visible surfaces

• US 5,825,363 A
• Filed: 05/24/1996
• Issued: 10/20/1998
• Est. Priority Date: 05/24/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Anderson, Michael D.
• Primary Examiner(s): Zimmerman, Mark K.
• Application Number:
  US08/653,380
• Time in Patent Office: 879 Days
• Field of Search: 345/421, 345/422, 345/435
• US Class Current: 345/422
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A system for rendering a three-dimensional scene by determining each visible surface of geometric shapes for a sequence of frames. For a selected frame, a working frame buffer is initialized by copying background data maintained in a background frame buffer to the working frame buffer. A working Z buffer is initialized by copying background depth data of the background Z buffer to the working Z buffer. The background data is represented by a bitmap defining values for pixels of a background remaining constant for the frame sequence. The background depth data is represented by depth values defining distances between a view point reference and the geometric shapes at the pixels of the selected frame. For a selected geometric shape, a pixel is selected from a set of pixels for the frame. This set of pixels is defined by an intersection between the view point reference and the selected geometric shape. A determination is then made whether the selected geometric shape obscures another geometric shape at the selected pixel. If so, a value of the selected pixel is obtained and stored within the working frame buffer. In addition, a depth value defined by a distance between the view point reference and the selected geometric shape is stored within the working Z buffer. These steps are completed for each remaining pixel within the set of pixels and, in turn, this process is completed for each remaining geometric shape.

Claims

1. A method for determining each visible surface of a scene comprising a sequence of frames, each having a plurality of geometric shapes and corresponding to a plurality of pixels, the scene having a background remaining constant for the frame sequence, to support a presentation on a pixel-oriented output device of an image of the scene, comprising the steps of:

(a) initializing a frame number variable, each frame associated with a frame number;

(b) initializing a working frame buffer by copying background data of a background frame buffer to the working frame buffer, the background data defined by values for pixels corresponding to the background, and initializing a working Z buffer by copying background depth data of a background Z buffer to the working Z buffer, the background depth data represented by depth values defining spatial relationships between a view point reference and geometric shapes at the pixels of the background;

(c) responsive to initializing the working frame buffer and the working Z buffer, for a selected frame corresponding to the frame number variable, rendering the geometric shapes into the working frame buffer and the working Z buffer;

(d) incrementing the frame number variable; and

(e) repeating steps (b)-(d) until the frame number variable is greater than the number of frames within the frame sequence.

2. The method of claim 1, wherein the rendering step comprises the steps of:

for a selected one of the geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected geometric shape and the view point reference;

determining whether the selected geometric shape obscures another one of the geometric shapes at the selected pixel,

if so, obtaining a value of the selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

repeating the determining step for each remaining pixel within the set of pixels; and

repeating the above steps for each remaining geometric shape.

3. The process of claim 2, wherein the step of determining whether the selected geometric shape obscures another one of the geometric shapes comprises the steps of:

calculating the distance between the view point reference and the selected geometric shape at the selected pixel; and

determining whether the calculated distance is greater than one of the depth values in the working Z buffer at the selected pixel,

if so, then the selected geometric shape obscures the geometric shape at the selected pixel within the set of pixels.

4. The process of claim 3 further comprising the step of:

responsive to rendering the geometric shapes associated with the selected frame, presenting the scene image for the selected frame on the pixel-oriented output device by copying a bitmap of the updated working frame buffer to the pixel-oriented output device.

5. The process of claim 1, wherein the steps of initializing the working frame buffer and the working Z buffer comprise:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.

6. The process of claim 1, wherein each depth value of the background depth data comprises a numerical value representing a distance between the view point reference and the background at one of the background pixels.

7. A method for determining each visible surface of a scene comprising a sequence of frames, each having a plurality of geometric shapes and corresponding to a plurality of pixels, the scene having a pre-rendered background of geometric shapes remaining constant for the frame sequence, to support a presentation on a pixel-oriented output device of an image of the scene, comprising the steps of:

(a) for a selected one of the frames, initializing a working frame buffer by copying background data of a background frame buffer to the working frame buffer, the background data defined by values for pixels corresponding to the background, and initializing a working Z buffer by copying background depth data of a background Z buffer to the working Z buffer, the background depth data represented by depth values defining spatial relationships between a view point reference and geometric shapes at the pixels of the background;

(b) responsive to initializing the working frame buffer and the working Z buffer, rendering the selected frame by;

(i) for a selected one of the geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected geometric shape and the view point reference;

(ii) determining whether the selected geometric shape obscures another one of the geometric shapes at the selected pixel,

if so, obtaining a value of the selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

(iii) repeating step (ii) for each remaining pixel within the set of pixels; and

(iv) repeating steps (i)-(iii) for each remaining geometric shape.

8. The process of claim 7, wherein each depth value of the background depth data comprises a numerical value representing a distance between the view point reference and one of the geometric shapes of the background at one of the background pixels.

9. The process of claim 7, wherein the step of determining whether the selected geometric shape obscures another one of the geometric shapes comprises the steps of:

calculating the distance between the view point reference and the selected geometric shape at the selected pixel; and

determining whether the calculated distance is greater than one of the depth values in the working Z buffer at the selected pixel,

if so, then the selected geometric shape obscures the geometric shape at the selected pixel within the set of pixels.

10. The process of claim 7 further comprising the step of:

(c) presenting the scene image for the selected frame on the pixel-oriented output device by copying a bitmap of the updated working frame buffer to the pixel-oriented output device.

11. The process of claim 10 further comprising the steps of:

in response to presenting the scene image of the selected frame on the pixel-oriented output device, repeating steps (a)-(b) for another one of the frames.

12. The process of claim 11, wherein the steps of initializing the working frame buffer and the working Z buffer comprise:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.

13. The process of claim 7, wherein the scene further comprises static objects of geometric shapes that remain static during the frame sequence and non-static objects of geometric shapes that change during the frame sequence, and the rendering step comprises:

identifying the static objects in the frame sequence;

rendering the identified static objects into the working frame buffer and the working Z buffer by conducting steps (b)(i)-(iv) for each geometric shape of the static objects;

responsive to rendering the identified static objects, copying the working frame buffer into the background frame buffer, and copying the working Z buffer into the background Z buffer; and

for each frame, rendering the non-static objects into the working frame buffer and the working Z buffer by conducting steps (b)(i)-(iv) for each geometric shape of the non-static objects.

14. The process of claim 13, wherein the step of rendering the nonstatic objects comprises:

for each frame of the frame sequence,

rendering the non-static objects into the working frame buffer and the working Z buffer;

copying the working frame buffer to a pixel-oriented output device for presentation of an image of the scene; and

copying the background frame buffer into the working frame buffer, and copying the background Z buffer into the working Z buffer.

15. A computer--implemented method for rendering a scene comprising a sequence of frames, each having a plurality of geometric shapes and corresponding to a plurality of pixels, the scene having a background of geometric shapes remaining constant for the frame sequence, to support a presentation of an image of the scene, comprising the steps:

(a) initialize a frame number variable, each frame associated with a frame number;

(b) for a selected one of the frame corresponding to the frame number variable, initialize a working frame buffer by copying background data of a background frame buffer to the working frame buffer, the background data defined by a bitmap having values for pixels of the background, the working frame buffer operative to store a bitmap defining values for pixels of the selected frame;

(c) initialize a working Z buffer by copying background depth data of a background Z buffer to the working Z buffer, the background depth data represented by depth values defining distances between a fixed view point reference and geometric shapes at the pixels of the background, the working Z buffer operative to store depth values defining distances between the view point reference and geometric shapes at the pixels of the selected frame;

(d) responsive to initializing the working frame buffer and the working Z buffer, render the selected frame by;

(i) for a selected one of the geometric shapes of the scene, selecting one of the pixels within a set of pixels intersected between the selected geometric shape and the view point reference;

(ii) determining whether the selected geometric shape obscures another one of the geometric shapes at the selected pixel within the set of pixels,

if so, obtaining a value of the selected pixel and storing the selected pixel value within the bitmap of the working frame buffer, and storing within the working Z buffer a depth value defined by a distance between the view point reference and the selected geometric shape at the selected pixel;

(iii) repeating steps (ii) for each remaining pixel of the set of pixels;

(iv) repeating steps (i)-(iii) for each remaining geometric shape;

(e) present an image for the selected frame by copying a bitmap of the updated working frame buffer to a pixel-oriented output device;

(f) increment the frame number variable; and

(g) repeat steps (a)-(f) for each remaining frame.

16. The computer--implemented method of claim 15, wherein the step of initializing the working frame buffer and the working Z buffer comprises the steps:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.

17. The computer-implemented method of claim 15, wherein the step of determining whether the selected geometric shape obscures one of the geometric shapes comprises the steps:

calculating the distance between the view point reference and the selected geometric shape at the selected pixel; and

determining whether the calculated distance is greater than one of the depth values in the working Z buffer at the selected pixel,

if so, then the selected geometric shape obscures the geometric shape at the selected pixel within the set of pixels.

18. The computer-implemented method of claim 15, wherein the step of rendering the selected frame comprises the steps:

(A) for the selected frame of the frame sequence, identifying each geometric shape of the scene, other than the background, which remains static during the frame sequence;

(B) for a selected one of the identified geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected identified geometric shape and the view point reference,

(C) determining whether the selected identified geometric shape obscures another geometric shape at the selected pixel,

if so, obtaining a value of the identified selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

(D) repeating step (C) for each remaining pixel of the set of pixels;

(E) repeating steps (C)-(D) for each remaining geometric shape;

(F) copying the working frame buffer and the working Z buffer to the background Z buffer and the background Z buffer; and

(G) for a selected one of the geometric shapes of the scene, other than the geometric shapes of the background and the static geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected geometric shape and the view point reference,

(H) determining whether the selected geometric shape obscures another geometric shape at the selected pixel,

if so, obtaining a value of the selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

(I) repeating step (H) for each remaining pixel of the set of pixels; and

(J) repeating steps (H)-(I) for each remaining geometric shape.

19. The computer-implemented method of claim 18 further comprising the steps of:

in response to completing step (j), copying the working frame buffer to a pixel-oriented output device; and

copying the background frame buffer into the working frame buffer, and copying the background Z buffer into the working Z buffer.

20. For a computer characterized by a pixel-oriented output device and a memory containing a background frame buffer, working frame buffer, a background Z buffer, and a working Z buffer, a computer-implemented method for rendering a scene comprising a sequence of frames, each having a plurality of polygons and corresponding to a plurality of pixels, the scene having a background of polygons remaining constant for the frame sequence, to support a presentation of an image of the scene on a pixel-oriented output device, comprising the steps of:

initializing the working frame buffer and the working Z buffer by;

(a) for a selected one of the frames, copying background data maintained in the background frame buffer to the working frame buffer, the background data represented by a bitmap defining values for pixels of the background, the working frame buffer operative to store a bitmap defining values for pixels of the frame to be rendered;

(b) for the selected frame, copying background depth data of the background Z buffer to the working Z buffer, the background depth data represented by numerical values defining distances between a view point reference and polygons at the background pixels, the working Z buffer operative to store numerical values defining distances between the view point reference and polygons at the pixels of the frame to be rendered, the view point reference defining a fixed point located in front of the background;

(c) responsive to initializing the working frame buffer and the working Z buffer. rendering the selected frame by;

(i) for a selected one of the polygons, determine a set of the pixels intersected between the selected polygon and the view point reference;

(ii) for a pixel selected from the set of pixels, calculating a distance between the view point reference and the selected polygon at the selected pixel;

(iii) comparing the calculated distance to the numerical value for the polygon at the selected pixel in the working Z buffer;

if the calculated distance is greater than the numerical value for the selected pixel, then repeat step (ii) for one of the remaining pixels of the set of pixels;

otherwise, obtain a value of the selected pixel and store the selected pixel value within the working frame buffer, and store the calculated distance within the working Z buffer;

(iv) repeating steps (ii)-(iii) for each remaining pixel within the set of pixels;

(v) repeating steps (i)-(iv) for each remaining polygon;

(d) presenting the image for the selected frame on the pixel-oriented output device by copying a bitmap of the working frame buffer to the pixel-oriented output device;

(e) selecting a remaining one of the frames in response to presenting the image of the selected frame on the pixel-oriented output device, and repeating steps (a)-(d) for each remaining selected frame.

21. The computer-implemented method of claim 20, wherein the view point reference is located in front of the background and remains fixed for the frame sequence.

22. The computer-implemented method of claim 20, wherein the steps of initializing the working frame buffer and the working Z buffer comprise:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.

23. A computer-readable medium on which is stored a program module for rendering a scene comprising a sequence of frames, each having a plurality of geometric shapes and corresponding to a plurality of pixels, the scene having a background of geometric shapes remaining constant for the frame sequence, the program module comprising computer-executable instructions for performing the steps of:

(a) for a selected one of the frames, initialize the working frame buffer by copying background data maintained in a background frame buffer to the working frame buffer, the background data represented by a bitmap defining values for pixels of a background that remains constant for the frame sequence, the working frame buffer operative to store a bitmap defining values for pixels of the frame to be rendered;

(b) initialize a working Z buffer by copying background depth data of the background Z buffer to the working Z buffer, the background depth data represented by depth values defining distances between a fixed view point reference and geometric shapes at the background pixels, the working Z buffer operative to store depth values defining distances between the view point reference and geometric shapes at the pixels of the frame to be rendered;

(c) for each frame of the frame sequence, identifying each geometric shape of the scene, other than the background, which remains static during the frame sequence;

(d) for a selected one of the identified geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected identified geometric shape and the view point reference,

(e) determining whether the selected identified geometric shape obscures another geometric shape at the selected pixel,

if so, obtaining a value of the identified selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

(f) repeating step (e) for each remaining pixel of the set of pixels;

(g) repeating steps (d)-(f) for each remaining geometric shape;

(h) copying the working frame buffer and the working Z buffer to the background frame buffer and the background Z buffer; and

(i) for a selected one of the geometric shapes of the scene, other than the geometric shapes of the background and the static geometric shapes, selecting one of the pixels within a set of the pixels of the scene intersected between the selected geometric shape and the view point reference,

(j) determining whether the selected geometric shape obscures another geometric shape at the selected pixel,

if so, obtaining a value of the selected pixel and storing the selected pixel value within the working frame buffer, and storing within the working Z buffer a depth value defining a spatial relationship between the selected geometric shape at the selected pixel and the view point reference;

(k) repeating step (j) for each remaining pixel of the set of pixels;

(l) repeating steps (j)-(k) for each remaining geometric shape;

(m) presenting an image for the selected frame on the pixel-oriented output device by copying a bitmap of the updated working frame buffer to the pixel-oriented output device;

(n) responsive to presenting the image, copying the background frame buffer to the working frame buffer and copying the background Z buffer to the working Z buffer; and

(o) repeating steps (i)-(n) for each one of the remaining frames.

24. The computer-readable medium of claim 23, wherein the computer-executable instructions for initializing the working frame buffer and the working Z buffer comprise the steps:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.

25. A computer-readable medium on which is stored a program module for rendering a scene comprising a sequence of frames having background objects, at least one static object, and at least one non-static object, the background objects remaining constant for the frame sequence during a fixed view point reference, each static object remaining constant during the frame sequence, each non-static object changing during the frame sequence, the program module comprising computer-executable instructions for performing the steps of:

loading the background objects into the background frame buffer and the background Z buffer, the background objects defined by pre-rendered background data rendered prior to execution of the program module on the computer;

copying the background frame buffer into the working frame buffer, and copying the background Z buffer into the working Z buffer;

identifying the static objects in the frame sequence;

rendering the identified static objects into the working frame buffer and the working Z buffer;

responsive to rendering the static objects, copying the working frame buffer into the background frame buffer, and copying the working Z buffer into the background Z buffer;

for a selected one of the frames, rendering the non-static objects into the working frame buffer and the working Z buffer; and

copying the working frame buffer to a pixel-oriented output device, coupled to the computer, for presentation of an image of the scene for the selected frame.

26. The computer-readable medium of claim 25, wherein the program module further comprises computer-executable instructions for performing the steps of:

in response to copying the working frame buffer to the pixel-oriented output device, copying the background frame buffer into the working frame buffer, and copying the background Z buffer into the working Z buffer;

for each one of the remaining frames of the frame sequence,

rendering the non-static objects into the working frame buffer and the working Z buffer;

responsive to rendering the non-static objects copying the working frame buffer to a pixel-oriented output device for presentation of an image of the scene for the remaining frame; and

copying the background frame buffer into the working frame buffer, and copying the background Z buffer into the working Z buffer.

27. The computer-readable medium of claim 25, wherein the computer-executable instructions for copying the background frame buffer to the working frame buffer and copying the background Z buffer to the working Z buffer comprise the steps of:

determining regions of the working frame buffer and the working Z buffer that are dirty in response to rendering a prior one of the frames;

defining an overall dirty region representing a union of the dirty regions for the working frame buffer and the working Z buffer; and

copying pixel values corresponding to the overall dirty region from the background frame buffer to the working frame buffer and depth values corresponding to the overall dirty region from the background Z buffer to the working Z buffer.