- 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 start
LOAD 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 start
ADDC 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 loop
c_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 now
JUMP circle_loop