Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-03-18
2002-10-15
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S422000
Reexamination Certificate
active
06466207
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to imaging rendering and, more particularly, to an improved method, apparatus and computer product for space transformation in an image based rendered scene.
BACKGROUND OF THE INVENTION
Image based rendering (IBR) techniques are efficient ways of rendering real and synthetic objects in a three-dimensional scene. With traditional rendering techniques, the time required to render an image becomes unbounded as the geometric complexity of the scene increases. The rendering time also increases as the shading computations become more complex.
In the simplest IBR technique, one synthesizes a new image from a single input depth image (DI). A DI is an image with z-buffer information stored with each pixel. Hidden surfaces are not included in the input image, and thus the image has an effective depth complexity of one. Shading computations that have been computed for the input image can be reused by subsequent images. Finally, if a depth image is obtained from a real world scene using real images, new views can be created with IBR methods without first creating a traditional geometric representation of the scene.
Because the pixels of an image form a regular grid, IBR computations are largely incremental and inexpensive. Moreover, McMillan, in Leonard McMillan, “A list-priority rendering algorithm for redisplaying projected surfaces”,
UNC Technical Report
, 95-005, University of North Carolina, 1995, presents an ordering algorithm that ensures that pixels in the synthesized image are drawn back to front, and thus no depth comparisons are required. This also permits proper alpha compositing or blending of pixels without depth sorting.
Despite these advantages, there still exist many problems with current IBR methods. For example, if the viewer moves slightly and thereby uncovers a surface, no relevant information is available for this newly unoccluded surface. This occurs because a single DI has no information about hidden surfaces. A simple solution to this problem is the use of more than one input DI. If n input images are used, the size of the scene description is multiplied by n, and the rendering cost increases accordingly. Moreover, with more than one input DI, hidden surface removal must be performed.
Another difficulty arises because the input DI has a different sampling pattern and density than the output image. When mapping the discrete pixels forward from the input DI, many pixels might squeeze together in an output pixel. These pixels must be properly blended for anti-aliasing. Also, forward mapping of the image spreads the pixels apart, creating gaps in the output image. One solution includes performing a backwards mapping from the output image location to the input DI. This is an expensive operation that requires some amount of searching in the input DI. Another solution is to think of the input DI as a mesh of micro-polygons, and to scan-convert these polygons in the output image. This is also expensive, because it requires a polygon scan-convert setup for each input pixel.
The simplest solution to fill gaps in the output image is to predict the projected size of an input pixel in the new projected view, and to “splat” the input pixel into the output image using a precomputed footprint. For the splats to combine smoothly in the output image, the outer regions of the splat should have fractional alpha values and be composed into the new image using an ordering algorithm. This requires the output pixels to be drawn in depth order. But, McMillan's ordering algorithm cannot be applied when more than one input DI is used, and so a depth sort is required.
Nelson Ma in “Rendering trees from precomputed z-buffer views, Sixth Eurographics Workshop on Rendering”,
Eurographics
, June 1995, discusses using layered depth images (LDI) for the purpose of high quality anti-aliasing. LDIs are images that include information of objects that are hidden by foreground objects. In other words, an LDI includes multiple depth layers. Max warps from n input LDIs with different camera information to an output LDI, thereby rendering at about five minutes per frame. This technique generates high quality anti-aliasing of the output picture, but is expensive and cannot run in real time.
The present invention is directed to overcoming the foregoing and other disadvantages. More specifically, the present invention is directed to providing a method, apparatus, and computer product suitable for real-time MBR of objects in a transversable three-dimensional space.
SUMMARY OF THE INVENTION
In accordance with this invention, a method and computer product for rendering real-time three-dimensional images on a display based on viewpoint manipulation of prestored depth images in a global coordinate space is provided.
The method formed in accordance with this invention includes warping pixels from one or more depth images to a layered depth image. The warping of pixels from one or more depth images to a layered depth image is performed by retrieving depth image pixels that correspond to a ray traced location within the layered depth image, comparing the z-value of the retrieved pixels to the z-values of the pixels previouisly stored at z-value layers within the layered depth image at the ray traced locations within the layered depth image that correspond to the retrieved pixels from the depth images, and saving the retrieved pixels in the layered depth image based on the ray traced location and the retrieved pixel's z-value, if no previously stored pixels have a compared z-value that is less than a preset value from the retrieved pixels' z-values. The retrieved pixels are averaged with previously stored pixels in the layered depth image that have compared z-values that are less than a preset value from the retrieved pixel's z-value. The averaged result is saved based on the the ray traced locations and the retrieved pixels' z-values.
In accordance with other aspects of this invention, a method for rendering real-time three-dimensional images from prestored depth images in a global coordinate space on a display based on a viewpoint manipulation is provided. A layered depth image is generated from the prestored depth images based on a predetermined display viewpoint. Then, the generated layered depth image is assigned as the current layered depth image. An output image is generated from the current layered depth image based on the predetermined display viewpoint. Next, it is determined if the display viewpoint of the current layered depth image has been manipulated within the global coordinate space. An output image is generated from the current layered depth image based on the determined display viewpoint, if the display viewpoint has been manipulated and the manipulation is within a predetermined threshold distance from the current layered depth image's viewpoint. A next closest layered depth image is generated, if the display viewpoint has been manipulated and the manipulation is outside the predetermined threshold distance of the current layered depth images viewpoint. An output image is generating from the next closest layered depth image based on the determined display viewpoint and the next closest layered depth image is assigned as the current layered depth image, if the next closest layered depth image has been fully generated.
In accordance with still other aspects of this invention, the generating of an output image from the current and next closest layered depth image includes warping the generated layered depth image based on the manipulated display viewpoint, splatting the pixels from the layered depth image onto the warped image, and generating and displaying an output image based on the splat pixels.
In accordance with further other aspects of this invention, the splatting includes selecting one of two or more splat sizes and splatting pixels based on the splat size selected.
In accordance with still further other aspects of this invention, each splat size comprises a predefined splat mask.
In accordance with still yet fart
Cohen Michael F.
Gortler Steven J.
He Li-wei
Christensen O'Connor Johnson & Kindness PLLC
Microsoft Corporation
Stevenson Philip
Zimmerman Mark
LandOfFree
Real-time image rendering with layered depth images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time image rendering with layered depth images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time image rendering with layered depth images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2962645