2D subdivision algorithm
Author
Hey,
I am looking for a way to divide a bitmap (with some transparent pixels) into n rectangles, which do not have to be axis-aligned. The rectangles must roughly outline the shape of the non-transparent pixels. Does anyone have an efficient way of doing this?
My idea was to find the n largest visible areas on the bitmap and put a rect around them, then with the remaining pixels, union them with the nearest of the n rects. I'm still not sure how I'd go about finding the largest area of non-transparent pixels though (not axis-aligned).
If anyone wants to provide any code, the language being used is C++ and the purpose of the rectangle subdivision is for more accurate collision detection than just the bounding box.
EDIT: Clarified what I need. New information:
I already have the pixels so all I need is a subdivision algorithm. The n value is a variable which can be set during run-time if needed (but will only be re-subdivided during loading, so the speed of the technique isn't as important as accuracy).
[edited by - red_sodium on March 18, 2004 8:13:03 AM]
Author
It sure is :D
Anyone who thinks I might be foolish for accepting non-axis-aligned bounding boxes in my algorithm must know that I plan on rotating and scaling the sprites with the rects, so they''ll be non-axis-aligned anyway.
Anyone who thinks I might be foolish for accepting non-axis-aligned bounding boxes in my algorithm must know that I plan on rotating and scaling the sprites with the rects, so they''ll be non-axis-aligned anyway.
Here''s my proposal for axis-aligned:
1. Make a list of all the outline pixels
2. Your optimization function is (number of outline pixels covered total * k - number of transparent pixels covered)
3. Put your n rectangles on random outline pixels (they can be 1x1 rectangles at first)
4. Evaluate your optimization function
5. Randomly select a rectangle, change one of its 4 coordinates randomly (+-random(5))
6. Compare the current result of the optimization function with the one obtained in 4. If it''s worse, revert back the change.
7. Rinse and repeat 4-6 until you have reached a satisfactory configuration (i.e.: the optimization function hasn''t been increased in the past 100 tries).
You can try it many times to try to get the best result on the optimization function. You can also vary k.
To support non-aligned rectangle, add a tilt angle to the 4 coordinates (number 5), and vary it randomly too.
This is more or less hill-climbing. It should give decent results if there aren''t too many local minimums (in this case, I wouldn''t be too worried, though I don''t have much experience with this). Plus, it should be pretty fun to code
Cédric
1. Make a list of all the outline pixels
2. Your optimization function is (number of outline pixels covered total * k - number of transparent pixels covered)
3. Put your n rectangles on random outline pixels (they can be 1x1 rectangles at first)
4. Evaluate your optimization function
5. Randomly select a rectangle, change one of its 4 coordinates randomly (+-random(5))
6. Compare the current result of the optimization function with the one obtained in 4. If it''s worse, revert back the change.
7. Rinse and repeat 4-6 until you have reached a satisfactory configuration (i.e.: the optimization function hasn''t been increased in the past 100 tries).
You can try it many times to try to get the best result on the optimization function. You can also vary k.
To support non-aligned rectangle, add a tilt angle to the 4 coordinates (number 5), and vary it randomly too.
This is more or less hill-climbing. It should give decent results if there aren''t too many local minimums (in this case, I wouldn''t be too worried, though I don''t have much experience with this). Plus, it should be pretty fun to code
Cédric
I suppose rectangle decomposition in such a way won''t be too fast, since if you have 2 objects, one with m rectangles and the other with n rectangles, collision will be a O(m*n) algorithm.
You could do much better with a simple quadtree decomposition.
Just build the quadtree to the wanted precision.
Another advantage is that inside the quadtree, the rectangles are oriented alike, so it requires less rotation computations, since apart from the initial coordinated, finding the coords of subrects is just a matter of splitting segments in half.
If the quadtree splits in 4 equal parts, then you can store it in a compact bitfield.
You could do much better with a simple quadtree decomposition.
Just build the quadtree to the wanted precision.
Another advantage is that inside the quadtree, the rectangles are oriented alike, so it requires less rotation computations, since apart from the initial coordinated, finding the coords of subrects is just a matter of splitting segments in half.
If the quadtree splits in 4 equal parts, then you can store it in a compact bitfield.
Author
Thanks for your responses, but a few things:
Cedric
This sounds a bit too much like trial-and-error, but the good thing about this is that I already have a function to get the outline pixels. What I don''t really understand is k. Is it a constant, what''s it do and why/where would I vary it, and to what effect?
Is there an algorithm you could think of which would find the best way of changing the co-ords instead of doing completely randomly?
Janos:
Sounds like the more conventional way, and I must admit I''d forgotten about quadtrees. I was only planning on using around 10-20 rectangles per sprite anyway, but perhaps the quadtree method will be easier to implement.
Are there any more thoughts out there?
Cedric
This sounds a bit too much like trial-and-error, but the good thing about this is that I already have a function to get the outline pixels. What I don''t really understand is k. Is it a constant, what''s it do and why/where would I vary it, and to what effect?
Is there an algorithm you could think of which would find the best way of changing the co-ords instead of doing completely randomly?
Janos:
Sounds like the more conventional way, and I must admit I''d forgotten about quadtrees. I was only planning on using around 10-20 rectangles per sprite anyway, but perhaps the quadtree method will be easier to implement.
Are there any more thoughts out there?
quote:Original post by red_sodiumThere''s nothing wrong with T&E if it achieves what you want. What I proposed is actually closer to hill-climbing. Random hill-climbing.
This sounds a bit too much like trial-and-error
quote:What I don''t really understand is k. Is it a constant, what''s it do and why/where would I vary it, and to what effect?It allows you to ponderate the importance of having all of the outline pixels vs the importance of avoiding transparent pixels. If k is high (say > 5), all of the outline pixels will be covered, at the expense of containing a lot of transparent pixels. If k is low (~ 1 or lower), then you will get more of a balance. You start the process with a definite value of k (1.5, for instance), and you keep it until it has converged. If the rectangle distribution doesn''t satisfy you, restart with another value of k. Experiment.
quote:Is there an algorithm you could think of which would find the best way of changing the co-ords instead of doing completely randomly?Not really. Going randomly is the easiest to code. It''s going to be a slow process, but who cares? It''s a preprocessing step, isn''t it? You can then save the rectangles to a file, and never recalculate them again.
As for quadtrees, I would also recommend them over what you are doing. You can vary the granularity with quadtrees too. And there is quite a bit of room available for optimization.
Look around the web, I''m sure that you can find good ressources on the subject.
And don''t forget: premature optimization is the root of all evil.
Cédric
you can build a quadtree like this:
here is some pseudo-code to build the quad tree
[cpp]
QuadtreeNode * BuildQuadTree(image, rect)
{
if (rect.IsEmpty())
return NULL;
if (image.IsAlphaMonochromaticForRect(rect))
return new QuadTreeLeaf(image[rect.MinX, rect.MinY]).Alpha);
QuadTreeNode result;
result.Son00 = BuildQuadTree(image, rect.GetQuarter(0,0))
result.Son01 = BuildQuadTree(image, rect.GetQuarter(0,1))
result.Son10 = BuildQuadTree(image, rect.GetQuarter(1,0))
result.Son11 = BuildQuadTree(image, rect.GetQuarter(1,1))
}
[/cpp]
to test the intersection, put some thought into it.
(basically you try to find if there exist 2 leaves, on in each tree, that have a non-void intersection).
here is some pseudo-code to build the quad tree
[cpp]
QuadtreeNode * BuildQuadTree(image, rect)
{
if (rect.IsEmpty())
return NULL;
if (image.IsAlphaMonochromaticForRect(rect))
return new QuadTreeLeaf(image[rect.MinX, rect.MinY]).Alpha);
QuadTreeNode result;
result.Son00 = BuildQuadTree(image, rect.GetQuarter(0,0))
result.Son01 = BuildQuadTree(image, rect.GetQuarter(0,1))
result.Son10 = BuildQuadTree(image, rect.GetQuarter(1,0))
result.Son11 = BuildQuadTree(image, rect.GetQuarter(1,1))
}
[/cpp]
to test the intersection, put some thought into it.
(basically you try to find if there exist 2 leaves, on in each tree, that have a non-void intersection).
Author
Okay, thanks very much for all your responses Cedric and Janos, I reckon I''ll go the quadtree route then.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
