Graphics Reference
In-Depth Information
x := 0;
y := r;
g := 2*r - 3;
dgr := - 6; dgd := 4*r - 10;
while
x £ y
do
begin
if
g < 0
then
{ go diagonal }
begin
g := g + dgd;
dgd := dgd - 8; { -4 (x+1) + 4 (y-1) - 10 = -4x + 4y - 10 - 8 }
y := y - 1;
end
else
{ go right }
begin
g := g + dgr;
dgd := dgd - 4; { y stays the same, x increases by 1 }
end
;
dgr := dgr - 4;
{ x always gets incremented: -4 (x+1) - 6 = -4x - 6 - 4 }
x := x + 1;
Draw (x,y);
end
;
Algorithm 2.9.2.2.
An improved Bresenham circle-drawing algorithm (one octant).
and we can generate points on it using the standard parameterization
Æ
(
)
q
a
cos
q
,
b
sin
q
.
Differentiating equation (2.6) implicitly gives the differential equation
2
2
.
dy
dx
x
y
b
a
=-
This leads to a DDA approach similar to the case of a circle.
Because ellipses are an important class of curves, many algorithms exist to draw
them. The Bresenham approach to drawing a circle can be extended to ellipses, but
that algorithm will no longer guarantee a minimum linear error between the ellipse
and the chosen pixels. See [Mcil92] for a correct Bresenham-type algorithm. Alterna-
tively, a version of the midpoint algorithm described in Section 2.5.3 produces an
efficient and more accurate algorithm. For more details and other references see
[VanN85] and [Roge98].
