Backface primitives culling

Details Backface primitives culling Backface primitives culling

1998-07-06

2002-03-19

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

C345S423000, C345S427000, C345S619000, C345S623000

Reexamination Certificate

active

06359629

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of computer generated graphics. More specifically, the present invention relates to methods of increasing efficiency of rendering two-dimensional images of three-dimensional objects in computers.
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 publishing, 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 for display onto a two-dimensional computer screen. This is accomplished by using a number of polygons to represent a three-dimensional object. 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. Finally, lighting, shading, shadowing, translucency, and blending effects are applied.
For a high resolution display (1280×1024) having over a million pixels, for which values must be generated for each and every pixel, displaying a three-dimensional scene on a computer system is a rather complicated task. Processes like lighting, shading, shadowing, texture mapping, blending, etc., are particularly computation intensive, requiring a tremendous amount of processing power. Indeed, even more processing power is necessary for displaying interactive computer graphics, where 3-D images change in response to a user input (e.g. flight simulation). Naturally, the more complex the scene, the more processing power will be required to render that scene.
Although throughput of computer graphics systems has increased considerably in recent years, the size and complexity of three-dimension scenes have been growing even faster. Scenes composed of millions of polygons are no longer uncommon. In light of the enormous processing power necessary to generate highly-complex scenes and the limitations in the speed of currently available hardware, there have been efforts to develop more efficient methods to simplify the task of rendering images of three-dimensional objects. One such method is known as visibility culling or occlusion culling. Simply put, visibility culling limits the number of polygons rendered in each frame by removing hidden or obscured surfaces from the graphics pipeline. When these hidden surfaces are culled away, highly complex scenes can be rendered at a very high rate.
One well known method for reducing computational workload without sacrificing rendering accuracy is known as backface culling. The backface culling method is validated by the fact that polygons facing away from the viewer must be invisible and thus can be omitted from further graphics processing. Typically, the backface test involves calculating the dot product between the polygon's normal and the view vector formed from any point on the polygon to the viewing point. If the result is positive then the polygon is facing towards the viewer. If the result is negative then the polygon is facing away from the viewer and may be removed from the graphics pipeline.
Although conventional backface culling methods are efficient in reducing the number of polygons that are sent down to the graphics pipeline, performance gain is somewhat limited as a tremendous amount of computational power is required to determined which polygons are backfacing and which polygons are visible. To this end, numerous methods have been proposed to reduce the computational overhead of conventional backface culling methods. One such method is proposed by Zhang et al. in “Fast Backface Culling Using Normal Masks”, ACM Symposium, 1997. The method described by Zhang et al. makes use of a bitmask to represent a normal direction per polygon, and then compares the bitmask to a backface mask. The polygon is culled if the bitmask is covered by the backface mask.
The method described in Zhang et al., however, does not address the problem that each polygon is individually tested and processed. While that method is useful in high-end graphics computer systems, it is not as useful in lower-end models where computational bandwidth is limited. Thus, what is needed is a method and apparatus for accelerating interactive rendering of complex scenes. What is further needed is a method and apparatus for performing visibility culling that is capable of efficiently removing backfacing polygons with minimal computational effort.
SUMMARY OF THE PRESENT DISCLOSURE
The present invention is a method and apparatus for performing visibility culling that is capable of efficiently removing backfacing polygons with minimal computational effort. More specifically, in one embodiment of the present invention, a bounding cone of all the normal vectors of each primitive in the model is calculated during a pre-processing phase. A center vector and an apex angle of the bounding cone is then stored in association with the primitive. Thereafter, during rendering, the bounding cone associated with the primitive is then tested against a visible half-space defined by a viewing vector. If the bounding cone intersects the visible half-space, the primitive is considered visible, and is sent down the graphics pipeline. However, if the bounding cone does not intersect the visible half-space, the primitive is considered backfacing, and is culled. That is, the primitive is not sent down the graphics pipeline.
According to another embodiment of the present invention, during a pre-processing phase, for each primitive, P, having a plurality of normal vectors, the normal vectors are classified with respect to a tessellation, T, of a unit sphere. In particular, a normal bit-vector, N, comprising n-bits and wherein each bit corresponds to one facet of the tessellation, T, is used to represent the directions of the normal vectors. Particularly, in this embodiment, a bit of the normal bit-vector, N, is set to 1 if the facet corresponding to that bit intersects one of the normal vectors of P; and the bit is set to 0 if the corresponding facet does not intersect one of the normal vectors of P. Thereafter, during the rendering stage, a visibility bit-vector is computed. The visibility bit-vector also comprises n-bits wherein each bit corresponds to one facet of the tessellation T. A bit of the visibility bit-vector is set to 1 if a corresponding facet lies within the visible half-space of the viewing vector; and the bit is set to 0 if the corresponding facet does not lie within the visible half-space of the viewing vector. Then, before sending a primitive to the graphics pipeline, the normal bit-vector of the primitive calculated in the preprocessing phase is bitwise added with the visibility bit-vector. In this embodiment, primitives are culled according to the results of the comparison.


REFERENCES:
patent: 5357600 (1994-10-01), Shirman et al.
patent: 5583974 (1996-12-01), Winner et al.
patent: 5734806 (1998-03-01), Narayanaswami
patent: 5751291 (1998-05-01), Olsen et al.
patent: 5757321 (1998-05-01), Billyard
patent: 5764228 (1998-06-01), Baldwin
patent: 5825363 (1998-10-01), Anderson
patent: 5920687 (1999-07-01), Winner et al.
patent: 5977979 (1999-11-01), Clough et al.
patent: 5982376 (1999-11-01), Abe et al.
Zhang et al. “Fast Backface Culling Using Normal Masks.” ACM Symposium on 3D Graphics, Providence, 1997.
Kumar et al. “Interactive Display of Large Scale Trimmed NURBS Models.” Proceedings of the 1995 ACM Symposium on Interactive 3D Graphics, Monterey, CA, 1995.

Affiliated with

Also associated with

Rating

Backface primitives culling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Backface primitives culling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Backface primitives culling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2834025