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