Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-10-22
2003-09-30
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S502000
Reexamination Certificate
active
06628282
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to the viewing a scene of a 3D environment stored in a server machine from a client machine at a location remote from the server machine. More specifically, the present invention relates to viewing a scene of a 3D environment stored in a server machine from a client machine remote from the server machine where the client machine uses previous views of the scene to predict a next view and the server machine sends only a difference between the predicted view and the next view to the client machine for the client machine to form the next few.
BACKGROUND OF THE INVENTION
The steadily increase of computing power promises a wide variety of compelling multimedia experiences for users in the next decade. One often-stated goal is the development of shared virtual worlds and entertainment broadcasts that allow consumers to remotely explore 3D spaces. However, the speed of the Internet and other broadcast media cannot keep up with the demand for available bandwidth, if thousands of users are to have high-fidelity access to remote worlds. To address this issue, the present invention presents a class of compression schemes designed to significantly reduce the bandwidth required for remote navigation.
In a typical setup, amuser explores a virtual world on a client machine. This machine requests views of the world from a server machine. Sending the entire model over the network in advance is extremely slow, or impossible for dynamic scenes; one solution is to send each camera view from the server to the client for each frame as a compressed image. This solution will still require high network bandwidth to display video at interactive frame rates.
The present invention presents a novel compression scheme that predicts the appearance of new views from previous views, using the known camera motion and image-based rendering techniques. This allows the server to send only incremental amounts of information for each frame, greatly reducing the bandwidth required for remote navigation. Unlike most image compression schemes, this method is cooperative: the client and server can communicate to determine the data for the server to send to the client in each frame that maximizes quality of service for a given available bandwidth.
It is assumed that available network resources in the coming decade will lag far behind increasing processor power, and will be the limiting factor on navigation frame rates. Thus, some additional computation required for each frame is acceptable.
The present invention is based on image-based rendering, in which images are used as primitives rather than 3D models. (See [Sing Bing Kang. A Survey of Image-based Rendering Techniques. Technical Report 97/4. Digital Equipment Corporation Cambridge Research Laboratory, August 1997, incorporated by reference herein] for a survey.) Many authors have described image-based techniques for utilizing temporal coherence to reduce rendering latency; for example, see [Shenchang Eric Chen, Lance Williams, View Interpolation for Image Synthesis.
SIGGRAPH
93, August 1993, p279-288]; Shenchang Eric Chen. QuickTime VR—an image-based approach to virtual environment mapping.
SIGGRAPH
95, August 1995, p29-38]; Jay Torborg, Jim Kajiya. Talisman: Commodity Realtime 3D Graphics for the PC,
SIGGRAPH
96, 1996, p353-363]; Jonathan Shade, Dani Lischinski, David Salesin, Tony DeRose, John Snyder. Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments.
SIGGRAPH
96, p75-82]; Lucia Darsa, Bruno Costa, and Amitabh Varshney, Navigating Static Environments Using Image-Space Simplification and Morphing.
ACM Symposium on Interactive
3
D Graphics
, Providence, R.I., 1997, pp. 25-34; Francois Sillion, George Drettakis, and Benoit Bodelet. Efficient Impostor Manipulation for Real-Time Visualization of Urban Scenery. Computer Graphics Forum (Proc. of Eurographics '97). September, 1997. p207-218, all of which are incorporated by reference herein]. Regan and Pose [Matthew Regan, Ronald Pose. Priority Rendering with a Virtual Reality Address Recalculation Pipeline.
Computer Graphics
(
SIGGRAPH
94
Conference Proceedings
). 1994, incorporated by reference herein] use an image-based approach to overcome high network latencies. In these systems, reference images are generated and sent to the client system. The client then reprojects these images to generate new views at interactive rates until the next set of reference images arrive. [Brook Conner and Loring Holden. Providing a Low Latency User Experience In a High Latency Application
ACM Symposium on Interactive
3
D Graphics
, Providence, R.I., 1997, pp. 45-48, incorporated by reference herein] discusses techniques for hiding the effects of latency in a shared world. These methods are complementary to the approach of the present invention, since they address latency rather than bandwidth.
Two commercial products, Apple QuickTime VR 3.0 [Apple Computer, Inc., QuickTime VR 3.0. http://www.apple.com/quicktime, incorporated by reference herein] and LivePicture ImageServer [Live Picture, Inc., http://www.livepicture.com/, incorporated by reference herein] send panoramas over the network in pieces, so that the client may view the scene without having to receive the entire panorama. However, a large portion of the panorama must be downloaded before much viewing can begin. Also, these systems are not easily extensible to handle dynamic imagery or camera translations.
The approach presented in the present invention is an image-compression scheme, based on specialized a prior knowledge about the images. Compare, for example, the multiscale compression schemes [Peter Burt, Edward Adelson. The laplacian pyramid as a compact image code.
IEEE Transactions on Communications
, 31(4):532-540, April 1983, incorporated by reference herein] and [Wim Sweldens. The lifting scheme: A custom-design construction of biorthogonal wavelets. Technical Paper 1994:7, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1994, incorporated by reference herein] , which use prediction and difference. This work is designed for a cooperative client-server approach, similar to [Marc Levoy. Polygon-Assisted JPEG and MPEG Compression of Synthetic Images.
SIGGRAPH
95, (August 95), p21-28, incorporated by reference herein]. The MPEG compression scheme [D. Le Gall, MPEG: A Video Compression Standard for Multimedia Application.
Communications of the ACM
, Vol. 34, No. 4, April 1991, p46-58, incorporated by reference herein] uses optical flow to predict video frames, for replaying prerecorded video. Chang et al. [Ee-chien Chang, Chee Yap, T. J. Yen. Realtime Visualization of Large Images over a Thinwire.
IEEE Visualization
'97 (Late Breaking Hot Topics). Tucson, Ariz., 1997, incorporated by reference herein] use foveation, a spatially-varying compression scheme for remote viewing of very large 2D images. This is a generalization of wavelets, that allows an image to be displayed at different resolutions at different locations. In this system, the server sends only the image coefficients necessary to update the view of a static, 2D space.
A panorama viewer (such as QuickTime VR) takes a source image or “environment map”, projects it into view space using a view transform (for example, using a cylindrical or spheric projection), and then displays this projected image on the screen. This technique can be used to create an impression of a navigable 3D environment. Most panorama viewers assume a fixed camera position, and navigation is performed using a combination of rotations and scales. Translations are done by jumping from one panorama to another. For example, LivePicture [Live Picture, Inc., http://www.livepicture.com/, incorporated by reference herein] has created nested panoramas, allowing the user to zoom in and be transferred from one panorama to another.
Source images for panora
Biermann Henning
Hertzmann Aaron
Meyer Jon
Perlin Kenneth
Cao Huedung X.
New York University
Schwartz Ansel M.
Zimmerman Mark
LandOfFree
Stateless remote environment navigation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Stateless remote environment navigation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stateless remote environment navigation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3046728