Implementing the Bresenham circle algorithm

The name "Bresenham algorithm" is better known in association with a fast method for line plotting. But besides the line-algorithm there is also a less well known circle drawing algorithm.

At this point I do not want to go deeper into the theory and how this algorithm works in detail. This information can be easily found elsewhere. I found that the implementation was a delightful task to extend my knowledge about 6502-assembler. Furthermore I wanted to know how fast an Apple ][ can draw circles.

So here we go: as a first shot I implemented the algorithm in AppleSoft-Basic which draws exactly a single circle at a fixed position with a fixed radius. I wanted to have something to compare the assembler algorithm with regarding the differences in execution speed.

I have created a little demonstration video which shows the assembler algorithm in effect - as well as the drawing of a single circle using the AppleSoft-code. The difference in execution speed is remarkable:

A little enhancement of the algorithm allows the circles to be filled with the drawing color, nevertheless this new piece of code slows down the drawing speed a bit. Circle filling can be disabled when calling the assembler subroutine:

Before we take a closer look on the listings you can download a PDF with the complete assembler listing and a disk image (DSK-format, 140 kB) of the simple circle algorithm (without fill option!) which can be run in an Apple ][-emulator or copied to a "real" floppy disk using a disk transfer program like ADTpro:

Download a Apple ][ disk image — Apple ][ disk image
*DOS 3.3 compatible*

These downloads are the assembler code (Merlin-8) and a DSK-image with the filled circle algorithm:

So how is this done in detail? This Wikipedia-page (sorry only available in German!) yields a useful pseudo-BASIC-snippet which was a good template for my AppleSoft-routine. The above floppy-disk image contains the following AppleSoft-demonstration program which draws a single circle on the HIRES-screen:


10 REM BRESENHAM CIRCLE ALGORITHM IN APPLESOFT
20 REM RADIUS = X
21 X = 32 : REM INIT X = RADIUS
30 Y = 0
40 FE = 10 : REM ERROR TERM
50 HGR : HCOLOR = 3
60 XM = 140 : YM = 80 : REM CENTER OF THE CIRCLE
70 HPLOT XM + X,YM + Y
80 REM LOOP
90 DY = Y * 2 + 1 : Y = Y + 1
100 FE = FE - DY
110 IF FE < 0 THEN DX = 1 - X * 2 : X = X - 1 : FE = FE - DX
120 HPLOT XM + X,YM + Y
121 HPLOT XM - X,YM + Y
122 HPLOT XM - X,YM - Y
123 HPLOT XM + X,YM - Y
124 HPLOT XM + Y,YM + X
125 HPLOT XM - Y,YM + X
126 HPLOT XM - Y,YM - X
127 HPLOT XM + Y,YM - X
130 IF Y < X GOTO 80
140 END

And finally let's peek a bit into the beginning of the assembler listing and the way the assembler routine needs to be called from BASIC. The complete listing can be downloaded with the PDF above. The assembler routine is configured to be called directly from BASIC using the syntax as shown in the following code-snippet (this code example is also included on the disk image):


]LIST
 10 REM BRESENHAM DEMO
 15 TEXT : HOME : HGR2
 20 PRINT CHR$ (4);"BLOAD CALLBRESENHAM,A$6000"
 30 FOR I = 2 TO 74 STEP 4
 40 CALL 24576,140,96,I,3
 50 NEXT I
 100 END

Where CALL 24576, XM, YM, RA, HC calls the assembler routine with the required input parameters which are defined as:

XM: X-coordinate of the center of the circle (0..279)
YM: Y-coordinate of the center of the circle (0..191)
RA: Radius (0..255)
HC: HIRES-color (0..7)

So here we go:


