flat assembler
Message board for the users of flat assembler.

Index > Main > edfedham line algorythm for fool.

Author
Thread Post new topic Reply to topic
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
32 bits code of line.
this time, the pixel function is indepedant.

pixel will test for valid coordinates in eax & ebx.
color in ecx.


Code:
linepix:
.call=0
.x=4
.y=8
.xl=12
.yl=16
.c=20
        push eax ebx ecx edx esi edi
        mov ecx,1
        mov edx,1
        xor edi,edi
        mov eax,[esi+.xl]
        mov ebx,[esi+.yl]
        cmp eax,edi
        jge @f
        neg eax
        neg ecx
@@:
        cmp ebx,edi
        jge @f
        neg ebx
        neg edx
@@:
        cmp eax,ebx
        jl .isy
.isx:
        mov [.xinc1],ecx
        mov [.xinc2],edi
        mov [.yinc1],edi
        mov [.yinc2],edx
        mov [.dmax],eax
        mov [.dmin],ebx
        jmp @f
.isy:
        mov [.xinc1],edi
        mov [.xinc2],ecx
        mov [.yinc1],edx
        mov [.yinc2],edi
        mov [.dmax],ebx
        mov [.dmin],eax
@@:
        mov eax,[esi+.x] ; eax = x
        mov ebx,[esi+.y] ; ebx = y
        mov edx,[.dmax]
        shr edx,1 ; middle of the line will be the middle of the line
        mov cl,[esi+.c]
        mov edi,[.dmax]
@@: ;main loop
        call pixel
        dec edi
        jl @f ; last pixel!
        add eax,[.xinc1]      ; this loop needs some optimisation
        add ebx,[.yinc1]      ; like using only registers, or a sort of paths combinaison 
        sub edx,[.dmin]    ; note that incs are 0, 1 or -1, and there are only 8 combinaisons. (0,0 cannot exist)
        jge @b ; loop main loop1
        add eax,[.xinc2]
        add ebx,[.yinc2]
        add edx,[.dmax]
        jmp @b ; loop main loop2 
@@:
        pop edi esi edx ecx ebx eax
        ret

.xinc1  rd 1 ; the fact that theses datas exits is:
we cannot use this function as a thread, or we need to reserve bytes in memory for each line instance...
.xinc2  rd 1
.yinc1  rd 1
.yinc2  rd 1
.dmin   rd 1
.dmax   rd 1

pixel:
;eax=x
;ebx=y
;ecx=color
        push ebx ; it will test for valid coordinates
        cmp eax,0    ; this test can be avoided if interpolation is done with caller function.
        jl @f  ; later, it will compare ( or interpolate) with vesa info stytle datas.
        cmp eax,320
        jge @f
        cmp ebx,0
        jl @f
        cmp ebx,200
        jge @f
        imul ebx,320
        mov [fs:eax+ebx],cl
@@:
        pop ebx 
        ret      
    



here is ONE big serious problem.

.xinc1
.xinc2
.yinc1
.yinc2
.dmax
.dmin

theses 6 dwords are very temporary datas as long as the line needs only 4 dwords to be defined.

to test this function, it is very easy:
no need for fool.
Code:
include 'linepix.inc'
testline dd linepix,0,0,320,200,4 
start:
 mov esi,testline
 call near[esi]
    
Post 14 Jan 2010, 05:49
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
Quote:
to test this function, it is very easy:

I suppose much more is needed...
Post 14 Jan 2010, 14:27
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
yep.

setup mode 13h
set fs as frame buffer.
Code:
org 100h
mov ax,13h
int 10h
mov ax,0a000h
mov fs,ax
jmp start
include 'line.inc'
testline dd line,0,0,320,200,4
start:
mov esi,testline
call near[esi]
jmp start         
Post 14 Jan 2010, 15:34
View user's profile Send private message Visit poster's website Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 764
Location: Massachusetts, USA
bitshifter
LOL, I love the name, edfedham Smile

A few tips for speedup...

