- Electronics
- PicoBlaze
- Source code
- Xilinx

# Line drawing

Here is my implementation of the Bresenham Line 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).

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 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 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

- 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
*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
*xN*and*yN*registers hold the current X and Y coordinates - The
*toxN*and*toyN*scratch memory registers hold the destination X and Y coordinates

### Initialisation

LOAD 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 checking

If 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 - pre-calculations

x_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 Y-axis, since we're swapping the start and end points in order to ensure that we are moving from left to right.

### X stepping - pre-loop

Xbres1: ; 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 - loop

Xbres_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 algorithm

bres_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 - pre-calculations

y_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 vice-versa.

### Y stepping - pre-loop

Ybres1: ; 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 - loop

Ybres_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!