Graphic Primitives

[i586coder]

Hi to all,

Ok guy's, i spent 2 or 3 days to optimize my UNEXT/os windowing system,to make some performance
but i got stuck in Graphic Primitives, lines,rectangles,...,i noticed the current implementation is too slow,
and look like this

Code: Select all

void lineH(int x, int y, int len, int color,dword buffer){//draw horizontal line
        for(int i=0; i<len;i++)
         putPixel(x+i,y,color,buffer); //this function check border
}

so in my opinion the solution is

Code: Select all

#define VGA 0xA0000
#define screen_width 800L

void lineH(int x, int y, int len, int color,dword buffer){//draw horizontal line
	dword p;
	p=buffer+(long)y*screen_width +(long)x;
	memset32(p, colour, len);
}

p is a pointer to buffer plus line offset in that buffer
memset32() is 32bit FLAT-mode code used to fill in the line with color.

The above function does not check to see if the line goes off the right edge of the screen.
If the line did extend past the right edge it would continue on the next line starting at the left edge.
Drawing a very long line at (800,600) can crash program, and this is my question

How to improve the code to check borders

CheerS ,
a.T.d

[i586coder]

Use clipping is the most obvious answer.

first, thank you for replying , and i guessed such answer, never min

please notice that, i'm using memset(); to repeat bytes(pixels),so how to make clipping in memset

ThanX

[Combuster]

how to make clipping in memset

You don't.

You should clip once, and only once. adding clipping in memset will check against the screen boundaries for each row of pixels being set. If you know that one row clips, then you know that all other rows will clip the same way (squares), will not clip (only two ends of a line clip), or clip on one side (triangles).

Hence, you transform an object into a clipped object, then render that object without clipping, which is the fastest (and most obvious way).

Edit: trivial code removed, If you can't do this on your own, youre hopeless.

[Troy Martin]

Is double-buffering an option here? Or does that make an opposite of what will happen: poor performance, same issue...?

The memset thing is an interesting idea, but what makes memset'ing the line to the screen faster than doing it by hand in a loop? Certainly making a function call to memset has to be way less efficient than writing a loop.

[DeletedAccount]

Hi,
Cohen Sutherland algorithm is the easiest way and resonably efficent way to implement clipping . For the line drawing part ,use bresenham's line line drawing alogirthm which is fairly easy to implement ( and you can use the same algorithm to implemnt rudimentry chasing in a tiled environment ) .Memset thing is an interesting idea , but not an original one , you will find it if you perform a moderate search on the net . It more efficent there is only once call to memeset than lots of calls to putpixel which inturns pokes a memory address . memset does it in a snap ( u can also use string instuctions to implement memset ) . You may use a profiler to find out which is faster .

@Troy : Double buffering is useful only if you do so animations etc , for static drawing its not really required
Regards
Shrek

[Creature]

Code: Select all

void lineH(int x, int y, int len, int color,dword buffer){//draw horizontal line
        for(int i=0; i<len;i++)
         putPixel(x+i,y,color,buffer); //this function check border
}

If you want to stick with this, a valuable optimization (might seem small but can cause a huge performance if it is needed often) could be:

Code: Select all

void lineH(int x, int y, int len, int color,dword buffer){//draw horizontal line
        for(int i(0); i<len;)
         putPixel(x + i++,y,color,buffer); //this function check border
}

The int i(0) might not work if you're using C, but then again I don't believe you can create variables in the for-statement in C, so I'm assuming you use C++. The 'i++' inside the putPixel instead of the for-loop can (CAN) cause a performance boost.

Lastly, are you sure that your 'x', 'y' and 'len' variables need to be integers? Why not make them shorts? I doubt your coordinates or lengths will ever become larger than that (seeing that resolutions only go to somewhere around 2000x1600 [guess]). You might also make 'color' an unsigned, unless you're planning to use negative colour values for something special (such as maybe some strange way to store special colour values).

[i586coder]

Edit: trivial code removed, If you can't do this on your own, youre hopeless.

hehehe, don't worry i will try to make smart clipping with memset

Is double-buffering an option here?

