OSDev.org

Posted: **Sat Oct 12, 2002 5:04 pm**

[attachment deleted by admin]

Posted: **Sat Oct 12, 2002 8:04 pm**

Well, I'll take a stab at it, for better or worse

Storing top left coords and bottom right coords of each box would save you one addition calculation/loop (Possible 4096 loops, so potential saving is reasonable).

As for the loops, you're checking every window, every time (So it seems).

There's a few ways of reducing that (I don't know even close to all of them).

You could maintain your list of windows in a sorted fashion, so resorting every time a window changes zorder, but you get the bonus of only checking number of windows at one specific zorder. That would probably mean changing quite a bit of stuff though.

Another possibility (Within your existing scheme) is to create an array of unchecked windows. So you'd have an array of 64 elements, then remove those elements from the array whenever a window is found not to match. So the array reduces in size/iteration, and that inner loop doesn't check window elements that it already has eliminated once. I don't mean to copy over the entire windows array, just an array of ints from 0->63 will do, then have that inner for loop do something like (Eww, pseudocode):

Code: Select all

Create an array Some_Array={0,1,2,3,4...MAXWINDOWS}

for(tz=0;tz<MAXWINDOWS;tz++){

for(j=0;j<sizeof(Some_Array);j++){
  i=Some_Array[j];
  if (wm_elements[i].zorder == tz)
  NO  YES
  |      |
  |      Test to see if x,y coords are inside
  |      NO  YES
  |      |      |
  |      |      Return i
  |      Forget it ever existed
  Add i to New_Array  
  Make Some_Array=New_Array
}
}

Hope it's clear what the idea is, I'm not too good at explanations. The idea being that you remove previously checked windows from the inner loop.

Either way, or something else, concentrates on reducing the number of times you go through the loop. Right now you're looping for every window at every depth. Not much you can do about the depth (Although a variable listing max zorder would help I guess), but that inner loop just doesn't need to go through every window for every depth. Maybe someone else can explain that more clearly.

Curufir

Btw, had a play with it, I like it ;D

Posted: **Sat Oct 12, 2002 8:07 pm**

