Welcome to Tribbeck.com

Introduction | Schematic | PCB Design | Prototype | Initial tests | Reading | Writing
Instructions | Useful stuff | Acceleration I II | Coordinates | Circles | Font preparation | Fonts

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!

Introduction | Schematic | PCB Design | Prototype | Initial tests | Reading | Writing
Instructions | Useful stuff | Acceleration I II | Coordinates | Circles | Font preparation | Fonts

Updated: 2011-06-08 20:41:21 | Comments: 0 | Show comments | Add comment
© Copyright 1997-2013
Tribbeck.com / Jason Tribbeck
All trademarks are the property of their respective owners.