page 132,132
title line.asm
comment *
An example of drawing lines by Recursive Bisection
This algorithm was developed as an alternative to the Bresenham
technique. The idea is very simple: Take a line, and find it's
centerpoint. Then find the centerpoint of each of the two new line
segments. Then find the centerpoint of each of the four resulting
line segments, and so on. If you identify all possible centerpoints,
you will have your line.
I developed my original algorithm after seeing a cryptic note by Dr.
C. H. Ting printed in the Journal of Forth Research. The note said
(to paraphrase in the style of Fermat): 'I have discovered a truly
marvelous line drawing algorithm making use of recursion, which,
unfortunately, this space is too small to contain.' Fortunately, Dr.
Ting was not forced to write this in the margin.
After thinking about it for awhile, I came up with the idea of
recursive segmentation. Later, I saw Dr. Ting's original routine,
which, sure enough, employs the same technique. The algorithm
presented here is a composite of both routines, using the best of
each.
The random number generation routine, by the way, was adapted from the
book 'Starting Forth', by Leo Brodie. Don't ask me how it works, I've
been trying to understand it for years.
Richard Leggitt
Left Coast Logic
304 San Lorenzo Av.
Felton, CA 95018
*
code segment
assume cs:code,ds:code
org 100h
; These are setup for EGA. Change to suit your monitor as required.
mode equ 10h ; EGA graphics mode, use 6 for CGA
wides equ 640 ; EGA/CGA screen width
highs equ 350 ; EGA screen height, use 200 for CGA
start: mov ah,0fh ; get current video mode
int 10h
mov vmode,al ; save it so we can restore on exit
mov ah,0 ; now set graphics mode
mov al,mode ; using the predefined mode constant
int 10h
again: mov dx,wides ; pick a random x1
call random ;
mov ax,dx ; put it in ax
mov dx,highs ; pick a random y1
call random ;
mov bx,dx ; put it in bx
mov dx,wides ; pick a random x2
call random ;
mov cx,dx ; put it in cx
mov dx,highs ; pick a random y2
call random ; leave it in dx
call line ; go draw the line ax,bx to cx,dx
mov ah,01h ; check for keypress
int 16h ; use rom bios so ^C won't abort us
jz again ; do another line if no key
xor ah,ah ; key has been pressed, gobble it
int 16h
xor ah,ah ; restore original video mode
mov al,vmode
int 10h
int 20h ; and exit to DOS
; Pseudo-random number generator.
; Call with LIMIT in dx.
; Returns number 0 through LIMIT-1 inclusive in dx.
; SEED is updated with each call.
seed dw 0 ; current seed value
random: push ax ; save ax
push dx ; and limit
mov ax,31421 ; Start with 31421
mul seed ; multiply by current seed value
add ax,6927 ; add 6927
mov seed,ax ; update seed
pop dx ; get back limit
mul dx ; Mulitply seed by limit into DX and AX
pop ax ; Keep overflow as the random number
ret
; The recursive bisection line drawing algorithm.
; Call with X1 in ax, Y1 in bx, X2 in cx, Y2 in dx.
; Draws a line from X1,Y1 to X2,Y2, non-inclusive of X1,Y1
; This routine is recursive, and can reach a nested depth of up to 10 levels,
; depending on the maximum line length (2^10=length of 512 to 1024).
; Each level requires 12 bytes of stack.
line: push cx ; save X2
push dx ; and Y2
; First, calculate centerpoint
add cx,ax ; Average of X1 and X2
shr cx,1 ; is XC
add dx,bx ; Average of Y1 and Y2
shr dx,1 ; is YC
; Does CX match X coord of either end-point?
mov bp,sp ; point bp to stack top
cmp cx,ax ; XC = X1?
jz checky ; yes, go check Y
cmp cx,[bp+2] ; XC = X2?
jnz cont ; no, continue
; Does CY match Y coord of either end-point?
checky: cmp dx,bx ; YC = Y1?
jz adjoin ; yes, go plot
cmp dx,[bp+0] ; YC = Y2?
jnz cont ; no, continue
; Here, X and Y both match, so endpoints must be adjacent.
; Plot X2,Y2 and return.
; Note that X2,Y2 is actually the centerpoint from a previous
; level, except for one case when it is the original end-point.
; In real life, we wouldn't use ROM BIOS, it is too SLOOOOW!!
adjoin: pop dx ; restore Y2
pop cx ; and X2
mov ax,0c0fh ; draw white pixel
xor bx,bx ; to page zero
int 10h ; plot cx,dx
ret ; and return
; Here, endpoints are not adjacent, keep on recursing!
cont: push cx ; push XC
push dx ; and YC
call line ; recurse from X1,Y1 to XC,YC
pop bx ; pop YC into bx (as Y1)
pop ax ; pop XC into ax (as X1)
pop dx ; pop Y2 into dx
pop cx ; pop X2 into cx
call line ; recurse from XC,YC to X2,Y2
ret ; all done
vmode db ? ; saved video mode on entry
code ends
end start
