Triangle Rendering Algorithm
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Given a triangle defined in two-space to be mapped onto a discrete-pixel display, this invention offers improved methods for both locating pixels interior to the triangle and determining appropriate color, Z and alpha values for these pixels.
Triangle Rendering Algorithm
triangle defined in two-space to be mapped onto a
discrete-pixel display, this invention offers improved methods for
both locating pixels interior to the triangle and determining
appropriate color, Z and alpha values for these pixels.
coordinates of the vertices of a triangle, and
associated attributes such as color, Z, and alpha values, the problem
is to represent the triangle on a computer-graphics display as a set
of discrete pixels such that the attribute values of the pixel set
are two-dimensional linear interpolations among the given attributes.
The solution of this problem has two components: determination of
which pixels are part of the triangle, and what the attributes of
each pixel should be. This disclosure includes new techniques that
address each of these requirements.
Determination of the Interior of a Triangle: Discussion
of a triangle may be represented by a set of
three vectors, as shown in the figure below:
Each vector is a segment of a line that
may be described by the
relationship Ax+By+C = 0. Given, for example, points P1 (at
coordinates (x1,y1)) and P2 (at (x2,y2)) from the figure above, and
the assertions (which will not be demonstrated here, but may be shown
to be true) that:
A = y2 - y1
B = x2 - x1 (1)
C = x2y1 - x1y2
the resultant relationship becomes:
(y2 - y1)x + (x1 - x2)y + (x2y1 - x1y2) = 0 (2)
the expression on the left side of the relation
is evaluated at a point on the line, the result is zero. By
implication, if it is evaluated anywhere else, the result is
non-zero. As an example, evaluating this relation for the given
-12x - 8y + 272 = 0
At point (0,0), the expression evaluates to
272; at (20,16),
-96. The significant thing to notice is that the evaluation at one
side of the line is positive, at the other negative. This
observation allows the half-planes separated by the lines of which
the vectors are segments to be consistently tagged as being either
the "positive" half-plane or the "negative" half-plane.
distinction between the half-planes is affected by the
orientation of vectors defining them. The above example assumed that
the vector was defined by the ordered pair (P1,P2). Had it been
defined as (P2,P1), the resultant relationships would have been:
(y1 - y2)x + (x2 - x1)y + (x1y2 - x2y1) = 0
12x + 8y - 272 = 0
which defines the same line, but would have resulted in a reversal of
the positive and negative half planes.
If the same
analysis is done to the other two vectors, it is
apparent that the interior of the triangle is the area common to all
three positive half-planes. The following description discusses...