 |
XLE
v0.02.0
|
Sequentially pack rectangles within a fixed area More...
#include <RectanglePacking.h>
Public Types | |
| using | Rectangle = std::pair< UInt2, UInt2 > |
Public Member Functions | |
| Rectangle | Allocate (UInt2 dims) |
| UInt2 | TotalSize () const |
| std::pair< UInt2, UInt2 > | LargestFreeBlock () const |
| RectanglePacker (const UInt2 dimensions) | |
| RectanglePacker (RectanglePacker &&moveFrom) never_throws | |
| RectanglePacker & | operator= (RectanglePacker &&moveFrom) never_throws |
| RectanglePacker (const RectanglePacker &) | |
| RectanglePacker & | operator= (const RectanglePacker &) |
Sequentially pack rectangles within a fixed area
When building a texture atlas, we often want to find efficient algorithms for packing many differently sized textures within one larger texture.
We want to find the arrangement of rectangles that leaves the least unused space left over. We can also (perhaps) rotate the rectangle 90 degrees (if it produces a better packed result).
There are two variations to this: 1) when we know all of the rectangles to pack before hand 2) when we will be sequentially adding rectangles in an undeterminate manner
If we know all of the rectangles before hand, there are some very accurate approximations see: https://www.jair.org/media/3735/live-3735-6794-jair.pdf http://clb.demon.fi/files/RectangleBinPack.pdf However, many of these methods aren't perfectly suitable for the texture altas problem we'd like to solve.
However, we will use a simple & practical method. This method uses a binary tree so that when every rectangle is placed, we partition the remaining space into "right" and "down" space.
See http://codeincomplete.com/posts/2011/5/7/bin_packing/ for a good description of this method.
The results are reasonably good, but not perfect. When we know all rectangles before-hand, we want can get good packing by sorting them by max(width, height)
There are many other references available; eg: https://code.google.com/p/texture-atlas/source/browse/trunk/TexturePacker.cpp http://pollinimini.net/blog/rectangle-packing-2d-packing/ http://www.blackpawn.com/texts/lightmaps/default.html http://codesuppository.blogspot.kr/2009/04/texture-packing-code-snippet-to-compute.html http://www.eng.biu.ac.il/~rawitzd/Papers/srp.pdf (scheduling WiMax packets)
1.8.10
