Graphics Reference
In-Depth Information
Figure 2.10.
The midpoint line-drawing algorithm
decision.
where -b ≥ a ≥ 0. This assumption implies that our line has slope between 0 and 1.
Lines with other slopes are handled in a symmetric way like in Bresenham's algo-
rithm. Vertical lines are a very special case that would be handled separately. Another
important consequence of our assumptions is that f(x,y) will be positive for points
(x,y) below the line and negative for points above the line. Also like in the Bresenham
algorithm, the points p i = (x i ,y i ) that we will generate for the line will have the prop-
erty that the x-coordinate will be incremented by 1 each time, x i+1 = x i + 1, so that we
only have to determine the change in the y coordinate.
See Figure 2.10. The only possible value for y i+1 is y i or y i + 1. The decision will
be based on the sign of
(
)
dfx
=++
1
,
y
.
5
.
i
i
i
If d i > 0, then the line L crosses the line x = x i + 1 above the point (x i + 1, y i + 0.5) and
we need to let y i+1 be y i + 1. If d i < 0, then we should let y i+1 be y i . If d i = 0, then either
y value would be satisfactory. We shall choose y i in that case. Choosing our points p i
in this way is what constitutes the basic idea behind the midpoint line-drawing algo-
rithm. The only thing that is left is to describe some optimizations that can be made
in the computations. First, the d i can be computed efficiently in an incremental way.
By definition, if d i £ 0, then
(
)
df x
=+ +
2
,
y
0 5
.
i
+
1
i
i
(
) +
(
) +
=
ax
+
2
by
+
0 5
.
c
i
i
=+
da
.
i
On the other hand, if d i > 0, then
(
)
df x
=+ +
2
,
y
.
5
i
+
1
i
i
(
) +
(
) +
=
ax
+
2
by
+
1 5
.
c
i
i
=++
dab
.
i
This shows that the next value of the decision variable can be computed by simple
additions to the previous value. If our line L starts at the point p 0 = (x 0 ,y 0 ) , then
(
) = (
) ++
df x
=
+
1
,
y
+
0 5
.
f xy ab
,
2
.
0
0
0
0
0
This gives us the starting value for the decision variable and all the rest are computed
incrementally. We can avoid the fraction in the starting value and do all our compu-
Search WWH ::




Custom Search