Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-04
2001-08-28
Nguyen, Phu K. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06281903
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to graphics processing and display systems and, in particular, to those capable of rendering together for display two dimensional (2D) scene images and three dimensional (3D) objects.
BACKGROUND OF THE INVENTION
The continually increasing complexity of polygonal models for computer display applications has tended to outpace the advances made in hardware technology. As such, the rendering of complex polygonal models, at interactive rates, remains a challenging task. The various techniques developed to address this problem can be classified into three main categories; geometry-based, image-based, and hybrid.
The hybrid method combines the use of three dimensional geometric modeling with two dimensional images in an attempt to draw on the strengths of both the geometry-based and image-based categories. The underlying strategy is to render those parts of the model close to the viewer as geometry, i.e., as a three dimensional (3D) model, and to render more distant visible parts as two dimensional (2D) images. Such schemes offer the advantage of increased performance in cases where geometry-based simplification techniques (e.g., visibility culling) break down, and the rendering time is proportional to the size of the nearby geometry and the number of images used. Moreover, the amount of storage required is considerably reduced as compared to image-based methods. Hybrid techniques are also well suited to the transmission of large models over networks.
To avoid long delays between the time of a request and the subsequent display of the model, adaptive techniques that combine different transmission methods have been proposed. For example, to deliver a 3D scene from a server to a client, a panoramic image of the scene could be transmitted first to provide the client with a quick view of the model. Subsequently, 3D geometric objects are transmitted to progressively replace parts of the panorama as they are received by the client.
One significant problem to be addressed when implementing algorithms that combine images with geometry are so-called ‘occlusion errors’. Occlusion errors occur when previously hidden areas of an image become visible, as objects in the scene move. For example, contrast
FIG. 1A
to
FIG. 1B
, and note the existence of the occlusion errors (OEs) in
FIG. 1B
due to the movement of the objects to the right in the drawing. The occurrence of occlusion errors is objectionable to most users, and can seriously degrade a desired illusion of realism being conveyed by a displayed scene and object(s).
In order to deal with these occlusion errors several strategies have been proposed. A first strategy is based on the use of a “neutral” fill color, while a second strategy is based on an interpolation of the colors of the pixels that surround the occlusion error. A discussion of both of these strategies can be found in a publication by Bengt-Olaf Schneider and Linus Vepstas, Extending VRML to Support Panoramic Images. A third strategy is based on the use of multiple layer images, as proposed by Schaufler et al., Per-Object Image Warping with Layered Impostors, Proceedings of the 9
th
Eurographics Workshop on Rendering, 1998.
Unfortunately, these various strategies typically either yield very rough approximations of the scene behind the objects that have moved, or require a considerable amount of additional storage and non-trivial computation to fill in the gaps resulting from the occlusion errors.
It will become apparent below that a capability to embed data into a 3D geometric object is an important aspect of this invention. It is thus made of record that various techniques for data embedding have been previously investigated for still images, video and audio data, texts, and 3D geometric models. Reference in this regard can be had to: Mintzer et al., Effective and Ineffective Digital Watermarks, Proceedings 1997 International Conference on Image Processing, pp.9-12, 1997; and Memon et al., Protecting Digital Media Content, Communications of the ACM, 41(7), pp. 35-43, 1998.
In the case of 3D models, the annotations of scene description formats such a Virtual Reality Modeling Language (VRML) have been the primary means for adding such information (see Carey et al., The Annotated VRML 2.0 Reference Manual, Addison Wesley, 1997.) More recently, techniques for embedding watermarks into the geometry of models have been proposed by Ohbuchi et al., Watermarking Three Dimensional Polygonal Models Through Geometric and Topological Modifications, Journal of Selected Areas in Communications, 16(4), pp. 551-560, 1998.
However, these known data embedding techniques are generally limited to the encoding of relatively small amounts of information, mainly text, into objects, and are primarily targeted towards security applications, such as copyright protection, theft deterrence, and inventories. In other words, these conventional data embedding techniques do not suggest or provide a solution to the occlusion problem.
OBJECTS AND ADVANTAGES OF THE INVENTION
It is a first object and advantage of this invention to provide an efficient and effective solution to the occlusion problem, and with little or no additional storage cost or computational complexity.
It is a further object and advantage of this invention to provide a technique to encode content information from hidden parts of a scene into visible parts of the scene, and to subsequently retrieve the encoded content information as an arrangement of objects in the visible part of the scene change their spatial relationship relative to the background of the scene, thereby enabling the previously hidden part of the scene to be rendered and thus avoiding the occurrence of an occlusion error or errors.
It is another object and advantage of this invention to provide a technique to encode a specification of a two dimensional background image into a foreground three dimensional geometric object (which could be a polygonal object, or one defined in some other way), and to subsequently retrieve the encoded specification and then render the background image in response to a movement of the foreground object relative to the background scene, thereby avoiding the occurrence of an occlusion error.
SUMMARY OF THE INVENTION
The foregoing and other problems are overcome and the objects of the invention are realized by methods and apparatus in accordance with embodiments of this invention, wherein there is provided a method and apparatus for combining two dimensional (2D) images with three dimensional (3D) polygonal models of objects so as to encode image content information into the 3D objects for efficient rendering and transmission of complex scenes.
In a method for avoiding an occurrence of an occlusion error in a digital data processing system that comprises a display, this invention teaches steps of (a) encoding a specification of a two dimensional background image into at least one three dimensional foreground object that overlies and occludes a portion of the background image; (b) displaying to a viewer the background image and the at least one overlying foreground object; and, in response to a movement of the foreground object that makes a portion of the background image visible to the viewer, (c) displaying the portion of the background image that has become visible. The step of displaying uses the encoded specification that is retrieved from the foreground object.
The three dimensional foreground object is defined using polygons, each having vertices, edges and faces. A polygonal model, or one based on, for example, patches or splines could be used. The step of encoding encodes data from the background image that is comprised of color data and, optionally, depth data that is descriptive of occluded pixels.
The step of encoding could occur at a first data processor (e.g., a server), and the steps of displaying could occur at a second data processor (e.g., a client). In this case the server and client can be coupled together through a data communications network.
For example, and for a case
Martin Ioana M
Schneider Bengt-Olaf
Cameron Douglas W.
International Business Machines - Corporation
Nguyen Phu K.
Perman & Green LLP
LandOfFree
Methods and apparatus for embedding 2D image content into 3D... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for embedding 2D image content into 3D..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for embedding 2D image content into 3D... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2537396