Sign in to follow this  

How to calculate a RECT to fit X amount of other RECTS into?

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I am using C++ and Direct3D9. I have X amount of subRECTs and I want to calculate a mainRECT for all the subRECTS to fit into. subRECT and mainRECT are RECTS (eg with left, right, top, bottom). When the mainRECT is calculated, I want to be able to fit all the subRECTs in the mainRECT, wasting as little space as possible. How would I do this?

Share this post


Link to post
Share on other sites
texture tiler, hey? :)

it's actually not straight forward. A wild stab, Since I;ve never actually done such a thing. Sort the rects by size, and fill up the gaps starting with the largest rectangle. Also, log the space left as a list of rectangle areas, also sorted by size.

surely, there are some better schemes.

Share this post


Link to post
Share on other sites
Here's a standard solution to this problem. Note that rather than packing all the textures into a single large rect, it packs them into N rects of a predetermined size. This is probably better anyway, as you will want to choose the size of the aggregate textures for optimal performance.

1. Sort the textures by area, from largest to smallest.

2. Create a new 'texture rect' of dimension size * size. 'size' should be big enough to hold the largest of your textures.

3. Go through the texture list and find the first one that fits in your texture rect. If none fits (this won't happen on the first pass), go back to 2 and create a new group texture.

4. If it fits, put it in the upper left. You can now split the remaining area in two ways, either along the textures right edge or bottom edge. Choose the split that results in the largest single new rect. After the split, we'll call the larger of the resulting rects A and the smaller B.

5. Goto 3, recursing on rect A.

6. Goto 3, recursing on rect B.

Anyway, that's how I remember it (it was in one of the Watt/Policarpo books). It's probably not the only solution, but it is a solution.

Also, I think this is the general idea of oliii's solution as well.

Share this post


Link to post
Share on other sites
Thanks oliii and jyk. I was thinking along similar lines. Yes, basically I want to be able to go through a list of textures and merge them all into one texture.

@jyk
For step 2, what if a massive texture was created that could fit any size and any amount of subtextures. Place all the subtextures on, biggest first. Then make a new texture, that fits the grouped subtextures and copy the grouped subtextures to the new texture.

Share this post


Link to post
Share on other sites
Quote:
For step 2, what if a massive texture was created that could fit any size and any amount of subtextures. Place all the subtextures on, biggest first. Then make a new texture, that fits the grouped subtextures and copy the grouped subtextures to the new texture.
I see what you're saying. Is it a good idea? I don't know :-) I haven't coded this, so I can't really say what the best approach is. I'm thinking though that there might be issues with texture size, caching, memory, API-specific things, and whatnot, so perhaps one big texture wouldn't be ideal, and a number of smaller ones would perform better.

Again though, I'm just guessing :-)

Share this post


Link to post
Share on other sites

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this