Bounding volume for 3D graphic primitives

Details Bounding volume for 3D graphic primitives Bounding volume for 3D graphic primitives

1998-12-10

2001-06-05

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

06243097

ABSTRACT:

BACKGROUND
1. Field of the Present Invention
The present invention generally relates to 3D graphics and more particularly to a system and method for bounding 3D graphic primitives to reduce the probability of failing to detect a trivial accept or trivial reject without significantly increasing the complexity of the bounding volume.
2. History of Related Art
Graphics display subsystems are almost universally encountered in microprocessor based computer systems to facilitate a variety of graphics tasks and applications. Graphics processors, graphics adapters, and a variety of similarly designed computer products provide specialized hardware to speed the execution of graphics instructions and rendering of graphic images. These processors and adapters typically include, for example, circuitry optimized for translating, rotating, and scaling 3D graphic images. In a typical application, a graphical image that is displayed on a display terminal or other output device is composed of one or more graphic primitives. For purposes of this disclosure, a graphic primitive may be thought of as one or more points, lines, or polygons that are associated with one another, such as by being connected to one another. Typically, the displayed image is generated by creating one or more graphic primitives, assigning various attributes to the graphic primitives, defining a viewing point and a viewing volume, determining which of the graphic primitives are within the defined viewing volume, and rendering those graphic primitives as they would appear from the viewing point. This process can require a tremendous amount of computing power to keep pace with the ever increasingly complex graphics applications that are commercially available. Accordingly, designers of graphics systems and graphics applications are continuously seeking cost effective means for improving the efficiency at which graphic images are rendered and displayed.
A significant portion of any graphic application is typically consumed determining what portions, if any, of a graphic primitive are within the viewing volume. If a graphic primitive is only partially within a specified viewing volume, a clipping process must be performed on the graphic primitive to eliminate the portion of the graphic primitive exterior to the viewing volume. If the graphic primitive is completely exterior to the viewing volume, further consideration of the primitive is unnecessary. If the graphic primitive is completely within the viewing volume, the rendering process may be initiated without performing any clipping. Thus, it will be appreciated by those experienced in computer graphics that determining a graphic primitive's spatial relationship to a viewing volume provides an opportunity to eliminate a potentially significant amount of processing. Unfortunately, the process of determining whether a graphic primitive is within a specified viewing volume is typically either undesirably time consuming or undesirably inaccurate. If a graphic primitive is thought of as a collection of vertices, an accurate but potentially time consuming method of determining whether the primitive is within a viewing volume includes simply determining whether each vertex of the primitive is within the viewing volume. For extremely simple graphic primitives comprised of relatively few vertices, such a direct method is preferred for its simplicity and accuracy. This direct method, however, quickly becomes burdensome as the complexity of the primitive increases. If, for example, the graphic primitive includes thousands of vertices, the direct approach will require thousand of comparisons, as each vertex is compared to the boundaries of the viewing volume using well known line clipping techniques.
The time required to complete the comparison process can be made essentially independent of the complexity of the graphic primitive if the primitive is approximated by a simple geometric shape referred to as a bounding volume that encloses the entire primitive. Regardless of the complexity of the graphic primitive that it encloses, the bounding volume is defined by a relatively few vertices. In a common application, for example, the bounding volume is the smallest rectangular parallelepiped that completely encloses the primitive. Regardless of the complexity of the primitive, this bounding volume has only eight vertices. Accordingly, a routine can quickly determine if the bounding volume is within the viewing volume by comparing just eight points to the boundaries of the viewing volume. The problem with such a simplistic bounding volume is the accuracy of the comparison results. If the graphic primitive is irregularly shaped, the simple bounding volume does a poor job of approximating the graphic primitive's shape and use of the simple bounding volume to determine whether the graphic primitive is within a viewing volume may result in a failure to detect a trivial accept or trivially reject condition. The penalty for failing to detect such trivial accept/reject conditions can be significant, especially in applications that include complex graphic primitives. Accordingly it is highly desirable to introduce a method and system for reducing the probability of failing to detect a trivial accept/reject condition without significantly impacting the performance of the trivial accept/reject process.
SUMMARY OF THE INVENTION
The problems identified above are in large part addressed by a method and system for creating and utilizing a modified bounding volume that strikes a balance between the accuracy of testing for trivial acceptance/rejection by checking each vertex of a graphic primitive and the speed of determining trivial acceptance/rejection by utilizing a rectangular parallelepiped bounding volume. By marginally increasing the complexity of the bounding volume a significant improvement is achieved in reducing the probability of failing to detect a trivial acceptance or rejection of a graphic primitive when constructing a particular graphic image.
Broad speaking, the present invention contemplates a method of bounding a graphic primitive. An initial bounding volume, such as a rectangular parallelepiped, is defined by the graphic primitive's maximum and minimum x, y, and z coordinates in an initial coordinate system. A first bounding volume is then defined by the graphic primitive's maximum and minimum x′, y′, and z′ coordinates in a first coordinate system, where the first coordinate system is transformed with respect to the initial coordinate system. Preferably this transformation comprises a 45° rotation about a common axis shared by the initial and first coordinate systems. The initial bounding volume and the first bounding volume are then intersected to form a modified bounding volume that provides a more accurate approximation of the graphic primitive than either the initial bounding volume or the first bounding volume. The vertices of the modified bounding volume are then available for use in determining whether the graphic primitive may be trivially rejected or accepted within a specified viewing volume.
Preferably, the process of defining the first bounding volume includes applying the first transformation to each vertex of the graphic primitive to produce a transformed graphic primitive. A transformed bounding volume is then defined by maximum and minimum x, y, and z values of the transformed graphic primitive in the initial coordinate system. The transformed bounding volume is comprised of a plurality of transformed vertices. An inverse of the first transformation is then applied to each of the transformed vertices to transform the first bounding volume to a common coordinate system with the initial bounding volume. In one embodiment, the method further includes defining a second modified bounding volume by intersecting the initial bounding volume with a second bounding volume defined by the graphic primitive's maximum and minimum x″, y″, and z″ values in a second coordinate system. The second coordinate system is determined

Affiliated with

Also associated with

Rating

Bounding volume for 3D graphic primitives does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bounding volume for 3D graphic primitives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounding volume for 3D graphic primitives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2457376