Need AI to fit rectangles in a larger square
Author
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.
What you search for is known as : The knapsack problem..
you can maybe find some algorithms using google.
Usually brute force or genetic algorithms.
you can maybe find some algorithms using google.
Usually brute force or genetic algorithms.
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.
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.
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?
Author
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.
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.
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.
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.
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.<!--QUOTE--></td></tr></table></BLOCKQUOTE><!--/QUOTE--><!--ENDQUOTE--><br><br>I wish I had noticed this thread before. I'd be glad to have a look at that javascript code.<br><br>Thanks!
Here's a link to the site with a javascript version: <a href='http://blog.netxus.es/blog/rectangle-packing-2d-packing'>http://blog.netxus.es/blog/rectangle-packing-2d-packing</a>
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
