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
Circle Routine with Aspect Ratio
Moderator: Moderators
- MrSterlingBS
- Vic 20 Enthusiast
- Posts: 178
- Joined: Tue Jan 31, 2023 2:56 am
- Location: Germany,Braunschweig
- Mike
- Herr VC
- Posts: 4846
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Circle Routine with Aspect Ratio
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
Other than that: http://sleepingelephant.com/ipw-web/bul ... mit=Search
- MrSterlingBS
- Vic 20 Enthusiast
- Posts: 178
- Joined: Tue Jan 31, 2023 2:56 am
- Location: Germany,Braunschweig
Re: Circle Routine with Aspect Ratio
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.
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
- Herr VC
- Posts: 4846
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Circle Routine with Aspect Ratio
Even though it is table-based, your implementation suffers from several inefficiencies:
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 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).
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
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.
Please note that:MrSterlingBS wrote:in basic with the MiniGrafik
- 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.
- MrSterlingBS
- Vic 20 Enthusiast
- Posts: 178
- Joined: Tue Jan 31, 2023 2:56 am
- Location: Germany,Braunschweig
Re: Circle Routine with Aspect Ratio
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
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
- Herr VC
- Posts: 4846
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Circle Routine with Aspect Ratio
I'd hope so.MrSterlingBS wrote:[...] thanks for the still efficient code [...]
- MrSterlingBS
- Vic 20 Enthusiast
- Posts: 178
- Joined: Tue Jan 31, 2023 2:56 am
- Location: Germany,Braunschweig
Re: Circle Routine with Aspect Ratio
Sorry Mike for my last post.
Thanks for the even more efficient code!!!thanks for the still efficient code
It was a typing or translation error...
- javierglez
- Vic 20 Hobbyist
- Posts: 107
- Joined: Sat Jun 03, 2017 3:33 pm
Re: Circle Routine with Aspect Ratio
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.
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
- Herr VC
- Posts: 4846
- Joined: Wed Dec 01, 2004 1:57 pm
- Location: Munich, Germany
- Occupation: electrical engineer
Re: Circle Routine with Aspect Ratio
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:
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):
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
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):