Circle Routine with Aspect Ratio

[MrSterlingBS]

Dear all,

After implementing the C Hacking Issue 9 Circle Code to the VIC the cirlce shows like an ellipse. Is here someone who can give me a tip to change this?

https://codebase64.org/doku.php?id=base:circle_routine

Is used a 168x192 BitMap and the Code from the above Link. The Original Code from C Hacking can Downloaded from the codebase64 site.

Best regards
Sven

[Mike]

The VIC-I chip displays non-square pixels, so a pure circle routine is not that useful on the VIC-20. You need an actual ellipse drawing routine, with the half axes suitably chosen to compensate the non-square pixel aspect ratio.

Other than that: http://sleepingelephant.com/ipw-web/bul ... mit=Search

[MrSterlingBS]

Hello,

here is my solution of a circle (ellipse) drawing routine in basic with the MiniGrafik.
My solution works with cos, sin, some dim arrays and line drawing.

Change the t value for less or more accuracy.

Code: Select all

10 @on:@clr
12 t=24
15 dimcs(t/4+1):dimsn(t/4+1)
20 w=0:w1=2*3.14159265/t
30 x=80:y=96:rx=57:ry=95
35 fora=1tot/4+1
40 cs(a)=cos(w):sn(a)=sin(w)
42 w=w+w1:next
50 poke36879,28
51 ti$="000000"
55 fora=1tot/4
60 @1,x+cs(a)*rx,y+sn(a)*rytox+cs(a+1)*rx,y+sn(a+1)*ry
62 @1,x+cs(a)*rx,y-sn(a)*rytox+cs(a+1)*rx,y-sn(a+1)*ry
64 @1,x-cs(a)*rx,y-sn(a)*rytox-cs(a+1)*rx,y-sn(a+1)*ry
66 @1,x-cs(a)*rx,y+sn(a)*rytox-cs(a+1)*rx,y+sn(a+1)*ry
70 next
71 te=ti
75 poke36879,27
80 geta$
90 ifa$=""then80
100 @return
110 printte/60

[Mike]

Even though it is table-based, your implementation suffers from several inefficiencies:

• In general, you would want to calculate the sub-expressions "RX*CS(...)" and "RY*SN(...)" only once per loop iteration and otherwise take advantage of the 4-fold symmetry of axis-aligned ellipses,
• re-indexing the arrays CS() and SN() from 1..T/4+1 to 0..T/4 easily shaves off another few split seconds, and
• summing up the angle W with W=W+W1 accumulates round-off error. It is better to use W=A*W1 instead (with A going 0..T/4).

With otherwise the same accuracy (T=24), this version here brings down the time from 0.8 seconds to less than 0.5 seconds:

Code: Select all

10 @ON:@CLR
12 T=24
15 DIMCS(T/4):DIMSN(T/4)
20 W=0:W1=2*3.14159265/T
30 X=80.5:Y=96.5:RX=57:RY=95
35 FORA=0TOT/4
40 W=A*W1:CS(A)=COS(W):SN(A)=SIN(W)
42 NEXT
50 POKE36879,28
51 TI$="000000"
54 C2=RX:S2=0
55 FORA=1TOT/4
56 C1=C2:S1=S2:C2=CS(A)*RX:S2=SN(A)*RY
60 @1,X+C1,Y+S1TOX+C2,Y+S2
62 @1,X+C1,Y-S1TOX+C2,Y-S2
64 @1,X-C1,Y-S1TOX-C2,Y-S2
66 @1,X-C1,Y+S1TOX-C2,Y+S2
70 NEXT
71 TE=TI
75 POKE36879,27
80 GETA$
90 IFA$=""THEN80
100 @RETURN
110 PRINTTE/60

I also offset all co-ordinates by 0.5 (by adding that constant to X and Y in line 30) to ensure proper rounding.

That being said, methods drawing circles, ellipses - or arcs of both - from line segments always trade accuracy for speed. With T=24, the polygon characteristic is clearly visible even at that size (and resolution). As soon as only arcs are drawn, perhaps even rotated, you lose the 4-fold symmetry and you have to calculate all endpoints of the line segments in full. You then pretty much end up with the implementation of ellipse arcs that I already had presented here: https://sleepingelephant.com/ipw-web/bu ... 6&start=33.

When it comes to implementations using Bresenham, it can be shown that drawing curved plots from line segments is always slower and less accurate than solving the difference equations for the higher order (which is 2 for conic sections), the latter which also guarantees to plot only exact those pixels as are required and mathematically correct.

in basic with the MiniGrafik

Please note that:

• BASIC is an acronym for Beginner's All-purpose Symbolic Instruction Code and supposed to be spelt in all-caps,
• MINIGRAFIK is a proper name. Proper names generally omit "the" before them (using it is considered either bad style or even pejorative), and
• I chose the spelling of MINIGRAFIK as-is, to be in all-caps. Not MiniGrafik, not Mini-Grafik, not anything else. Except MG as abbreviation when it's clear from context.

