• FEATURED
• FEATURED
• FEATURED
• FEATURED
• FEATURED

View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Need AI to fit rectangles in a larger square

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

9 replies to this topic

#1TheSilverHammer  Members

Posted 02 November 2007 - 05:10 AM

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.

#2VincentGreen  Members

Posted 02 November 2007 - 05:27 AM

What you search for is known as : The knapsack problem..
you can maybe find some algorithms using google.
Usually brute force or genetic algorithms.

#3Trenki  Members

Posted 02 November 2007 - 05:30 AM

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.

#4ID Merlin  Members

Posted 02 November 2007 - 01:41 PM

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?

#5TheSilverHammer  Members

Posted 04 November 2007 - 05:16 AM

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.

Posted 05 November 2007 - 02:14 AM

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.

#7ID Merlin  Members

Posted 16 November 2007 - 02:35 PM

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.

#8Rainweaver  Members

Posted 24 November 2007 - 09:35 PM

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!

#9ID Merlin  Members

Posted 25 November 2007 - 07:50 AM

Here's a link to the site with a javascript version: http://blog.netxus.es/blog/rectangle-packing-2d-packing

#10Rainweaver  Members

Posted 25 November 2007 - 11:27 PM

Thank you, that's very interesting.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.