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 Circle 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).

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 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
cx0             EQU     $10
cx1             EQU     $11
cy0             EQU     $12
cy1             EQU     $13
rad0            EQU     $14
rad1            EQU     $15

; 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 xN and yN registers hold the current X and Y coordinates
  • 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 radN scratch memory registers hold the radius

Initialisation

                LOAD    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

Pre-loop 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.

Finalisation

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

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

There'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
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-2017
Tribbeck.com / Jason Tribbeck
All trademarks are the property of their respective owners.