Graphics Reference
In-Depth Information
Code for drawing the discrete line from (0,0) to the point (a,b) in the first octant:
begin
integer
d, x, y;
d := 2*b - a;
x := 0;
y := 0;
while true do
begin
Draw (x,y);
if
x = a
then
Exit;
if
d ≥ 0
then
begin
y := y + 1;
d := d - 2*a;
end;
x := x + 1;
d := d + 2*b;
end
end
Algorithm 2.5.2.1.
Basic line-drawing algorithm.
comes from [Heck90c] and works for all lines. It generates the same points as the
original Bresenham line-drawing algorithm but is slightly more efficient.
To further improve the efficiency of DDA-based algorithms, there are n-step algo-
rithms that compute several pixels of a line at a time. The first of these was based on
the idea of double stepping. See [RoWW90] or [Wyvi90]. There are also algorithms
that use a 3- or 4-step process. See [BoyB00] for an n-step algorithm that automati-
cally uses the optimal n and claims to be at least twice as fast as earlier ones.
2.5.3
The Midpoint Line-Drawing Algorithm
Because drawing lines efficiently is so important to graphics, one is always on the
lookout for better algorithms. Another well-known line-drawing algorithm is the so-
called
midpoint line-drawing algorithm
. It produces the same pixels as the Bresenham
algorithm, but is better suited for generalizing to other implicitly defined curves such
as conics and also to lines in three dimensions (see Section 10.4.1). The general idea
was first described in [Pitt67] and is discussed in greater detail by [VanN85].
Assume that a
nonvertical
line
L
is defined by an equation of the form
(
)
=++=0
fxy
,
ax by c
,
