In order to draw a line on a screen we need to turn on appropriate pixels along
the line (assume bit map). Assume the coordinates of the end points of the line
are specified in the bit-map space (i.e. pixel number => integer coordinates),
say, x1, y1 and x2, y2.
For the following algorithms also assume that the slope of the line:
0 > (y2-y1)/(x2-x1) > 1 .
(For slopes with magnitudes greater than 1, we make minor adjustments as described
Digital Difference Analyzer (DDA) algorithm
We start at x1 and advance along the x dimension in steps of one,
finding the appropriate value of y ,for each value of x. This can be
simply done by inspecting the equation of the line
y = m x + B, where B is the y intercept
of the line. For our line that is:
y = (y2-y1)/(x2-x1)x
Now suppose we know the point (x,y on the line. We can
compute the value of y at x+1 as m(x+1) + B . But we
know that y = mx + B . Hence the value we seek is: y + m.
Thus by performing one addition, we can incrementally compute the value of y
for each value of x. Note that we need real valued arithmetic as m is a
To compute the pixel number we need to turn on, we just round the value y + m.
This algorithm is practically the same as another algorithm known after its inventor
as the Bresenham's algorithm. The central idea of both these algorithms is to determine
at each step whether to set the pixel immediately to the right of the current pixel,
or the one above it. (Note that these are the only possibilities. Remember that the
slope lies between 0 and 1.) Bresenham's algorithm draws the pixel closer to the line.
The mid-point algorithm tests if the line passes above or below the mid-point between
the two pixels. If it passes above, it must be closer to the upper pixel and if it
passes below, it must be closer to the lower pixel. Since it is more straightforward
to generalize the mid-point algorithm to circles, ellipses and general curves, it is
Let us start with the implicit form of the line equation:
F(x,y) = Ax + By + C = 0.
For consistency, assume A > 0 (if A < 0, negate all coefficients).
Suppose we the current pixel on the line = (xp, yp).
We next need to choose between pixels (xp+1, yp) and
(xp+1, yp+1). In order to do that, we need to test the
sign of dp = F(xp+1, yp+0.5). We call
d the decision variable. (It is F evaluated at the mid-point of the two pixels).
If dp > 0, we must choose the upper pixel otherwise we choose the
lower pixel. Note that to compute dp, as described, we need real
valued arithmetic. We can eliminate all real arithmetic by resorting to incremental
Assume we know dp. We can then compute dp+1 as
We choose (xp+1, yp) at the current step.
dp = A(xp+1) + B(yp+0.5) + C
dp+1 = A(xp+2) + B(yp+0.5) + C
dp+1 - dp = A
We choose (xp+1, yp+1) at the current step.
dp = A(xp+1) + B(yp+0.5) + C
dp+1 = A(xp+2) + B(yp+1.5) + C
dp+1 - dp = A + B
Thus if dp, A and B were integers, we could
incrementally compute dp+1 using a simple addition. (Note that
A + B is a constant and the addition needs to be computed at most once per
line.) Of course, A = (y2-y1)
and B = (x1-x2) are integers.
But what about dp?
Let us look at the starting point (x1,y1):
d1 = A(x1+1) + B(y1+0.5) + C
= A(x1) + B(y1) + C + A + B/2 = A + B/2
Thus, if B is an even number, d1 is an integer.
If B is an odd number, all we need to do is multiply all coefficients
of the equation of the line by 2 (and go through the math again).
This leaves the line unchanged:
2Ax + 2By + 2C = 0.
If the end points of the line lie beyond the edges of the window (or the bit-map),
one easy solution is to round off the intersection of the line with the window, and
perform the same algorithm. However, this can result in a different line from the
one intended. This may result in, for instance, two collinear line segments not looking
collinear anymore. Let us first consider a line that extends beyond the left edge (right
edge is similar, when moving from right to left).
While we must draw the closest pixel to the actual intersection point,
we should also initialize the decision variable, d, appropriately.
For example, if the first pixel is (xp, yp), the
decision variable d1 is:
A(xp+1) + B(yp+0.5) + C. This is not equal to
B/2 any more, but it still is an integer:
Assume xp = x1 + ix and
yp = y1 + iy .
(ix and iy are integers.)
Now, d1 = A(x1+ix+1) +
B(y1+iy+0.5) + C.
That is an integer (why?).
If the line extends beyond a horizontal boundary, the problem is more acute. Suppose the
line intersects the lower boundary of the window. Check to see what happens for lines
with slope close to zero, if we start at the rounded value of the intersection point.
A number of pixels that are closer to the boundary than the scan-line beyond it do not
get drawn. To account for this short-sightedness (no pun intended), we find the
intersection with the line corresponding to half a pixel lower than the actual boundary.
Now, if we round of this intersection, we start at exactly the pixel that we would have
started at if the window was not truncated below this boundary.
The algorithm needs to change only slightly for slopes outside the range (0,1). For
slopes greater than 1, we choose y as the primary axis. We increment y
and find an appropriate value of x each time.
For negative slopes, we just need to test for the lower, rather than the upper, pixel.
Remember that it is not wise to change the order of drawing to, say, an always increasing
primary axis. This can result in "patterned" poly-lines looking wrong.
The extension of the mid-point algorithm for circle is quite simple. All we need to do
is replace F with the equation of the circle. Again, we subdivide the circle into eight
sectors. For the sector which has its slope between 0 and 1:
If the mid-point lies inside the circle
we must pick the lower point and if it lies outside, we pick the upper point. The other
sectors can be obtained by rotation/reflection.
Note that the if we start at the first pixel and draw until the last pixel, we draw a line
a little longer than the original length. This is because the pixels are not mathematical
points, but have dimensions on the screen. The left-most pixel extends half a pixel size
(diameter) to its left and the right-most pixel extends half the a size to its right.
To draw a line of the intended length, we must reduce a pixel's worth. This done by
using the convention that lines (and other primitives) are closed on there lower end
and open at the other end, i.e. the upper end point does not belong the line. Hence we do
not draw the upper end point. For horizontal lines, we do not draw the right end point.
This also makes sure that for poly-lines -- mutually connected line segments -- we do
not duplicate the end points.
Polygon drawing is quite like line drawing, except we must fill in the area between the
lines. For simplicity, let us assume that polygons are simple (i.e. no holes or
intersecting lines). (Note: simple extensions to the algorithm described below handle
Again, we use incremental algorithms to compute the pixels to be filled. (Such algorithms
are also called coherent algorithms --
a part of the computation at each stage is already available from the previous stage --
not that other algorithms are necessarily
incoherent, but these algorithms take advantage of inherent coherence of computations :)
We compute the part of the window inside the polygon, one scanline at a time.
- Compute all intersections of the polygon edges with the current scan line
- Sort all intersections
- Use Odd-Even parity rule to compute the spans of pixels that need to be turned on:
- Start with even parity.
- At each intersection flip the parity
- If the current parity is odd, draw each pixel until the next intersection
(this is a span).
We use coherence in computing the intersections with the current scan-line. If the
intersection of the segment with the previous scan-line is known, we can use a line
drawing algorithm to compute the current intersection. Using a DDA-like algorithm
(remember, now y is our primary axis), given the previous intersection
(x,y) we can compute the intersection at y = (y+1)
as (x + 1/m).
Again, with a little manipulation we can get away with integer arithmetic. We break
1/m into an integer part i and a fractional part r.
Remember, we need to keep adding 1/m to the current value of x.
This can be done by adding i each time and updating r = N/D, N < D.
We need to add N/D, 2N/D, 3N/D, and so on.
We keep adding N to the numerator until it exceeds D,
each time adding i to x. Once the numerator exceeds D,
we add 1 more to x, and subtract 1 from the fractional part, which is achieved
by subtracting D from numerator.
Remember, we must set only pixels lying in the interior of the polygon. Hence
on the left edges of the span, we round up, and on the right edges of a span we round
down. If the point of intersection lies exactly on a pixel, using our length convention,
on the lower end, we include the pixel, and on the upper end we exclude the pixel
from being drawn.
We use coherence in sorting again. If no new edges start at the new scan-line (i.e.,
no vertices lie at the scan line) the sorted order remains the same (remember, we are
assuming no self-intersections). If a new vertex does start, we can easily insert it
in the current list of sorted intersections, by using insertion sort.
The intersection list can easily be managed by starting with a y sorted list
of edges (usually a bucket sort) and maintaining the currently active list of
intersections. Once we reach a scan line at which an edge starts (by looking at the
bucket corresponding to the current scan line), we insert it into the active list.
We need to consider the special case of when a vertex of the polygon lies on the
scan line. For closed polygons, such vertices would normally be repeated as they
lie on two edges. Always counting them twice (or even once) for the odd-even parity
results in inconsistencies. However, using the following rule eliminates any such
What happens to the horizontal edges of polygons?
- If the vertex is the lower of the two vertices of an edge, count it.
- Otherwise, do not count it.
- Do not count vertices of horizontal edges.