Need AI to fit rectangles in a larger square

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

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 on other sites
What you search for is known as : The knapsack problem..
you can maybe find some algorithms using google.
Usually brute force or genetic algorithms.

Share on other sites
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 on other sites
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 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 on other sites
There's always the NVidia Texture Atlas Tools which might do what you need already. It includes a whitepaper which explains some of the details of how the tool works, and the methods it uses to avoid problems with mipmaps, and out of range UVs.

Share on other sites
Ironically, today I got a newsletter with the solution to your problem, almost.

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

Share on other sites
Quote:
 Original post by ID MerlinIronically, 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 on other sites
Thank you, that's very interesting.

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 17
• 14
• 10
• 9
• 11
• Forum Statistics

• Total Topics
634094
• Total Posts
3015498
×

Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!