- Electronics
- PicoBlaze
- Source code
- Xilinx

# Circle drawing

Here is my implementation of the Bresenham Circle Drawing algorithm for the PicoBlaze. The pseudo-code is taken from *Fundamentals of Interactive Computer Graphics* by J.D Foley and A. Van Dam (ISBN 0-201-14468-9).

When assembled, the code consumes 118 instructions (there may be some optimisations it can do), and 6 scratch registers.

**No range checking is performed - if you try to draw a circle that is off-screen, it wil do so.**

### Register, scratch and I/O definitions

; CPU registers temp EQU s8 colour EQU sA length EQU sB x0 EQU sC x1 EQU sD y0 EQU sE y1 EQU sF ; Scratch memory registers cx0 EQU $10 cx1 EQU $11 cy0 EQU $12 cy1 EQU $13 rad0 EQU $14 rad1 EQU $15 ; Output ports ocolour DSOUT $08

- The
*colour*register holds the current byte colour to plot *length*is the number of bytes to transfer (bulk transfer) - 1. For this code, it's zero- The
*xN*and*yN*registers hold the current X and Y coordinates - The
*ocolour*output port is written to in order to write a byte at the current coordinate. The address is automatically calculated by the FPGA outside of the PicoBlaze, so if you are using this code, you will need to take that into consideration. - The
*radN*scratch memory registers hold the radius

### Initialisation

LOAD length, $00 STORE x0, cx0 STORE x1, cx1 STORE y0, cy0 STORE y1, cy1

The length is set to a single pixel plot, and the current X and Y coordinates are stored in scratch memory

### Pre-loop initialisation

; x = 0 LOAD s0, 0 LOAD s1, 0 ; y = radius FETCH s2, rad0 FETCH s3, rad1 ; d = 3 - 2 * radius LOAD s4, 3 LOAD s5, 0 SUB s4, s2 SUBC s5, s3 SUB s4, s2 SUBC s5, s3

This code is actually simpler than the line drawing algorithm, and doesn't really need much preparation before we start plotting

### Loop

; while (x < y) circle_loop: LOAD x0, s0 LOAD x1, s1 SUB x0, s2 SUBC x1, s3 JUMP NC, circle_end ; CIRCLE_POINTS(x, y, value) CALL circle_points ; if (d < 0) TEST s5, $80 JUMP Z, c_d_pos ; { ; d = d + 4 * x + 6 ADD s4, 6 ADDC s5, 0 LOAD x0, s0 LOAD x1, s1 SL0 x0 SLA x1 SL0 x0 SLA x1 ADD s4, x0 ADDC s5, x1 ; } JUMP c_d_neg ; else { c_d_pos: ; d = d + 4 * (x - y) + 10 ADD s4, 10 ADDC s5, 0 LOAD x0, s0 LOAD x1, s1 SUB x0, s2 SUBC x1, s3 SL0 x0 SLA x1 SL0 x0 SLA x1 ADD s4, x0 ADDC s5, x1 ; y = y - 1 SUB s2, 1 SUBC s3, 0 ; } c_d_neg: ; x = x + 1 ADD s0, 1 ADDC s1, 0 JUMP circle_loop

This does pretty much all the work in drawing 1/8th of the circle - the *circle_points* code will ensure the whole circle is plotted.

### Finalisation

At the end, we need to check to see if X and Y are the same, and if they are, then plot 4 points. Finally, we restore the X and Y coordinates to the initial values

circle_end: ; if (x = y) CIRCLE_POINTS(x, y, value) COMP s0, s2 JUMP NZ, c_noend COMP s1, s3 CALL Z, circle_points4 c_noend: circle_reload: FETCH x0, cx0 FETCH x1, cx1 FETCH y0, cy0 FETCH y1, cy1 RET

### Plotting the 8 points

Because the algorithm only plots 1/8th of the circle, we need to plot 8 points for each point the algorithm thinks it is plotting. Luckily these are based on the X and Y coordinates, centred around the circle's centre.

circle_points: ; -x, -y CALL circle_reload SUB x0, s0 SUBC x1, s1 SUB y0, s2 SUBC y1, s3 OUT colour, ocolour ; +x, -y CALL circle_reload ADD x0, s0 ADDC x1, s1 SUB y0, s2 SUBC y1, s3 OUT colour, ocolour ; -x, +y CALL circle_reload SUB x0, s0 SUBC x1, s1 ADD y0, s2 ADDC y1, s3 OUT colour, ocolour ; +x, +y CALL circle_reload ADD x0, s0 ADDC x1, s1 ADD y0, s2 ADDC y1, s3 OUT colour, ocolour circle_points4: ; -y, -x CALL circle_reload SUB x0, s2 SUBC x1, s3 SUB y0, s0 SUBC y1, s1 OUT colour, ocolour ; +y, -x CALL circle_reload ADD x0, s2 ADDC x1, s3 SUB y0, s0 SUBC y1, s1 OUT colour, ocolour ; -y, +x CALL circle_reload SUB x0, s2 SUBC x1, s3 ADD y0, s0 ADDC y1, s1 OUT colour, ocolour ; +y, +x CALL circle_reload ADD x0, s2 ADDC x1, s3 ADD y0, s0 ADDC y1, s1 OUT colour, ocolour RET

There's an optimisation which is used by the very last case where X and Y are the same. In theory, a similar optimisation could be done where X is zero (the initial plot), but that would add more instructions.

### Loop optimisation

There's a redundant jump in the loop code, where it jumps to increment X, and then jumps back to the loop. The increment X could be duplicated there, but a better optimisation is to start X at -1, and increment at the start of the loop. Then, the code could just jump back to the loop start, saving a cycle.

LOAD s0, $ff; Set X to -1 at the startLOAD s1, $ff FETCH s2, rad0 FETCH s3, rad1 LOAD s4, 3 LOAD s5, 0 SUB s4, s2 SUBC s5, s3 SUB s4, s2 SUBC s5, s3 circle_loop: ADD s0, 1; Increment X at the startADDC s1, 0 LOAD x0, s0 LOAD x1, s1 SUB x0, s2 SUBC x1, s3 JUMP NC, circle_end CALL circle_points TEST s5, $80 JUMP Z, c_d_pos ADD s4, 6 ADDC s5, 0 LOAD x0, s0 LOAD x1, s1 SL0 x0 SLA x1 SL0 x0 SLA x1 ADD s4, x0 ADDC s5, x1 JUMP circle_loop; Jump back to main loopc_d_pos: ADD s4, 10 ADDC s5, 0 LOAD x0, s0 LOAD x1, s1 SUB x0, s2 SUBC x1, s3 SL0 x0 SLA x1 SL0 x0 SLA x1 ADD s4, x0 ADDC s5, x1 SUB s2, 1 SUBC s3, 0 c_d_neg:; No need to increment here nowJUMP circle_loop