Finally - please consider using the attachment facility of the forum to include working *.prg files or *.d64 disk images instead of just providing text dumps. I consider the copy and paste facility of VICE broken as even after all those years it was introduced in 2009 it still does not properly support control characters, CBM characters and vital characters such as {PI}, which is why you needed to write {PI} out as "3.1415..." instead. When I provide (source) code in text form, then only for documentary purposes and I route it through a self-written converter that quotes all non-PETSCII characters in curly brackets (employing one of the several conventions used in the contemporary computer magazines for type-in listings), see here.

[MrSterlingBS]

Dear Mike,

Many thanks for the still efficient code and your explanations. In the future I will attach programs as .prg or .d64 files.
I will note the terms BASIC and MINIGRAFIK.

Best regrads
Sven

[Mike]

[...] thanks for the still efficient code [...]

I'd hope so.

[MrSterlingBS]

Sorry Mike for my last post.

thanks for the still efficient code

Thanks for the even more efficient code!!!



It was a typing or translation error...

[javierglez]

There's this video from a a scener which usually does 8088 assembler code, showing his adventure to draw ellipses with a generic orientation regarding the screen axes. He did a comprehensive work.

https://www.youtube.com/watch?v=d8ulXJZD0P8

I did a standard bresenham circle for a game, but to compute movement, not to draw pixels.

[Mike]

That's actually a very nice YT video you linked to!

Point is, even for the relatively simple task of drawing circles, one is forced to draw on one's reserves because of the non-square pixel aspect ratio of VIC-I for both PAL and NTSC. We're not even talking about rotated ellipses at that point.

The video shows the general idea of rasterization for lines, circles and ellipses: there is a main direction (either along the x-axis or along the y-axis) that is followed by printing one single pixel along it. There is a decision variable, which is kept updated as the routine steps along the line or curve, which indicates when to go perpendicular to the main direction.

Axis-aligned ellipses can be drawn entirely from integer valued calculations. Here's the relevant part of the demo program I wrote in 2006, with some statements regarding pixel clipping slightly rearranged:

Code: Select all

15 X=0:Y=B:S=B*B:T=A*A*(2*Y-1):U=2*B*B:V=2*A*A:E=0
16 X1=CX+X:Y1=CY+Y:P1=X1>=0ANDX1<160:P2=Y1>=0ANDY1<192
17 X2=CX-X:Y2=CY-Y:P3=X2>=0ANDX2<160:P4=Y2>=0ANDY2<192
18 IFP1ANDP2THEN:@1,X1,Y1
19 IFP1ANDP4THEN:@1,X1,Y2
20 IFP3ANDP4THEN:@1,X2,Y2
21 IFP3ANDP2THEN:@1,X2,Y1
22 IFX=AANDY=0THENRETURN
23 F=E+S:D=0
24 G=F-T:IFABS(F)>ABS(G)THENF=G:D=1
25 G=E-T:IFABS(F)>ABS(G)THENF=G:D=2
26 E=F
27 IFD<2THENX=X+1:S=S+U
28 IFD>0THENY=Y-1:T=T-V
29 GOTO16

You see, those are mainly integer additions, subtractions, comparisons and some multiplications, the latter having been neatly factored out of the main loop. No divisions, no square roots, no sine or cosine functions. However, even for relatively small values of 0..255 for the A and B half axes, the values in the variables E, F, G, S, T, U and V become rather large and it is necessary to do these with 32 bit integer arithmetic, i.e. 4 times LDA/ADC/STA for each of the expressions.

The implementation above uses a slight deviation of the main/perpendicular direction ansatz mentioned in the YT video, where the decision variable is actually defined for the current point (and 0 per definition at the start!). It then tests three possible step directions (horizontal/diagonal/vertical) and takes the one with the lowest magnitude of the new decision variable (see lines 23..26). That avoids a case selection found in other ellipse draw implementations, which separates the horizontal/diagonal steps part of the ellipse from the diagonal/vertical steps part. The problem with said case selection is, it once again requires the use of more complicated arithmetic functions, and I found it to fail for extremely skinny ellipses. My implementation works fine even in those cases.

As given, the routine only does axis-aligned ellipses, no rotated ones and also no arcs. And being written in BASIC, it is also somewhat slower than the re-implementation of the BASIC V3.5/V7 CIRCLE command I already had linked to. There exists a rather straight-forward port of the routine in 65xx machine language, I put it into MAXIGRAFIK. That one manages ~4000 pixels/second.

For the more general case of rotated ellipses and ellipse arcs, I am nonetheless quite content with the "pure BASIC" version. The focus being put on capability/flexibility and less so on speed, it does a nice job in a port of a Super Expander demo, which draws Garfield mostly from ellipse arcs (see here):