Page 49 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 3: Implementing Line Algorithm

Notes
Œ – = ∆x
end if
x + = 1
Œ + = ∆y
next i
finish

3.2.4 Specifying the Driving Axis
If x is the driving axis, Bresenham’s algorithm creates only one illuminated cell per column
in the matrix of pixels. This feature permits the algorithm to be helpful in the rasterization of
polygons in image space. In this algorithm, we need only one illuminated pixel per row be
produced which is likely with Bresenham’s algorithm by fixing the driving axis as the y axis.
This can be done by a simple change to the main loop of the algorithm. Normally, within the
main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit
and the coordinate corresponding to the other axis need only be incremented occasionally. When
we fix the driving axis, the coordinate on the DA is still incremented by one unit; however the
coordinate on the other axis may be incremented several times. This is actually a simple change
to the algorithm, and can be implemented by replacing the statement:
if ( Œ ≥ 0)
with
while ( Œ ≥ 0)

The algorithm now appears as follows, we also note we have changed the algorithm to reflect
that the y axis is the driving axis. We note that m =∆x/∆y, and that according to the following
picture:

We must consider two possible initial values for, one if ∆x > 0 (the left-hand illustration) and
one if ∆x < 0 (the right-hand illustration). Referring to the illustration, we have either
ε = − (1 − x 1 − y 1 ∆x/∆y)
in the first case, or
ε = −(x 1 − y 1 ∆x/∆y)

1
In general x 1 must be replaced by x - Í Î 1 and y 1 by y - Í Î y ˙ as the figure is drawn as if
1
x ˙ ˚
˚
1
the lower-left-hand corner of the pixel is (0, 0). We also need to recognize that may be greater
than zero immediately, as in the following figure. Therefore, we must move the “illuminate”
step in our algorithm below the “while” statement. This will insure that we are at the correct
boundary pixel for the trapezoid.

LOVELY PROFESSIONAL UNIVERSITY 43