Fast Atari BASIC circle

[Graham Dearsley]

Below I have listed what I think is the fastest possible circle drawing program in Atari BASIC.

 

10 GRAPHICS 8:COLOR 1
20 R=40:CX=150:CY=100
30 X=0:Y=R:D=5-(4*R):DA=12:DB=20-(8*R)
40 PLOT CX+X,CY+Y:PLOT CX+X,CY-Y:PLOT CX-X,CY+Y:PLOT CX-X,CY-Y
45 PLOT CX+Y,CY+X:PLOT CX+Y,CY-X:PLOT CX-Y,CY+X:PLOT CX-Y,CY-X
50 IF D<0 THEN D=D+DA:DB=DB+8:GOTO 70
60 IF D>0 OR D=0 THEN Y=Y-1:D=D+DB:DB=DB+16
70 X=X+1:DA=DA+8
80 IF X<Y THEN GOTO 40

 

I adapted this to Atari BASIC from some pseudo code I found online and NO I do not understand the maths .

Can anyone do better ?

 

CIRCLE.BAS CIRCLE.TXT

[thorfdbg]

9 minutes ago, Graham Dearsley said:

I adapted this to Atari BASIC from some pseudo code I found online and NO I do not understand the maths .

Can anyone do better ?

Explaining or implementing? As far as explaining is concerned, this is a Bresenham style circle drawer similar to the Bresenham line drawer that is in the Os. The circle is the zero-set of the function f(x,y) = (x^2 + y^2 -r^2), and what this algorithm does is essentially an edge tracer of this zero-set, updating the function value f as it goes along. As an update to a quadratic function is linear, no multiplication is required.

 

One cannot really draw circles much faster in terms of simplicity, but there are related algorithms (Bresenham-style) to draw conic sections, i.e. circles, ellipses and so on, just with addition, subtraction and shifts.

[Graham Dearsley]

Yep this is a Bresenham style circle and the pseudo code I found was in a computer science article written by him back in the late 1970's, he also mentions his line drawing algorithm in there ? 

[+Eyvind Bernhardsen]

You can make it run a tiny bit faster by skipping the tests on line 60: D must be >= 0 because line 50 skips to line 70 if D < 0. Your routine takes 112 jiffies on my emulator, removing the tests takes it down to 110.

 

[Graham Dearsley]

Er. If I rem out line 60 then it draws a square ?

[thorfdbg]

8 minutes ago, Graham Dearsley said:

Er. If I rem out line 60 then it draws a square ?

Not remove the line, just the if-condition upfront.

[Graham Dearsley]

Oh yes, silly me ?

Is probably now 2 jiffies faster so you did it ?

[StickJock]

Possibly speed it up a bit by replacing all constant integers in the loop with symbols (0, 1, 8, 16, 40, 70). Also, merge lines 10-30 together so that the goto finds line 40 faster.  Likewise, merge lines 40-50 together and merge lines 70-80 together so that you end up with just lines 10, 40, 60, 70.

 

Edited April 27, 2020 by StickJock

[Graham Dearsley]

There would be a bit of a problem with merging lines 40-50. The reason line 45 exists is because it wouldn't fit on line 40 ?

[explorer]

More speed precalculating operations

 

CXX=CX+X:CYY=CY+Y:CXY=CX+Y:CYX=CY+X:CYI=CY-Y:CYS=CY-X:CXS=CX-X:CXI=CX-Y

 

PLOT CXX,CYY:PLOT CXX,CYI:PLOT CXS,CYY:PLOT CXS,CYI
PLOT CXY,CYX:PLOT CXY,CYS:PLOT CXI,CYX:PLOT CXI,CYS

 

 

Edited April 27, 2020 by explorer

[ac.tomo]

 

20 GRAPHICS 8:COLOR 1:DEG

30 FOR I=0 TO 89

40 X=(COS(I)*50)+50

50 Y=(SIN(I)*50)+96

60 PLOT X,Y:PLOT 100-X-,100-Y

70 PLOT 100-X,Y:PLOT X,100-Y

80 NEXT I

 

This method does the circle 4 times faster than normal, there's no reason why you can't put more PLOTs in to make it 8 times faster. And then you could put the co-ordinates into a string or array in order to call up more circles almost immediately.

[Rybags]

A faster method still can be to keep an array with a SIN table.

Sacrifice some precision by increasing the angle steps, and do lines from prev to current rather than individual plots.

And you can effectively split the circle into 8 segments of 45 degrees each, and build each one during every loop iteration.

[Graham Dearsley]

