Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-01-30
2001-10-16
Zimmerman, Mark (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06304265
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer graphics systems and, more particularly, to a system and method for differentiating front facing graphics primitives from back facing graphics primitives in a computer graphics system.
2. Discussion of the Related Art
Computer graphics systems are commonly used for displaying graphical representations of objects on a two-dimensional video display screen. Current computer graphics display systems provide highly detailed representations and are used in a variety of applications. A computer graphics display system generally comprises a central processing unit (CPU), system memory, a graphics machine and a video display screen.
In typical computer graphics display systems, an object to be presented on the display screen is broken down into graphics primitives. Primitives are basic components of a graphics display and may include points, lines, vectors and polygons (e.g., triangles and quadrilaterals). Typically, a hardware/software scheme is implemented to render, or draw, the graphics primitives that represent a view of one or more objects being represented on the display screen.
Generally, the primitives of the three-dimensional object to be rendered are defined by the host CPU in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitive in terms of the X, Y and Z coordinates of its vertices, as well as in terms of the red, green, blue and alpha (R, G, B and &agr;) color values of each vertex. Alpha is a transparency value. Additional primitive data may be used in specific applications. Rendering hardware interpolates the primitive data to compute the display screen pixels that represent each primitive, and the R, G, B and &agr; values for each pixel.
The graphics machine generally includes a geometry accelerator, a rasterizer, a frame buffer controller and a frame buffer. The graphics machine may also include texture mapping hardware. The geometry accelerator receives vertex data from the host CPU that defines the primitives that make up the view to be displayed. The geometry accelerator typically comprises a transform component which receives vertex data from the CPU, a clipping component, an illumination component, and a plane equations component. The transform component performs transformations on the vertex data received from the CPU, such as rotation and translation of the image space defined by vertex data. The clipping component clips the vertex data so that only vertex data relating to primitives that make up the portion of the view that will be seen by the user is kept for further processing. The illumination or lighting component calculates the final colors of the vertices of the primitives based on the vertex data and based on lighting conditions. The plane equations component generates floating point equations which define the image space within the vertices. The floating point equations are later converted into fixed point equations and the rasterizer and texture mapping hardware generate the final screen coordinate and color data for each pixel in each primitive.
The operations of the geometry accelerator are computationally very intense. One frame of a three-dimensional (3-D) graphics display may include on the order of hundreds of thousands of primitives. To achieve state-of-the-art performance, the geometry accelerator may be required to perform several hundred million floating point calculations per second. Furthermore, the volume of data transferred between the host computer and the graphics hardware is very large. Additional data transmitted from the host computer to the geometry accelerator includes illumination parameters, clipping parameters and any other parameters needed to generate the graphics display.
Various techniques have been employed to improve the performance of geometry accelerators. These including pipelining, parallel processing, reducing redundancy, minimizing computations, etc. by or in a geometry accelerator. Indeed, the processing of graphics information is generally so computationally intense that virtually any method of speeding up this process is desirable. One way of improving the throughput of a geometry accelerator is to minimize the overall amount of data that must be processed by it. For example, this can be done by minimizing redundancy in the data being sent to the geometry accelerator. This may also be accomplished by eliminating data sent to the geometry accelerator that relates to graphics information that will not be displayed on the display. For example, if data relates to graphics information that is outside the viewing window of the display, or relates to graphics information that is behind the eye of the viewer, then the geometry accelerator need not process that data.
Another known manner of reducing the data sent to the geometry accelerator for processing is achieved eliminating unnecessary processing of data that, although within the graphics display window (or field of view), is to be culled or otherwise not displayed. For example, in a completely enclosed surface constructed from polygons with a consistent orientation, none of the back facing polygons are visible (as they are always obscured by the front-facing polygons). In such an instance, drawing speed may be increased by culling, or discarding, such polygons as soon at they are determined to be back facing. For example, OpenGL (which is a widely used graphics API that is rapidly becoming an industry standard), offers a robust, yet flexible, programming interface, and permits a graphics programmer to specify whether to enable culling non-visible primitives of a graphics image.
Importantly, and as it relates to the present invention, a computer graphics system often needs to determine whether a polygon or other graphics primitive is a front facing or back facing polygon. For example, in an OpenGL environment, if culling is enabled, then as soon as a graphics primitive is determined to be back facing, it may be discarded and not further processed by the graphics pipeline (e.g., the geometry accelerator).
By convention, polygons whose vertices appear in counterclockwise order on the screen are called front-facing (although this convention may be reversed through an OpenGL command). Stated another way, the decision of whether a face of a polygon is front facing or back facing is determined by the sign of the area of the polygon. Several, less than optimal, ways are presently known to make this computation. For example, OpenGL specifies a process of differentiating front and back facing primitives/polygons by transforming them to window coordinates, and then performing the area calculation in window coordinates (clipped or unclipped). One way that OpenGL specifies computing this area is through the equation:
a
=
1
2
∑
i
=
0
n
-
1
x
i
y
i
⊕
1
-
x
i
⊕
1
y
i
,
(Equation 1)
where x
i
and y
i
are the x and y window coordinates of the ith vertex of the n-vertex polygon, and i⊕1 is (i+1) mod n.
Unfortunately, one disadvantage of this approach is that it necessarily results in excessive work to be done and needless computations to be performed. Specifically, this approach requires that the system perform a transformation to window coordinates and, in most graphics systems, clipping is performed before the transformation to window coordinates. For polygons that are later determined to be back facing, and thus not visible, these additional steps and computations are wasted and thus consume additional processor time.
Another known approach for determining front facing and back facing polygons utilizes a dot product computation of a normal vector to the polygon. The normal vector is typically derived from the cross-product of two vectors formed from three consecutive vertices of the polygon and the vector <0,0,1> or <0,0,−1>, depending upon whether the coordinate system is left or right handed. The calculation of the normal vector is performed in ob
Harris Kathleen A.
Jensen Kimberly Wagner
Hewlett--Packard Company
Padmanabhan Mano
Zimmerman Mark
LandOfFree
System for distinguishing front facing and back facing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for distinguishing front facing and back facing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for distinguishing front facing and back facing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600257