Graphics Reference
In-Depth Information
Figure 2.9.
Simple and symmetric
DDA generated lines.
¥ simple DDA
∑ symmetric DDA
In the continuous case one always generates points on the line no matter what e
is chosen but the choice of e does matter when generating discrete lines. We now look
at two possible choices for e. These give rise to what are called the
simple
and
sym-
metric DDA
, respectively.
Let m = max(|Dx|,|Dy|).
The simple DDA:
Choose e=1/m.
The symmetric DDA:
Choose e=2
-n
, where 2
n-1
£ m < 2
n
.
2.5.1.1
Example.
Suppose that we want to generate the discrete line from (1,2) to
(6,5).
Solution.
In this case (Dx,Dy) = (5,3). For the simple DDA we have
+
(
)
e
=
15
,
e
D
x
=
1
,
e
D
y
=
35
,
and
pp
=
135
,
.
i
+
1
i
In the case of the symmetric DDA, we have
+
(
)
e
=
18
,
e
D
x
=
58
,
e
D
y
=
38
,
and
pp
=
5838
,
.
i
+
1
i
The points that are generated are shown in Figure 2.9. The points of the simple DDA
are shown as ¥¢s and those of the symmetric DDA are shown as solid circles.
2.5.2
The Bresenham Line-Drawing Algorithm
Although the DDA algorithms for drawing straight lines are simple, they involve
real
arithmetic. Some simple modifications result in an algorithm that does only
integer
arithmetic, and only additions at that.
Note that in the case of the simple DDA, either x or y will always be incremented
by 1. For simplicity, assume that the start point of our line is the origin. If we also
restrict ourselves to lines whose endpoint is in the first octant in the plane, then it will
be the x that always increases by 1. Therefore, we only need to worry about comput-
ing the y coordinates efficiently.