1) Bresenham was fast but now we have FPU which can
eliminate the jumping withing the main loop and also
we can mix INT and FPU operations to run in same cycle.
2) Clip the line with outcode testing instead of per pixel.
Even Barsky clipping would be better for that matter...
3) Handle all 8 octants seperately (with code size penalty of course)
4) Use a mask that may render multiple pixels at once...
And then we have run slice lines, which ill save for another day...

I have some fast C code for this (not yet converted ASM)
If you would like to see my ideas i can send you some code...
Post 14 Jan 2010, 19:51
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
8 FPU register???

hum...
and what about a multithred appliction?
how can i efficienttly save FPU registers?
Post 14 Jan 2010, 22:20
View user's profile Send private message Visit poster's website Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 764
Location: Massachusetts, USA
bitshifter
Only a couple FPU registers are needed to handle minor delta in loop.
Most everything is done with integer all except adding the fractional part.

Here is some C-code for DDA line drawing...
Please forgive me but i do ALL my prototyping in C first.
Code:
///////////////////////////////////////////////////////////////////////////////
//
//   315      0       45
//     \      |      /
//      \  8  |  1  /
//       \    |    /
//        \   |   /
//         \  |  /
//       7  \ | /  2
//           \|/
// 270 ------(*)------ 90
//           /|\
//       6  / | \  3
//         /  |  \
//        /   |   \
//       /    |    \
//      /  5  |  4  \
//     /      |      \
//   225     180     135
//
///////////////////////////////////////////////////////////////////////////////

void DrawLine(
   long x1,
   long y1,
   long x2,
   long y2,
   long color)
{
   // if going right -> possible sectors are [1,2,3,4]
   if(x1 < x2)
   {
      long delta_x = x2 - x1;

      // if going down -> possible sectors are [3,4]
      if(y1 < y2)
      {
         long delta_y = y2 - y1;

         // if more vertical (SECTOR 4)
         if(delta_x < delta_y)
         {
            printf("TRACE: SECTOR(4)\n");

            float m = float(delta_x) / float(delta_y);
            float x = float(x1);

            for(long y = y1; y <= y2; y++)
            {
               SetPixel(long(x),y,color);
               x += m;
            }
         }
         // else more horizontal (SECTOR 3)
         else
         {
            printf("TRACE: SECTOR(3)\n");

            float m = float(delta_y) / float(delta_x);
            float y = float(y1);

            for(long x = x1; x <= x2; x++)
            {
               SetPixel(x,long(y),color);
               y += m;
            }
         }
      }
      // else going up -> possible sectors are [1,2]
      else
      {
         long delta_y = y1 - y2;

         // if more vertical (SECTOR 1)
         if(delta_x < delta_y)
         {
            printf("TRACE: SECTOR(1)\n");
            g_elapse = -1;

            float m = float(delta_x) / float(delta_y);
            float x = float(x1);

            for(long y = y1; y >= y2; y--)
            {
               SetPixel(long(x),y,color);
               x += m;
            }
         }
         // else more horizontal (SECTOR 2)
         else
         {
            printf("TRACE: SECTOR(2)\n");

            float m = float(delta_y) / float(delta_x);
            float y = float(y2);

            for(long x = x2; x >= x1; x--)
            {
               SetPixel(x,long(y),color);
               y += m;
            }
         }
      }
   }
   // else going left -> possible sectors are [5,6,7,8]
   else
   {
      long delta_x = x1 - x2;

      // if going down -> possible sectors are [5,6]
      if(y1 < y2)
      {
         long delta_y = y2 - y1;

         // if more vertical (SECTOR 5)
         if(delta_x < delta_y)
         {
            printf("TRACE: SECTOR(5)\n");

            float m = float(delta_x) / float(delta_y);
            float x = float(x2);

            for(long y = y2; y >= y1; y--)
            {
               SetPixel(long(x),y,color);
               x += m;
            }
         }
         // else more horizontal (SECTOR 6)
         else
         {
            printf("TRACE: SECTOR(6)\n");

            float m = float(delta_y) / float(delta_x);
            float y = float(y1);

            for(long x = x1; x >= x2; x--)
            {
               SetPixel(x,long(y),color);
               y += m;
            }
         }
      }
      // else going up -> possible sectors are [7,8]
      else
      {
         long delta_y = y1 - y2;

         // if more vertical (SECTOR 8)
         if(delta_x < delta_y)
         {
            printf("TRACE: SECTOR(8)\n");

            float m = float(delta_x) / float(delta_y);
            float x = float(x2);

            for(long y = y2; y <= y1; y++)
            {
               SetPixel(long(x),y,color);
               x += m;
            }
         }
         // else if more horizontal (SECTOR 7)
         else
         {
            printf("TRACE: SECTOR(7)\n");

            float m = float(delta_y) / float(delta_x);
            float y = float(y2);

            for(long x = x2; x <= x1; x++)
            {
               SetPixel(x,long(y),color);
               y += m;
            }
         }
      }
   }
}
    


