Fast Line Drawing in Assembly: Bresenham's Algorithm in GRAPHICS 7

GRAPHICS 7 screen with two identical fans of 44 lines radiating from a centre point, brown on the left and green on the right, and a text window reading BRESENHAM:00064 FRAMES and OS DRAWTO:00277 FRAMES

The Atari OS can draw lines: BASIC's DRAWTO, and the same command from assembly, works in every graphics mode. But it is general-purpose code that goes through CIO for every line and handles any mode and colour, and it shows. For a wireframe game, a vector display or a fast chart you need your own line routine. This guide builds one using Bresenham's algorithm, which draws a straight line with nothing but additions, subtractions and comparisons, together with a pixel-plotting routine for GRAPHICS 7. A timed test against DRAWTO shows what the effort buys.

What you'll learn: how Bresenham's algorithm works, how to handle all eight directions with two loops, how pixels are packed in the four-colour bitmap modes, how to call DRAWTO from assembly through XIO 17, and how to time code with the frame counter.

What you need: MADS and an emulator, plus the background from Graphics in Atari BASIC: Modes, COLOR, SETCOLOR, PLOT, DRAWTO and FILL. The example was assembled with MADS and run in atari800 (NTSC, XL/XE OS Rev. 2).

1. The algorithm

A line from (x0, y0) to (x1, y1) has a long axis and a short one. Bresenham's idea is to step one pixel at a time along the long axis, and keep an error counter that says how far the true line has drifted along the short axis. For a line that is wider than it is tall:

  1. dx = |x1 − x0|, dy = |y1 − y0|. Note the step directions sx and sy (+1 or −1).
  2. Start with err = dx / 2, and repeat dx + 1 times:
  3. Plot (x, y). Step x by sx. Add dy to err.
  4. If err has reached dx, subtract dx and step y by sy.

Each pass costs two additions and a comparison. There is no multiplication, division or fraction, which suits the 6502. A line that is taller than it is wide uses the same loop with the roles of x and y swapped. Those two loops, plus the signs sx and sy, cover all eight octants.

Keeping err in one byte. In GRAPHICS 7, coordinates go up to 159 and 95, so err + dy can reach 318, beyond a byte. The routine handles that with the carry: after ADC dy, a set carry means the sum passed 255, so it is certainly at least dx, and the following SBC dx gives the correct remainder because the 6502's subtraction wraps the same way the addition did. No 16-bit arithmetic is needed.

2. Plotting a pixel in GRAPHICS 7

GRAPHICS 7 (ANTIC mode D) is 160 × 96 with four colours: 2 bits per pixel, 4 pixels per byte, 40 bytes per row. Pixel x sits in byte x / 4 of its row, and its two bits are at positions given by x AND 3, with the leftmost pixel in the top bits. To set a pixel without disturbing its three neighbours:

  1. Find the row's start address. The program builds a table of 96 row addresses at start-up, from SAVMSC, so it never has to multiply by 40.
  2. Read the byte, clear the pixel's two bits with a mask ($3F, $CF, $F3, $FC), then OR in the colour's bits for that position.

The colour is stored as a byte with the colour number repeated in all four positions ($55 for colour 1, $AA for colour 2, $FF for colour 3), so AND mask,X picks out the right two bits for any pixel. The same routine works for GRAPHICS 3, 5 and 7 with a different row length and table.

3. Calling DRAWTO from assembly

For comparison, the program also draws with the OS. BASIC's DRAWTO is CIO command 17 on the graphics IOCB (#6). From assembly:

  • OLDROW ($5A) and OLDCOL ($5B–$5C) hold the start point.
  • ROWCRS ($54) and COLCRS ($55–$56) hold the end point.
  • ATACHR ($02FB) holds the colour number.
  • Then set ICCOM to $11 (17), AUX1 to 12 and AUX2 to 0 on IOCB 6, and call CIOV with X = $60.

The program opens the screen the way BASIC's GRAPHICS 7 does: CLOSE #6, then OPEN #6 to "S:" with AUX1 = 28 (12 for read/write + 16 for a text window) and AUX2 = 7.

4. The program

Both halves of the screen get an identical fan of 44 lines from a centre point to the edges, drawn five times over. The left fan is drawn with the Bresenham routine in colour 1, the right one with DRAWTO in colour 2. The frame counter RTCLOK times each, and the results are printed in the text window through E:.

; Bresenham line drawing in GRAPHICS 7 (160x96, 4 colours), timed
; against the OS DRAWTO (XIO 17) drawing the same fan of lines.
RTCLOK  = $12
ROWCRS  = $54
COLCRS  = $55
SAVMSC  = $58
OLDROW  = $5A
OLDCOL  = $5B
ATACHR  = $02FB
ICCOM   = $0342
ICBAL   = $0344
ICBLL   = $0348
ICAX1   = $034A
ICAX2   = $034B
CIOV    = $E456
PTR     = $CB
REPS    = 5                 ; draw each fan this many times

        org $3000
