Re: Ack Egad Newbie needs help with his line drawing algorithm

From: Matt Taylor (para_at_tampabay.rr.com)
Date: 05/20/04 

Date: Thu, 20 May 2004 06:16:17 +0000 (UTC)

"Frogbert" <frogbert@host.sk> wrote in message
news:ab6f7e87.0405190259.6f5ac4e1@posting.google.com...
> I'm trying to write my first assembly program (well first of any
> value) for my comp arch and assembler course. Basicaly my program
> accepts 2 lots of x,y coodinates and then draws a line between them. I
> have the input stages all correct however I can't seem to get my line
> drawing algorithm to work correctly. I am porting the algorithm found
> here: http://www.gamedev.net/reference/articles/article1275.asp and as
> far as I can see I've done it correctly but that is not the case. I
> was hopeing a fresh pair of eyes might be able to spot a logic error.

Look for my comments inline.

>
;---------------------------------------------------------------------------
----------------
> ;DrawLine calculates the steps inbetween and then draws a line on the
> screen
>
;---------------------------------------------------------------------------
----------------
> DrawLine PROC X1:word, Y1:word, X2:word, Y2:word ;Calculates and draws
> a line on the screen
> LOCAL deltaX:word ;Distance between the x points
> LOCAL deltaY:word ;Distanve between the y points
> LOCAL X:word ;X counter, starts at the first x point
> LOCAL Y:word ;Y counter, starts at the first y point
> LOCAL xIncrement1:word ;Two X increment variables are needed
> LOCAL xIncrement2:word
> LOCAL yIncrement1:word ;as are two Y increment variables
> LOCAL yIncrement2:word
> LOCAL den:word ;denominator
> LOCAL num:word ;numerator
> LOCAL numadd:word ;number add
> LOCAL numPixels:word ;number of pixels
>
> mov ax, X1 ;start off at X1
> mov X, ax
> mov ax, Y1 ;and start off at Y1
> mov Y, ax
>
> mov ax, X2 ;
> sub ax, X1 ;
> call ABS ;
> mov deltaX, ax ; deltaX = abs(x2-x1)
>
> mov ax, Y2 ;
> sub ax, Y1 ;
> call ABS ;
> mov deltaY, ax ; deltaY = abs(y2-y1)
>
>
> mov ax, X2 ;put X2 into eax register to test
> cmp ax, X1 ;test to see if x values are increasing
> jge xIncreasing ;if they are jump to xIncreasing
> mov xIncrement1, -1 ;else x is decreasing
> mov xIncrement2, -1
> jmp testY ;jump to testY
> xIncreasing:
> mov xIncrement1, 1 ;X is increasing
> mov xIncrement2, 1

This logic could actually be simplified. Consider the following piece of C
code:

xinc1 = xinc2 = ((x2 >= x1) * 2) - 1;

This works because conditionals evaluate to 0 or 1. (I'm not sure that C
requires this, but it works that way with every compiler I've worked with.)
If x2 >= x1, then the expression becomes ((1) * 2) - 1 = 2 - 1 = 1. If x2 <
x1, the expression becomes ((0) * 2) - 1 = 0 - 1 = -1. We can change the
multiply into an add, and it then becomes:

xinc1 = xinc2 = ((x2 >= x1) + (x2 >= x1)) - 1;

The setcc family of instructions is intended for this purpose. However, I'm
going to cheat and write the logic negated using sbb. The setcc instructions
only update the low byte of the register which is fairly annoying.

mov ax, x2
cmp ax, x1
sbb dx, dx ; dx = (x2 < x1 ? -1 : 0)
add dx, dx ; dx = (x2 < x1 ? -2 : 0)
inc dx ; dx = (x2 < x1 ? -1 : 1)
mov xIncrement1, dx
mov xIncrement2, dx

Rewriting logic like this can make it more efficient. (IMO it is also easier
to follow because there are no branches.)

> testY:
> mov ax, Y2
> cmp ax, Y1 ;test to see if y values are increasing
> jge yIncreasing ;if they are jump to yIncreasing
> mov yIncrement1, 1 ;else
> mov yIncrement2, 1
> jmp testRatio ;jump to the test ratio part
> yIncreasing:
> mov yIncrement1, -1 ;Y is increasing
> mov yIncrement2, -1

You got the if/else clauses backward. It writes -1 to
yIncrement1/yIncrement2 if Y2 >= Y1.

> testRatio: ;Tests the ratio of x to y pixels
>
> mov ax, deltaX
> cmp ax, deltaY ;if deltaX >= deltaY
> jge oneXforEveryY

This test is also backward. You need to either swap the two sections of code
or change jge into its complement, jl.

> ;else
> mov bx, 0
> mov xIncrement1, bx
> mov yIncrement2, bx
> mov ax, deltaX

This is correct, but ax already holds deltaX at this point, so the load is
unnecessary.

> mov den, ax ;denominator = deltaX
> shr ax, 1 ;divide deltaX by 2
> mov num, ax ;and make it the numerator
> mov ax, deltaY
> mov numadd, ax ; numAdd = deltaY
> mov ax, deltaX
> mov numPixels, ax ; numPixles = deltaX
>
> jmp drawPixels
>
> oneXforEveryY:
> mov ebx, 0

Hmm, ebx? ;-)

