Pseudocode for CIRCLE algorithm?

Can anyone provide me with the pseudocode for the Spectrum's CIRCLE algorithm? My machine code knowledge isn't up to reading the ROM routine. I'm trying to recreate the algorithm in another language and have been using Bresenham's Midpoint Circle algorithm (copied from the web) which gives the same end result but doesn't 'corkscrew' from the origin point like the Spectrum. I need the peudocode to use x, y and radius as inputs. Thanks!

Comments

  • The algorithm is explained in The Complete Spectrum ROM Disassembly. Even if you don’t understand machine code, you should be able to figure out the math behind it.
    Every man should plant a tree, build a house, and write a ZX Spectrum game.

    Author of A Yankee in Iraq, a 50 fps shoot-’em-up—the first game to utilize the floating bus on the +2A/+3,
    and zasm Z80 Assembler syntax highlighter.
    Member of the team that discovered, analyzed, and detailed the floating bus behavior on the ZX Spectrum +2A/+3.

    A few Spectrum game fixes.
  • Unfortunately my machine code knowledge isn't up to reading the ROM routine. I'm looking for the maths algorithm and I'm not knowledgable about mc enough to extract the maths from the technical mc in the ROM routine.
  • If you are only faking to draw a circle, then just draw a circle.

    If that's too simple, here's an alternative:
    1) collect all the points you need to plot
    2) sort them in the order you can see in the circle draw command
    3) plot them all in that order.
  • edited February 17
    Good answer, thanks. My aim is to write a program in vb that simulates Spectrum BASIC as much as possible in the main program, such that anyone with a knowledge of Spectrum BASIC will be able to read the main prog and know what the program does. I'm 99% completed with plot, draw, over, print etc etc all finished. The final step is the circle instruction but I'm stuck as my limited knowledge of maths and machine code means I can't understand the ROM routine :(. I'm trying to find out how the Spectrum processes the x co-ord, y-coord and radius.
    Post edited by LevelUp on
  • You can find an implementation of the Spectrum's curve DRAW command in SpecBAS which is an almost complete implementation of Sinclair BASIC for PCs:
    Procedure SP_DrawSpeccyCurve(X, Y, Angle: aFloat);
    Var
      Z, W, F, M0, M1, M2, M3, M4, SC, MM1: aFloat;
      NumArcs: Integer;
    Begin
    
      If MathMode = 1 Then Angle := DegToRad(Angle);
    
      Z := Abs((Abs(X)+Abs(Y))/Sin(Angle/2));
      If (Round(Sin(Angle/2)*10000000) = 0) or (Z < 1) Then
        SP_DrawLine(X, Y)
      Else Begin
        NumArcs := Min(4*Round(Round(Abs(Angle*Sqrt(Z))+0.5)/8)+4, 252);
        W := Sin(Angle/(2*NumArcs))/Sin(Angle/2);
    
        M0 := DRPOSY;
        SC := DRPOSX;
        F := 0.5*(Angle-(Angle/NumArcs));
        M1 := (Y*W*Sin(F))+(X*W*Cos(F));
        M2 := (Y*W*Cos(F))-(X*W*Sin(F));
        M3 := Cos(Angle/NumArcs);
        M4 := Sin(Angle/NumArcs);
    
        While NumArcs > 0 Do Begin
    
          M0 := M0 + M2;
          SC := SC + M1;
    
          SP_DrawLine(SC - DRPOSX, M0 - DRPOSY);
    
          MM1 := M1;
          M1 := (M1*M3)-(M2*M4);
          M2 := (MM1*M4)+(M2*M3);
    
          Dec(NumArcs);
    
        End;
    
      End;
    
    End;
    

    You just need to set the angle to 2*PI iirc to get a circle. The CIRCLE command just sets up 2*PI prior to drawing arcs as in the algorithm above.
  • Dunny wrote: »
    You just need to set the angle to 2*PI iirc to get a circle. The CIRCLE command just sets up 2*PI prior to drawing arcs as in the algorithm above.

    Cheers, that looks like something I can work with. I'll have a go at implementing it at the weekend.
  • That routine will produce precisely the same curves that the Speccy ROM can - including the weird effects you can get when setting the angle parameter to insane values, so it will draw your circles.

    Unfortunately they're not very good circles, but if you're after authenticity then that's the way to go :)
  • edited August 12
    Bresenham circle is the way to go in my opinion

    https://geeksforgeeks.org/bresenhams-circle-drawing-algorithm/
    PIXADD		equ		$22AA
    CRGRE1		equ		$233B			; On entry stack = X Y Z -> Draws circle at X,Y with radius Z
    STACKA		equ		$2D28
    ;
    COORDS		equ		$5C7D			; Plot x,y values
    ;
    DRAWBRESCIRCLE equ $
    ; Draw a Bresenham circle at oX,oY radius Rad
    ; On entry B = oY, C = oX, A = Rad
    			LD (DBCOORDS),BC		; Save start coords
    			LD E,A					; Save radius
    			CP 35
    			JR NC,DBCDOBRES
    			PUSH AF					; Save radius
    			LD A,(DBCOORDS)
    			CALL STACKA
    			LD A,(DBCOORDS+1)
    			CALL STACKA
    			POP AF					; Restore radius
    			CALL STACKA
    			JP CRGRE1
    ; Use slow ROM routine circle routine
    ; for circles with radius < 20 pixels
    DBCDOBRES	LD A,$01
    			AND A
    			SUB E
    			LD (DBCDVAR),A			; d = 1 - Rad
    ;
    			XOR A
    			LD (DBCXVAR),A			; x = 0
    ;
    			LD A,E
    			LD (DBCYVAR),A			; y = Rad
    ;
    DBCLP1		LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCYVAR)
    			AND A
    			SUB E
    			JP C,DBCDONE			; while y > x
    ;
    ; Plot the eight sets of points for each bit of the circle
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			ADD A,E
    			LD C,A
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			ADD A,E
    			LD B,A
    			CALL PLOTSUB			; plot Xo + x, Yo + y
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			ADD A,E
    			LD C,A
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			SUB E
    			LD B,A
    			CALL PLOTSUB			; plot Xo + x, Yo - y
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			SUB E
    			LD C,A
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			ADD A,E
    			LD B,A
    			CALL PLOTSUB			; plot Xo - x, Yo + y
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			SUB E
    			LD C,A
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			SUB E
    			LD B,A
    			CALL PLOTSUB			; plot Xo - x, Yo - y
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			ADD A,E
    			LD C,A
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			ADD A,E
    			LD B,A
    			CALL PLOTSUB			; plot Xo + y, Yo + x
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			ADD A,E
    			LD C,A
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			SUB E
    			LD B,A
    			CALL PLOTSUB			; plot Xo + y, Yo - x
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			SUB E
    			LD C,A
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			ADD A,E
    			LD B,A
    			CALL PLOTSUB			; plot Xo - y, Yo + x
    			LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCOORDS)
    			SUB E
    			LD C,A
    			LD A,(DBCXVAR)
    			LD E,A
    			LD A,(DBCOORDS+1)
    			SUB E
    			LD B,A
    			CALL PLOTSUB			; plot Xo + y, Yo + x
    ;
    			LD A,(DBCDVAR)
    			AND A
    			JP M,DBCDNEG			; if d < 0 then
    			LD E,A					; save d
    			LD A,(DBCXVAR)
    			SLA A					; 2 * x
    			ADD A,E					; d + (2 * x)
    			ADD A,$03				; d + (2 * x) + 3
    			LD (DBCDVAR),A			; d = d + (2 * x) + 3
    			LD HL,DBCXVAR
    			INC (HL)				; x = x + 1
    			JP DBCLP1
    ; 
    DBCDNEG		LD A,(DBCYVAR)
    			LD E,A
    			LD A,(DBCXVAR)
    			AND A
    			SUB E					; x - y
    			SLA A					; 2 * (x - y)
    			LD E,A
    			LD A,(DBCDVAR)
    			ADD A,E					; d + 2 * (x - y)
    			ADD A,$05				; d + 2 * (x - y)
    			LD (DBCDVAR),A			; d = d + 2 * (x - y)
    			LD HL,DBCXVAR
    			INC (HL)				; x = x + 1
    			INC HL
    			DEC (HL)				; y = y - 1
    			JP DBCLP1
    ;
    DBCDONE	RET
    ;
    DBCOORDS defw 0
    ; Storage for start coords
    DBCDVAR defb 0
    DBCXVAR defb 0
    DBCYVAR defb 0
    ; Storage for temp variables
    ;
    PLOTSUB		LD (COORDS),BC
    			CALL PIXADD
    			LD B,A
    			INC B
    			LD A,1
    PLOTLOOP		RRCA
    			DJNZ PLOTLOOP
    			LD B,A
    			LD A,(HL)
    			OR B
    			LD (HL),A
    			RET
    ;
    

    If you want to return to BASIC do a
    			LD HL,$2758				; Restore HL' to the address in SCANNING of the 'end-calc' instruction (as CIRCLE ROM Calls alter it) as per The Complete Spectrum ROM Disassembly (p201) http://www.worldofspectrum.org/infoseekid.cgi?id=2000076
    			EXX
    

    after the DRAWBRESCIRCLE call as CRGRE1 (if used) changes HL' register

    Regards,
    Derek.
    Post edited by dbolli on
    1985: ZX Spectrum+ 48K Interface 1 ZX81 16KB ASZMIC/SP ROM Philips 12" B/W TV Epson Dot Matrix Printer ZX Printer Now: Late 2015 iMac 5K 27" 4GHz i7 32GB RAM macOS 10.15.7 1TB Ext SSD USB C Drive Ext 4TB 3TB and 2TB USB 3 Hard Disks Ext USB 3 Blu-Ray iPad R7 32GB iPhone 6s 64GB iOS 14.0.1 Apple TV Gen 2
  • Basic Interpolation Guides / Circle
    (c)SerzhSoft, somewhere in 1994..1998 maybe :)

    I_CIRCLE.BAS

    10 BORDER 0: PAPER 1: INK 7: CLS
    20 INPUT "x0=";x0;"; y0=";y0;"; r=";r
    30 GO SUB 1000
    40 GO TO 20
    1000 REM - Circle(x0,y0),r -
    1010 LET b=r: LET c=0
    1020 LET a=INT (r/2)
    1030 GO SUB 1500
    1050 LET c=c+1
    1055 LET a=a-c
    1080 IF a>=0 THEN GO TO 1030
    1100 LET b=b-1
    1110 LET a=a+b
    1120 IF b>=c THEN GO TO 1030
    1140 RETURN
    1500 REM - Put 8 pixels -
    1510 GO SUB 1600
    1600 REM - Put 4 pixels -
    1610 LET k=c: LET c=b: LET b=k
    1620 LET x1=x0+c
    1630 GO SUB 1700
    1640 LET x1=x0-c
    1700 REM --- Put 2 pixels ---
    1710 LET y1=y0+b
    1720 GO SUB 2000
    1730 LET y1=y0-b
    2000 REM - PutPixel(x1,y1) -
    2010 IF x1>=0 AND x1<=255 AND y1>=0 AND y1<=175 THEN PLOT x1,y1
    2020 RETURN
  • Basic Interpolation Guides
    Did you write it your self or is it from a book?
    in both cases i think such routine should have been in the ZX Basic manual, since its simple and direct and even fast, for basic
    if this is in asm you wont need the calculator so its MUCH faster then the original routine.
    thanx
    my old website http://home.hccnet.nl/c.born/ has changed to http://www.cborn.nl/zxfiles/ so just click it and select a file
  • yea, it was my unreleased book, started but freezed at last millenium :)
    written for simplest translate to z80 asm...

    here was, as I see :) -
    I_LINE.BAS
    I_CIRCLE.BAS
    I_F_CIR.BAS
    I_SCALIN.BAS
    I_SHADIN.BAS
    I_ARRAY.BAS
    ....

    maybe 'll finish it in next ages...
    Thanked by 1Luzie
  • edited August 14
    hmm..., finded some oldskool z80 implementation:
    ; Algorythm designed by SerzhSoft (c) 1996
    ; drawing a circle
    ; HL = x, DE = y (-32768 .. + 32767)
    ; A = radius (0..255); at 0 - point

    http://www.zxpress.ru/article.php?id=7876

    with translate:

    https://translate.google.ru/translate?hl=en&sl=ru&tl=en&u=http://www.zxpress.ru/article.php?id=7876

    hah, funny old turn-sprite procedure detected, with 360 degrees, not 256 :)))

    ...some s*h*i*t after
    BUFFER EQU $
    must be deleted...
    Post edited by Serzh on
    Thanked by 1Luzie
  • edited August 17
    Thanks for your link
    google is strange, they offer translate, download, print file, pure text file but TRANSLATE ?? None of the above is translate despite the original dejavu#4 has no such features
    so google is to stupid to translate, yet i have a text-based copy now ????

    and i am curious to you Basic Guide, i think i like to ad it to the BB compendium, a collection of knowledge aswell.
    Post edited by Crisis on
    my old website http://home.hccnet.nl/c.born/ has changed to http://www.cborn.nl/zxfiles/ so just click it and select a file
Sign In or Register to comment.