Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Bin packing, texture atlasing, glyph caching, how do you do it?


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
5 replies to this topic

#1 clb   Members   -  Reputation: 1785

Like
3Likes
Like

Posted 19 April 2010 - 12:29 PM

Hello,

the topic of bin packing comes up quite often at GameDev that we have a thread roughly every month or two about it. Rectangular bin packing comes up in contexts of light mapping, texture atlasing, font glyph caching, sprite packing and RPG-like tetris inventory organization. Most of the veterans here are surely familiar with this topic.

Last August I was in turn to approach this problem, and around the same time, I had to write a smallish academic study about a topic of my choice. Now that the stuff is finally done, I thought I'd share the results here, as so many people work on these things. Hopefully someone can find this material useful.

The results of my study are available here: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing (pdf).

Along the way, I've written three blog posts to accompany the paper:
Rectangle Bin Packing:The recursive GUILLOTINE algorithm, a sample video.
More Rectangle Bin Packing:Videos and explanatory pictures about the SHELF, (iterative) GUILLOTINE, MAXRECTS and SKYLINE variants.
Even More Rectangle Bin Packing:Downloadable source code, links to resources.

Any feedback on the contents is greatly appreciated.

Here's a short catalog of some of the more informative threads that have come up here at GameDev:
6/15/2003, Algorithm to pack items into container: Algorithm discussion, Shelf method.
5/11/2006, Rectangle packing: jyk shares his code that implements the Guillotine method.
4/28/2007, Fitting small rectangles into a large rectangle: utilae shares his implementation of a bin packer. Some discussion about optimally solving bin packing.
11/2/2007, Need AI to fit rectangles in a larger square: Algorithm discussion.
2/5/2008, Automatic Texture Atlas Generation: Discussion on rectangle packing atlases.
11/22/2008, Packing rectangles into a rectangle: Q&A on rectangle packing and jyk's code.
12/23/2008, How to merge multi small pngs into a single one with smallest size?: Performance considerations.
5/24/2009, Allocating a texture large enough to hold all font glyphs: Font glyph caching.
8/17/2009, Lightmap generation with Radiosity: Bin packing in the context of lightmapping.
8/23/2009, Freetype: Font glyph caching. My initial results on bin packing.

The motivation of this post is not only to sum up a list of links from my behalf, but to ask all you guys, how do you do it?

Now, there's quite a lot of links in this post. No need to bother going through all of them before replying, as that could take quite a lot of time! Just if you have your material on bin packing, please share it here! Code, knowledge, or pretty pictures at least? :)
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

Sponsor:

#2 scgames   Members   -  Reputation: 1977

Like
0Likes
Like

Posted 19 April 2010 - 02:47 PM

The paper looks good, and quite comprehensive. Nice job! :)

#3 clb   Members   -  Reputation: 1785

Like
0Likes
Like

Posted 20 April 2010 - 09:52 AM

Thanks! Assembling the stuff together did take some time. Unfortunately I had to draw the line somewhere, and didn't include some of the more interesting ones of recently published methods (least wasted fit, caving degree, corner-occupying action). If someone's got extra free time on their hands, there's a good topic to go for. :P
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

#4 clb   Members   -  Reputation: 1785

Like
0Likes
Like

Posted 31 August 2011 - 12:49 PM

Sorry to bring up an old thread, but since my website went down, the links referred to above no longer work. Someone was looking for the code and PDF files, so I'm attaching them here instead:

Attached File  RectangleBinPack_backup.zip   266.22KB   149 downloads
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

#5 Cygon   Crossbones+   -  Reputation: 1124

Like
0Likes
Like

Posted 31 August 2011 - 02:19 PM

I have invented my own algorithm for rectangle packing (though I'm quite sure someone else came up with the idea before). I wanted for it to be fast during runtime so I could use it to cache font characters and other small bitmaps on the fly.

All it does is try to place any new rectangle as high in the bin as possible. To quickly locate the position that allows this, my algorithm tracks the silhouette of the upper end of the bin (as a sorted list of "runs" or "slices", telling where on the X axis the run begins and how high it is on the Y axis). When a rectangle is inserted, it will attempt to put the rectangle at the start of each run with its left edge and then with its right edge. The placement that allowed for the highest placement is selected and the list of runs will be updated accordingly.

The algorithm averages on O(1) because once a full row of rectangles has been built, the search time for new rectangles tends to stay constant. Worst case performance could be O(n) but is very unlikely.

It's Open Sourced, so here are the docs: Rectangle Packing and here's the source: CygonRectanglePacker.cs, CygonRectanglePacker.Test.cs (unit tests)
Professional C++ and .NET developer trying to break into indie game development.
Follow my progress: http://blog.nuclex-games.com/ or Twitter - Topics: Ogre3D, Blender, game architecture tips & code snippets.

#6 clb   Members   -  Reputation: 1785

Like
0Likes
Like

Posted 31 August 2011 - 03:35 PM

The algorithm you describe sounds like the SkyLine algorithm I studied for the review. (though, I did not maintain a sorted order if I remember correctly)
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!




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