Notice that i adjusted the loop so the minor (fractional part) always increase.
This is to have consistent float->int conversion within every octants :)

I had a few goals when i wrote this code...
1) Refresh my memory on linear algebra slope formula.
2) Do very little precalculation as possable.
3) Render all octants seperately and watch them work.

Code size was not a problem so thats why its big but straight forward.
I am happy with the results, but some INT-FPU mixing could make it sing.
Just i have many projects going and it is not very high priority...
If you need help with 2D line clipping just let me know, i have much gfx code...
Post 15 Jan 2010, 10:55
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
i need to clip lines because i want no tests inside put pixel function.
then, putpixel will only take color, X, and Y
and hoplĂ , it will be in frame buffer.
i still does it for rectangle drawing, i clip its coordinates (x,y,xl,yl too) with the screen, and then, the drawing loop is faster.

the screen itself is a rectangle.
with X= Y = 0
xl=320 for the moment
YL=200 for the moment...

then, it will be a general function .
clip item1 in item 2

but a line doens't clip the same way as a rectangle.

about C? it means Chinese? Very Happy
Post 16 Jan 2010, 00:58
View user's profile Send private message Visit poster's website Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 764
Location: Massachusetts, USA
bitshifter
edfed said:
but a line doens't clip the same way as a rectangle.

Sure it does, think about points, which they both have in common...
The goal is to classify a point to a bounding volume.
And C is way easier to understand than chinese Smile
Post 16 Jan 2010, 01:05
View user's profile Send private message Reply with quote
edfed



Joined: 20 Feb 2006
Posts: 4242
Location: 2018
edfed
Code:
        mov edi,[desk]
        mov eax,[esi+.x]
        mov ebx,[esi+.xl]
        mov ecx,[edi+.x]
        mov edx,[edi+.xl]
        add edx,ecx
        cmp eax,edx
        jge .end
        cmp eax,ecx
        jnl @f
        sub eax,ecx
        add ebx,eax
        jle .end
        mov eax,ecx
@@:
        lea ecx,[eax+ebx]
        cmp ecx,edx
        jl @f
        sub edx,eax
        mov ebx,edx
@@:
        mov [esi+.x],eax
        mov [esi+.xl],ebx

        mov eax,[esi+.y]
        mov ebx,[esi+.yl]
        mov ecx,[edi+.y]
        mov edx,[edi+.yl]
        add edx,ecx
        cmp eax,edx
        jge .end
        cmp eax,ecx
        jnl @f
        sub eax,ecx
        add ebx,eax
        jle .end
        mov eax,ecx
@@:
        lea ecx,[eax+ebx]
        cmp ecx,edx
        jl @f
        sub edx,eax
        mov ebx,edx
@@:
        mov [esi+.y],eax
        mov [esi+.yl],ebx
    

if i use this code (it clips a rectangle with another rectangle (the screen)) on a line, it will not give me the intersects of the line with the screen.
Post 16 Jan 2010, 01:36
View user's profile Send private message Visit poster's website Reply with quote
bitshifter



Joined: 04 Dec 2007
Posts: 764
Location: Massachusetts, USA
bitshifter
When i get to my other PC (downstairs) i will get
some code for slope->edge intersection formula.

I have a bit more free time now, i was chasing a stupid bug
in one of my new gfx demo's for two days and finally found it!
So stupid was i to overlook something as simple as this...
Code:
mov ds,[g_segment_a]
mov es,[g_segment_b]
    
Post 16 Jan 2010, 03:24
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


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