Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-05-23
2003-12-16
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S623000
Reexamination Certificate
active
06664975
ABSTRACT:
FIELD OF INVENTION
The present invention relates to the field of processing scene graphs used in the display of computer-generated images. More specifically, the present invention relates to a method and apparatus for quickly and accurately creating well-behaved affine transformations of bounding spheres.
BACKGROUND OF THE INVENTION
Computer graphics is used in a wide variety of applications, such as in business, science, animation, simulation, computer-aided design, process control, electronic publication, gaming, medical diagnosis, etc. In an effort to portray a more realistic real-world representation, three-dimensional objects are transformed into models having the illusion of depth and displayed onto a two dimensional computer screen. Conventionally, polygons are used to construct these three-dimensional objects. Next, a scan conversion process is used to determine which pixels of a computer display fall within each of the specified polygons. Thereupon, texture is selectively applied to those pixels residing within specified polygons. In addition, hidden or obscured surfaces are eliminated from view. Finally, lighting shading, shadowing, translucency, and blending effects are applied.
For a high-resolution display, having over a million pixels, displaying a three-dimensional scene on a computer system is mathematically intensive and requires tremendous processor power. Furthermore, the computer system must be extremely fast to handle dynamic computer graphics, for example, displaying a three-dimensional object in motion. Even more processor power is required for interactive computer graphics, whereby three-dimensional images change in response to user input. Still more processor power is required to achieve a scene with more intricate details.
Given the tremendous demands that rendering scene graphs places on the processor. the number of complex mathematical computations performed should be kept to a minimum. One conventional alternative to performing complex mathematical operations is using mathematical shortcuts to estimate parameters. However, these shortcuts often fail to yield accurate results.
An example of this problem is calculating which portion of the object or scene graph needs to be displayed on the computer monitor. Conventionally, a bounding volume, which is stored in the scene graph, is compared with a viewer frustum or viewpoint. If they intersect. the computer displays the portion of the scene graph which corresponds to the bounding volume. If they do not intersect, there is no need to process the details of the un-displayed portion of the scene graph. During conventional image processing, the size and shape of the bounding volume is altered by a transform matrix. This matrix rotates, translates, squashes, or scales the object, as well as the bounding volume. It is computationally very difficult to arrive at the size and shape of the altered bounding volume. Conventionally, the exact size of a bounding sphere around the altered bounding volume may be calculated. However, this can require complex mathematical operations, such as solving a cubic polynomial. Another conventional method is to estimate the size of the bounding sphere. However, estimation is sometimes mathematically intensive, and mathematical shortcuts are often inaccurate. For example, some conventional methods produce accurate results for only a limited class of transform matrices.
Therefore, a need exists for a method and apparatus for obtaining a bounding sphere for the ellipsoid that results when an affine transformation matrix operates on a bounding volume. The method and apparatus needs to be computationally fast, as well as accurate for any type of affine transform matrix.
SUMMARY OF THE INVENTION
The present invention relates to a method and apparatus for obtaining a bounding sphere for the ellipsoid that results when an affine transformation matrix transforms a bounding volume. The present invention accomplishes this by using Gershgorin intervals to obtain a new radius for the bounding volume. The invention operates on a scene graph, which is comprised of a number of nodes arranged in a hierarchical organization. At least one of these nodes is an affine transformation matrix, which is used for operations such as rotations, scaling, and translations. Associated with the transformation matrix is a bounding sphere. The present invention calculates the radius of a new bounding sphere that encircles the ellipsoid formed when the affine matrix transforms the old bounding volume. The use of Gershgorin intervals is fast and yields accurate results. Thus, the present invention provides for a method and apparatus that is computationally fast and produces a well-behaved affine transformation of bounding spheres.
In another embodiment, the present invention compares the transformed bounding sphere with a viewer frustum to decide whether to display the corresponding portion of the scene graph and whether to continue traversing down the scene graph. Thus, the present invention provides a method and apparatus for fast and accurate rendering of scene graphs.
REFERENCES:
patent: 5757321 (1998-05-01), Billyard
Brier Jeffery
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Cheap well-behaved affine transformation of bounding spheres does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cheap well-behaved affine transformation of bounding spheres, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cheap well-behaved affine transformation of bounding spheres will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3134293