I can't get Bresenham working!

[wossname]

I'm trying to translate the Bresenham line-drawing algorithm into MASM 16 bit code so I can use it to draw lines in Mode 13h.

This is the C# code I started out with (adapted from some pseudo code I found on Wiki)...

Code Select Expand


private void DrawLine( Bitmap dc, short x0, short y0, short x1, short y1, Color c )
{
bool steep = Math.Abs( y1 - y0 ) > Math.Abs( x1 - x0 );

if ( steep )
{
short temp = x0;
x0 = y0;
y0 = temp;

temp = x1;
x1 = y1;
y1 = temp;

dc.SetPixel( y0, x0, c );
}
else
dc.SetPixel( x0, y0, c );

short deltax = Math.Abs( (short)(x1 - x0) );
short deltay = Math.Abs( (short)(y1 - y0) );
short error = 0;
short x = x0;
short y = y0;
short xstep, ystep;

if ( x0 < x1 )
xstep = 1;
else
xstep = -1;

if ( y0 < y1 )
ystep = 1;
else
ystep = -1;

while ( x != x1 )
{
x += xstep;
error += deltay;
if ( (2 * error) > deltax )
{
y += ystep;
error -= deltax;
}

if ( steep )
dc.SetPixel( y, x, c );
else
dc.SetPixel( x, y, c );
}
}


First thing I did was to replace as many variables as I could with 16 bit registers.  My version almost works but it tends to act strangely, drawing some lines bent or just at the wrong angle.

Here's my bad code...

Code Select Expand



;---------------------------
DrawLine PROC,
x0:WORD,
y0:WORD,
x1:WORD,
y1:WORD,
color:BYTE
;
; An implementation of the Bresenham line-drawing algorithm
; Translated to ASM by Adam Ward, 01/12/05
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
error:WORD,
xstep:WORD,
ystep:WORD

pusha

; validate all the arguments (both coords are on screen)
mov ax, SCREEN_WIDTH
mov bx, SCREEN_HEIGHT
xor cx, cx ; = 0

cmp x0, cx
jl DONE
cmp x1, cx
jl DONE
cmp y0, cx
jl DONE
cmp y1, cx
jl DONE

cmp x0, ax
jge DONE
cmp x1, ax
jge DONE
cmp y0, bx
jge DONE
cmp y1, bx
jge DONE

;####################################
;### START OF BRESENHAM ALGORITHM ###
;####################################

; cx = abs(y1 - y0) > abs(x1 - x0) ####################

mov ax, y1
sub ax, y0
jns ABS_Y_DONE
neg ax ; number is negative, so make it positive
ABS_Y_DONE:

mov bx, x1
sub bx, x0
jns ABS_X_DONE
neg bx ; number is negative, so make it positive
ABS_X_DONE:

cmp ax, bx
jbe ELSE1
; ax > bx
mov cx, 1
jmp ENDIF1
ELSE1:
; ax <= bx
mov cx, 0
ENDIF1:


; if cx then ####################

bt cx, 0
jnc ELSE2
; swap(x0, y0)
mov ax, x0
xchg ax, y0
mov x0, ax

; swap(x1, y1)
mov ax, x1
xchg ax, y1
mov x1, ax

INVOKE PlotPixel, y0, x0, color
ELSE2:
INVOKE PlotPixel, x0, y0, color
ENDIF2:

; deltax = abs(x1 - x0) ###########
mov ax, x1
sub ax, x0
jns ABS_X2_DONE
neg ax ; number is negative, so make it positive
ABS_X2_DONE:
mov deltax, ax

; deltay = abs(y1 - y0) ###########
mov ax, y1
sub ax, y0
jns ABS_Y2_DONE
neg ax ; number is negative, so make it positive
ABS_Y2_DONE:
mov deltay, ax

; error = 0 ##########
mov error, 0

; bx = x0 #########
mov bx, x0
; dx = y0 #########
mov dx, y0


; if x0 < x1 then #########

cmp bx, x1
jae ELSE3
; xstep = 1
mov xstep, 1
jmp ENDIF3
ELSE3:
; xstep = -1
mov xstep, -1
ENDIF3:


; if y0 < y1 then #########

cmp dx, y1
jae ELSE4
; ystep = 1
mov ystep, 1
jmp ENDIF4
ELSE4:
; ystep = -1
mov ystep, -1
ENDIF4:

; while bx != x1 ###############
L1:
cmp bx, x1
je Done

; bx = bx + xstep
add bx, xstep

; error = error + deltay
mov ax, error
add ax, deltay
mov error, ax

; if 2 * error > deltax ##########
; (error value is still in ax...)

shl ax, 1 ;error * 2
cmp ax, deltax
jbe ENDIF5
; dx = dx + ystep
add dx, ystep
; error = error - deltax
mov ax, deltax
sub error, ax
ENDIF5:

; if cx then #############
bt cx, 0
jnc ELSE6
; plot(dx,bx)
INVOKE PlotPixel, dx, bx, color
jmp L1 ; SHORTCUT TO BEGINNING OF WHILE LOOP
ELSE6:
; plot(bx,dx)
INVOKE PlotPixel, bx, dx, color

jmp L1 ; continue the while loop

DONE:
popa
ret
DrawLine ENDP

Whats wrong with this algorithm?  (PlotPixel is fine, I have checked that separately and its OK)

[raymond]

(PlotPixel is fine, I have checked that separately and its OK)

Have you also checked if PlotPixel does not trash the bx/dx registers. If it does, you should save them before the call and restore them after. Or, keep those values in memory variables (such as with x0, x1,..) instead of registers.

As a side note, there is no need to have a separate comparison of the input to 0 in order to check for negative values to validate the input. Use the jae mnemonic instead of the jge; all negative values would show as above and fail the test.

Raymond

[MichaelW]

It looks to me like your translation of the C# code is functionally correct. I created an app in QuickC to test the C# code and it seems to work just as it should. The DrawLine procedure does have some sort of problem, but looking at the code I cannot see it. I think it's debugger time.



[attachment deleted by admin]