Browse Prior Art Database

Computer Graphics - Scan Conversion of Triangles

IP.com Disclosure Number: IPCOM000101255D
Original Publication Date: 1990-Jul-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 116K

Publishing Venue

IBM

Related People

Albaugh, V: AUTHOR [+3]

Abstract

Disclosed is an algorithm for scan conversion of 3D triangles. The algorithm is more accurate and more efficient (both in speed and silicon required) than the most common approach. The algorithm lends itself to simple implementation in hardware logic. The algorithm permits a hardware implementation that scan converts a complete triangle as a task, rather than scan converting a triangle one scan line at a time.

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

Computer Graphics - Scan Conversion of Triangles

       Disclosed is an algorithm for scan conversion of 3D
triangles.  The algorithm is more accurate and more efficient (both
in speed and silicon required) than the most common approach.  The
algorithm lends itself to simple implementation in hardware logic.
The algorithm permits a hardware implementation that scan converts a
complete triangle as a task, rather than scan converting a triangle
one scan line at a time.

      It is standard practice to convert surfaces to a series of
triangles to be scan converted.  This is because three points
unambiguously describe the surface in linear terms. The three points
defining the triangle are defined by the variables P=(x,y,z,r,g,b).
The plane equation can be solved to determine the partial derivatives
of these variables with respect to x and with respect to y.  If more
than three points are used, they may not describe a planar surface
(even if planar in physical space, they may not be planar in color
space).

      In the following discussions, various orientations are
interchangeable.  Left and right are interchangeable with up and
down, and left is interchangeable with right and up is
interchangeable with down.

      A typical technique for scan converting is to pick the lowest
point of the triangle, determine the slope of the variables
(x,z,r,g,b) along the left edge and the slope of the variable (x)
along the right edge of the triangle.  The partial derivative with
respect to x for the variables (z,r,g,b) is also developed.  The edge
slopes are used to advance from the initial point and determine at
each scan line intersection the value of (x,z,r,g,b) at the left edge
and the value of x at the right edge.  Since advancing from scan line
to scan line is a constant y increment, successive scan line end
points can be found by adding the constant determined by the slope
for each of the variables.  The value of the left edge of the scan
line is assigned to the first pixel to the right of the left edge and
hardware interpolators are typically used to calculate each
successive horizontal pixel value (z,r,g,b) by successively adding
the partial derivative of these variables with respect to x.  The
main problem with this approach is accuracy.  Scan line intersections
of the edges do not typically intersect pixels.  Therefore, by
assigning the value of the left edge to the nearest pixel, a subpixel
error is being introduced.  This causes the pixel values of
successive scan lines comprising a surface to be randomly skewed to
the left or right by a sub-pixel error.  This effect is not generally
noticeable in the color domain; however, in the depth domain, a
significant error can be introduced depending on the size of the
partial derivative of z with respect to x.  This inhibits the capa
bility of the z-buffer to provide depth sorting of the surfaces and
causes surfaces close to each other to experience random horizontal
'b...