> mov xIncrement2, bx
> mov yIncrement1, bx
> mov ax, deltaY
> mov den, ax ;denominator = deltaY
> shr ax, 1 ;divide deltaY by 2
> mov num, ax ;and make it the numerator
> mov ax, deltaX
> mov numadd, ax ; numAdd = deltaX
> mov ax, deltaY
> mov numPixels, ax ; numPixles = deltaY
>
> drawPixels:
>
> mov cx, numPixels
>
> mov ah,0Fh ; Save the current video mode
> int 10h
> mov saveMode,al
>
> mov ah,0 ; Switch to a graphics mode
> mov al,0Dh ; set video mode
> int 10h
>
> drawLoop:
> INVOKE putPixel, X, Y ;draw pixel at x, y
> mov ax, num ;increase the numerator by the top of the fraction
> add ax, numadd ;add numadd to the numerator
> mov num, ax ;put it back into numerator
>
> cmp ax, den ;compare to the denominator to check if the numerator is
> greater
> jl changeValues ;change values
>
> sub ax, den
> mov num, ax ;numerator = numerator - denominator
> mov ax, X
> add ax, xIncrement1 ; increment x
> mov X, ax
> mov ax, Y
> add ax, yIncrement1 ; increment y
> mov Y, ax
>
> changeValues:
>
> mov ax, X
> add ax, xIncrement2
> mov X, ax
> mov ax, Y
> add ax, yIncrement2 ; increment y
> mov Y, ax
> loop drawLoop
>
> mov ah,0 ;wait for a key to be pressed
> int 16h
>
> ret
> DrawLine ENDP
>
>
;---------------------------------------------------------------------------
----------------
> ;ABS calcuates the absolute value of ax
>
;---------------------------------------------------------------------------
----------------
>
>
> ABS PROC
> cmp ax, 0 ;compare to zero
> jge ABS_end ;if the numbers positive return
> neg ax ;else times by -1 to make positive
> ABS_end:
> ret ;ta-da absolute value!
> ABS ENDP
>
>
;---------------------------------------------------------------------------
----------------
> ;putPixel places a pixel on the screen given two coodinates x and y
>
;---------------------------------------------------------------------------
----------------
>
> putPixel PROC uses cx dx, x:WORD, y:WORD ;draws a pixel to the
> screen
>
> mov ah, 0Ch ;select draw a pixel function
> mov al, 2 ;colour of pixel
> mov bh, 0 ;video page 0
> mov cx, x ;x coords
> mov dx, y ;y coords
> int 10h ;draw it

Just a note, but it would be much faster to do this:

; Save the es register
push es

; Point es to the video segment
push 0xA000
pop es

; Compute pointer
mov bx, y
imul bx, 320
add bx, x

; Write the color 2 to the screen
mov BYTE PTR [bx], 2

; Restore es
pop es

You can then get faster still by saving es in your line drawing routine and
assuming es=A000 in your put pixel routine. I'd guess it would be an order
of magnitude difference. Segment loads are very slow. Interrupts are slower.

> ret
> putPixel ENDP
<snip>

-Matt