Method and apparatus for determining visible surfaces
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
27 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19)
-
-
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. - View Dependent Claims (21, 22)
-
-
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. - View Dependent Claims (24)
-
-
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. - View Dependent Claims (26, 27)
-
Specification