start   ldx #$60            ; GRAPHICS 7 with text window on IOCB 6
        lda #12             ; CLOSE first
        sta ICCOM,x
        jsr CIOV
        ldx #$60
        lda #3              ; OPEN "S:", AUX1 = 12+16, AUX2 = 7
        sta ICCOM,x
        lda #<sname
        sta ICBAL,x
        lda #>sname
        sta ICBAL+1,x
        lda #28
        sta ICAX1,x
        lda #7
        sta ICAX2,x
        jsr CIOV
        ldy #0              ; table of row start addresses
        lda SAVMSC
        sta PTR
        lda SAVMSC+1
        sta PTR+1
rt      lda PTR
        sta rowlo,y
        lda PTR+1
        sta rowhi,y
        clc
        lda PTR
        adc #40
        sta PTR
        bcc rt1
        inc PTR+1
rt1     iny
        cpy #96
        bne rt

        lda #REPS           ; --- our Bresenham, left half, colour 1 ---
        sta rep
        jsr sync
        lda #$55            ; colour 1 in all four pixel positions
        sta colbits
f1      ldx #0
f1a     stx idx
        lda #40
        sta x0
        lda #47
        sta y0
        lda fanx,x
        sta x1
        lda fany,x
        sta y1
        jsr line
        ldx idx
        inx
        cpx #NFAN
        bne f1a
        dec rep
        bne f1
        jsr elapsed
        sta tmine
        stx tmine+1

        lda #REPS           ; --- OS DRAWTO, right half, colour 2 ---
        sta rep
        jsr sync
        lda #2
        sta ATACHR
f2      ldx #0
f2a     stx idx
        lda #120
        sta OLDCOL
        lda #0
        sta OLDCOL+1
        sta COLCRS+1
        lda #47
        sta OLDROW
        lda fanx,x
        clc
        adc #80
        sta COLCRS
        lda fany,x
        sta ROWCRS
        lda #2
        sta ATACHR
        ldx #$60
        lda #$11            ; XIO 17: DRAWTO
        sta ICCOM,x
        lda #12
        sta ICAX1,x
        lda #0
        sta ICAX2,x
        jsr CIOV
        ldx idx
        inx
        cpx #NFAN
        bne f2a
        dec rep
        bne f2
        jsr elapsed
        sta tos
        stx tos+1

        jsr say             ; results in the text window (E:)
        dta $9B,c'BRESENHAM:',0
        lda tmine
        ldx tmine+1
        jsr dec5
        jsr say
        dta c' FRAMES',$9B,c'OS DRAWTO:',0
        lda tos
        ldx tos+1
        jsr dec5
        jsr say
        dta c' FRAMES',0
        jmp *

; ---- draw a line from (x0,y0) to (x1,y1) in colour colbits ----
line    ldx #1              ; sx = +1 or -1, dx = |x1-x0|
        sec
        lda x1
        sbc x0
        bcs l1
        eor #$FF            ; negative: dx = -dx, sx = -1
        adc #1
        ldx #$FF
l1      sta dx
        stx sx
        ldx #1              ; sy, dy the same way
        sec
        lda y1
        sbc y0
        bcs l2
        eor #$FF
        adc #1
        ldx #$FF
l2      sta dy
        stx sy
        lda dx              ; count = longer axis, err = half of it
        cmp dy
        bcc ysteep
        sta count
        lsr
        sta err
xloop   jsr plot            ; x is the major axis
        lda count
        beq done
        dec count
        clc
        lda x0
        adc sx
        sta x0
        clc
        lda err
        adc dy              ; err += dy
        bcs xstep           ; past 255: certainly >= dx
        cmp dx
        bcc xsave
xstep   sbc dx              ; carry is set here
        pha
        clc
        lda y0
        adc sy
        sta y0
        pla
xsave   sta err
        jmp xloop
ysteep  lda dy              ; y is the major axis
        sta count
        lsr
        sta err
yloop   jsr plot
        lda count
        beq done
        dec count
        clc
        lda y0
        adc sy
        sta y0
        clc
        lda err
        adc dx
        bcs ystep
        cmp dy
        bcc ysave
ystep   sbc dy
        pha
        clc
        lda x0
        adc sx
        sta x0
        pla
ysave   sta err
        jmp yloop
done    rts

; ---- set pixel (x0,y0) in GRAPHICS 7: 4 pixels per byte ----
plot    ldy y0
        lda rowlo,y
        sta PTR
        lda rowhi,y
        sta PTR+1
        lda x0
        and #3
        tax                 ; X = pixel position in the byte
        lda x0
        lsr
        lsr
        tay                 ; Y = byte in the row
        lda (PTR),y
        and notmask,x       ; clear the old two bits
        sta tmp
        lda colbits
        and mask,x          ; this colour's bits in this position
        ora tmp
        sta (PTR),y
        rts

