Graphics Reference
In-Depth Information
2
2
2
.
Er
cur
=--
x
y
After an R-move the new E, call it E
R
, is
2
2
(
)
2
Er
=-+
x
1
21.
-
y
R
(
)
=
E
-
x
+
cur
After a D-move the new E, call it E
D
, is
2
2
2
(
)
(
)
Er
=-+
x
1 1
2121.
--
y
D
(
)
+-
(
)
=
E
-
x
+
y
cur
One algorithm for drawing a circle is to choose that move which makes our new error,
either E
R
or E
D
, have the opposite sign of our current one. The idea is that if we find
ourselves outside the circle we should move as quickly as possible back into the circle
and vice versa. This leads to Algorithm 2.9.2.1, the Bresenham circle-drawing algorithm.
The only problem with Algorithm 2.9.2.1 is that we were using a heuristic that does
not always minimize the real error E (Exercise 2.9.2.1). To get a better algorithm, we
have to make that our goal. Choosing the move that minimizes the error can be done by
testing the sign of |E
D
|-|E
R
|. To gain efficiency we want to avoid having to compute
absolute values of numbers. Consider the possible outcomes shown in following table:
E
D
E
R
|E
D
| - |E
R
|
++
E
D
-
E
R
=
2y
-
1, always positive
+-
E
D
+
E
R
-+
this case never happens
--
E
D
+
E
R
=-
(2y
-
1), always negative
x := 0; y := r;
E := 0;
while
x £ y
do
begin
if
E < 0
then
begin
E := E + y + y - 1;
y := y - 1;
end
;
E := E - x - x - 1;
x := x
+
1;
Draw (x,y);
end
;
Algorithm 2.9.2.1.
The Bresenham circle-drawing algorithm (one octant).
