# 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

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

### 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
; d = 3 - 2 * radius
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:
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
SL0     x0
SLA     x1
SL0     x0
SLA     x1
; }
JUMP    c_d_neg
; else {
c_d_pos:
; d = d + 4 * (x - y) + 10
SUB     x0, s2
SUBC    x1, s3
SL0     x0
SLA     x1
SL0     x0
SLA     x1
; y = y - 1
SUB     s2, 1
SUBC    s3, 0
; }
c_d_neg:
; x = x + 1
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:

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
SUB     x0, s0
SUBC    x1, s1
SUB     y0, s2
SUBC    y1, s3
OUT     colour, ocolour
; +x, -y
SUB     y0, s2
SUBC    y1, s3
OUT     colour, ocolour
; -x, +y
SUB     x0, s0
SUBC    x1, s1
OUT     colour, ocolour
; +x, +y
OUT     colour, ocolour
circle_points4:
; -y, -x
SUB     x0, s2
SUBC    x1, s3
SUB     y0, s0
SUBC    y1, s1
OUT     colour, ocolour
; +y, -x
SUB     y0, s0
SUBC    y1, s1
OUT     colour, ocolour
; -y, +x
SUB     x0, s2
SUBC    x1, s3
OUT     colour, ocolour
; +y, +x
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
SUB     s4, s2
SUBC    s5, s3
SUB     s4, s2
SUBC    s5, s3
circle_loop:
ADD     s0, 1       ; Increment X at the start
SUB     x0, s2
SUBC    x1, s3
JUMP    NC, circle_end
CALL    circle_points
TEST    s5, \$80
JUMP    Z, c_d_pos
SL0     x0
SLA     x1
SL0     x0
SLA     x1
JUMP    circle_loop  ; Jump back to main loop
c_d_pos:
SUB     x0, s2
SUBC    x1, s3
SL0     x0
SLA     x1
SL0     x0
SLA     x1