flat assembler
Message board for the users of flat assembler.

 Index > Main > edfedham line algorythm for fool.
Author
edfed

Joined: 20 Feb 2006
Posts: 4330
Location: Now
edfed 14 Jan 2010, 05:49
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
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]
```
14 Jan 2010, 05:49
vid
Verbosity in development

Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid 14 Jan 2010, 14:27
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: 4330
Location: Now
edfed 14 Jan 2010, 15:34
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: 796
Location: Massachusetts, USA
bitshifter 14 Jan 2010, 19:51
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: 4330
Location: Now
edfed 14 Jan 2010, 22:20
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: 796
Location: Massachusetts, USA
bitshifter 15 Jan 2010, 10:55
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: 4330
Location: Now
edfed 16 Jan 2010, 00:58
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.

16 Jan 2010, 00:58
bitshifter

Joined: 04 Dec 2007
Posts: 796
Location: Massachusetts, USA
bitshifter 16 Jan 2010, 01:05
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: 4330
Location: Now
edfed 16 Jan 2010, 01:36
Code:
```        mov edi,[desk]
mov eax,[esi+.x]
mov ebx,[esi+.xl]
mov ecx,[edi+.x]
mov edx,[edi+.xl]
cmp eax,edx
jge .end
cmp eax,ecx
jnl @f
sub eax,ecx
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]
cmp eax,edx
jge .end
cmp eax,ecx
jnl @f
sub eax,ecx
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: 796
Location: Massachusetts, USA
bitshifter 16 Jan 2010, 03:24
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