1  ********************************
2  * BRESENHAM´S CIRCLE ALGO 	  *
3  * 				  *
4  * BY MARC GOLOMBECK 		  *
5  * 				  *
6  * VERSION 1.1 / 22.03.2017 	  *
7  *    			  *
8  * VERSION WHICH CAN BE CALLED  *
9  * FROM BASIC VIA THE FOLLOWING *
10 * CALL-COMMAND:                *
11 *                              *
12 * CALL 24576,XM,YM,RA,HC       *
13 *                              *
14 * XM: X-CENTER (0..279)        *
15 * YM: Y-CENTER (0..191)        *
16 * RA: RADIUS OF CIRCLE (0-255) *
17 * HC: HCOLOR (0..7)            *
18 *                              *
19 * A SCREEN RANGE CHECK IS PER- *
20 * FORMED BEFORE EACH CIRCLE    *
21 * PIXEL IS DRAWN TO AVOID A    *
22 * WRAP-AROUND EFFECT           *
23 *                              *
24 ********************************
25 *
26 		ORG $6000
27 *
28 X 		EQU $EB 	; CURRENT POSITION ON ARC
29 Y 		EQU $ED 	; X = $EB, $EC / Y = $ED
30 DX 		EQU $06 	; BRESENHAM X-STEP
31 DY 		EQU $07 	; BRESENHAM Y-STEP
32 FEHLER 	EQU $08 	; BRESENHAM ERROR TERM
33 RADIUS 	EQU $09 	; CIRCLE RADIUS
34 XM 		EQU $FA 	; CIRCLE CENTER X, $FA $FB
35 YM 		EQU $FC 	; CIRCLE CENTER Y
36 XDRAW 	EQU $1A 	; DRAWING POSITION X
37 YDRAW 	EQU $09 	; DRAWING POSITION Y
38 XT 		EQU $FD 	; TWO´S COMPLEMENT OF X,Y
39 YT 		EQU $FF 	; FOR SUBTRACTION
40 *
41 PREAD 	EQU $FB1E 	; READ PADDLE - NOT YET USED
42 WAIT 	EQU $FCA8 	; WAIT-ROUTINE
43 HCOLOR 	EQU $F6F0 	; SET HCOLOR
44 HGR 		EQU $F3E2 	; SWITCH TO HGR
45 HPLOT 	EQU $F457 	; PLOT DOT AT X,Y
46 HPOSN 	EQU $F411 	; POSITION HGR-CURSOR
47 CHKCOM 	EQU $DEBE
48 FRMNUM 	EQU $DD67
49 GETADR 	EQU $E752
50 LINNUM 	EQU $50
51 COMBYTE 	EQU $E74C
52 *
53 * EVAL USER INPUT AND INIT VARIABLES
54 *
55 ENTRY 	JSR CHKCOM 	; READ X POSITION
56 		JSR FRMNUM 	; EVAL FORMULA
57 		JSR GETADR 	; PUT FAC TO LINNUM
58 		LDA LINNUM 	; READ OUT RESULTS
59 		STA XM 		; X-POS CIRCLE CENTER
60 		LDA LINNUM+1
61 		STA XM+1
62 *
63 		JSR COMBYTE 	; READ Y POSITION
64 		STX YM 		; ONLY A 1 BYTE-VALUE
65 *
66 		JSR COMBYTE 	; READ RADIUS
67 		STX RADIUS 	; ONLY A 1 BYTE-VALUE
68 *
69 		JSR COMBYTE 	; READ HCOLOR TO X-REG
70 		JSR HCOLOR 	; SET HCOLOR
71 *
72 INITVAR 	LDA RADIUS 	;
73 		STA FEHLER 	; FEHLER = RADIUS
74 		STA X 		; INIT X = RADIUS
75 		LDA #$00
76 		STA Y 		; INIT Y = 0
77 		STA X+1 	; INIT X-HIGHBYTE = 0
78 *
79 * DRAW THE FIRST PIXELS SO THAT THE CIRCLE HAS NO HOLES
80 *
81 		JSR CALCXTYT 	; GET -X AND -Y FOR PLOT
82 		JSR SETPIX1 	; DRAW FOUR CORNER PIXELS
83 *
84 * LOOP FOR THE OCTANTS
85 *
86 LOOP 	LDA Y
87 		CMP X
88 		BCC LOOPGO 	; IF Y < X THEN LOOP
89 EXIT 	RTS 		; CIRCLE IS FINISHED - EXIT!
90 *
91 * CALC BRESENHAM´S ALGORITHM
92 *
93 LOOPGO 	LDA Y
94 		ASL 		; Y*2
95 		ADC #$01 	; +1
96 		STA DY 		; DY = Y*2 + 1
97 		INC Y 		; Y = Y + 1
98 *
99 		LDA DY 		; CALCULATE TWO´S COMPLEMENT
100 		EOR #$FF 	; Y IS ALWAYS > 0
101 		CLC
102 		ADC #$01
103 		ADC FEHLER
104 		STA FEHLER 	; FEHLER = FEHLER - DY
105 		BPL DOPLOTS 	; IF FEHLER >= 0 THEN DO PLOT!
106 STEPX 	LDA X 		; STEP IN NEGATIVE X-DIR
107 		ASL 		; X*2
108 		EOR #$FF
109 		CLC
110 		ADC #$01 	; -X*2 TWO´S-COMPLEMENT
111 		ADC #$01 	; -X*2 + 1
112 		STA DX 		; DX = 1 - X*2
113 		DEC X 		; X = X - 1
114 		LDA DX 		; DX TWO´S COMPLEMENT
115 		EOR #$FF
116 		CLC
117 		ADC #$01
118 		ADC FEHLER
119 		STA FEHLER 	; FEHLER = FEHLER - DX
120 *
121 * CALC -X AND -Y
122 *
123 DOPLOTS 	JSR CALCXTYT
124 *
125 * PLOT CIRCLE OCTANTS
126 *
127 * HPLOT XM+X, YM+Y - 1ST OCTANT
128 		CLC 		; XM+X
129 		LDA XM
130 		ADC X
131 		STA XDRAW
132 		LDA XM+1
133 		ADC X+1
134 		STA XDRAW+1
135 *
136 		CLC ; YM+Y
137 		LDA YM
138 		ADC Y
139 		STA YDRAW
140 *
141 		JSR PLOTPIX
.
.
.