 |
Claims  |
|
|
What is claimed is:
1. A patch division unit for converting a set of control points for a current patch into a set of control points for a new patch, wherein the patch division unit comprises:
an X-curve division unit coupled to a patch buffer to receive current x coordinates for the set of control points for the current patch, and configured to convert the current x coordinates into new x coordinates for the control points of the new
patch;
a Y-curve division unit coupled to the patch buffer to receive current y coordinates for the set of control points for the current patch, and configured to convert the current y coordinates into new y coordinates for the control points of the new
patch; and
a Z-curve division unit coupled to the patch buffer to receive current z coordinates for the set of control points for the current patch, and configured to convert the current z coordinates into new z coordinates for the control points of the new
patch;
wherein each of the curve division units is further configured to receive an operation type signal and configured to generate coordinates for (a) a left subpatch if the operation type signal indicates a left child operation, (b) a right subpatch
if the operation type signal indicates a right sibling operation, and (c) a parent patch if the operation type signal indicates a parent operation.
2. The patch division unit of claim 1, wherein each of the curve division units generates coordinates for left subpatch control points L.sub.0i, L.sub.1i, L.sub.2i, L.sub.3i, 0.ltoreq.i.ltoreq.3, from coordinates of parent patch control points
P.sub.0i, P.sub.1i, P.sub.2i, P.sub.3i, 0.ltoreq.j.ltoreq.3, in accordance with equations L.sub.0i =P.sub.0i, L.sub.1i =(P.sub.0i +P.sub.1i)/2, L.sub.2i =(P.sub.0i +2P.sub.1i +P.sub.2i)/4, and L.sub.3i =(P.sub.0i +3P.sub.1i +3P.sub.2i +P.sub.3i)/8 for
0.ltoreq.i.ltoreq.3.
3. The patch division unit of claim 1, wherein each of the curve division units generates coordinates for right subpatch control points R.sub.0i, R.sub.1i, R.sub.2i, R.sub.3i, 0.ltoreq.i.ltoreq.3, from coordinates of left subpatch control points
L.sub.0i, L.sub.1i, L.sub.2i, L.sub.3i, 0.ltoreq.i.ltoreq.3, in accordance with equations R.sub.0i =L.sub.3i, R.sub.1i =-L.sub.2i +2L.sub.3i, R.sub.2i =L.sub.1i -4L.sub.2i +4L.sub.3i, and R.sub.3i =-L.sub.0i +6L.sub.1i -12L.sub.2i +8L.sub.3i for
0.ltoreq.i.ltoreq.3.
4. The patch division unit of claim 1, wherein each of the curve division units generates coordinates for parent patch control points P.sub.0i, P.sub.1i, P.sub.2i, P.sub.3i, 0.ltoreq.i.ltoreq.3, from coordinates of right subpatch control points
R.sub.0i, R.sub.1i, R.sub.2i, R.sub.3i, 0.ltoreq.i.ltoreq.3, in accordance with the equations P.sub.3i=R.sub.3i, P.sub.2i =-R.sub.3i +2R.sub.2i, P.sub.1i =R.sub.3i -4R.sub.2i +4R.sub.1i, and P.sub.0i =-R.sub.3i +6R.sub.2i -12R.sub.1i +8R.sub.0i for
0.ltoreq.i.ltoreq.3.
5. The patch division unit of claim 1, wherein each of the curve division units is coupled to store new coordinates for the control points of the new patch in the patch buffer, wherein coordinates are stored in the patch buffer with a fixed
precision, wherein the curve division units are coupled to store extra precision bits for left and right subpatch coordinates in a stack, and wherein the curve division units are coupled to the stack to receive extra precision bits with the current
coordinates from the patch buffer.
6. The patch division unit of claim 1, further comprising:
a W-curve division unit coupled to a patch buffer to receive current w coordinates for the set of control points for the current patch, and configured to convert the current w coordinates into new w coordinates for the control points of the new
patch;
a opacity-curve division unit coupled to a patch buffer to receive current opacity coordinates for the set of control points for the current patch, and configured to convert the current opacity coordinates into new opacity coordinates for the
control points of the new patch;
a red-curve division unit coupled to a patch buffer to receive current red color coordinates for the set of control points for the current patch, and configured to convert the current red color coordinates into new red color coordinates for the
control points of the new patch;
a blue-curve division unit coupled to a patch buffer to receive current blue color coordinates for the set of control points for the current patch, and configured to convert the current blue color coordinates into new blue color coordinates for
the control points of the new patch;
a green-curve division unit coupled to a patch buffer to receive current green color coordinates for the set of control points for the current patch, and configured to convert the current green color coordinates into new green color coordinates
for the control points of the new patch;
wherein each of the curve division units is further configured to receive an operation type signal and configured to generate coordinates for (a) a left subpatch if the operation type signal indicates a left child operation, (b) a right subpatch
if the operation type signal indicates a right sibling operation, and (c) a parent patch if the operation type signal indicates a parent operation.
7. The patch division unit of claim 6, further comprising:
a D-curve division unit coupled to a patch buffer to receive current shading coordinates for the set of control points for the current patch, and configured to convert the current shading coordinates into new shading coordinates for the control
points of the new patch;
a U-curve division unit coupled to a patch buffer to receive current first texture coordinates for the set of control points for the current patch, and configured to convert the current first texture coordinates into new first texture coordinates
for the control points of the new patch;
a V-curve division unit coupled to a patch buffer to receive current second texture coordinates for the set of control points for the current patch, and configured to convert the current second texture coordinates into new second texture
coordinates for the control points of the new patch;
wherein each of the curve division units is further configured to receive an operation type signal and configured to generate coordinates for (a) a left subpatch if the operation type signal indicates a left child operation, (b) a right subpatch
if the operation type signal indicates a right sibling operation, and (c) a parent patch if the operation type signal indicates a parent operation.
8. The patch division unit of claim 1, wherein each of the curve division units comprises:
a set of four registers which includes a first register, a second register, a third register, and a fourth register, wherein each of the four registers is configured to receive and store a common first control point value; and
a set of three operation units which includes a first operation unit, a second operation unit, and a third operation unit, wherein each of the three operation units is configured to receive a subsequent control point value, a control point
number, and an operation type;
wherein the first operation unit is coupled to read the first register's contents and coupled to write a result to the second register wherein when the control point number is one, the first operation unit is configured to (a) multiply the
subsequent control point value by three, add the first register's contents, divide by eight, and store the result in the second register if the operation type is left-child, (b) multiply the subsequent control point value by negative three, add double
the first register's contents, multiply by four, and store the result in the second register if the operation type is right-sibling, and (c) multiply the subsequent control point value by six, subtract the first register's contents, and store the result
in the second register if the operation type is parent;
wherein the second operation unit is coupled to read the second register's contents and coupled to write a result to the third register, wherein when the control point number is one, the second operation unit is configured to (a) multiply the
subsequent control point value by two, add the second register's contents, divide by four, and store the result if the operation type is left-child, (b) subtract the subsequent control point value from the second register's contents, multiply by four,
and store the result if the operation type is right-sibling, and (c) multiply the subsequent control point value by negative four, add the second register's contents, and store the result if the operation type is parent, wherein when the control point
number is two, the second operation unit is configured to (a) multiply the subsequent control point value by three, divide by eight, add the second register's contents, and store the result if the operation type is left-child, (b) multiply the subsequent
control point value by six, add the second register's contents, and store the result if the operation type is right-sibling, and (c) multiply the subsequent control point value by negative twelve, add the second register's contents, and store the result
if the operation type is parent; and
wherein the third operation unit is coupled to read the third register's contents and coupled to write a result to the fourth register, wherein when the control point number is one, the third operation unit is configured to (a) add the subsequent
control point value to the third register's contents, divide by two, and store the result if the operation type is left child, (b) multiply the third register's contents by two, subtract the subsequent control point value, and store the result if the
operation type is right-sibling, and (c) multiply the subsequent control point value by two, subtract the third register's contents, and store the result if the operation type is parent, wherein when the control point number is two, the third operation
unit is configured to (a) divide the subsequent control point value by four, add the third register's contents, and store the result if the operation type is left-child, (b) add the subsequent control point value to the third register's contents and
store the result if the operation type is right sibling, and (c) multiply the subsequent control point value by four, add the third register's contents, and store the result if the operation type is parent; wherein when the control point number is
three, the third operation unit is configured to (a) divide the subsequent control point value by eight, add the third register's contents, and store the result if the operation type is left-child, (b) subtract the subsequent control point value from the
third register's contents and store the result if the operation type is right-sibling, and (c) multiply the subsequent control point value by eight, add the third register's contents, and store the result if the operation type is parent. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of systems for converting object representations to images for graphical display, and in particular to a system for rendering a surface represented by a set of Bezier patches.
2. Description of the Related Art
There is a growing interest in the graphics, vision, and manufacturing communities to be able to acquire and digitally reproduce the shape and external appearance of objects for the purpose of transmission, display, and numerically controlled
fabrication. This would have applications in product design, fast prototyping, reverse engineering, and digitizing shapes for the visual simulation, animation, and entertainment industries. Current advancement in laser range scanners now offers a
promising methodology for fully-automated model acquisition of arbitrary objects. Several million points scanned on an arbitrary object can be converted easily into an irregular mesh of polygons. These polygons are then preferably converted into a
parametric surface representation, which is a more compact and manipulable form. U.S. patent application Ser. No. 08/810,256 (atty. docket # 5201-05100) titled "System and method for parametric surface representation of objects using high order
surface patches" filed Mar. 3, 1997, and authored by Nishit Kumar et al. provides a fully automated method for converting a polygonal representation into a set of Bezier patches. A method for rendering these patches is now desirable. A Bezier patch is
a two-dimensional Bezier curve. A Bezier curve is defined by the following equation: ##EQU1## where g.sub.i, 0.ltoreq.i.ltoreq.n, are control points as shown in FIG. 1A. The result is a curve that is formed by a weighted sum of the control points. In
cubic form, equation (1) can be represented by the following matrix equation: ##EQU2## where G.sub.c is a column vector containing the Bezier curve control points. If G.sub.c is parameterized in order to vary as a function of a second coordinate t, this
gives the two-dimensional surface: ##EQU3## Realizing that for 3rd order Bezier curves, G.sub.1 (t) can be expressed in the matrix equation
an expanded form of equation (3) can be written ##EQU4##
Equation (5) is the matrix form of a bicubic Bezier patch. An example of such a patch is shown in FIG. 1B. Equation (5) is decomposable into three equations of the same form, one equation for each coordinate axis of the control points. For
example, equation (5) could be written as
and
A generalization of the Bezier patch referred to as a "rational Bezier patch" is often used. A rational Bezier patch has a fourth equation
which is used in determining the equation of the points of the surface in the following way: the (x,y,z) points on the surface patch are given by ##EQU5## where 0.ltoreq.s,t.ltoreq.1.
Three properties of Bezier patches are noted here. A Bezier patch is completely contained within the convex hull formed by the control points which define the patch. One exemplary consequence of this is that it may be determined that a patch is
not within the screen boundaries if none of the control points is within the screen boundaries. A desired affine transformation (e.g. rotation, translation, magnification) of a Bezier patch may be achieved by applying the transformation to the control
points. An exemplary consequence of this is that the transformation may be applied before the patch is rendered, thereby providing a significant decrease in the associated computation. Finally, an affine transformation may be applied to the s,t
parameters of a Bezier patch without inducing any variation in the patch. These three properties will be used in later discussion.
In addition to the surface coordinates of an object, Bezier patches may be used to represent other aspects of the object. Examples include patches which provide values for the normal to the surface (N), the direction of the light source (L), the
direction of reflected objects (R), the surface color and opacity of an object (R,G,B,A), and the coordinates of a texture image to be mapped onto the surface (U,V). In addition to these primary attribute patches, secondary attribute patches may also be
associated with an object for special effects. All of these attribute patches must be rendered during the rendering of the surface to provide realism and a variety of special effects.
The usage of Bezier patches advantageously provides a method for compact) high-quality representation of objects. This method also allows for efficient execution of affine transformations on the object. It is desirable to have a method for
converting Bezier patches into sets of triangles or other polygons for which established graphics rendering hardware exists.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a high order surface patch rendering system with adaptive tessellation. A patch is rendered by subdividing a patch until the subpatches are sufficiently flat that they can be approximated
by a quadrilateral. To subdivide a patch, the patch rendering system uses a patch division unit which accepts the control points of a patch and divides the patch in half by determining the control points of a subpatch. The relationship of the patch to
it's subpatches is that of a binary tree, where every patch division produces two subpatches which may themselves be subject to patch division. In one embodiment, the patch division unit is able to traverse the binary subdivision tree in three
directions (parent to left-child, left-child to right-sibling, and right-sibling to parent) to minimize memory requirements.
The present invention contemplates a patch division unit for converting a set of control points for a current patch into a set of control points for a new patch. The patch division unit comprises a set of curve division units. An X-curve
division unit is coupled to a patch buffer to receive current X coordinates for the set of control points for the current patch, and configured to convert the current X coordinates into new X coordinates for the control points of the new patch. A
Y-curve division unit is coupled to the patch buffer to receive current Y coordinates for the set of control points for the current patch, and configured to convert the current Y coordinates into new Y coordinates for the control points of the new patch. A Z-curve division unit is coupled to the patch buffer to receive current Z coordinates for the set of control points for the current patch, and configured to convert the current Z coordinates into new Z coordinates for the control points of the new
patch. Each of the curve division units is further configured to receive an operation type
signal and configured to generate coordinates for (a) a left subpatch if the operation type signal indicates a left child operation, (b) a right subpatch if the operation type signal indicates a right sibling operation, and (c) a parent patch if
the operation type signal indicates a parent operation.
BRIEF DESCRIPTION OF THE DRAWINGS
Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:
FIG. 1a shows an example of a cubic Bezier curve having four control points;
FIG. 1b shows an example of a bicubic Bezier patch having sixteen control points;
FIG. 2a shows a computer system which graphically renders surface patches;
FIG. 2b shows an architecture of a computer system which graphically renders surface patches;
FIG. 3 shows a functional schematic of a graphics rendering pipeline using a method for rendering surface patches;
FIG. 4 shows a flowchart of the method for rendering surface patches;
FIG. 5 illustrates a patch subdivision process;
FIG. 6 shows a patch subdivision tree;
FIG. 7 illustrates a de Casteljau technique for performing a patch subdivision;
FIG. 8 illustrates a variation of the de Casteljau technique which may be used to determine the control points of a right sibling subpatch;
FIG. 9 illustrates a variation of the de Casteljau technique which may be used to determine the control points of a parent surface patch;
FIG. 10 illustrates the relationships between corner points of a parent surface patch and the right and left subpatches;
FIG. 11 illustrates a subdivision of a line which has been classified as straight;
FIG. 12 illustrates a method for storing flags indicative of the straightness of base edges for a surface patch;
FIG. 13 illustrates a test for straightness of an edge;
FIG. 14 illustrates an alternate test for straightness of an edge;
FIG. 15 is a block diagram of a patch tessellator;
FIG. 16 illustrates the configuration of a patch buffer unit;
FIG. 17 illustrates the configuration of a patch division unit;
FIG. 18 illustrates the interface of the patch division unit;
FIG. 19 is a block diagram of a homogeneous coordinate unit;
FIG. 20 illustrates the interface of a flatness test unit;
FIG. 21A is a block diagram of a flatness test unit;
FIG. 21B is a block diagram of a flatness test unit;
FIG. 22 illustrates the interface of a cull unit;
FIG. 23 is a block diagram of a cull unit;
FIG. 24 is a scheduling table for operations in the cull unit;
FIG. 25 illustrates the interface of a corner unit;
FIG. 26 is a block diagram of a corner unit;
FIG. 27 illustrates the configuration of a stack;
FIG. 28 is a block diagram of a projection unit; and
FIG. 29 is a scheduling table for operations in the projection unit.
While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will
herein be described in detail. It should be understood, however, that the drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the intention is to cover all
modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.
DETAILED DESCRIPTION OF THE INVENTION
The following references are hereby incorporated by reference as though entirely and completely set forth herein:
E. Catmull, A Sub-division algorithm for computer display of curved surfaces, Computer Science, University of Utah, UTEC-CSc-74-133, December 1974.
G. Farin, Curves and surfaces for CAGD, a practical guide, Academic Press, 1992.
J. D. Foley, et al., Computer graphics, principles and practice, Addison Wesley Publishing Company, 1990.
S. Lien, M. Shantz, and V. Pratt, "Adaptive forward differencing for rendering curves and surfaces, Computer Graphics," vol. 21, no. 4, July 1987, pp. 111-117.
M. Shantz and S. Lien, "Shading bicubic patches," Computer Graphics, vol. 21, no. 4, July 1987, pp. 189-196.
Alan Watt and Mark Watt, Advanced animation and rendering techniques, theory and practice, Addison Wesley Publishing Company, 1992.
FIG. 2a shows a computer system 10 having a graphics display card 12 which is connected to a graphics display 14. As shown in FIG. 2b, graphics display card 12 includes a floating point unit 28, a patch tessellator 30, and a rasterizer 32.
These units are coupled together to implement a graphics rendering pipeline, as will be discussed further below. Computer system 10 also includes a CPU 20, a bus bridge 22, a system memory 24, a bus 26, and video memory 34. During the course of
operation, computer system will display objects on display 14 via video memory 34. These objects may be represented in the form of Bezier surface patches. Graphics display card 12 operates to render these Bezier surface patches according to the present
invention.
It is noted that computer system 10 is programmable and that in one embodiment, instructions for configuring computer system 10 to operate as described herein may be stored in read-only memory (not shown) or on a storage medium (also not shown).
These instructions would then be retrieved and transferred to a processing unit which would then perform the function of patch tessellator 30.
In FIG. 3, a rendering pipeline 100 for rational Bezier patches is shown. This rendering pipeline implements a method for converting rational Bezier patches describing the surface of an object, hereafter called surface patches, into a set of
triangles. Associated with the surface patches are various attribute patches, e.g., normal patches, RGBA patches, texture patches, half-vector patches, light patches, and reflection vector patches. Normal patches indicate the direction of the normal to
the surface patch at each point. RGBA patches indicate the color and opacity of the patch at each point. Texture patches indicate coordinates of an image to be "painted" on a patch. Normal, RGBA, and texture patches are invariant, and may be
predetermined and provided along with the surface patches as input. Half-vector patches are an average of the viewing vector and the normal vector at each point on the surface patch. Light patches indicate the direction of incident light at each point
on the surface patch. Reflection patches indicate the reflection vector at each point on the surface patch. Half-vector, light vector, and reflection vector patches are dependent on the viewing angle, and must be computed after the orientation
transformation has been applied to the surface and normal patches. It is noted that for special effects, secondary RGBA and texture patches may also be associated with a surface patch.
Rendering pipeline 100 receives surface, normal, RGBA, and texture patches 102 at functional block 104. The operations of functional block 104 are preferably performed by a CPU or floating point unit, and the operations include: (i) transforming
the surface patches to provide a desired perspective, (ii) transforming the normal patches associated with the surface patches, (iii) computing attribute patches for reflection vectors, diffuse color and halfway vector, and (iv) clipping surface patches
and corresponding attribute patches such that surface patches fit within 1+e times height and width of viewing screen, where e is a predetermined fraction of the screen dimensions. As mentioned in the background section, the transformations (i) and (ii)
may be applied to the patch control points. The computation of the half-vector, light vector, and reflection vector attributes patches may be performed from the surface patch using Coon's patch as will be described further below. The clipping
operations (iv), which are performed to facilitate fixed point computations in functional block 106, are preceded by a location test which may use the convex hull property of the Bezier patch control points. As output, functional block 104 provides
transformed (and clipped if appropriate) surface and attribute patches. These patches are forwarded to functional block 106.
The operations of functional block 106 include: (i) culling of surface patches and the corresponding attribute patches, (ii) flatness and linearity of shading tests, (iii) tessellations of patches, (iv) computation of coordinates and normal at
corners of patches, and (v) specular color computation. In functional block 106 the patches are tessellated into a set of triangles, based on flatness and linearity of shading, as will be described further below. Also in functional block 106, culling
and clipping operations are applied to the surface and attributes patches, so that patches which are back-faced or not visible are discarded. The result of the tessellation operations of functional block 106 is a list of triangles with color and texture
coordinates at the vertices, and this result is stored in memory buffer 108, and thereafter forwarded to rasterizer 110. Rasterizer 110 also accepts triangles with color and texture coordinates at the vertices from a polygon tessellator 112. Functional
block 106 directly forwards the output from polygon tessellator 112 to the rasterizer 110. Rasterizer 110 then provides a sequence of image pixel data suitable for display. The image pixel data may be converted to a video signal by a RAMDAC (random
access memory digital to analog converter) video memory.
Referring back to FIG. 2b with continued reference to FIG. 3, floating point unit 28 may be used to implement functional block 104, patch tessellator 30 may be used to implement functional blocks 106 and 108, and rasterizer 32 may be used to
implement functional block 110. Floating point unit 28 would then provide transformed patches, transformed triangles, and various commands to the patch tessellator 30. Patch tessellator 30 provides projected triangles or quadrilaterals to rasterizer
32, and rasterizer 32 provides texture, color, and z coordinates to video memory 34.
Turning now to FIG. 4 where a flowchart of the rendering method is shown, the operations of functional block 106 are discussed in greater detail. In functional block 106, the method begins with step 202 where the corner points of the original
patch are computed. After this step, the term "patch" is used to refer to both the original patch (the first iteration) and to subpatches of the original patch (in any subsequent iterations). In step 204 a test is made to determine if the patch can be
culled, i.e. if the patch is back-faced, and in step 206, a test is made to determine if the patch is outside the viewing window. If the answer to either of these is true, then in step 208 the patch is discarded. After the discard, in step 210, a test
is performed to determine if any subpatches are in the stack. If not, the method concludes in step 212 having completely rendered the original patch. If there are subpatches in the stack, then in step 214 the subpatch parameters are retrieved, and the
method returns to step 204.
If both the tests in steps 204, 206 are false, then in step 216 a test is made to determine if the patch is flat, and in step 218 a test is made to determine if the shading of the patch has a linear variation. If either test is false, i.e., if
the surface patch is not flat and/or the shading variation is not linear in pitch, then in step 220 the patch is subdivided (along with the associated attribute patches). After the patch is subdivided in step 220, in step 222 new corner points for the
subpatches are calculated, and one of the subpatches is placed on the stack. The method then returns to step 204 with the remaining subpatch. If both tests in steps 216, 218 are true, i.e., the surface patch is flat and the shading variation is linear
in pitch, then in step 224 then patch is divided into triangles and written out. The method then proceeds to step 210 where, as discussed before, a test is made to determine if the stack is empty.
A patch is considered flat if all the curves forming the patch are straight lines within a given user specified tolerance bound. Similarly, a patch is considered linearly shaded if all the curves forming the RGBA patch are straight lines within
a given user specified tolerance bound. If the flatness or linear shading condition is not satisfied, the patch is subdivided along the s or t direction. The subdivision process for a patch is shown in FIG. 5. Operations and computations performed in
the rendering pipeline are now individually discussed in greater detail.
Patch Subdivision
In FIG. 5, patch A is subdivided along s direction into left patch B and right patch C. Patch B is called a left child of patch A while patch C is called a right sibling of patch B. Patch A is called a parent of patches B or C. Similar operations
are performed for patch B and C. When a patch meets flatness and linearity of shading criteria, the patch is divided across any two diagonal corners to form triangles. These triangles are then written out, i.e. the spatial and color coordinates of the
triangles are forwarded to the memory buffer and from there to the rasterizer. Once a patch is written out in the form of triangles, its right sibling is generated. For example, once patch B is written out, patch C (right sibling of B) is then
generated. Once patch C is also written out in the form of triangles, the triangles representing patches B and C may be combined to form patch A. This completes tessellation of patch A as both subpatches B and C have been written out in the form of
triangles. The above described process is repeated recursively for all the patches.
A typical subdivision process is shown in the form of subdivision tree in FIG. 6. The order of traversal of the tree is:
Preferably, the subdivision direction alternates, e.g. s, then t, then s. However, once a patch has been determined to be flat in one direction, it is no longer subdivided in that direction, i.e. if a patch is flat in the s direction, it is not
thereafter subdivided in the s direction. Rather, all subdivisions will be in the t direction until the t direction has also been determined to be flat. In FIG. 6, patches A, C, G, H are subdivided along s direction and patch B is subdivided along t
direction.
A subdivision process for bicubic patches is now described. A bicubic patch is formed by four cubic curves. Subdividing a bicubic patch is equivalent to subdividing each of the four cubic curves. A subdivision process based on the de Casteljau
algorithm is described in FIG. 7. This algorithm can be derived from the affine transform properties of Bezier patches. Here, p.sub.0, p.sub.1, p.sub.2 and p3 are the four control points of an original cubic curve and l.sub.0, l.sub.1, l.sub.2 and
l.sub.3 are the four control points of a subdivided left cubic curve. A value is determined at each node by taking the average of the two inputs. These operations result in the following control point values for the cubic curves of the left child.
##EQU6##
It is noted that for fixed point representation of control points, these equations indicate that the 0, 1, 2 and 3 least significant bits of l.sub.0, l.sub.1, l.sub.2, and l.sub.3, respectively, can be stored in the stack. These bits can then be
retrieved from the stack and attached to the least significant positions of the left child control points before computing the control points of the right sibling as described next.
Turning to FIG. 8, a method is described for determining the right sibling control points r.sub.0, r.sub.1, r.sub.2, and r.sub.3, from left child control points l.sub.0, l.sub.1, l.sub.2, and l.sub.3. A value is determined at each node by
doubling the left input and subtracting the right input. These operations result in the following control point values for the cubic curves of the right sibling.
The above operations are performed after returning precision bits from the stack to the least significant positions of the left sibling control points. After these operations, the 3, 2, 1, and 0 least significant bits of r.sub.0, r.sub.1,
r.sub.2, and r.sub.3, respectively, may be stored in the stack to be used later for computing the parent patch if necessary (e.g. to regenerate the control points for the parent patch so that the control points for the as-yet-unrendered right sibling of
the parent patch may be obtained). The control points of the parent patch can be obtained from the control points r.sub.0, r.sub.1, r.sub.2, and r.sub.3, of the right sibling using computations as described by FIG. 9. A value is determined for each of
the nodes by doubling the right input and subtracting the left input. These operations give following values for the control points of the parent patch.
In repeated subdivisions, it sometimes occurs that the sign of a re-calculated parent patch control point is lost. To prevent this from occurring, a sign bit is stored on the stack with the precision bits. When the precision bits are retrieved
and used to calculate a new patch, the sign bits are used to replace the calculated sign bits.
The subdivision process requires that, in addition to the control points, the coordinates and normals of the new corner points of the patches be computed. This is done as follows. If the coordinates of the corner points of patch A are
A.C.sub.00, A.C.sub.0n, A.C..sub.n0, and A.C.sub.nn as shown in FIG. 10, and the normals are A.N.sub.00, A.N.sub.0n, A.N.sub.n0, and A.N.sub.nn, then after a subdivision along s, the new corner points are now
Similarly, the normals are
Therefore, only two new corner points are computed for each subdivision. Since patch B may be tessellated (i.e. subdivided) further, the corner points of patch C are pushed into stack which are retrieved when the tessellations of patch B have
been completed and patch C is ready to be computed for tessellations. If patch A is subdivided along i direction, the corner points are now
Similarly, the normals are
If an edge is classified as linear, the new corner points may be computed as shown in FIG. 11. The curve v1,vm,v2 is presumed to be linear. The new corner point vp corresponding to vm is computed as
where
Patch Flatness
A 4-bit flag called an edge flag is used to store linearity classification of edges for a patch. The bits of the edge flag may be associated with specific edges of a patch as shown in FIG. 12. After a subdivision along the s direction, the edge
flag for the left child is initialized from the parent edge flag according to edge&0111. Similarly, for the right child, the edge flag is initialized according to edge&1011. For subdivision along the t direction, the edge flag for the left child is
initialized to edge&1101, and for the right child edge&1110. Three bits of the edge flag are thereby determined, and the fourth bit which corresponds to the new edge is set according to the results of a straightness test. Since the left child may be
tessellated further the edge flag for the right child is pushed into stack.
If all the curves of a given patch satisfy the straightness criterion, the given patch is classified to be flat. The straightness criterion is now described. FIG. 13 shows a two-dimensional example. The distance Dy of a point
p=(x.sub.1,y.sub.1) from line s.sub.0 s.sub.e along y direction is given by following expression. ##EQU7## If the resolution in Y direction is T.sub.y, for (x.sub.1,y.sub.1) to be approximately on the line, following condition should be satisfied.
or
When line s.sub.0 s.sub.1 is parallel to Y-axis as shown in FIG. 14, both sides of the above expression become zero. In this case, the distance Dx, is calculated according to the following expression. ##EQU8## If the resolution in X direction
is T.sub.x, then for (x.sub.1,y.sub.1) to be approximately on the line, the following condition should be satisfied.
or
A Bezier curve is completely contained within the convex hull of its control points. Hence if all the control points are less than a given distance away from a line connecting the end points, then every point on the curve is less than this
distance away from the line. Applying the above comparisons using the intermediate control points (i.e. the control points which are not also end points) consequently yields a useful straightness test.
In general, the above conditions for straightness test of a curve may be written as follows.
if
then
else
For the 3D case, for a point (x.sub.1,y.sub.1,z.sub.1) to be approximately on the line joining points (x.sub.0,y.sub.0,z.sub.0) and (x.sub.e,y.sub.e,z.sub.e), the following conditions are satisfied.
if
then
else
For a given patch, this process is performed for non-straight edges (edges with zero bit in the edge flag) of patch. If at least one edge of patch along the s direction and at least one edge along t direction are not straight, the patch is
subdivided along the s direction if previous subdivision was along t direction, otherwise subdivision is performed along the t direction. Otherwise, if edges are non-straight along only one of the s or t directions, the patch is subdivided along the
non-straight direction. If edges along both the s and t directions are straight, then all the non-edge curves of a patch are tested for straightness. If all the curves of a patch along one direction are straight, patch is called flat along this
direction. If a patch is flat along both s and It directions, the patch is classified as flat, otherwise it is subdivided along non-flat direction.
Linearity of Shading
This criterion is based on the linearity of change in the diffuse component of color across a patch classified as flat based on flatness criterion. The control points D.sub.ij 0.ltoreq.i,j.ltoreq.3, of the RGBA color patch are used for linearly
interpolating diffuse color across a patch (the computation of these control points is discussed further below). This criterion is tested after a patch is classified to be flat. This criterion is tested using expressions which are extensions of the
previous expressions for the flatness criterion. Let the color value at s.sub.0, s.sub.e, and (x.sub.1,y.sub.1,z.sub.1) be d.sub.0, d.sub.e, and d.sub.1, respectively. The condition for testing linearity in shading is given by
if
then
else
where T.sub.d is tolerance for color.
Culling
A patch is completely culled if
for all the control points, where 0.ltoreq.i.ltoreq.s.sub.-- degree and 0.ltoreq.j<t.sub.-- degree. If this test holds true, the patch is backfaced and cannot be seen. If the above product is greater than zero for all the control points, it
implies that the patch is completely visible. In such cases, a cull flag for the patch is set to zero so that no culling test need be done for any of its subpatches.
Clipping
A patch is completely clipped if none of its control points lies inside the viewing window, i.e. -(1+e)<g.sub.i+1,j.x<(1+e), -(1+e)<g.sub.i+1,j.y<(1+e), and -1<g.sub.i+1,j.z<0,
for 0.ltoreq.i.ltoreq.s.sub.-- degree and 0.ltoreq.j.ltoreq.t.sub.-- degree. On the other hand, if all the control points of a patch lie inside the viewing window, a clip flag for the patch is set to zero, implying no clipping test need be
performed for any of its subpatches. Here, e is a small fraction of image size. For example, for 512.times.512 image, e can be set to 1/64, allowing 520.times.520 viewing space for patch clipping.
Normal Computation
The normal to a surface at a point may be defined as ##EQU9## Using this definition as a method for computation is undesirable since it is computationally expensive. One division, one square root and number of additions and multiplications would
be required in order to compute the normal at each point. To avoid this expensive operation, the normal computation for a patch is instead approximated using Coon's patch. Coon's patch is a bicubic Bezier patch which may be used to approximate a
two-dimensional function from samples of the function and its derivatives at the corner points.
The determination of the normal proceeds in the following manner. The components of the above cross product appear as follows: ##EQU10## The derivatives ##EQU11## of n.sub.x, n.sub.y, and n.sub.z may then be computed by evaluating derivatives of
above equations. Since it is the unit normal vector which is of primary interest, its components are computed as follows: ##EQU12## For clarity, let ##EQU13## then the derivatives of the unit normal components are: ##EQU14## with the derivatives of
W(s,t) given by: ##EQU15##
With the above equations, the unit normal components and their derivatives can be quickly evaluated at the corner points of the patch. A matrix is formed of the results (only the x component is shown, the other components are similarly
obtained): ##EQU16##
From this, the Coon's patch approximation is obtained by the following equation:
where ##EQU17## Diffuse Color Computation
Let the light source be at (l.sub.x,l.sub.y,l.sub.z) then the diffuse color at (x(s,t), y(s,t), z(s,t)) is given by ##EQU18## where (L.sub.x (s,t),L.sub.y (s,t),L.sub.z(s,t))=(l.sub.x -x(s,t),l.sub.y -y(s,t),l.sub.z -z(s,t)). In a manner similar
to the normal vector computation, the above function may be approximated with the Coon's patch technique to avoid computing the diffuse color at each point with the above equation. The following matrix is formed: ##EQU19## and the Coon's patch
approximation made:
where once again ##EQU20## Half Way Vector Computation
Let the light source be at (l.sub.x,l.sub.y,l.sub.z), and viewing location be at (v.sub.x,v.sub.y,v.sub.z). Next, let L(s,t)=(L.sub.x (s,t),L.sub.y (s,t),L.sub.z (s,t))=(l.sub.x -x(s,t),l.sub.y -y(s,t),l.sub.z -z(s,t)) and V(s,t)=(V.sub.x
(s,t),V.sub.y (s,t),V.sub.z (s,t))=(v.sub.x -x(s,t),v.sub.y -y(s,t),v.sub.z -z(s,t)), and define the unit vectors ##EQU21## Then the half-way vector at (x(s,t), y(s,t), z(s,t)) is given by ##EQU22## Once again, the Coon's patch technique may be employed:
##EQU23##
where C is as previously defined.
Reflection Vector Computation
The reflection vector at a point (x(s,t),y(s,t),z(s,t)) is given by
and may also be approximated with the Coon's patch technique, so that:
As before, the y and z components are computed in a similar fashion. ##EQU24##
Now that the operations of the rendering pipeline shown in FIG. 4 have been discussed in detail, portions of the system of FIG. 2b for implementing the rendering pipeline are now discussed at greater length.
Turning to FIG. 15, a block diagram of patch tessellator 30 is shown. The patch tessellator 30 generates (adaptively or to a fixed depth) a set of projected triangles from rational bezier patches of third degree or less. It can also compute
specular colors and/or discard back-face portion of a patch. After getting a transformed surface patch and its attribute patches, the patch tessellator 30 tests the surface patches for back-face culling and flatness. A patch is considered flat if all
its eight curves (in the case of a bicubic patch) are straight within a given user specified tolerance bound. If the flatness criterion is not satisfied, the patch is sub-divided. If the patch is flat for a given tolerance criterion, it can be tested
for shading uniformity. Once a patch meets the uniformity of shading criterion, it is sent to rasterizer a pair of triangles for rendering. In the case of fixed-depth tessellation, the patch is not tested for flatness. A patch is tessellated in the s
and t directions alternately until the specified level of sub-division is reached.
When a pair of triangles specifying a patch is sent to the rasterizer 32, the pair of triangles can be specified using only four vertices in | | |
