flat assembler
Message board for the users of flat assembler.

 Index > Main > Bresenham's linedrawing algorithm in ASM [SOLVED] Goto page 1, 2  Next
Author

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
BACKGROUND:
For a long time I've been trying to make some reasonably fast and simple (few registers) linedrawing algorithm in ASM.

The first tries were based on the algo found on: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
Look at the optimization part. Its no secret that MenuetOS64 uses this in its
linedrawing part.

The problems with this approach are that there are many XCHG commands
and if you are going to XCHG some memory then you better not. Also the
painful part is the end where in the tightest loop you have to DECIDE if it is
X,Y or Y,X you are drawing. If you can't imagine what is done then this
might help: the line is mirrored on another line specified by y=x (its a
diagonal).
I managed to make it work, but the loop is too complicated. If it wasn't for
triangle-filling algorithm I would have left it there...but imagine sorting
triangle's coordinates when you don't know their position (even if X is X and
Y is Y)

The second approach I made was from a code found from: http://www.gamedev.net/reference/articles/article1275.asp
This one is great because it inits all the possible variables it needs and in
the inner loop it only increments by them (they can be negative too...).

My implementation of this algorithm (that I think is correct) draws everything
correctly but the 7th octant. This is strange because everything should be
symmetrical. In the 7th octant the line is drawn in exactly the opposite
direction

THE CODE:
This is where I need your hands to help me

Code:
```;ORIGINAL - C-style syntax
;==================
deltax = abs(x2 - x1);        // The difference between the x's
deltay = abs(y2 - y1);        // The difference between the y's
x = x1;                       // Start x off at the first pixel
y = y1;                       // Start y off at the first pixel

if (x2 >= x1)                 // The x-values are increasing
{
xinc1 = 1;
xinc2 = 1;
}
else                          // The x-values are decreasing
{
xinc1 = -1;
xinc2 = -1
}

if (y2 >= y1)                 // The y-values are increasing
{
yinc1 = 1;
yinc2 = 1;
}
else                          // The y-values are decreasing
{
yinc1 = -1;
yinc2 = -1;
}

if (deltax >= deltay)         // There is at least one x-value for every y-value
{
xinc1 = 0;                  // Don't change the x when numerator >= denominator
yinc2 = 0;                  // Don't change the y for every iteration
den = deltax;
num = deltax / 2;
numpixels = deltax;         // There are more x-values than y-values
}
else                          // There is at least one y-value for every x-value
{
xinc2 = 0;                  // Don't change the x for every iteration
yinc1 = 0;                  // Don't change the y when numerator >= denominator
den = deltay;
num = deltay / 2;
numpixels = deltay;         // There are more y-values than x-values
}

for (curpixel = 0; curpixel <= numpixels; curpixel++)
{
PutPixel(x, y);             // Draw the current pixel
num += numadd;              // Increase the numerator by the top of the fraction
if (num >= den)             // Check if numerator >= denominator
{
num -= den;               // Calculate the new numerator value
x += xinc1;               // Change the x as appropriate
y += yinc1;               // Change the y as appropriate
}
x += xinc2;                 // Change the x as appropriate
y += yinc2;                 // Change the y as appropriate
}
```

Code:
```;MY UNDERSTANDING:
;===============
; Let us make a line from Axy to Bxy so
; registers rax rbx rcx rdx are used

mov         rex,rcx ;rbx=x2
sub         rex,rax ;rax=x1
sbb         rhx,rhx
xor         rex,rhx
sub         rex,rhx ;rex=abs(rcx-rax)
mov         rfx,rdx ;rdx=y2
sub         rfx,rbx ;rcx=y1
sbb         rhx,rhx
xor         rfx,rhx
sub         rfx,rhx ;rfx=abs(rdx-rbx)

or          rsi,-1
or          rdi,-1
cmp         rcx,rax
jc          @f
neg         rsi
neg         rdi
@@:
or          rix,-1
or          rjx,-1
cmp         rdx,rbx
jc          @f
neg         rix
neg         rjx
@@:

cmp         rex,rfx
jc          @f
xor         rsi,rsi ; xinc1 = 0
xor         rjx,rjx ; yinc2 = 0
mov         rkx,rex ; den = deltax
mov         rlx,rex
shr         rlx,1   ; num = deltax/2
mov         rbp,rfx ; numadd = deltay
mov         rdx,rex ; numpixels = deltax
jmp         .endloc
@@:
xor         rdi,rdi ; xinc2 = 0
xor         rix,rix ; yinc1 = 0
mov         rkx,rfx ; den=deltay
mov         rlx,rfx
shr         rlx,1   ; num=deltay/2
mov         rbp,rex ; numadd = deltax
mov         rdx,rfx ; numpixels = deltay
.endloc:

.linedraw:
push        rax rbx rcx rdx rex rfx
mov         rex,rbx
mov         rdx,rax   ; I chose to draw a thick "pixel" to see better
mov         rcx,rbx   ; This can also be some PutPixel(rax,rbx)
mov         rbx,rax
mov         rax,38
mov         rfx,255
int         60h
pop         rfx rex rdx rcx rbx rax
cmp         rlx,rkx ; num >= den
jc          @f
sub         rlx,rkx ; num -= den
@@:
sub         rdx,1
jnc         .linedraw
```

