Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
9 replies to this topic

#1 TheSilverHammer   Members   -  Reputation: 122

Like
0Likes
Like

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.

Sponsor:

#2 VincentGreen   Members   -  Reputation: 122

Like
0Likes
Like

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.

#3 Trenki   Members   -  Reputation: 341

Like
0Likes
Like

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.

#4 ID Merlin   Members   -  Reputation: 115

Like
0Likes
Like

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?

#5 TheSilverHammer   Members   -  Reputation: 122

Like
0Likes
Like

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.

#6 Adam_42   Crossbones+   -  Reputation: 2618

Like
0Likes
Like

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.

#7 ID Merlin   Members   -  Reputation: 115

Like
0Likes
Like

Posted 16 November 2007 - 02:35 PM

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.

#8 Rainweaver   Members   -  Reputation: 220

Like
0Likes
Like

Posted 24 November 2007 - 09:35 PM

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!

#9 ID Merlin   Members   -  Reputation: 115

Like
0Likes
Like

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

#10 Rainweaver   Members   -  Reputation: 220

Like
0Likes
Like

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.



PARTNERS