Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1997-08-27
2001-04-03
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S426000, C345S440000
Reexamination Certificate
active
06211883
ABSTRACT:
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. Pat. No. 5,999,188 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:
Q
(
s
)
=
∑
i
=
1
n
g
i
(
n
!
i
!
(
n
-
i
)
!
)
s
i
(
1
-
s
)
n
-
i
,
(
1
)
where g
i
, 0≦i≦n, are control points as shown in FIG.
1
A. 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:
Q
(
s
)
=
[
&AutoRightMatch;
s
3
s
2
s
1
&AutoLeftMatch;
]
[
-
1
3
-
3
1
3
-
6
3
0
-
3
3
0
0
1
0
0
0
]
[
g
0
g
1
g
2
g
3
]
=
SMG
c
,
(
2
)
where G
c
is a column vector containing the Bezier curve control points. If G
c
is parameterized in order to vary as a function of a second coordinate t, this gives the two-dimensional surface:
Q
(
s
,
t
)
=
SM
[
G
0
(
t
)
G
1
(
t
)
G
2
(
t
)
G
3
(
t
)
]
.
(
3
)
Realizing that for 3rd order Bezier curves, G
i
(t) can be expressed in the matrix equation
G
i
(t)=T M G
ci
, (4)
an expanded form of equation (3) can be written
Q
(
s
,
t
)
=
SM
[
g
00
g
01
g
02
g
03
g
10
g
11
g
12
g
13
g
20
g
21
g
22
g
23
g
30
g
31
g
32
g
33
]
M
T
T
T
.
(
5
)
Equation (5) is the matrix form of a bicubic Bezier patch. An example of such a patch is shown in FIG.
1
B. 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
X(s,t)=S M G
x
M T
T
, (6)
Y(s,t)=S M G
y
M T
T
, and (7)
Z(s,t)=S M G
z
M T
T
. (8)
A generalization of the Bezier patch referred to as a “rational Bezier patch” is often used. A rational Bezier patch has a fourth equation
W(s,t)=S M G
w
M T
T
, (9)
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
(
X
(
s
,
t
)
W
(
s
,
t
)
,
Y
(
s
,
t
)
W
(
s
,
t
)
,
Z
(
s
,
t
)
W
(
s
,
t
)
)
where
0≦s,t≦1. (10)
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 determine when a sub-patch is flat enough to be approximated with a quadrilateral, the patch rendering system uses a patch flatness test unit which tests the straightness of the edges and internal curves of the sub-patch. The edges and internal curves of a subpatch are determined to be straight if the intermediate control points of a curve are within a tolerance range of a straight line between the curve's endpoints. The tolerance range is chosen with respect to a pixel resolution of the final image so that subpatch is determined to be flat when the curvature of the subpatch cannot be perceived relative to a flat surface.
The present invention contemplates a flatness test unit for determining the flatness of a patch having a set of control points. The flatness test unit comprises a series of stages. The first stage is configured to receive and store the set of control points. The second stage is coupled to the first stage to receive pairs of control points and configured to determine control point coordinate differences. The third stage is coupled to the second stage to receive the control point coordinate differences and configured to determine absolute values of the control point differences. The fourth stage is coupled to the third stage to receive absolute values of the control point coordinate differences along with the control point differences and configured to determine multiplicand pairs. The fifth stage is coupled to the fourth stage to receive and multiply multiplicand pairs to determine products. The sixth stage is coupled to the fifth stage to receive products and configured to determine control point deviations and deviation tolerances. The seventh stage is coupled to the sixth stage to receive the control point deviations and deviation tolerances and configured to determine a deviation flag to indicate if the control point deviations are less than the deviation tolerances. The eighth stage is coupled to the seventh stage to receive the deviation flag and determine edge straightness and patch flatness flags.
REFERENCES:
patent: 4646251 (1987-02-01), Hayes et al.
patent: 4890242 (1989-12-01), Sinha et al.
patent: 4912659 (1990-03-01), Liang
patent: 4999789 (1991-03-01), Fiasconaro
patent: 5107444 (1992-04-01), Wu
patent: 5278948 (1994-01-01), Luken,
LSI Logic Corporation
Vo Cliff N.
LandOfFree
Patch-flatness test unit for high order rational surface... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Patch-flatness test unit for high order rational surface..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Patch-flatness test unit for high order rational surface... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505959