
Introduction 
Schematic 
PCB Design 
Prototype 
Initial tests 
Reading 
Writing Line drawingHere is my implementation of the Bresenham Circle Drawing algorithm for the PicoBlaze. The pseudocode is taken from Fundamentals of Interactive Computer Graphics by J.D Foley and A. Van Dam (ISBN 0201144689). 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 offscreen, 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
InitialisationLOAD 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 Preloop 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. FinalisationAt 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 pointsBecause 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 optimisationThere'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
Introduction 
Schematic 
PCB Design 
Prototype 
Initial tests 
Reading 
Writing
Updated: 20110608 20:41:21  Comments: 0
 Show comments
 Add comment

© Copyright 19972013 Tribbeck.com / Jason Tribbeck All trademarks are the property of their respective owners. 