Fast Line Drawing in Assembly: Bresenham's Algorithm in GRAPHICS 7
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:
- dx = |x1 − x0|, dy = |y1 − y0|. Note the step directions sx and sy (+1 or −1).
- Start with err = dx / 2, and repeat dx + 1 times:
- Plot (x, y). Step x by sx. Add dy to err.
- 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:
- 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.
- 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
sxandsybecomeINC/DECinstructions 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
EORplot 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
- Picture: The example: the left fan drawn by the Bresenham routine, the right fan by the OS's DRAWTO, five times each. The text window shows the frames each took. — Program authors; screenshot by the site
- Mapping the Atari — 84-86 ROWCRS/COLCRS, 90-92 OLDROW/OLDCOL (DRAWTO start), 763 ATACHR (DRAW colour), XIO 17/18 — AtariArchives.org
- Atari Operating System User's Manual — display handler (S:) open options and special commands — ksquiggle