I've worked days on this and didn't figure out what's wrong - maybe a rested
sharp-eye can see where the problem is

Thanks!

_________________
My updated idol http://www.agner.org/optimize/

Last edited by Madis731 on 03 Aug 2006, 12:04; edited 1 time in total
02 Aug 2006, 12:27
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 02 Aug 2006, 13:01
in the book of Jordane (not sure if backward transliteration is right - i have russian translated book and not near me) "Reference for programming IBM PC, XT and AT" that algo has been implemented in assembler for 8086. i'll look there this evening for exact book name and compare your code with it once before i even had been converted it to pascal.
02 Aug 2006, 13:01
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 02 Aug 2006, 13:15
use self-modyfing code, and you have VERY small line algorithm, without all those IFs. even source will be shorter than C's
02 Aug 2006, 13:15
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 02 Aug 2006, 13:16
2 shorick: it's Jourdain's book. The great book!
02 Aug 2006, 13:16

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Vid - I would like to do all kinds of tricks on the code, but FIRST I need it do draw correct lines at every angle
Simply put: I need to know what to change in the code so that IF -1<slope<0 THEN NEG(x increments) andNEG(y increments).

Even if its a bit more code - I can continue from there and compress it somehow in the algorithm. I think that something is missing from the Gamedev's article, but I just can't put my finger on it
02 Aug 2006, 13:18
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 02 Aug 2006, 13:23
then first draw correct line at one angle, like 0 to 45 degrees...
02 Aug 2006, 13:23
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 02 Aug 2006, 13:28
use self-modyfing code > what if code section will be read-only?
02 Aug 2006, 13:28

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Self-modyfying code is not so good on modern CPUs - Intel has warned about the penalties - I don't know how much it is exactly, but copy-pasting the code and jumping to modifications tends to be faster. Afterall AMD64 and EM64T CPUs ARE ALL NEW CPUs They can't read ahead and they just couldn't reorder the instructions if someone surprisingly modifys some of them :S

If it will be very much faster - I'll consider.

Someone at intel once said this also: "If you are jumping, think about what are you doing wrong!"
This is why I used no jump instructions in the ABS() parts of the code. Then its all predictable and takes the same amount of clocks. Jumps will never give you the same answer (clock count), neither would self-modifying code.
02 Aug 2006, 13:37
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 02 Aug 2006, 13:48
Quote:
what if code section will be read-only?

hmmm... if he is writing all code by himself (i suppose he is), then he can define it as writeable

well, if you generate ideal algortihm with SMC, you get the penalty ONCE, but loops goes so many times that result is better.

idea tested with my 2D blit vs. directdraw's blit
02 Aug 2006, 13:48

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Hmm, maybe your right - at least you will get it to shrink and yes I'm writing the code myself, but I though it was bad practise to do smc but well.... ... maybe I can find an even smaller and vaster trick without smc.

Thanks for the ideas, but most appreciated would be a hint to a line in the code to look at. I know that I just can't flip something like -1 <=> 1 because I don't want the result to be opposite - only under some condition.
02 Aug 2006, 14:01
Vasilev Vjacheslav

Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav 02 Aug 2006, 18:54
maybe this could help, it's my code for drawing line without approximation in 32-bit dib buffer, coded in masm

