Browse Prior Art Database

# Triangle Rendering Algorithm

IP.com Disclosure Number: IPCOM000108701D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 7 page(s) / 283K

IBM

## Related People

Moller, CHL: AUTHOR

## Abstract

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.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 22% of the total text.

Triangle Rendering Algorithm

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.

Given the 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
Determination of the Interior of a Triangle: Discussion

The perimeter 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)

Obviously, if 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
vector yields:
-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.

This 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...