
Introduction 
Schematic 
PCB Design 
Prototype 
Initial tests 
Reading 
Writing Line drawingHere is my implementation of the Bresenham Line 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). The code has been extended to cope with all quadrant plotting (the basic algorithm assumes that dX < dY and dY is positive). When assembled, the code consumes 166 instructions (there may be some optimisations it can do), and 14 scratch registers. No range checking is performed  if you try to draw a line 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 tox0 EQU $10 tox1 EQU $11 toy0 EQU $12 toy1 EQU $13 dx0 EQU $14 dx1 EQU $15 dy0 EQU $16 dy1 EQU $17 d0 EQU $18 d1 EQU $19 incra0 EQU $1a incra1 EQU $1b incrb0 EQU $1c incrb1 EQU $1d ; Output ports ocolour DSOUT $08
InitialisationLOAD length, $00 LOAD temp, $00 Not much happens here  we'll mark it as a single byte transfer (length = 0), and temp is used to indicate whether dx and dy were negative (this is for quadrant calculations) Calculation of dx and dy; dx = ABS(x2  x1) FETCH s0, tox0 FETCH s1, tox1 SUB s0, x0 SUBC s1, x1 JUMP NC, x_pos XOR s0, $FF XOR s1, $FF ADD s0, $01 ADDC s1, $00 OR temp, 2 x_pos: STORE s0, dx0 STORE s1, dx1 ; dy = ABS(y2  y1) FETCH s2, toy0 FETCH s3, toy1 SUB s2, y0 SUBC s3, y1 JUMP NC, y_pos XOR s2, $FF XOR s3, $FF ADD s2, $01 ADDC s3, $00 OR temp, 1 y_pos: STORE s2, dy0 STORE s3, dy1 There isn't really anything complicated going on here. temp will have bit 0 set if dy was negative, and bit 1 set if dx was negative. Quadrant checkingIf dy is greater than dx, then we need to do the stepping in the Y direction; otherwise, it's stepping in the X (the original algorithm in the book only presents steeping in the X). SUBC s1, s3 JUMP C, y_larger After this, the code splits depending on whether it needs to do X or Y stepping. X stepping  precalculationsx_larger: ; d = 2*dy  dx FETCH s0, dy0 FETCH s1, dy1 SL0 s0 SLA s1 FETCH s2, dx0 FETCH s3, dx1 ; incr1 = 2 * dy STORE s0, incra0 STORE s1, incra1 SUB s0, s2 SUBC s1, s3 STORE s0, d0 STORE s1, d1 ; incr2 = 2* (dy  dx) FETCH s0, dy0 FETCH s1, dy1 FETCH s2, dx0 FETCH s3, dx1 SUB s0, s2 SUBC s1, s3 SL0 s0 SLA s1 STORE s0, incrb0 STORE s1, incrb1 ; if(x1 > x2) { TEST temp, 2 JUMP Z, Xx1_lt_x0 ; x = x2 FETCH x0, tox0 FETCH x1, tox1 ; y = y2 FETCH y0, toy0 FETCH y1, toy1 XOR temp, 1 ; } ; JUMP Xbres1 ; else { Xx1_lt_x0: ; x = x1 ; y = y1 ; } This calculates the incr1, incr2 and d values. Note that the xend value is not used, since the dx value is used instead. Also note that the final XOR temp, 1 is used to 'flip' the Yaxis, since we're swapping the start and end points in order to ensure that we are moving from left to right. X stepping  preloopXbres1: ; WRITE_PIXEL(x, y, value) OUT colour, ocolour FETCH s2, d0 FETCH s3, d1 FETCH s4, dx0 FETCH s5, dx1 Here, we write the first pixel, and also fetch the d and dx values. These are held in normal registers for speed. X stepping  loopXbres_loop: ; while (x < xend) [dx] LOAD s0, s4 OR s0, s5 JUMP Z, bres_end ADD x0, $01 ADDC x1, $00 ; if(d < 0) TEST s3, $80 JUMP Z, Xd_ge_0 ; { ; d += incr1 FETCH s0, incra0 FETCH s1, incra1 ADD s2, s0 ADDC s3, s1 JUMP Xd_lt_0 ; } Xy_neg: SUB y0, $01 SUBC y1, $00 JUMP Xy_changed Xd_ge_0: ; else { ; y ++ TEST temp, 1 JUMP NZ, Xy_neg ADD y0, $01 ADDC y1, $00 Xy_changed: ; d += incr2 FETCH s0, incrb0 FETCH s1, incrb1 ADD s2, s0 ADDC s3, s1 ; } Xd_lt_0: ; WRITE_PIXEL(x, y, value) OUT colour, ocolour SUB s4, $01 SUBC s5, $00 JUMP Xbres_loop This differs slightly to the book in that it firstly uses dx instead of comparing x to xend, and secondly it allows for negative Y steps (under the control of the temp register). End of the line algorithmbres_end: FETCH x0, tox0 FETCH x1, tox1 FETCH y0, toy0 FETCH y1, toy1 RET This isn't really the end  it's the end for the X stepping code (the Y stepping also uses it). It ensures that the current X and Y coordinates are set to the destination X and Y coordinates, before exiting. Y stepping  precalculationsy_larger: ; d = 2*dx  dy FETCH s0, dx0 FETCH s1, dx1 SL0 s0 SLA s1 FETCH s2, dy0 FETCH s3, dy1 ; incr1 = 2 * dx STORE s0, incra0 STORE s1, incra1 SUB s0, s2 SUBC s1, s3 STORE s0, d0 STORE s1, d1 ; incr2 = 2* (dx  dy) FETCH s0, dx0 FETCH s1, dx1 FETCH s2, dy0 FETCH s3, dy1 SUB s0, s2 SUBC s1, s3 SL0 s0 SLA s1 STORE s0, incrb0 STORE s1, incrb1 ; if(y1 > y2) { TEST temp, 1 JUMP Z, Yx1_lt_x0 ; x = x2 FETCH x0, tox0 FETCH x1, tox1 ; y = y2 FETCH y0, toy0 FETCH y1, toy1 XOR temp, 2 ; } ; JUMP bres1 ; else { Yx1_lt_x0: ; x = x1 ; y = y1 ; } This is identical to the X stepping precalculation code, except x is used where y was used and viceversa. Y stepping  preloopYbres1: ; WRITE_PIXEL(x, y, value) OUT colour, ocolour FETCH s2, d0 FETCH s3, d1 FETCH s4, dy0 FETCH s5, dy1 Again, identical to the X code Y stepping  loopYbres_loop: ; while (y < yend) [dy] LOAD s0, s4 OR s0, s5 JUMP Z, bres_end ADD y0, $01 ADDC y1, $00 ; if(d < 0) TEST s3, $80 JUMP Z, Yd_ge_0 ; { ; d += incr1 FETCH s0, incra0 FETCH s1, incra1 ADD s2, s0 ADDC s3, s1 JUMP Yd_lt_0 ; } Yx_neg: SUB x0, $01 SUBC x1, $00 JUMP Yx_changed Yd_ge_0: ; else { ; x ++ TEST temp, 2 JUMP NZ, Yx_neg ADD x0, $01 ADDC x1, $00 Yx_changed: ; d += incr2 FETCH s0, incrb0 FETCH s1, incrb1 ADD s2, s0 ADDC s3, s1 ; } Yd_lt_0: ; WRITE_PIXEL(x, y, value) OUT colour, ocolour SUB s4, $01 SUBC s5, $00 JUMP Ybres_loop And that's the code done!
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. 