In my last post, I had mentioned circle drawing algorithms and how I'd rediscovered one after a couple of decades. "Why rasterize circles in this era of GPUs and 3d accelerators?", the gentle reader may ask...

Simply because :

A circle has the equation : - So, if you iterate x over the range 0 to r, you can solve for y at each x.

Drawing lines between these points sequentially gives you an arc that's quarter of a circle. One can then mirror these points about the origin, both vertically and horizontally to get the other three quarters of the pi(e).

Code follows...

Why

Because it is based on Object Pascal, the simplest, type safe, statically compiled language that I know of - It has all the low level power ofC , and most of the convenient features of OO, decent type safe generics, more akin to C++ templates than those of Java or C# , plus a superb IDE and RAD designer. It takes very little time to create fully working native GUI applications with it, which are very easily modified.

The language is verbose, and sometimes it requires a lot more code to do some stuff than inC++ - but it is very readable - besides, Wirth is my all time favorite computer science chap, and so I've a soft spot for Pascal based languages.

So in the code, we iterate x across the range0..r because we can compute one quarter of the circle, and draw it mirrored across the X and Y axes.

Actually we can even compute just 1/8th of the circle and generate the other 7 sections by using all combinations of mirroring and swapping X and Y values.

Note that since we iterate overX linearly, The exact shape drawn is not a perfect circle - At the points where Y gets incremented a lot of a change of 1 in X , there are quite straight lines. Doing it by mirroring four or eight pieces does it much better, since a quarter or eighth of 90 degrees is not a big angle and the maximum dx/dy for that range is less than 1

Not much to say about this - When I first learned of sines and cosines, I was like - - And for the most part it is....

Inside your FPU is a lookup table and some interpolation magic to give yousin() and cos()

We iterate over the360 degrees, but we do not choose an arbitrary increment. Too small an increment and we redraw the same pixel, too big and our circle becomes a polygon.

Since the perimeter of a circle is and we want that many pixels drawn at most and at least, the angle we increment by is which is

This means the target pixel drawn at each iteration is one pixel distance away from the last one. This will certainly result in some overdraw, but it is a reasonable value to use. Any more and we will get gaps where the small line segments that form our circle are parallel to theX and Y axes.

sin() and cos() are not so expensive after all, they are probably single cycle instructions on all current processors.

Once again, we use the sine and cosine relations while iterating over all the angles, however, a simple trigonometric identity lets us avoid callingsin() and cos() more than once. If A be our initial angle namely 0 , and B be the increment, we can get sin(A + B) and cos(A + B) quite simply. After that A gets the new incremented angle and we can repeat the process.

We ended up replacing thesin() and cos() function calls with four multiplications and an addition and a subtraction.

In a static compiled orJIT compiled language sin() and cos() go down as single FPU instructions, and this doesn't make much of a difference in speed - However, in an interpreted language, I believe a function call will occur, and might end up being hundreds of times more expensive than the arithmetic.

It might even be possible to write this code using integer arithmetic alone, which you can't do withsin() and cos() - This may be useful in some embedded systems.

There is something quite similar (or is it exactly same?) on

One thing to bear in mind is that errors might get accumulated in this method, since it is incremental in nature, but we're working with integer co-ordinate output, so I doubt if you would get enough error to plot an incorrect pixel.

So that was the mystery of the third circle!

Simply because :

- It's always fun to re-visit fundamentals.
- One may wish to merely iterate a point over a circular path and a GPU can't help you there.
- One may have never heard or thought of this method, so it's fun!

**The math here is the simplest...Which is why it made most sense to me when I was 9 years old.**

The first method

The first method

A circle has the equation :

*x^2 + y^2 = r^2*

Drawing lines between these points sequentially gives you an arc that's quarter of a circle. One can then mirror these points about the origin, both vertically and horizontally to get the other three quarters of the pi(e).

Code follows...

