Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-10-22
2002-04-30
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06380936
ABSTRACT:
COPYRIGHT AUTHORIZATION
The Appendix of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The present invention relates generally to computer graphics systems using projective mapping of a two-dimensional (2D) image to be rendered on a screen. Still more particularly, the present invention relates to a barycentric coordinate system for improved projective mapping of a 2D image after a transformation or distortion.
BACKGROUND OF THE INVENTION
In a computer graphics system, it is desirable to represent an object as efficiently as possible to preserve memory and system bandwidth, and to enhance rendering speed. Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ applications such as two-dimensional projective mapping during rendering images of objects. A 2D mapping is a mapping or transformation that distorts a 2D source space into a 2D destination space. A source point is mapped to a destination point according to a predetermined function. Current graphics cards and graphics accelerators use an industry standard 3×3 projection matrix for projective mapping.
In two-dimensional projective mapping, a 2D image is rendered on a screen after some transformation or distortion. To accomplish this, a (U,V) projective coordinate must be determined for each (X,Y) location on the screen. A common transformation is
U
=
aX
+
bY
+
c
gX
+
hY
+
j
,
V
=
dX
+
eY
+
f
gX
+
hY
+
j
.
By picking the proper values for the coefficients a . . . j, the 2D projection can be manipulated to an arbitrary position, orientation, and perspective projection on the screen. The coefficients can be generated by a concatenation of 3D rotation, translation, scale, and perspective matrices, so the homogeneous matrix representation of this transformation is used, as follows:
[
X
Y
1
]
[
a
d
g
b
e
h
c
f
j
]
=
[
u
v
w
]
[
U
V
]
=
[
u
w
v
w
]
.
A more direct approach to finding a . . . j uses a 2D to 2D mapping that is specified by four arbitrary points in screen space and the corresponding four arbitrary points in destination space that are mapped into the points in source space. A restriction is that no three of the input or output points may be collinear. This method of transformation specification is useful, for example, in taking flat objects digitized in perspective and processing them into orthographic views.
As shown in
FIG. 3
, given four 2D screen coordinates Z
i
=(X
i
, Y
i
, 1), and four 2D projective coordinates T
i
=(U
i
, V
i
, 1), it is desirable to find the 3×3 homogeneous transformation M
st
that maps one to the other so that Z
i
M
st
=w
i
T
i
(Eq. 1). Note that the w
i
values in the equation acknowledge the fact that even though the original input and output points are nonhomogeneous (their third component is 1), the output of the matrix multiplication will be homogeneous. The w values are determined as a side effect of solving for the elements of M
st
.
For one conventional solution, using a . . . j for the elements of M
st
, Equation 1 is rewritten as
[
X
i
Y
i
1
]
[
a
d
g
b
e
h
c
f
j
]
=
w
i
[
U
i
V
i
1
]
Multiplying out and equating each component results in:
aX
i
+bY
i
+c=w
i
U
i
dX
i
+eY
i
+f=w
i
V
i
gX
i
+hY
i
+j=w
i
Rearranging gives:
aX
i
+bY
i
+c−gX
i
U
i
−hY
i
U
i
−jU
i
=0
dX
i
+eY
i
+f−gX
i
V
i
−hY
i
V
i
−jV
i
=0.
Writing this as a matrix equation in terms of a . . . j gives:
[
X
i
Y
i
1
0
0
0
-
X
i
U
i
-
Y
i
U
i
-
U
i
0
0
0
X
i
Y
i
1
-
X
i
V
i
-
Y
i
V
i
-
V
i
]
=
[
a
b
c
d
e
f
g
h
j
]
=
[
0
0
]
Each input point gives two more nine element rows; four points give an 8×9 matrix. Because this is a homogeneous system, that is all that is needed to solve for the nine values a . . . j (with an arbitrary global scale factor). One way to determine each of these nine values is to find the determinant of the 8×8 matrix formed by deleting the matching column of the 8×9 matrix. However, this is very complex.
Heckbert provides an improvement by splitting the transformation into two separate matrices (Heckbert, Fundamentals of Texture Mapping and Image Warping, Master's Thesis, Univ. of California, Berkeley, Dept. of Electrical Engineering and Computer Science, 1989). Heckbert first maps the input points to a canonical unit square with one matrix, and then maps that square into the output points of another matrix. Each of these matrices is easier to calculate than the complete transformation. Heckbert uses 4 divides, 65 adds, and 69 multiplies to provide the industry standard 3×3 projection matrix for projective mapping. Because of the divides, Heckbert's technique is slow and processor-intensive.
There is a wide range of applications involving computer graphics in which it is necessary or desirable to provide projective mapping. Accordingly, a goal of the present invention is to provide a projective mapping transformation that is efficient and accurate and avoids using comparisons and divisions.
SUMMARY OF THE INVENTION
The present invention provides systems and methods for providing improved (faster for a given amount of computer resources) computer projective mapping of a 2D image to be rendered on a screen after some transformation or distortion, and can be used in interactive applications such as 3D video games and virtual environments.
The invention provides an improved technique for defining a projective mapping of quadrilaterals by specifying the images of four independent points and imposing the additional constraint that straight lines are mapped to straight lines. The invention performs 49 adds and 48 multiplies to achieve the desired 3×3 projection matrix. This is more efficient than conventional techniques which typically use multiple divides to provide the industry standard 3×3 projection matrix for projective mapping.
According to the present invention, a barycentric coordinate system is used to represent four points in the source space and their corresponding four points in the destination space. Barycentric coordinates represent an arbitrary point (e.g., one of the four points) in the plane as the weighted sum of three basis points (e.g., the three other points). The present invention uses the constraint that the barycentric coordinates sum to one (i.e., the weights on the three points sum to 1). The two barycentric coordinate systems are related by a mapping from the points in the source space to the points in the destination space such that the barycentric coordinates of all four input points map to the barycentric coordinates of their respective output points. A ratio of the associated weights is determined for each of the three basis points in the two spaces. These ratios provide a triplet that defines the mapping (transformation) in three coordinates. These three coordinates are then transformed to the 3×3 industry standard.
Thus, the present invention more efficiently manipulates 16 numbers (four points in two spaces, each point having two coordinate values) to provide the 9 numbers used by current graphics cards and graphics accelerators.
Other features of the invention are described below.
REFERENCES:
patent: 5319744 (1994-06-01), Kelly et al.
patent: 5361385 (1994-11-01), Bakalash
patent: 5548693 (1996-08-01), Shinya
patent: 6111582 (2000-08-01), Jenkins
Blinn, J.F., “Jim Blinn's Corner: Inferring Transforms,”IEEE Computer Graphics and Applications, May/Jun., 1999, 93-98.
Heckbert, P.S., “Fundamentals of Texture Mapping and Image Warping,” Master's Thesis, University of California , Berke
Microsoft Corportion
Vo Cliff N.
Woodcock & Washburn LLP
LandOfFree
System and method for inferring projective mappings 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 and method for inferring projective mappings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for inferring projective mappings will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2932762