# Thread: [RESOLVED] Bresenham won't work for me :(

1. ## [RESOLVED] Bresenham won't work for me :(

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:
```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.

Code:
```;---------------------------
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

; error = error + deltay
mov ax, error
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
; 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)

2. ## Re: Bresenham won't work for me :(

hehe I guess you're looking for me - wait let me read it hehe
Hmmmm 16-bit - im not sure about it but ill try.

3. ## Re: Bresenham won't work for me :(

grrrr gotta go out - ill check it out later

Thanks mate.

5. ## Re: Bresenham won't work for me :(

I'm not sure about the MASM but you might wanna optimise your base code and just redo hoping you don't make the same mistake...

here's some optimised from your code (I just optimised it for my program... but I'm passing in deltax and deltay instead of x1 and y1 so I had to convert back)

I just followed the two basic rules of optimisation: don't recompute anything (for instance, deltax and deltay) and take everything you can out of the loop (like the xstep > 0 determination)... I also changed it to use increment and decrement operators as much as possible, because on certain processors inc and dec can take zero clocks, and on earlier processors inc and dec take less time than add and sub

private void DrawLine( Bitmap dc, short x0, short y0, short x1, short y1, Color c )
{
short deltax = x1 < x0 ? x0 - x1 : x1 - x0;
short deltay = y1 < y0 ? y0 - y1 : y1 - y0;
bool steep = deltay > deltax;
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 error = 0;
short x = x0;
short y = y0;
short xstep, ystep;

xstep = deltax < 0 ? -1 : 1;
ystep = deltay < 0 ? -1 : 1;

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

if ( steep )
dc.SetPixel( y, x, c );
else
dc.SetPixel( x, y, c );
}
} else {
while ( x != x1 )
{
x --;
error += deltay;
if ( (2 * error) > deltax )
{
y += ystep;
error -= deltax;
}

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

6. ## Re: Bresenham won't work for me :(

Oh I forgot to mention...

Another handy optimisation if you're drawing to a byte array is to forgo the plot pixel altogether and only compute the y component of the address when it changes...

I'm drawing to an int array (32-bit AHSL color) and I just compute int yline = (y * width); everytime I update y... then my pixel operation looks like

imageBuffer[liney + x] = color;

no multiplies = faster code

7. ## Re: Bresenham won't work for me :(

Not sure if I found your exact mistakes but I noticed some 'unecessary code'
; error = error + deltay
mov ax, error
mov error, ax

should be:
; error = error + deltay
mov ax, deltay

bt cx, 0
jnc ELSE6

could be just:
jcxz ELSE6 ;(Because you are using the cx register -- this actually could be problem of the algorithm because you are testing only 1 bit in the 16-bit register )

same again

bt cx, 0
jnc ELSE2

should be:
jcxz ELSE2

I think it should work now - but I've only read it off-screen - not tested it in action.

Btw ....why are you using POPA and PUSHA - they are kinda slow unless you really need to preserve all 7 registers - here you are only using a few - it'll be much faster if you use individual push and pops.

8. ## Re: Bresenham won't work for me :(

because on certain processors inc and dec can take zero clocks
No can't be true - all instructions take clocks.
Unless you are referring to pairing - on older processors inc/dec is slightly faster than add/sub because there was less pairing and inc/dec was a shorter instruction

On newer processors, inc/dec don't pair so well and add/sub are faster than inc/dec - check pentopt.pdf on agner fog's site.
And in 64bit asm programming - inc/dec 1 byte opcodes are no longer valid - so their advantage of having a shorter instruction is gone as well - its being deprecated in favour for add/sub.
So unless you are programming for processors 486 and below- you can happily use add/sub because i believe from P1 to P3 the speed of the instructions are about the same and P4 add/sub are faster.

9. ## Re: Bresenham won't work for me :(

Does it work wossname?

10. ## Re: Bresenham won't work for me :(

Thanks for checking my code out. I appreciate your help. Actually that bit of code you said is unecessary (actually I did think that too for a while until i realised the i could re-use ax without any extra code). check out the comment below it and it should become clear.

I have used the jcxz's though.

Sadly the alg still doesnt work. i'll keep you posted.

Thanks again

11. ## Re: Bresenham won't work for me :(

Thanks to merlin also. I was not going to optimise it until i had a working algorithm up and running. I'll take a look at your idea though. Cheers

12. ## Re: Bresenham won't work for me :(

Could you post the code + test code - and then i can debug it easily .

13. ## Re: Bresenham won't work for me :(

Here you go... (Im using MASM615 by the way).

How do you debug an ASM in Visual Studio? I can't figure it out. I can do it if the ASM crashes but this program isn't crashing its just doing the wrong thing.

14. ## Re: Bresenham won't work for me :(

Debugging in Visual Studio is a pain unless its in vb/vc#.
For assembly code i use ollydbg (http://www.ollydbg.de/)
But if you really want to do it in Visual Studio - you insert user breakpoints i.e.

int 3 ;User Breakpoint
;Code
mov ax, [blahblah]

This will actually cause the program to crash :P because windows considers int 3 as a problem with your program. Int 3 is the official way of putting a breakpoint to crash your program but in a debugger , you can step over it easily unlike other crashes because its just a breakpoint.

If you are thinking of step by step debugging - you can load a exe in visual studio i think and start by stepping in - then you probably can highlight areas you want to breakpoint. However, I find Visual Studio too slow to load for my liking so i use Ollydbg.

Cheers.

15. ## Re: Bresenham won't work for me :(

It won't assemble - either because I don't have AWFont.INC or maybe my masm command line is wrong or maybe because im using MASM 7.1
Could you give me your command line for assembling?

16. ## Re: Bresenham won't work for me :(

D:\masm32\Code\Lines>ml lines.asm /FeTestLine.exe
Microsoft (R) Macro Assembler Version 7.10.3077

Assembling: lines.asm
awgrafix.inc(35) : error A2074: cannot access label through segment registers
awgrafix.inc(56) : error A2074: cannot access label through segment registers
lines.asm(31) : error A2006: undefined symbol : DGROUP

17. ## Re: Bresenham won't work for me :(

Sorry, you can delete the AWFONT.INC line. Its a remnant of another program.

Int 3 doesn't do anything for me, maybe its because its not a 32bit program?

18. ## Re: [RESOLVED] Bresenham won't work for me :(

Woooohoooo!!!!! I fixed it...

I've highlighted the correction I made (changed a jbe to a jle because I forgot it was a signed value.

Next I'm going to check for horizontal or vertical lines and treat them separately. For the horizontal lines I can write 4 pixels at once by filling eax with color bytes and then writing eax to VRAM repeatedly. I'll post the code once i've finished it and optimised it

Thanks for everyone's help.

Code:
```PlotPixel PROC USES ax bx di dx,
x:WORD,
y:WORD,
color:BYTE

mov ax, y						; store y coord
mov bx, SCREEN_WIDTH
cwd								; empty dx ready for mul
mul bx							; y * screen width
add ax, x						; + x
mov di, ax						; pixel's VRAM address
mov al, color

mov BYTE PTR es:[di], al		; plot the pixel

ret
PlotPixel ENDP

;---------------------------
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, 10/12/05
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
er: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

cmp x0, ax
jae DONE
cmp x1, ax
jae DONE
cmp y0, bx
jae DONE
cmp y1, bx
jae 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 ####################

jcxz 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
jmp ENDIF2
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

; er = 0 ##########
mov er, 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

; er = er + deltay
mov ax, er
mov er, ax

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

shl ax, 1		; er * 2
cmp ax, deltax
jle ENDIF5
; dx = dx + ystep
; er = er - deltax
mov ax, deltax
sub er, ax
ENDIF5:

; if cx then #############
jcxz 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```

19. ## Re: [RESOLVED] Bresenham won't work for me :(

hehe usually one little mistake always happens congrats anyway.
I thought Int 3 worked for everything but then i might be wrong.

20. ## Re: [RESOLVED] Bresenham won't work for me :(

OK here it is in all its glory

Code:
```;--------------------------------
PlotPixel PROC USES ax bx di dx,
x:WORD,
y:WORD,
color:BYTE
;
;	Plots a single pixel at given coords in the given color
;--------------------------------

mov ax, y						; store y coord
mov bx, SCREEN_WIDTH
mul bx							; y * screen width
add ax, x						; + x
mov di, ax						; pixel's VRAM address
mov al, color

mov BYTE PTR es:[di], al		; plot the pixel

ret
PlotPixel ENDP

;---------------------------
DrawLine PROC USES eax bx cx dx di si,
x0:WORD,
y0:WORD,
x1:WORD,
y1:WORD,
color:BYTE
;
; An implementation of the Bresenham line-drawing algorithm
; Translated to ASM by Adam Ward, 10/12/05
;
;	NOTES:
;		- Treats horizontal and vertical lines separately for extra speed.
;		- Horizontal lines with a length that is a multiple of 4 will be the most efficient.
;		- Single pixels are the least efficient (Use PlotPixel instead)
;---------------------------
LOCAL deltax:WORD,
deltay:WORD,
xstep:WORD,
ystep:WORD

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

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

mov ax, y0
cmp ax, y1
je LINE_IS_HORIZONTAL

mov ax, x0
cmp ax, x1
je LINE_IS_VERTICAL

;####################################
;### 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 ####################

jcxz 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
jmp ENDIF2
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

; si = 0 ##########
xor si, si

; 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

; er = er + deltay

; if 2 * er > deltax ##########
mov ax, si
shl ax, 1		; er * 2
cmp ax, deltax
jle ENDIF5
; dx = dx + ystep
; er = er - deltax
sub si, deltax
ENDIF5:

; if cx then #############
jcxz 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

;########################################

LINE_IS_HORIZONTAL:
; find the length of the line
mov ax, x1
sub ax, x0
jz LINE_IS_VERTICAL		; single-pixel lines are better handled by the vertical algorithm
jns LH_OK

LH_SWAP:
neg ax			; we can change the sign of ax without having to subtract again
mov bx, x0
xchg bx, x1
mov x0, bx

LH_OK:
; AX now contains the length of the line (pixels)
inc ax
mov bx, TYPE DWORD
div bx
push dx			; the remainder, which is used as the second loop number
push ax			; the quotient which is used as the first loop number

; calculate the left-hand end of the line
mov ax, y0
mov bx, SCREEN_WIDTH
mul bx
mov di, ax

; fill eax with color bytes
mov bl, color
mov bh, bl
mov ax, bx
shl eax, 16
mov ax, bx

; draw chunks of 4 pixels at a time to accelerate horizontal lines
pop cx
mov bx, TYPE DWORD
jcxz LH_REMAINDER		; avoid cx=0 looping error
LH1:
mov DWORD PTR es:[di], eax
Loop LH1

; draw the remaining 1 - 3 bytes if required
LH_REMAINDER:
pop cx				; remainder (so 1 pixel at a time)
jcxz DONE			; avoid cx=0 looping error
LH2:
mov BYTE PTR es:[di], al
inc di
Loop LH2

jmp DONE

;########################################

LINE_IS_VERTICAL:

; find the length of the line
mov ax, y1
sub ax, y0
jns LV_OK

LV_SWAP:
neg ax			; we can change the sign of ax without having to subtract again
mov bx, y0
xchg bx, y1
mov y0, bx

LV_OK:
; AX now contains the length of the line (pixels)
inc ax			; add 1 because its zero-based
mov cx, ax

; calculate the top end of the line
mov ax, y0
mov bx, SCREEN_WIDTH
mul bx
mov di, ax

mov al, color					; source byte

; draw chunks of 4 pixels at a time to accelerate horizontal lines
mov bx, SCREEN_WIDTH
LV1:
mov BYTE PTR es:[di], al	; draw the pixel
Loop LV1

;########################################
DONE:
ret
DrawLine ENDP```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured