Sign in to follow this  
TheSilverHammer

Need AI to fit rectangles in a larger square

Recommended Posts

I need an algorithm that can efficiently fit some 2d rectangles in a larger 2d square. Actually this is for a tool for a game. I would like to have a directory of textures which can be a rectangle of any dimensions, ie: 48x48 64 x 128, 18 x 96, etc... Then I want to specify a texture page of a square size, like 512 x 512. I would like this algorithm to fit as many textures as it can on the texture page using space the most efficiently it can. It would then generate as many texture pages as it needed, creating the absolute minimum possible.

Share this post


Link to post
Share on other sites
Trenki    345
You don't need AI to solve this. This problem is known under the name "bin packing" or "rectangle packing" and it is a NP-hard problem, which basically means that computing the most efficient solution is not an option as it would take way too much time (possibly years and more).

There exist algorithms for this that are widely used in the industry but I'm not aware of any source code that could be used directly. It's not too hard to come up with an algorithm yourself to do this but the space efficiency might not be the best. In computer graphics this is most likely used for packing lightmaps. Quake 1 uses a very simple algorithm. Here is also a description of an algoritm that could be used.

Share this post


Link to post
Share on other sites
ID Merlin    119
If the number of textures that need to be fit is relatively small, you could just brute-force it. Ten textures would give about 1,000 combinations of which one is fit first. Since your shapes are all rectangles, there wouldn't be that many more permutations of side-by-side fits. Right?

Share this post


Link to post
Share on other sites
I have no idea. If I had a bunch of small textures, there could be a lot per page. Ill have to look at those other algorithms mentioned. At least I know what they are called, which should make searching for them much easier.

Share this post


Link to post
Share on other sites
Rainweaver    220
Quote:
Original post by ID Merlin
Ironically, today I got a newsletter with the solution to your problem, almost.

Here's the link: http://www.devx.com/dotnet/Article/36005

I also found a javascript application that implements an algorithm that is almost what you are looking for. Post here if you want code.


I wish I had noticed this thread before. I'd be glad to have a look at that javascript code.

Thanks!

Share this post


Link to post
Share on other sites

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