Clustered backface culling

Details Clustered backface culling Clustered backface culling

2000-04-17

2003-06-03

Vo, Cliff N. (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S423000

Reexamination Certificate

active

06573895

ABSTRACT:

TECHNICAL FIELD
The present invention is related in general to three-dimensional graphics imaging, and, in particular, to a method and system for culling (removing) polygons that face in a direction away from a viewpoint (backface) when an image is rendered on a graphics device.
BACKGROUND
Shaded rendering of polygonal models at interactive frame rates has been a core research area of Computer Graphics since its inception. Contemporary workstations and personal computers with hardware z-buffer graphics accelerators are capable of rendering several million triangles a second. However, advances in graphics accelerators have constantly been outpaced by the demands of applications; models with several tens or hundreds of million polygons are routinely encountered, for example, in the design and evaluation of mechanical systems such as cars and airplanes. Approaches to the large model rendering problem concentrate on identifying a minimal subset of polygons that represents the given model, and rendering only this subset. One long-used technique is backface culling, whereby only the polygons facing in the direction of the viewpoint are rendered.
The rendering pipeline of common graphics accelerators consists, roughly speaking, of two stages: a transform stage that transforms 3D vertex and normal data by a 4×4 matrix to view coordinates, and a rasterizer stage that produces shaded pixels and places them into a frame buffer. Also, polygonal data typically resides in RAM and has to be transferred to the graphics accelerator by some means, e.g. the system bus.
Considering the transfer/transform/rasterizer pipeline, traditional hardware-based backface culling operates after the transform stage and before the rasterizer stage. Pipeline throughput is limited by its slowest stage; if this happens to be the rasterizer, then backface culling may improve overall graphics performance by up to a factor of two, as half of all polygons face away from the viewer, on average. However, if the pipeline bottleneck is presented by the transfer or transform stage, as is not uncommon for contemporary graphics accelerators, then backface culling may have no effect on performance, or even be detrimental. In these cases it is desirable to perform backface culling on the host CPU, before sending data to the graphics accelerator. The traditional single-polygon backface culling test, however, takes time linear in the number of polygons, and proves impractical for this purpose, even if the test is accelerated, as described in Zhang et al.,
Fast Backface Culling Using Normal Masks
, ACM Symposium of Interactive 3D Graphics, Providence, 1997.
In order to perform backface culling in sub-linear time, it is necessary to have a single test decide upon the orientation of a whole cluster of polygons. Such a test has to be conservative and identify clusters that are guaranteed to only contain back facing polygons; any cluster for which this fact cannot be established, or that contains at least one front facing polygon, must be rendered. Thus, culling effectiveness for clusters of polygons is smaller than for single polygons, and polygons that are actually back facing may erroneously be sent to the graphics accelerator (but will consequently be culled by the accelerator).
For simple models, clusters of back facing polygons may be identified by hand, as described in J. Foley et al.,
Computer Graphics—Principles and Practice
, Second Ed., Addison Wesley, 1990. Consider, for example, a cube centered at the origin, with faces perpendicular to the coordinate axes. If the eye point of a perspective view is located in the positive octant, then the three faces with negative normal coordinates are all back facing. This relationship can easily be established for each of the eight octants, and the result stored in a lookup table. At rendering time, this table is indexed with the octant in which the eye point is located.
Manually constructed tables are clearly impractical for all but very simple and/or symmetric polyhedra. Aspect graphs, as described in Z. Gugus et al,
Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects
, IEEE Trans. on PAMI, vol. 13, pp. 542-51, 1991, subdivide space into cells that correspond to eye point equivalence classes with respect to face visibility. However, for a polyhedron with N faces, there are worst case O(N
9
) cells, which makes such a general indexing technique impractical.
For convex polyhedra, Tanimoto,
A Graph
-
Theoretic Real
-
Time Visible Surface Editing Technique
, SIGGRAPH 7, pp 223-228, suggests an algorithm that incrementally updates the object space outline separating back facing and front facing polygons, using frame to frame coherency. For general polyhedra, Kumar et al.,
Hierarchical Back
-
Face Computation
, Eurographics Workshop on Rendering, 1996, proposes a cluster culling test based on the explicit construction of an object space cell that contains all eye points for which the cluster is back facing. Such a construction is awkward, and the ensuing space subdivision consumes considerable time and memory.
SUMMARY OF THE INVENTION
The present invention is directed to a backface culling technique which operates on two-dimensional surfaces, or polygons, such as triangles, quadrilaterals, and the like, or groups ofa these arranged as tristrips, trifans, quadstrips, or meshes. In the present invention, collections of these two-dimensional polygons are arranged into clusters. Each cluster is bounded by up to eight bounding planes, one for each octant of the 3D Cartesian coordinate space within which an eye point may lie. Portions of a cluster on one side of each bounding plane may then be culled.
In one aspect of the invention, two existing clusters are joined together to form a single cluster based on whether a backface culling probability of the single cluster exceeds a predetermined value related to the weighted backface culling probabilities of the two individual clusters and a value related to the incremental cost of rendering an additional cluster.
In yet another aspect of the invention, the center of each cluster is shifted to provide it with a local coordinate system and a new eye point to increase the accuracy of the backface culling process.
In yet another aspect of the invention, the memory requirements for the present backface culling test are relatively low, taking about 40 bytes per test, assuming single precision floating point.
In another aspect of the invention, the backface tests are arranged hierarchically, and frontface tests are added for symmetry, the frontface tests consuming only an additional 4 bytes per test.


REFERENCES:
patent: 5861885 (1999-01-01), Strasnick et al.
patent: 6061065 (2000-05-01), Nagasawa
patent: 6307555 (2001-10-01), Lee
patent: 6201542 (2002-03-01), Arai et al.

Affiliated with

Also associated with

Rating

Clustered backface 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 Clustered backface culling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clustered backface culling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3136902