Code:
```_drawhline proc uses ebx esi edi ppvBits:dword,x1:dword,x2:dword,y:dword,wdth:dword,col:dword
mov             ecx,[x2]
mov             eax,[x1]
cmp             ecx,eax
jge             @F
mov             edx,eax
mov             eax,ecx
mov             ecx,edx
@@:
mov             edx,[y]
imul    edx,[wdth]
mov             esi,[ppvBits]
cmp             eax,ecx
lea             edi,[esi+edx*4]
je              @F
sub             ecx,eax
mov             eax,[col]
rep     stosd

@@:
ret
_drawhline endp

_drawvline proc ppvBits:dword,x:dword,y1:dword,y2:dword,wdth:dword,col:dword
mov             eax,[y2]
mov             esi,[y1]
cmp             esi,eax
jle             @F
mov             ecx,esi
mov             esi,eax
mov             eax,ecx
cmp             esi,eax
@@:
je              @@ret
mov             ecx,[wdth]
mov             edi,esi
imul    edi,ecx
mov             edx,ecx
mov             ecx,[ppvBits]
shl             edx,2
lea             ecx,[ecx+edi*4]
sub             eax,esi

@@:
mov             esi,[col]
mov             [ecx],esi
dec             eax
jne             @B

@@ret:
ret
_drawvline endp

_drawline proc uses ebx esi edi ppvBits:dword,x1:dword,y1:dword,x2:dword,y2:dword,wdth:dword,col:dword
local   htmp:dword

mov             eax,[x1]
mov             ecx,[y1]
mov             esi,[x2]
mov             edi,[y2]
mov             edx,edi
sub             esi,eax
sub             edx,ecx
mov             [htmp],edx
mov             [y2],edx
jne             @@a
test    esi,esi
jne             @@b
imul    ecx,[wdth]
mov             edx,[ppvBits]
mov             eax,[col]
mov             [edx+ecx*4],eax
jmp             @@ret

@@b:
invoke  _drawhline,[ppvBits],eax,[x2],ecx,[wdth],[col]
jmp             @@ret

@@a:
test    esi,esi
jne             @@c

invoke  _drawvline,[ppvBits],eax,ecx,edi,[wdth],[col]
jmp             @@ret

@@c:
mov             eax,[y2]
cdq
mov             ebx,eax
xor             ebx,edx
sub             ebx,edx
mov             eax,esi
cdq
xor             eax,edx
sub             eax,edx
cmp             eax,ebx
jle             @@d

cmp             [y2],0
jle             @F

xor             eax,eax
inc             eax
jmp             @@e

@@:
or              eax,-1
neg             [y2]

@@e:
mov             edx,[y2]
sar             edx,1
test    esi,esi
jl              @@f

mov             edi,[x1]
mov             ebx,edi
cmp             ebx,[x2]
mov             [y1],edi
je              @@ret

imul    ecx,[wdth]
imul    eax,[wdth]
mov             [wdth],eax

@@lp:
mov             ebx,[ppvBits]
cmp             edx,esi
lea             eax,[ecx+edi]
mov             edi,[col]
mov             [ebx+eax*4],edi
jle             @F
sub             edx,esi
@@:
mov             edi,[y1]
inc             edi
cmp             edi,[x2]
mov             [y1],edi
jne             @@lp

jmp             @@ret

@@f:
mov             ecx,[x2]
neg             [y2]
neg             esi
cmp             ecx,[x1]
mov             [y1],ecx
je              @@ret
imul    edi,[wdth]
imul    eax,[wdth]
mov             [wdth],eax

@@lp1:
mov             eax,[y1]
sub             edx,[y2]
mov             ecx,[col]
mov             ebx,[ppvBits]
cmp             edx,esi
mov             [ebx+eax*4],ecx
jle             @F
sub             edi,[wdth]
sub             edx,esi
@@:
inc             [y1]
mov             eax,[y1]
cmp             eax,[x1]
jne             @@lp1

jmp             @@ret

@@d:
test    esi,esi
jle             @@g

mov             [y1],1
jmp             @@h

@@g:
or              [y1],-1
neg             esi

@@h:
mov             edx,esi
sar             edx,1
cmp             [y2],0
jl              @@j

cmp             ecx,edi
mov             eax,[x1]
mov             [x1],eax
je              @@ret
mov             eax,[htmp]
imul    ecx,[wdth]
mov             [x2],eax

@@lp2:
mov             eax,[x1]
mov             edi,[col]
mov             ebx,[ppvBits]
cmp             edx,[y2]
mov             [ebx+eax*4],edi
jle             @F
mov             eax,[y1]
sub             edx,[y2]
@@:
dec             [x2]
jne             @@lp2

jmp             @@ret

@@j:
mov             eax,[x2]
neg             [y2]
neg             esi
cmp             edi,ecx
mov             [x1],eax
je              @@ret
mov             eax,edi
imul    eax,[wdth]
sub             ecx,edi
mov             [x2],ecx

@@lp3:
mov             ecx,[x1]
mov             edi,[col]
mov             ebx,[ppvBits]
sub             edx,esi
cmp             edx,[y2]
mov             [ebx+ecx*4],edi
jle             @F
mov             ecx,[y1]
sub             [x1],ecx
sub             edx,[y2]
@@:
dec             [x2]
jne             @@lp3

@@ret:
ret
_drawline endp
```
02 Aug 2006, 18:54
f0dder

