Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-08-31
2003-09-23
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S611000
Reexamination Certificate
active
06624811
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer graphics, and more particularly to constructing primitives for rendering purposes in a computer graphics pipeline.
BACKGROUND OF THE INVENTION
In 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 a surface 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.
Tessellation refers to the process of decomposing the surface into simpler primitives such as triangles or quadrilaterals. The desired size of each primitive may be determined by the transformation of the representation to screen space. Prior Art
FIG. 1
illustrates the results of one example of a representative conventional tessellation, or decomposition, process on a surface
100
. First, a plurality of parallel, equally spaced strip curves
102
are defined in the parameter space of the surface. Such strip curves
102
span a width of the surface
100
and coincide with a plurality of vertices
104
. Strip curves
102
simply refer to any line or curve connecting a plurality of vertices
104
. Thereafter, during an evaluation process, the vertices
104
of adjacent strip curves
102
are connected in a sequential order from one side of the surface to an opposite side. Resulting is a tessellation or group, of a plurality of equally or roughly parametrically sized primitives, i.e. triangles, that are ready to be rendered.
There are numerous evaluation techniques for evaluating a surface in the foregoing manner. Such evaluation techniques include, but are not limited to Homer's Method, De Casteljau, knot insertion, and forward differencing. Prior Art
FIG. 2
illustrates an example of the method associated with forward differencing.
Forward differencing is an efficient technique for the evaluation of a polynomial. As shown in Prior Art
FIG. 2
, the forward differencing of a cubic polynomial is illustrated. The bottom row of circles represents values of the polynomial at equally spaced parameters. The second row represents those values that when added to the first row of values steps the polynomial to the next circle. For a cubic polynomial, the top row of circles, labeled p′″, contain an unchanging constant. Because the top row is constant, the evaluation can start with the first column of four values and derive each subsequent column by performing three additions. One drawback of the use of such forward differencing is the accumulation of round-off error.
Complications arise when using the above forward differencing technique to evaluate adjacent patches, as shown in Prior Art
FIG. 1
Such problems particularly arise when the adjacent patches have a rotated orientation. As shown, when evaluating an area adjacent to an adjoining strip curve
105
between the patches, the value of points
106
along the strip curve
105
may differ from the corresponding values resulting from evaluation of the strip curves
102
of the adjacent patch. In other words, a problem exists in getting the right edge of the left-hand patch
108
to match the strip curve along the left edge of the right-hand patch
110
. The values along the right edge of the left-hand patch
108
are the result of a long series of additions with rounding errors. The values along the corresponding left edge of the right-hand patch
110
are the result of a different series of additions along a single strip curve. Even if these operations are performed in the same floating-point engine, the resulting values and positions do not match. Unfortunately, as a general rule, it is not possible to reorient the patches to avoid this complication which, in turn, results in rendering artifacts in the form of pixel dropouts, double hits and/or cracking.
There is thus a need for a process of evaluating adjacent patches such that the values are consistent, thus avoiding rendering artifacts.
DISCLOSURE OF THE INVENTION
A system, method and article of manufacture are provided for decomposing surfaces using guard curves for rendering purposes during computer graphics processing. Initially, a patch is received. Thereafter, a plurality of strip curves associated with the patch is defined in a first predetermined direction. As such, areas are defined by the strip curves which are adapted for being decomposed into a plurality of primitives. Next, at least one guard curve associated with the patch is generated. The guard curve is positioned along ends of the strips curves and in a second predetermined direction perpendicular with respect to the first predetermined direction in parameter space. Such guard curve is thus adapted to be determined consistent with curves on edges/boundaries of adjacent patches.
In use, the guard curve prevents vertex mismatches when tessellating adjacent curved surfaces into triangles. In particular, the guard curve ensures decomposition of the patch consistent with a curve of an adjacent patch. As an option, the areas defined by the strip curves may be adapted for being decomposed into a plurality of primitives using forward differencing.
In one embodiment of the present invention, a reversed strip curve may be generated in a third predetermined direction parallel and opposite with respect to the first predetermined direction. An area defined by one of the strip curves in the first predetermined direction and the reversed strip curve may then be tessellated using reverse stitching.
In one aspect of the present invention, a plurality of guard curves are generated, and a distance between the guard curves is determined based on a size of a vertex memory into which vertices of the primitives are loaded. As an option, a length of the guard curve is also determined based on the size of the vertex memory into which vertices of the primitives are loaded. Still yet, the guard curve may include position values, normal values, or any other vertex components such as color or texture coordinates.
These and other advantages of the present invention will become apparent upon reading the following detailed description and studying the various figures of the drawings.
REFERENCES:
patent: 4912659 (1990-03-01), Liang
patent: 5283860 (1994-02-01), Einkauf et al.
patent: 5363478 (1994-11-01), Fiasconaro
patent: 5377320 (1994-12-01), Abi-Ezzi et al.
patent: 5428718 (1995-06-01), Peterson et al.
patent: 5488684 (1996-01-01), Gharachorloo et al.
Article “Towards Hardware Implementation of Loop Subdivision” by Stephan Bischoff et al. Proceedings 2000 SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware Aug. 2000. Publisher ACM Press pp.:41-50 Series-Proceeding-Article.*
Article “Drawing Antialiased Cubic Spline Curves” Author R. Victor Klassen Xerox Corp., Webster, NY Publisher ACm Press New York, NY, USA pp.: 92-108 Periodical-Issue-Article Year of Publication: 1991 ISSN:0730-0301.
Legakis Justin
Moreton Henry P.
NVIDIA Corporation
Santiago Enrique L
Silicon Valley IP Group
Zilka Kevin J.
Zimmerman Mark
LandOfFree
System, method and article of manufacture for decomposing... 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 decomposing..., 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 decomposing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3007233