Graphics Reference
In-Depth Information
Figure 2.8.
Generating an integral curve
approximation.
=+
(
(
)
(
)
)
pp
e
hx y
,
,
gx y
,
.
(2.2)
i
+
1
i
i
i
i
i
See Figure 2.8. The sequence of points
p
0
,
p
1
,
...
,
p
n
obtained in this way becomes
our approximation to the actual integral curve passing through
p
0
.
Unfortunately, as we move from point to point we start drifting away from the
actual curve and so our approximation will, in general, get further and further away
from the true solution. To make the method work we need to compensate for any
possible error as we move along. There are some very good algorithms that solve dif-
ferential equations with basically this approach by using some fancy error-correcting
terms. For more information see a text on numerical analysis such as [ConD72] or
[DahB74].
Discrete curve-drawing algorithms that are based on the qualitative solutions to
differential equations as described above are called
digital differential analyzer
or
DDA
type algorithms. Let us see what we get in the special case of straight lines.
The differential equation for the straight line that passes through the points (x
0
,y
0
)
and (x
1
,y
1
) is
dy
dx
D
D
y
x
e
e
D
D
y
x
==
,
where Dy = y
1
- y
0
, Dx = x
1
- x
0
, and e is any positive real number. Specializing the
approximation formula, equation (2.2), to this differential equation gives us a
sequence of points
p
i
defined by
=+
(
)
pp
eDD
xy
,
.
(2.3)
i
+
1
i
In fact, the points
p
i
we generate will actually fall on the line, so that we do not have
to worry about compensating for any errors. Although this may seem like overkill in
the case of continuous lines, it does motivate an approach to generating discrete lines
that leads to an extremely efficient such algorithm (the Bresenham algorithm). Note
that if
q
i
is the point with integer coordinates that is gotten from
p
i
by rounding each
real coordinate of
p
i
to its nearest integer, then the points
q
i
define a discrete curve
that is an approximation to the continuous one. The key to getting an efficient line-
drawing algorithm is to be able to compute the
q
i
efficiently.