No, it's not, buffer is necessary,to put all drawing in buffer and then copy each 64KB of buffer to VGA buffer,
this code to copy buffer to screen

Code: Select all

void copy2VESA(dword src){
 for(int i=0; i<MAX_BANKS; i++){
  bank(i); //set banks
  memcpy32(0xA0000,src,BANK_SIZE);//BANK_SIZE==65536 (64KB)
  src+=BANK_SIZE;
 }
}

@Troy : Double buffering is useful only if you do so animations etc , for static drawing its not really required

i'm not drawing static image, i'm going to creat GUI for my os, you know there is many windows,frames,etc drawing
together at once,so i think double buffering isn't bad idea to do that also double buffer is helpful to kill flickers

I'm assuming you use C++.
:
:
Lastly, are you sure that your 'x', 'y' and 'len' variables need to be integers? Why not make them shorts? I doubt your coordinates or lengths will ever become larger than that (seeing that resolutions only go to somewhere around 2000x1600 [guess]). You might also make 'color' an unsigned, unless you're planning to use negative colour values for something special (such as maybe some strange way to store special colour values).

Yup i'm using C++,..., no problem i will change all data types in function declare, if this make some performance


Thank you guy's for helpful comments

CheerS ,
a.T.d

[Creature]

Yup i'm using C++,..., no problem i will change all data types in function declare, if this make some performance

Well, performance not necessarily, but it will save you memory in the function. Double-buffering will most likely slow down everything, you should only use it when your drawing is fast enough and you're experiencing flickering or artifacts, as that's what its common purpose is.

[bewing]

You can easily get a 5% speed improvement just by counting your loops from N down to 0, rather than from 0 up to N.

[Combuster]

The biggest speed improvement will still be when you skip the entire memset or putpixel call. putpixel is slow because it recomputes a lot every time, memcpy is slow because it's a libc function and can not be inlined.

And again, memset has predefined properties and doing clipping in your own memset style function only leads to it being done too often or wrong since it doesn't have the x and y coordinate to work with in the first place.

[AndrewAPrice]

When you're talking about drawing a line, are you drawing lines (borders) around every window and drawing all the text curves/lines, every time the screen is updated?

What I'm doing is rendering the border/title into the window's frame (the border is drawn by the user lib than the window manager in my OS, it makes it easier to have windowless borders, new types of windows, stylised windows, etc without modifying the window manager), and treat the window's frame as a 'texture', and then render the exposed rectangle of each windows' texture to onto the screen.

[i586coder]

Hi again,

after some modification on my horizontal line, it's look like this

Code: Select all

void lineH(short x,short y,short len,byte color,dword buffer){
 if(y<0 || y>screen_height) return;//up down clip

 if(x+len > screen_width){//right clip
  int clip= (x+len)-screen_width;//calc. the out of boundary value
  len-=clip;                            //subtract it from line length
  if(len<0) len=0;
 }
 
 if(x<0){//left clip
  len+=x; //yup it's + because x already minus (-+ = -)  
  x=0;
  if(len<0) len=0;
 }

 dword p=buffer + (long)y*screen_width +(long)x;
 memset32(p,color,len);
}

well it's my view to clipping, the main idea is to adjust line length
what do you think about it

CheerS ,
a.T.d

[i586coder]

When you're talking about drawing a line, are you drawing lines (borders) around every window and drawing all the text curves/lines, every time the screen is updated?

unfortunately yes

[i586coder]

memcpy is slow because it's a libc function and can not be inlined.

hmm, when i decided to wrote my own OS ,i wrote my own libs, so memset32,or any things related to memory is really inlined in my kernel

for example :

Code: Select all

void memset32(dword d,byte i,long n){
 _ES=0;
 asm{.386
        push edi
        mov edi, [d]
        mov al, [i]
        mov ah,al
        mov bx,ax
        shl eax,16
        mov ax,bx
        mov ecx, [n]
        push ecx
        and ecx,3
        rep stosb
        pop ecx
        shr ecx,2
        rep stosd
        pop edi
 }
}

any comments

[i586coder]

take a look at AGG (antigrain.com) - very educational.

very interesting web site and cool examples inside, thank you alot

CheerS
a.T.d