Joined: 19 Feb 2004
Posts: 3175
Location: Denmark
f0dder 02 Aug 2006, 19:37
If you're going for quality and not just speed, have a look at http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm .
02 Aug 2006, 19:37
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 03 Aug 2006, 06:26
sub rex,rax ;rax=x1
sbb rhx,rhx
xor rex,rhx

is it really abs?
---
"xor rex,-1" means "not rex", should be "neg rex", or "not rex/inc rex"
03 Aug 2006, 06:26
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 03 Aug 2006, 06:33
xor ecx,ecx
sub eax,edx
sets cl
sbb ebx,ebx
xor eax,eax

-- if it has sense
03 Aug 2006, 06:33

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
Code:
```    mov         rex,rcx ;rbx=x2
sub         rex,rax ;rax=x1
sbb         rhx,rhx
xor         rex,rhx ; This isn't ABS() but NOT() as you mentioned
sub         rex,rhx ;...but this line will increase it by one if necessary
```

This is tested and works exactly the same as:
Code:
```    mov         rex,rcx ;rbx=x2
sub         rex,rax ;rax=x1
jnc         @f
neg         rex
@@:
```

@Fodder: Yeah, I already researched this. It will be fun to try that out
in the future and I already have a plan to FSAA with integer-only method
by taking different colours as input (if I'm at the edge of colour transition).
03 Aug 2006, 07:51
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 03 Aug 2006, 08:11
got it. then next question - what these "ors" mean:
or rsi,-1
or rdi,-1
cmp rcx,rax
(i do not have 64-bit cpu, nor familiar with 64-bit modes)
==
no, got it - it is conditional 1/-1 assuming (what advantage against mov reg,1?)
03 Aug 2006, 08:11

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
or rsi,-1 is shorter and again :\$ tested with other conditional methods and
works the same way.

OR RSI,-1 is shorter 5 vs. 7 bytes (MOV RSI,-1)...
...hmm now when I think of it there IS NO advantage

I'm still stuck with 32-bit there it was 3 vs. 5 bytes. Gain has dropped from 40% to 29%.
03 Aug 2006, 09:19
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 03 Aug 2006, 09:42
i can not switch to this task fully to got it in whole (busy - he-he)
but next:
i think, your asm equivalent does not match c-source exactly. it seems to me there is this difference:
if (x2 > x1) // but in originall c-source >=
{
xinc1 = 1;
xinc2 = 1;
}
else // The x-values are decreasing
{
xinc1 = -1;
xinc2 = -1
}
===
not sure i'm right, but also not sure about your comments (where which x and y stored in real):
1.
mov rex,rcx ;rbx=x2
sub rex,rax ;rax=x1
2.
if (x2 >= x1) // The x-values are increasing
..
sub rfx,rbx ;rcx=y1
..
cmp rcx,rax ; is it x2 to x1 comparing?
03 Aug 2006, 09:42

Joined: 25 Sep 2003
Posts: 2139
Location: Estonia
It goes like this:
if (x2 >= x1) will translate to "cmp x2,x1 \ jc else" pair because if x2 is greater or equal, then x2-x1 won't result in a carry. If x2 is less, then it
results in a carry and will continue with that "else" which is the increments
remain the same. Otherwise they will be negated.

I want to go through my theory - if the problem WOULD be in these
conditions then the line would look wrong in the near 0 or near infinity
steeps which is not the case. Because its doing something wrong in the
-1 to 0 region its has got to be hiding somewhere in the "There are more
x-values than y-values" or the other similar part (dy>dx)...

@Vasilev: I started munching through your code, but I can't figure it out
is it Bresenham or some modified version of it. There seems to be a lot
of jumps and code, but I think its because of the memory access. I have
some advantage to use 15 registers.

EDIT: Theory2
Because the steeps are okay, but only the direction is off and in the drawing
part it only increments nominator and denominator then I think it can be
fixed when starting point is fixed. swap(x1,x2), swap(y1,y2)
03 Aug 2006, 10:01
shoorick

Joined: 25 Feb 2005
Posts: 1614
Location: Ukraine
shoorick 03 Aug 2006, 10:13
ok, agree. then had not you mixed y1 and x2:
mov rex,rcx ;rbx=x2
...
sub rfx,rbx ;rcx=y1

?
maybe, more tests will show you more problems?
03 Aug 2006, 10:13
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum