Browse Prior Art Database

Rasterization Algorithm for Triangles by using Bresenham's Algorithm

IP.com Disclosure Number: IPCOM000113140D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 68K

Publishing Venue

IBM

Related People

Hirota, G: AUTHOR [+3]

Abstract

Disclosed is a rasterization algorithm for two-dimensional triangles. It is designed to handle sub-pixel addressing triangles. The rasterization is done in each vertical span, and it is assumed that a pixel must be filled on an adjoining edge only once. This algorithm rasterizes triangles without division and decimal fraction, by applying Bresenham's algorithm.

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

Rasterization Algorithm for Triangles by using Bresenham's Algorithm

      Disclosed is a rasterization algorithm for two-dimensional
triangles.  It is designed to handle sub-pixel addressing triangles.
The rasterization is done in each vertical span, and it is assumed
that a pixel must be filled on an adjoining edge only once.  This
algorithm rasterizes triangles without division and decimal fraction,
by applying Bresenham's algorithm.

      The disclosed algorithm offers some improvements in the
performance of displaying graphic objects.

Fig. 1 shows an example of a rasterized triangle.

The rasterization procedure consists of the following five steps:

1.  Translate each vertex (x,y) into (x-1/2,y-1/2) in order to fit
    each pixel center into an integer grid.

2.  Sort the vertices by their x-coordinate values.

3.  Divide the triangle vertically through the middle vertex.

4.  Rasterize the left half of the triangle for each vertical span.

5.  Rasterize the right half of the triangle for each vertical span.

      Rasterization in a vertical span means calculating in that span
all the pixels included by a given triangle in case span.  This
relation of inclusion is calculated by using the sign of the erro
term (Fig. 2) in Bresenham's algorithm.  Fig. 3 shows the relation
between the sign of the error term of a selected pixel and a given
edge.

The relation of inclusion is as follows:

(I1)In the case of an upper edge:
     if {the error term is po...