flat assembler
Message board for the users of flat assembler. Index > Main > edfedham line algorythm for fool.
Author
 Thread  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] ``` _________________ fool gitlab fasmstuff gitlab foolstuff 14 Jan 2010, 05:49
 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... 14 Jan 2010, 14:27
 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 ``` 14 Jan 2010, 15:34
bitshifter

Joined: 04 Dec 2007
Posts: 764
Location: Massachusetts, USA
bitshifter
LOL, I love the name, edfedham 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... 14 Jan 2010, 19:51  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? 14 Jan 2010, 22:20
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... 15 Jan 2010, 10:55  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?  16 Jan 2010, 00:58
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  16 Jan 2010, 01:05  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. 16 Jan 2010, 01:36
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]
``` 16 Jan 2010, 03:24  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

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