Browse Prior Art Database

# Fast Triangle Rasterizer using the Line Pixel Sampling and the Pixel Line Propagation Techniques

IP.com Disclosure Number: IPCOM000122864D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 6 page(s) / 171K

IBM

Kwok, TY: AUTHOR

## Abstract

Disclosed is a method to improve the efficiency of any software rasterizer for 3D graphics by using the line pixel sampling and the pixel line propagation techniques in a triangle rasterizer.

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

Fast Triangle Rasterizer using the Line Pixel Sampling and the Pixel
Line Propagation Techniques

Disclosed is a method to improve the efficiency of any software
rasterizer for 3D graphics by using the line pixel sampling and the
pixel line propagation techniques in a triangle rasterizer.

The rasterization has to be performed first on all the
triangles and lines, then the rasterization on points can be carried
out.  Vertices are sorted by y coordinate either in ascending or
descending order and the triangle is divided along the horizontal
line through the second vertex into the upper and lower portions.
The upper  portion of a generalized triangle for rasterization after
sorting vertices by y coordinate is shown in Fig. 1.

Derivatives for the interpolation of z coordinate are computed
for the increment or decrement of one pixel position at a time in
either x or y coordinates.  Vertex x, y, z coordinates and r, g, b
colors of the triangle for rasterization can be converted into
sub-pixel integers.  The equations of the line A-B and A-C are
obtained in the form
y % + % A sub L % * % x %% = %% C sub L eqno (1)
for the line A-B on the left and
y % + % A sub R % * % x %% = %% C sub R eqno (2)
for the line A-C on the right.  A sub L, A sub R, C sub L,
C sub R are constants.  The slopes of these two lines are
given by equations (3) and (4):
dy over dx %% = %% - % A sub L eqno (3)
dy over dx %% = %% - % A sub R eqno (4)

As shown in Fig. 1, the angle theta or phi between line A-B or A-C
with the horizontal line is less than 90 degrees if A sub L or A sub
R is negative correspondingly.  The angle theta or phi is greater
than 90 degrees if A sub L or A sub R is positive.

Either in descending (upper portion triangle) or ascending
(lower portion triangle) order along the y coordinate, the x, y
coordinates of pixels just on or next to the two edges within the
upper or lower region triangle are obtained.  They can be calculated
either from the extrapolation on edge slopes or the pixel point
propagation along edge technique with test of being on the left or
right sides of the edge.  Points right on either left or right edge
are counted as pixels within the triangle to assure that every pixel
only belongs to one triangle.  The pixel calculations for vertically
decremented points will start from vertex A from Y sub A down to Y
sub B .  The first test point is obtained by shifting y along the
nearest vertical pixel line to the nearest horizontal pixel position
just below the vertex A.

For the case of negative A sub L and positive A sub R, this
first test point is the first pixel within the triangle without
testing, as shown in Fig. 1.  This first pixel will be used as both
the edge left  and right vertical points.  Its  c sub l and c sub r
are calculated from  equations (5) and (6):
c sub l %% = %% y % + % A sub L % * % x eqno (5)
...