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
Thread Post new topic Reply to topic
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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) Very Happy

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 Sad

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

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;
  numadd = deltay;
  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;
  numadd = deltax;
  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
    add         rex,1     ; INT60 eax=38 is a MenuetOS function for lines
    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
    add         rlx,rbp ; num += numadd
    cmp         rlx,rkx ; num >= den
    jc          @f
    sub         rlx,rkx ; num -= den
    add         rax,rsi
    add         rbx,rdi
  @@:
    add         rax,rix
    add         rbx,rjx
    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 Smile

Thanks!

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


Last edited by Madis731 on 03 Aug 2006, 12:04; edited 1 time in total
Post 02 Aug 2006, 12:27
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
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 Wink once before i even had been converted it to pascal.
Post 02 Aug 2006, 13:01
View user's profile Send private message Visit poster's website Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
use self-modyfing code, and you have VERY small line algorithm, without all those IFs. even source will be shorter than C's Razz
Post 02 Aug 2006, 13:15
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 490
Location: Belarus
zhak
2 shorick: it's Jourdain's book. The great book!
Post 02 Aug 2006, 13:16
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Very Happy 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 Wink
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 Sad
Post 02 Aug 2006, 13:18
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
then first draw correct line at one angle, like 0 to 45 degrees...
Post 02 Aug 2006, 13:23
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
use self-modyfing code > what if code section will be read-only?
Post 02 Aug 2006, 13:28
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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 Wink 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.
Post 02 Aug 2006, 13:37
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
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 Smile Wink

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
Post 02 Aug 2006, 13:48
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
Hmm, maybe your right - at least you will get it to shrink Wink and yes I'm writing the code myself, but I though it was bad practise to do smc but well....Razz ... 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.
Post 02 Aug 2006, 14:01
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
Vasilev Vjacheslav



Joined: 11 Aug 2004
Posts: 392
Vasilev Vjacheslav
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]
        add             edx,eax
        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
        add             edi,[x]
        mov             edx,ecx
        mov             ecx,[ppvBits]
        shl             edx,2
        lea             ecx,[ecx+edi*4]
        sub             eax,esi

  @@:
        mov             esi,[col]
        mov             [ecx],esi
        add             ecx,edx
        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]
        add             ecx,eax
        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:
        add             edx,[y2]
        mov             ebx,[ppvBits]
        cmp             edx,esi
        lea             eax,[ecx+edi]
        mov             edi,[col]
        mov             [ebx+eax*4],edi
        jle             @F
        add             ecx,[wdth]
        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]
        add             eax,edi
        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]
        add             eax,ecx
        add             edx,esi
        cmp             edx,[y2]
        mov             [ebx+eax*4],edi
        jle             @F
        mov             eax,[y1]
        add             [x1],eax
        sub             edx,[y2]
  @@:
        add             ecx,[wdth]
        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]
        add             ecx,eax
        sub             edx,esi
        cmp             edx,[y2]
        mov             [ebx+ecx*4],edi
        jle             @F
        mov             ecx,[y1]
        sub             [x1],ecx
        sub             edx,[y2]
  @@:
        add             eax,[wdth]
        dec             [x2]
        jne             @@lp3

  @@ret:
        ret
_drawline endp
    
Post 02 Aug 2006, 18:54
View user's profile Send private message Reply with quote
f0dder



Joined: 19 Feb 2004
Posts: 3170
Location: Denmark
f0dder
If you're going for quality and not just speed, have a look at http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm .
Post 02 Aug 2006, 19:37
View user's profile Send private message Visit poster's website Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
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"
Post 03 Aug 2006, 06:26
View user's profile Send private message Visit poster's website Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
xor ecx,ecx
sub eax,edx
sets cl
sbb ebx,ebx
xor eax,eax
add eax,ecx

-- if it has sense
Post 03 Aug 2006, 06:33
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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).
Post 03 Aug 2006, 07:51
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
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?)
Post 03 Aug 2006, 08:11
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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 Razz

I'm still stuck with 32-bit Sad there it was 3 vs. 5 bytes. Gain has dropped from 40% to 29%.
Post 03 Aug 2006, 09:19
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
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?
Post 03 Aug 2006, 09:42
View user's profile Send private message Visit poster's website Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Madis731
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)
Post 03 Aug 2006, 10:01
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
shoorick



Joined: 25 Feb 2005
Posts: 1608
Location: Ukraine
shoorick
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?
Post 03 Aug 2006, 10:13
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  
Goto page 1, 2  Next

< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.