        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