That code doesn't work ac.tomo but if it did I see that it uses the sin and cosin functions and a FOR/NEXT loop, Atari BASIC and the OS math functions are slow at such things.

Did you try my routine ?

[ac.tomo]

16 minutes ago, Graham Dearsley said:

That code doesn't work ac.tomo but if it did I see that it uses the sin and cosin functions and a FOR/NEXT loop, Atari BASIC and the OS math functions are slow at such things.

Did you try my routine ?

I did try your routine, it's very fast, I never really thought it was possible to create a circle without the trig functions such as COS and SIN. Yes, I did try to increase the PLOTs in my routine but I couldn't do it, I remember doing it a long time ago, and being a bit rusty I can't remember how I did it.

[Graham Dearsley]

I only discovered it could be done last week ?

[Graham Dearsley]

Where would I put the pre calculations Explorer ? As far as I can see they would have to be within the loop, would that really be faster ? 

[Graham Dearsley]

I can't find the original article I based my routine on but below is a similar one for all the mathematicians among you

circlealgorithm.pdf

[StickJock]

5 hours ago, Graham Dearsley said:

There would be a bit of a problem with merging lines 40-50. The reason line 45 exists is because it wouldn't fit on line 40 ?

Maybe if you change the symbols to single characters each?

 

[+Eyvind Bernhardsen]

I made the main loop a for loop:

10 GRAPHICS 8:COLOR 1:R=40:CX=150:CY=100:X=0:Y=R:D=5-(4*R):DA=12:DB=20-(8*R):LIMIT=R*0.707+0.5
20 TI=PEEK(18)*65536+PEEK(19)*256+PEEK(20):FOR X=0 TO LIMIT:PLOT CX+X,CY+Y:PLOT CX+X,CY-Y:PLOT CX-X,CY+Y
30 PLOT CX-X,CY-Y:PLOT CX+Y,CY+X:PLOT CX+Y,CY-X:PLOT CX-Y,CY+X:PLOT CX-Y,CY-X:IF D<0 THEN D=D+DA:DB=DB+8:GOTO 50
40 Y=Y-1:D=D+DB:DB=DB+16
50 DA=DA+8:NEXT X:? PEEK(18)*65536+PEEK(19)*256+PEEK(20)-TI

Now it runs in 102 jiffies (Atari BASIC, PAL machine, emulated). I tried precalculation and making variables for the constants, but it didn't make a measurable difference.

[tebe]

procedure Circle(x0,y0,radius: word);
(*
@description:
Bresenham Circle
*)
var    x,y, dx,dy, txp, typ, txm, tym: word;
    d: smallint;

    procedure DrawCircle;
    begin
        PutPixel( txp, typ);
        PutPixel( txp, tym);
        PutPixel( txm, typ);
        PutPixel( txm, tym);
    end;

begin

    x := 0;
    dx := 0;

    y := radius;
    dy := y shl 2;

    d := 3 - (radius shl 1);            // Decision criterion
    
    while (x <= y) do begin

        if d >= 0 then begin            

            d := 4 + d - dy ;

            dec(dy, 4);

            dec(y);
        end;

        txp := x0+x;  typ := y0+y;
        txm := x0-x;  tym := y0-y;

        DrawCircle;

        txp := x0+y;  typ := y0+x;
        txm := x0-y;  tym := y0-x;

        DrawCircle;

        d := 6 + d + dx;
        
        inc(dx, 4);

        inc(x);
    end;

end;

[danwinslow]

No fair - this is about BASIC

[tebe]

it's only algorithm, similar

Edited April 27, 2020 by tebe

[ac.tomo]

6 hours ago, Graham Dearsley said:

That code doesn't work ac.tomo but if it did I see that it uses the sin and cosin functions and a FOR/NEXT loop, Atari BASIC and the OS math functions are slow at such things.

Did you try my routine ?

When you said my code didn't work do you mean not at all? Or do you mean you cannot expand on it with the other PLOTs, the reason I ask is because I'm having fun with my 65xe, it's not working as it should.

[Graham Dearsley]

As it is it just draws a bit of a line at four corners and then exits with a cursor out range error 3.

 

[ac.tomo]

ok, that does actually work on mine, but it won't allow me to put more PLOT's in. I was playing about with a different program and that wasn't doing what it was supposed to be doing, initially I thought it was me but realised afterwards it is in fact my 65XE. I can't press my RESET key too many times either. Anyone know of an Atari for sale (that works!). This is twice this has happened to me, the other time was a 1050 I bought, realising later after I got it; it loads, but you can't save on it.