Midpoint Circle Algorithm

[TomXP411]

Since the topic of circles has come up, here's the Midpoint Circle Algorithm:

10 SCREEN 128
20 Z1=TI
100 XC=160:YC=120
110 R=118:T1=R/16:X=R:Y=0
120 PSET XC+X,YC+Y,0
121 PSET XC+X,YC-Y,0
122 PSET XC-X,YC+Y,0
123 PSET XC-X,YC-Y,0
124 PSET XC+Y,YC+X,0
125 PSET XC+Y,YC-X,0
126 PSET XC-Y,YC+X,0
127 PSET XC-Y,YC-X,0
130 Y=Y+1
140 T1=T1+Y
150 T2=T1-X
160 IF T2 >= 0 THEN T1=T2:X=X-1
170 IF X>=Y   THEN 120
200 PRINT TI-Z1

The general idea here is that the algorithm draws one point per row, starting at the right side of the circle, going down. T1 and T2 are used to curve the point inward, toward the center column, as Y increases. Once the angle reaches 45 degrees, you can no longer draw an unbroken curve, so the algorithm ends. To draw the rest of the circle, you simply need to repeat the curve and mirror X, then Y, and then X and Y.

As far as I know, this is the fastest way to approximate a circle with single pixel accuracy. If you're willing to reduce the accuracy, you can actually get pretty fast with SIN/COS, but you need to use fewer than 46 segments (increment by Pi/23 radians) to match the Midpoint algorithm. At this point, you will se noticeable segmentation.

For the largest circle you can draw fully on screen, this takes 53 jiffies, or .88 seconds. This gets faster as the circle gets smaller. You can get similar performance out of a SIN/COS algorithm, if you draw an arc at 4° increments.

All times are for a circle drawn at (160,120) with a radius of 118 pixels:

Midpoint: 53 jiffies (0.88 seconds)
SIN/COS 360 cycles: 179 jiffies (2.45 seconds)
SIN/COS 4° steps: 91 jiffies (.77 seconds)

Finally, if you want to fill a circle, you can take advantage of the fact that the midpoint algorithm draws per-row:

10 SCREEN 128
20 Z1=TI
100 XC=160:YC=120
110 R=118:T1=R/16:X=R:Y=0
120 LINE XC+X,YC+Y,XC-X,YC+Y,0
122 LINE XC+Y,YC+X,XC-Y,YC+X,0
124 LINE XC+X,YC-Y,XC-X,YC-Y,0
126 LINE XC+Y,YC-X,XC-Y,YC-X,0
130 Y=Y+1
140 T1=T1+Y
150 T2=T1-X
160 IF T2 >= 0 THEN T1=T2:X=X-1
170 IF X>=Y   THEN 120
200 PRINT TI-Z1

Surprisingly, this only takes 48 jiffies. It's actually faster than just drawing the outside arc! This is because it uses fewer BASIC statements, and as we already know, BASIC's biggest bottleneck is in the parsing and dispatching of statements.

[ahenry3068]

Thanks for Posting this Tom I was having a tough time finding an example
for this in BASIC. I found one in JavaScript but they had the X,Y grid inverted.

[ahenry3068]

I'm going to take a deep dive on this code and see if I can make it do
everything my routine is doing. I already incorporated the
SIN/COS implementation into my upcoming Game Code
so I'll have to make this a drop in replacement for my code. Before I can use it.

Again, Thanks.. I've been out of programming for 15 years and probably
25 years since I programmed in a minimal BASIC. It's kinda fun

[ahenry3068]

I've never been the best mathematician. And at the age of 60 I've got noticeably slower at it.
That being said a couple of my early projects on MS-DOS where a PCX decoder
a Windows BMP decoder and an FLI decoder. (Very late confession
I put out the FLI code out on Compuserve as my own in Turbo Pascal. ) But
the first version was an almost direct translation from some C code I had
found on a BBS (yes a BBS not the Web). I ended up rewriting almost
every frame subroutine in Inline ASM though. So I didn't feel to bad.
If I remember right it got somewhere between 35 and 40 frames a second
on a 486sx 25 with an ISA bus Video card (320x200x256 resolution)

[ahenry3068]

That might not be right. It was definitely a 16 bit video card. I think a Matrox
but I might have been running the DX4 75 mhz upgrade for that frame rate.

[TomXP411]

Ok, just to explain things better:

XC and YC are the center position. R is the radius.

X and Y are the current position of the point being drawn, relative to the center.

So the first point is the rightmost edge of the circle, this is X=R and Y=0.

So when XC=160 and YC=120 (the center of the screen in mode $80), then the first point drawn is (278,120).

If you want to draw an ellipse, you can do so by scaling the column when you draw the line:

LINE XC+X*XS,YC+Y,XC-X*XS,YC+Y,0

XS is the horizontal scale. This allows you to make the ellipse wider or narrower; you cannot scale vertically, because this will result in blank lines. (actually, you can reduce the scale vertically. You can't increase it without drawing filler lines. But I'm not going to go there.)

10 SCREEN 128
20 Z1=TI
100 XC=160:YC=120
110 R=78:T1=R/16:X=R:Y=0:XS=2.0
120 LINE XC+X*XS,YC+Y,XC-X*XS,YC+Y,0
122 LINE XC+Y*XS,YC+X,XC-Y*XS,YC+X,0
124 LINE XC+X*XS,YC-Y,XC-X*XS,YC-Y,0
126 LINE XC+Y*XS,YC-X,XC-Y*XS,YC-X,0
130 Y=Y+1
140 T1=T1+Y
150 T2=T1-X
160 IF T2 >= 0 THEN T1=T2:X=X-1
170 IF X>=Y   THEN 120
200 PRINT TI-Z1

So the caveat is that the above code only works with filled ellipses. To draw unfilled ellipses, you need to scale X and Y, based on the narrower dimension, and you can only reduce the scale, not increase it. So you'd need to add a YS variable, then scale by reducing the XS or YS from 1.0 downward to scale the ellipse.

[ahenry3068]

That is what my COS/SIN/PI code is doing. Downscaling.... No Upscaling.

I am following you. And this is MUCH faster then the SIN/COS approach.

At this point I really do have to make it do everything my other routine does.

I'm using it in the Development of HangMan already. I think I'll be able to
make it work.. 1/2 the work might be making sure I can call it as GOSUB 3000
LOL.

[ahenry3068]

I really appreciate the Input. I had a momentary flash of hope
When I saw OVAL in the C128 version of BASIC then
found it wasn't implemented on the CX16

[ahenry3068]

At the moment Super speed is not an issue. Though
I do like to optimize code. I'm setting at slightly less than one
minute to draw the entire Hangman Background, The Gallows
The Noose, and then the victims face. When I implement
Game logic, these things will not be done all at once but
broken out as the Game proceeds. If I can stay under 90
seconds for the Entire Draw (as I complete the guy to
be Hung... ) I think that will be acceptable.

I'm definitely grateful for your example code.

[ahenry3068]

I did put in in my code. Tryed first for substituting the Sine / Cosine algortithm.
That didn't work for me... because I got gaps when using Xsquish & Ysquisth.

I did put it in my Hangman code mostly for the cloud algortithm. Filling many
circles simultaneously... The speed difference was immense.