ARG, I did GUI programming a while ago, I think I had a way to fix that, but I forgot most of my GUI programming ( i'd look in my code but i DELETED all my header files by mistake! )

sorry...but try using less fors and use more tricky C code ( i.e

if ( wm_elements....... && /* other stuff */ )

that Might ( Might might might ) help

Posted: **Sat Oct 12, 2002 8:27 pm**

Ok, had another think, and my C is rusty so be kind

This one is really ugly, and would be horrible with many more than 64 windows. What it does do however is make the loop cost exactly the same every single time (Unless the matching window happens to be at zorder 0).

Code: Select all

unsigned char inwhatwin(int x, int y)
{
    unsigned int minz;
    unsigned int fi;
    unsigned char i;

    minz=MAXWINDOWS;
    fi=255;

    for (i = 0; i < MAXWINDOWS; i++)
    {
        if (wm_elements[i].flags & WMFLAGS_ACTIVE)
        {        
            if ((x >= wm_elements[i].x) && (x < (wm_elements[i].x + wm_elements[i].width))){
                if ((y >= wm_elements[i].y) && (y < (wm_elements[i].y + wm_elements[i].height))){
                    if(minz>wm_elements[i].zorder){
                        minz=wm_elements[i].zorder;
                        fi=i;
                        if(minz==0) return fi;
                    }
                }
            }
        }
    }
    return fi;
}

Think that'd work anyway, idea being to simply run through all the windows and find the one that matches the coords at the least depth.

Oh, and I guess you could (As someone else said) reduce that whole set of if statements into a single one, dunno if the compiler would optimize that any better, but who knows ;D

Curufir

Posted: **Sat Oct 12, 2002 9:39 pm**

Wow! Thanks alot people! I knew this could definitely be optimized! I didn't know how much though!... There are about 4 of those functions with the double for loops... It's VERY ugly, but for the moment it works... I understand an optimization you made, go through the windows, check if it's active and then check zorder loop... I never thought of that... But it doesn't work for the drawgui() function...

Posted: **Sat Oct 12, 2002 10:20 pm**

Curufir, I tried one of my own optimizations and it didn't work at all... I tried your new optimization and it seemed to work fine... exactly the same way my other function did, but you lost a for loop

. In the end, I believe your way of doing that would be great, but I see what you mean by more than 64 windows would be brutal... I'll have to think about what I should use... (but who would use more than 64 windows(including menus, and message boxes) ? ) One more thing, your code goes through every window(no matter how many), while my code goes though the first, until it finds the top and then the next and returns right when it finds the right one. For the average user, my approach on that function may be better, but for the power user with many windows up, your solution may be better... Thanks alot for the help

I have about 4 double-looped functions... Here's another(I forget):

Code: Select all

void movefrontwin(unsigned char handle)
{
    int tz, i;
    unsigned char t_zorder = wm_elements[handle].zorder;

    for (tz = t_zorder; tz >= 0; tz--)
    {
        for (i = 0; i < MAXWINDOWS; i++)
        {
            if (tz == wm_elements[i].zorder)
            {
                wm_elements[i].zorder++;
            }
        }
    }
    wm_elements[handle].zorder = 0;
}

...Now that one's not really so brutal...

I think I will try to change the widths and heights into x2 and y2... it will make the programming of it a bit less enjoyable, but I agree that the thing will definitely run faster!

About the compiler, it's very small (1.27MBytes) so it fits on a floppy(I have it on my D Drive)... I'm not sure about what it does for optimization, but if you want a look, email me and I'll send it

[email protected]

BTW: Thanks alot! This could greatly improve the speed of my GUI. I need lots of speed to be able to use this on my OS!

Posted: **Sat Oct 12, 2002 10:52 pm**

OK...
I could probably sort the windows after I do a zorder rearrange... my window structures are as follows:

Code: Select all

struct WINDOW
{
    unsigned short x;
    unsigned short y;
    unsigned short width;
    unsigned short height;
    unsigned char *caption;
    unsigned short zorder;      /* From 0 - MAXWINDOWS */
    unsigned long flags;        /* Use WMFLAGS_xxxx to set flags */
    unsigned char handle;       /* From 0 - MAXWINDOWS */
};

So much for keeping my code confidential, eh?

In my initgui() function, I give every window a unique handle according to it's array position. Now, I could sort these structures and they would still keep their handles so I could identify them and say "Gee, this window moved to here, so get it"...

Tom, you said you deleted all your header files... do you still have the source files??? Did you go about doing your GUI in the same way I did with a massive list of windows? Who else tried this? Answers to these questions and more coming up on... oh whatever

Posted: **Sun Oct 13, 2002 11:39 am**

Code: Select all

void movefrontwin(unsigned char handle)
{
    int tz, i;
    unsigned char t_zorder = wm_elements[handle].zorder;

    for (i = 0; i < MAXWINDOWS; i++)
    {
        if (t_zorder > wm_elements[i].zorder)
        {
            wm_elements[i].zorder++;
        }
    }
    wm_elements[handle].zorder = 0;
}

Should work if I understand what you're doing properly. I think you're pushing one window up to zorder 0 and everything that was above it downwards, leaving the others alone. No real need for the extra loop.

**

Hmm, dunno if it's the best way, but couldn't you do something along these lines with a 2 dimensional array of window structures.
wm_elements[zorder][index]=window structure.

Excuse my asciii art

Code: Select all

zorder    index
0---------0->structure of window at zorder 0
          1->structure of window at zorder 0
1---------0->structure of window at zorder 1
          1->structure of window at zorder 1
          2->structure of window at zorder 1
2---------0->structure of window at zorder 2
.
.
.
MaxZ------X->structure of window at zorder MaxZ (Maximum zorder currently being used)

Then a window moving from zorder eg 2->1 would just involve moving it in the array, checking its dimensions against those at the same zorder and moving down those that it clashes with. Guess that effectively breaks your MAXWINDOWS thing though, seeing as that scheme can handle any amount of window/depths that happen to be currently used.
Then all the checks take place by checking the array of windows at a specific zorder (Which will be small), which should improve the speed on some things a little as you don't have to check all the windows.
Wouldn't really help with the move to front code though, as you'd have to do a recursive move down for any windows that the one moving to 0 zorder clashed with, one of those judgement calls I guess

.

Curufir

Posted: **Sun Oct 13, 2002 3:25 pm**

OK, here's a completely different and IMHO better way of maintaining the z-order. Regardless of where you store your actual window structures (e.g. array, malloc, etc.), put a linked list of child windows sorted by z-order in each window. Then:

Code: Select all

window_t *inwhatwin(window_t *parent, int x, int y)
{
    window_t *child, *hit;

    for (child = parent->child_first; child != NULL; child = child->next)
    {
        hit = inwhatwin(child, x, y);
        if (hit != NULL)
            return hit;
    }

    if (PointInRect(parent->position, x, y))
        return parent;

    return NULL;
}

Moving windows around in the z-order is simply a matter of breaking and re-forming part of the linked list. Note also that there is no upper limit on the number of windows (you can use malloc instead of an array here). However, you might still want to maintain a (dynamic) array for handle->window_t mappings.

Posted: **Sun Oct 13, 2002 9:22 pm**

Id like to see ur video driver code.. or how did u do it?

thanks

Posted: **Mon Oct 14, 2002 9:48 am**

I don't have any code to show yet (I'm prototyping it under Windows first -- I don't have a Mobius debugger

) but I can describe some of the algorithms if you want.

Posted: **Mon Oct 14, 2002 12:50 pm**

What kind of algorythms?? for drawing lines and so ??
if anyone is interested in stuff like that, andhow to set up RGB and those kind of things, check out the windows game programming gurus by andre lamonthe(Has nothing to do with windoze)

most of the stuff he has there are plain algorythms portable for anything... though some chapters are totally directX and so on

so what kinda algorythms do u have

thanks
later

Posted: **Mon Oct 14, 2002 3:39 pm**

soilwork wrote:so what kinda algorythms do u have

Sorry, I'm not sure what you're asking now. The thread started on windowing but now you're asking about graphics.

Posted: **Mon Oct 14, 2002 4:29 pm**

Well, I posted this exact same question on the forum at VBWORLD and they came to the same conclusions you guys did: Use a sorted list... sorted right after the zorder check... I think this is exactly what I will do. Thanks alot!

All I need to do is create my own sort function... I'll have to try and figure it out...

Is there any more optimizations to do?

Posted: **Mon Oct 14, 2002 5:20 pm**

dori wrote: Id like to see ur video driver code.. or how did u do it?

thanks

I wouldn't really call it a video driver... All it is is a setvmode(mode) function that uses int 10h(video interrupt), and then I put a pixel by changing a byte in the video memory at 0xA0000000. Simple. Find (IMHO) the BEST VGA tutorial @ http://www.brackeen.com/home/vga

As for my drawing algorhythms: Is two for loops (one for x and for y) to plot pixels to fill an area good enough? That's all I use... and for drawing my border? That's a special algorhythm. I don't want to give that out (but it does need some work - changes when you move a window - I know how to fix that). I think I'll post GUI.EXE updates as they come so you can see what I change and see any speed-ups

OSDev.org

My GUI... check, optimization, hints...

My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...

Re:My GUI... check, optimization, hints...