greg@jiff.berkeley.edu (Greg) (01/29/88)
Recently, many people have asked about algorithms to draw thick and
antialiased lines, circles, and ellipses. There is a vast
generalization of Bresenham's algorithm, the famous efficient algorithm
for drawing lines, that works for all of these cases. Before
describing all of the applications in this two-part posting, I will
give an explanation of Bresenham's algorithm.
The general plan
We may imagine that the curve we wish to draw will be traced out
by a jogger whose position is always some point on the pixel grid
on the screen. The jogger is running along a beach and want to
stay as close as possible to the shore. The shore is the ideal
curve which we wish to draw. The jogger knows that the shore
slopes in a direction between say east and northeast, so he
will only move in one of those two directions. The situation
might look like this:
pixels->X X X X X X X
land
X X X >X X X----X
/ -----------
shore-> --------/-- water
X jogger->J--->X X X X
In this situation, if the jogger moves northeast, he goes uphill,
while if he goes east, he moves downhill. Let us assume that
the jogger can compute his altitude, or at least tell if his feet
are in the water. Which direction should he move? One obvious
choice is for him to go uphill if he is in the water and downhill
if he is on land.
Drawing lines
What remains is to choose what the shore will be, or rather to choose
the altitude function a(x,y) whose zero set is the curve we want.
Suppose we want to draw a line segment from (x1,y1) to (x2,y2).
Then it is appropriate to make the altitude a linear function.
The function a(x,y) = (x-x1)*(y2-y1) - (y-y1)*(x2-x1) will suffice.
We must also choose the two directions closest to the slope of the
line segment and decide which raises the value of a and which decreases
it. The jogger will start at (x1,y1) and will quit when he arrives
at (x2,y2).
It looks as if two multiplies are needed at each step to compute
altitude, but this is not so. Since the altitude function is linear,
it changes by a constant amount up or down with each move. If the
altitude is as above, it changes by y2-y1 for E and y2-y1+x1-x2 for
NE. We may precompute these, keep a running total of the altitude, and
reduce the per-pixel computation to one addition and two compares (one
to choose directions and one to terminate).
Drawing circles
For a circle of radius r around the point (x0,y0), the function a(x,y)
= (x-x0)^2 + (y-y0)^2 - r^2 is a good choice. This time a complication
appears off the bat. The two plausible directions change over time.
The fastest solution for circles is to divide the circle into octants,
have the jogger trace out one octant, and use reflected images for the
other seven. However, the most general solution is to keep track of
the possible changes in altitude at each point. If both of your
directions go uphill or downhill, it's time to change bearings.
This time it looks even more like multiplies are needed. But note that
the altitude changes are 2*(x-x0)+1 for E and 2*(y-y0+x-x0)+1 for NE.
If you keep track of the current x and y coordinates, only left
shifts and adds are required.
Drawing ellipses and many other things
With the term "ellipse", most graphics users (and graphics packages)
think of a circle stretched vertically or horizontally. However,
ellipses stretched in other directions are often useful, as are
hyperbolas and parabolas. They are not much harder to draw. The
general formula for conic sections is a quadratic equation, i.e.
a*x^2+b*x*y+c*y^2+d*x+e*y+f = 0. We can easily plug this equation into
the generalized Bresenham's algorithm, as long as we can find a
suitable starting point and we keep in mind the caveat about changing
directions. Which quadratic equation correspond to which ellipses?
The best way to handle this issue is to use transformations for
rotation, translation, and stretching. For example:
1) Start with a circle, like x^2 + y^2 - 100 = 0.
2) Stretch vertically by a factor of two: oldy = newy/2, i.e.
x^2 + y^2/4 - 100 = 0.
3) Rotate 45 degrees using the formula
oldx = newx*cos(theta) - newy*sin(theta)
oldy = newy*cos(theta) + newx*sin(theta), to obtain
(x-y)^2/2 + (x+y)^2/8 - 100 = 0, or 5/8*x^2 + 3/8*y^2 - 3/4*x*y - 100 = 0.
4) Translate, using oldx = newx - x0, oldy = newy - y0.
5) Multiply both halves the equation by some suitable constant to
make arithmetic more convenient.
The other issue is optimization. Although the altitude function is
not linear, and therefore the amount to add in each direction changes,
the differences between adjacent pixels are themselves linear.
So you can keep a running total of the amount to add when the jogger
goes East or Northeast, because those two numbers only change by
constants with each step. There is a law of commutative derivatives
here: If dE(f) is the change in f with one E step, then dE(dNE(f))
= dNE(dE(f)). In any case, if multiplies are expensive, you can avoid
them by keeping track of these increments.
More generally, you may have some hairy curve given by some awful
implicit equation which you wish to draw efficiently. Bresenham's
algorithm still works. If it is a polynomial, you can keep track
of increments, or increments of increments of increments, and
somewhere at the bottom the increments will be constant. Keep
in mind that if the altitude function is sufficiently complicated,
it's better just to multiply.
In the follow-up article, I will discussing drawing thick
and anti-aliased curves.
--
Greg