So I wouldn't worry about that, it's best left to the caller to optimize the RECTs.

I agree with this - but it might be nice creating a "RECT optimizer". I had a few ideas during school today, but still waiting for time to create an algorithm for it. I don't think there's any "optimal" solution to this problem, short of trying all possibilities... but it should be possible to come up with something fairly good.
Posted on 2004-08-09 10:32:39 by f0dder


I agree with this - but it might be nice creating a "RECT optimizer". I had a few ideas during school today, but still waiting for time to create an algorithm for it. I don't think there's any "optimal" solution to this problem, short of trying all possibilities... but it should be possible to come up with something fairly good.

Yeah, I've been toying with that idea too since that update to the region generator. I'm sure the OS's solution is not optimal, but I still couldn't find any algorithms to do it (let alone think of one myself :sweat: )
Posted on 2004-08-09 10:38:27 by QvasiModo
I was thinking of some loop that runs until "no changes has been done". It would try combining adjacent RECTs, and possibly split RECTs if one of the resulting RECTs would be larger than the old one... it's conceptually simple and would probably work okay - but would still require a fair amount of code.

It would be nice with some tool to visualize RECTs with different colors or something, to test algoritms...
Posted on 2004-08-09 11:04:18 by f0dder
Hi f0dder,

Conceptually simple but I think it would be hard to implement in an efficient way. Off topic a bit, I was reading Raymond Chen's blog on the performance hits using small regions and they are large if you have large windows. Essentially the window manager just takes the region data and does a PtInRect in a loop for the whole window, it eliminates regions that are outside the bounding RECT fo the window to increase efficiency. So if your window is significantly larger than the total area of the region the hit grows exponentially. His server is down at the moment but google cache saves the day...

Blog
Posted on 2004-08-09 11:44:29 by donkey
A nice read as always.

Anyway... you'd probably want as *big* RECTs as possible for blitting, and as *few* RECTs as possible for hit-testing. I guess a routine optimizing for big RECTs would usually create few rects?


Has anybody looked at / know info about how ExtCreateRegion optimizes the region data? Is it simply doing per-scanline?
Posted on 2004-08-09 11:59:37 by f0dder
Thanks to f0dder's help and this site I have added an ellipse function to the library. Also I now clip the SetDIBPixel so that it will not attempt to set a pixel outside of the DIB surface, this was leading to alot of GPFs and the extra couple of lines is a small tradeoff for the increased stability.
Posted on 2004-08-09 16:58:06 by donkey
A couple of suggestions:

*) move SetDIBPixel to a separate asm file to improve modularity

*) get/setpixel based algorithms are slower than working directly on the bitmap data... but I think you should keep it as-is, as it's easier to read. There's not much point in using macros for get/setpixel as only call/ret overhead would be shaved off, and the gains you get from not using get/setpixel is usually related to using pointer operations etc.

*) you have four compares for X,Y clipping - iirc there's a way of cutting this down to two compares - something along the lines of subtracting width from xpos and doing signed check for below zero. Will of course fail if coordinates are WAY off :)
Posted on 2004-08-09 17:10:34 by f0dder
1: There is a bug in GoAsm lib imports that requires that it is contained in the line module, Jeremy is looking into it but for now BresLine will GPF without it for some reason I only partially understand. This does not affect MASM builds but the GoAsm lib support is relatively new and is still a bit wet behind the ears.

2: Yeah, I had considered making it a macro, originally it was one but I decided it would be useful to export it and not worry about the call overhead. I ran a grayscale with Get/SetPixel from the GDI and one with mine and mine was on the order of 30 times faster. With the GDI you could actually see the image changing. The macro would have solved the SetDIBPixel problem, I had done the same thing (more or less) with creating bitmaps. The main idea was to have it register independant so I could use it in any routine and didn't have to worry about which registers were x/y every time I passed to the function. With a proc it allows me a bit more latitude to select registers.

3: I have already improved the clipping with an unsigned compare, it takes care of the extra 2 cmps, you downloaded it too fast, when I uploaded it I figured that I was going to get comments on that one. Pretty dumb but I was testing and testing and did it long hand first then forgot to change it :)
Posted on 2004-08-09 17:34:50 by donkey

1: There is a bug in GoAsm lib imports that requires that it is contained in the line module, Jeremy is looking into it but for now BresLine will GPF without it for some reason I only partially understand. This does not affect MASM builds but the GoAsm lib support is relatively new and is still a bit wet behind the ears.


My bad, the problem was fixed in release 0.50.2 and I hadn't noticed. I have separated the 2 functions and everything seems fine. You will need the latest beta of GoAsm in order to build the lib or projects using it.
Posted on 2004-08-09 18:03:15 by donkey