sync    lda RTCLOK+2        ; wait for a new frame, remember it
s1      cmp RTCLOK+2
        beq s1
        lda RTCLOK+2
        sta t0
        lda RTCLOK+1
        sta t0+1
        rts
elapsed sec                 ; frames since sync: A = low, X = high
        lda RTCLOK+2
        sbc t0
        pha
        lda RTCLOK+1
        sbc t0+1
        tax
        pla
        rts

say     pla                 ; print the string after the JSR via E:
        sta PTR
        pla
        sta PTR+1
sy1     inc PTR
        bne sy2
        inc PTR+1
sy2     ldy #0
        lda (PTR),y
        beq sy3
        jsr putc
        jmp sy1
sy3     lda PTR+1
        pha
        lda PTR
        pha
        rts
putc    ldx #0
        stx ICBLL
        stx ICBLL+1
        pha
        lda #11
        sta ICCOM
        pla
        jmp CIOV
dec5    sta num             ; A/X as a decimal number, 5 digits
        stx num+1
        ldx #0
dc1     lda #'0'
        sta digit
dc2     lda num
        sec
        sbc p10lo,x
        tay
        lda num+1
        sbc p10hi,x
        bcc dc3
        sta num+1
        sty num
        inc digit
        bne dc2
dc3     stx savx
        lda digit
        jsr putc
        ldx savx
        inx
        cpx #5
        bne dc1
        rts
p10lo   dta <10000,<1000,<100,<10,<1
p10hi   dta >10000,>1000,>100,>10,>1
num     dta a(0)
digit   dta 0
savx    dta 0

mask    dta $C0,$30,$0C,$03
notmask dta $3F,$CF,$F3,$FC
sname   dta c'S:',$9B
NFAN    = 44
fanx    :10 dta #*8         ; top edge
        :10 dta #*8+7       ; bottom edge
        :12 dta 0           ; left edge
        :12 dta 79          ; right edge
fany    :10 dta 0
        :10 dta 95
        :12 dta #*8
        :12 dta #*8+7
x0      dta 0
y0      dta 0
x1      dta 0
y1      dta 0
dx      dta 0
dy      dta 0
sx      dta 0
sy      dta 0
err     dta 0
count   dta 0
colbits dta 0
tmp     dta 0
idx     dta 0
rep     dta 0
t0      dta a(0)
tmine   dta a(0)
tos     dta a(0)
rowlo   .ds 96
rowhi   .ds 96
        run start

5. Results

On NTSC, the Bresenham routine took 64 frames for its 220 lines, and DRAWTO took 277 frames for the same lines: our routine was about 4.3 times faster. At a glance the two fans look the same. Zoomed in, some steps fall on different pixels, because each routine rounds differently along the way.

Most of our routine's time is spent in plot: the table lookups, the read-modify-write of the screen byte and the subroutine call. The usual next steps, which we have not measured here, are:

  • Plot inline, and move a pointer instead of recalculating it. Moving one pixel right only changes the mask (and the byte every fourth pixel), and moving one row only adds 40 to the pointer.
  • Write separate loops per octant, so that sx and sy become INC/DEC instructions instead of additions.
  • Draw horizontal and vertical lines with special cases. A horizontal line can fill whole bytes.
  • Use the right colour mode. Plotting in GRAPHICS 8 (2 colours, 8 pixels per byte) needs a different mask table, and an EOR plot gives lines that can be erased by drawing them again.

6. A bug worth knowing about

Our first version printed the timings with a small decimal routine that kept the tens digit in X while it called the character output. CIO doesn't preserve X, so the tens digit vanished and the screen showed nonsense timings. Any routine that calls CIOV must expect A, X and Y to change. The final program keeps the digit counter in memory around each call.

Troubleshooting

  • Lines go the wrong way, or wrap around the screen: the sign of sx or sy is wrong, or dx and dy were not made positive.
  • Steep lines are drawn as dotted horizontal ones: you need the second loop for lines taller than they are wide.
  • Neighbouring pixels get erased: the mask isn't clearing just the two bits of the pixel being set.
  • A line goes past its end point: the count must be dx (or dy). The loop plots once more before checking, giving dx + 1 pixels.
  • DRAWTO draws nothing: the screen wasn't opened on IOCB 6, or ATACHR holds colour 0 (the background).
  • Crash with large coordinates: the row table has 96 entries; check y < 96 and x < 160 before plotting, or clip the line first.

Further reading

  • Ian Chadwick, Mapping the Atari: OLDROW/OLDCOL (90–92), ROWCRS/COLCRS (84–86), ATACHR (763) and the screen handler.
  • On this site: Graphics in Atari BASIC: Modes, COLOR, SETCOLOR, PLOT, DRAWTO and FILL, Circles, Polygons and Curves in Atari BASIC, Signed Numbers on the 6502: Two's Complement, Overflow and Signed Comparisons, CIO and IOCBs: How Atari Input/Output Really Works.

Credits