Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-09-05
2004-03-09
Zimmermann, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S506000
Reexamination Certificate
active
06704010
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer graphics, and more particularly to rendering triangular patches in a computer graphics-processing pipeline.
BACKGROUND OF THE INVENTION
In conventional computer graphic systems, rendering and displaying three-dimensional graphics typically involves many calculations and computations. For example, to render a three-dimensional object, a set of coordinate points or vertices that define the object to be rendered must be formed. Vertices can be joined to form polygons, or primitives, that define the surface of the object to be rendered and displayed. Groups of polygons may be generated using patches. A patch is a mathematical description of a surface that may be sampled by evaluating a collection of the vertices.
Once the vertices that define an object are formed, the vertices must be transformed from an object or model frame of reference to a world frame of reference and finally to two-dimensional coordinates that can be displayed on a flat display device. Along the way, vertices may be rotated, scaled, eliminated or clipped because they fall outside the viewable area, lit by various lighting schemes, colorized, and so forth.
A general system
100
that implements such a pipelined procedure is illustrated in Prior Art FIG.
1
. In this system, a tessellator
102
is adapted to use patches to calculate vertices and form triangles. The transform/lighting module
106
may be used to perform scaling, rotation, and projection of a set of three dimensional vertices from their local or model coordinates to the two dimensional window that will be used to display the rendered object. The transform/lighting module
106
also sets the color and appearance of a vertex based on various lighting schemes, light locations, ambient light levels, materials, and so forth.
System
100
further includes a rasterization module
108
that rasterizes or renders triangles that have previously been transformed and/or lit. The rasterization module
108
renders the object to a rendering target which can be a display device or intermediate hardware or software structure that in turn moves the rendered data to a display device.
Traditionally, the tessellator
102
has been equipped to handle quadrilateral patches. Thus, when a triangular patch is encountered, prior art system
100
may employ a trimming module
104
which converts, or “trims,” the output of tesselator to produce a triangular subset of the usual quadrilateral collection of triangles.
FIG. 2
illustrates an exemplary result of the trimming performed by trimming module
104
. In use, the tensor product tessellator
102
is designed to evaluate the entire parameter space [0 . . . 1]×[0 . . . 1], wherein the triangle is only defined on the lower triangular sub-domain. Thus, the output of the tessellator
102
must be trimmed to the triangular domain. It should be noted that in the example of
FIG. 2
, the relative placement of control points are only approximate. As shown, a triangular patch
200
would be directly rendered by evaluating the triangular patch
200
with the surface (patch) parameters varying from (0,0) to (1,0) and (0,1) at the corners, forming a triangle. A tensor product patch
202
is directly rendered by evaluating the quadrilateral patch
202
with the surface parameters varying from (0,0) to (1,1) at the diagonally opposite corner forming a square. To render a triangular patch
200
using tensor product hardware, it must be converted to tensor product form (using algebra) and then the conventional tensor product hardware must be prevented from rendering its usual full square.
An alternate approach to the solution of
FIG. 2
is shown in FIG.
2
A. As shown, the technique
204
maps the triangular patch to an equivalent degenerate tensor product that needs no trimming. The problem with this approach is that is results in a poor pattern of tessellation (many sliver triangles). In addition to the poor quality of the tessellation pattern the mapping used results in a parametric singularity. This is a problem because the parametric derivatives (one of the derivatives is undefined at the singularity) of the patch are typically used to compute normal vectors that are subsequently used for lighting. The result is that triangular patches rendered using this technique have a lighting artifact at one corner (the location of the singularity).
While the trimming module
106
and the alternate approach perform a necessary task, the various associated operations can be complex and require a great deal of computing time and overhead. Sometimes, the extra computations are even done when they are not even necessary. Therefore, it is desirable to have a computer graphics system that is capable of providing the rasterization module
108
with triangles without performing conventional prior art trimming operations or other alternate cumbersome approaches.
DISCLOSURE OF THE INVENTION
A system, method and article of manufacture are provided for converting triangular patches into a form suitable for being rendered using a graphics pipeline adapted to render quadrilateral patches. First, a triangular patch is received. The received triangular patch is then divided into a plurality of quadrilateral patches. Such quadrilateral patches are suitable for being processed by a graphics pipeline specifically equipped to render quadrilateral patches.
While triangular patches are used less frequently than quadrilateral patches, or tensor products, they are in use in the graphics community and it is important to be able to render them efficiently. The present invention provides a method for rendering such triangular patches that does not require additional hardware support for trimming operations, and delivers improved performance.
In one embodiment of the present invention, each quadrilateral patch may be convex. As an option, one corner of each quadrilateral patch may be positioned at a midpoint of a side of the triangular patch. Further, one corner of each quadrilateral patch may optionally be positioned at a centroid of the triangular patch.
In another embodiment of the present invention, each side of the quadrilateral patches may be linear in parameter space. Also, a degree of the triangular patch may be preserved after being divided into a plurality of quadrilateral patches.
REFERENCES:
patent: 5133049 (1992-07-01), Cain et al.
patent: 5546515 (1996-08-01), Mochizuki
patent: 5774124 (1998-06-01), Itoh et al.
patent: 6198488 (2001-03-01), Lindholm et al.
patent: 6211883 (2001-04-01), Goel
patent: 6304265 (2001-10-01), Haris et al.
patent: 6456287 (2002-09-01), Kamen et al.
Cao Huedung X.
NVIDIA Corporation
Silicon Valley IP Group PC
Zilka Kevin J.
Zimmermann Mark
LandOfFree
System, method and article of manufacture for rendering... 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, method and article of manufacture for rendering..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and article of manufacture for rendering... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241184