procedure TForm1.DrawCircle1(cx, cy, r: Integer); var x, y, rSquared : Integer; oldy, oldx : integer; begin PaintBox1.Canvas.MoveTo(cx, cy + r); rSquared := r * r; oldx := 0 ; oldy := r; for x := 0 to r do with PaintBox1.Canvas do begin y := Round(Sqrt(rSquared - (x * x))); MoveTo(cx - oldx, cy - oldy); LineTo(cx - x, cy - y); MoveTo(cx - oldx, cy + oldy); LineTo(cx - x, cy + y); MoveTo(cx + oldx, cy - oldy); LineTo(cx + x, cy - y); MoveTo(cx + oldx, cy + oldy); LineTo(cx + x, cy + y); oldx := x; oldy := y; end ; end ;

Why

*Delphi?*

Because it is based on Object Pascal, the simplest, type safe, statically compiled language that I know of - It has all the low level power of

The language is verbose, and sometimes it requires a lot more code to do some stuff than in

So in the code, we iterate x across the range

Actually we can even compute just 1/8th of the circle and generate the other 7 sections by using all combinations of mirroring and swapping X and Y values.

Note that since we iterate over

**I know, all you academic minded ones were dying to read this one.**

Method 2

Method 2

*x = r cos Q and y = r sin Q*

Not much to say about this - When I first learned of sines and cosines, I was like -

*"Ah OK, it's just a look-up table of magic values for the ratios of x and y with h for every angle"*

Inside your FPU is a lookup table and some interpolation magic to give you

procedure TForm1.DrawCircle2(cx, cy, r: Integer); var angle, angleInc, angleMax : Extended; x, y : Extended; begin PaintBox1.Canvas.MoveTo(cx + r, cy); angleinc := 1 / r; angle := 0 ; angleMax := ( 2 * 3.14159265 ) + angleinc; while angle <= angleMax do begin x := r * Cos(angle); y := r * Sin(angle); PaintBox1.Canvas.LineTo(Round(x) + cx, Round(y) + cy); angle := angle + angleinc; end ; end ;

We iterate over the

Since the perimeter of a circle is

*2 * PI * r*

*(2 * PI) / (2 * PI * r)*

*1/r*

This means the target pixel drawn at each iteration is one pixel distance away from the last one. This will certainly result in some overdraw, but it is a reasonable value to use. Any more and we will get gaps where the small line segments that form our circle are parallel to the

**This is a surprisingly ingenious way to avoid trigonometric functions in the loop. Back in the old days, such operations were really heavy, and I dare say this method would have been the fastest. In my test code, it just about beats the second method, but the margin is too small to be of much significance. The reason is that in this day and age,**

Method 3

Method 3

procedure TForm1.DrawCircle3(cx, cy, r: Integer); var angle, angleInc : Extended; i : integer; x, y, sina, sinb, cosa, cosb, sinab, cosab : Extended; begin PaintBox1.Canvas.MoveTo(cx + r, cy); angleinc := 360 / r; sinb := Sin(angleinc / ( 180.0 / 3.14159 )); cosb := Cos(angleinc / ( 180.0 / 3.14159 )); sina := 0 ; cosa := 1 ; i := Round( 360 / angleinc); while i > 0 do begin sinab := sina * cosb + cosa * sinb; cosab := cosa * cosb - sina * sinb; x := r * cosab; y := r * sinab; sina := sinab; cosa := cosab; Dec(i); PaintBox1.Canvas.LineTo(Round(x) + cx, Round(y) + cy); end ; end ;

Once again, we use the sine and cosine relations while iterating over all the angles, however, a simple trigonometric identity lets us avoid calling

sin(a + b) = sin(a) * cos(b) + cos(a) * sin(b)

cos(a + b) = cos(a) * cos(b) - sin(a) * sin(b)

sin(a + b) = sin(a) * cos(b) + cos(a) * sin(b)

cos(a + b) = cos(a) * cos(b) - sin(a) * sin(b)

We ended up replacing the

In a static compiled or

It might even be possible to write this code using integer arithmetic alone, which you can't do with

There is something quite similar (or is it exactly same?) on

__, but that doesn't give a universal circle drawing algorithm.__ HAKMEM item 149 to 152One thing to bear in mind is that errors might get accumulated in this method, since it is incremental in nature, but we're working with integer co-ordinate output, so I doubt if you would get enough error to plot an incorrect pixel.

## No comments:

## Post a Comment