LÖVE

Posted: **Wed Feb 28, 2018 3:52 pm**

Hi,

I couldn't find a pure Lua bin packing library, so here's Mike Popoloski's MIT-licensed BinPacker.cs from SharpFont ported to Lua.

What's a bin packer?

This is an implementation of one algorithm (MAXRECTS) used to solve rectangle bin packing in 2D.

Think of automatically creating an e.g. 2048x2048 spritesheet. If you know all the tiles you need to put in it are 16x16, maybe that's not a very hard problem to solve.

But what if your tiles aren't all the same size? What if they might not even all fit in one spritesheet (bin)?

You need a 2D bin packer, my friend.

Bin packing is an NP-complete problem. That is, mathematically, there is no efficient way to get a perfect solution. Instead you have to rely on algorithms that seem to do a decent job fast.

How2use

Code: Select all

local binpack_new = require('binpack')
local bp = binpack_new(2048, 2048)

local rect1 = bp:insert(32, 64)
--  (rect1 has .x, .y, .w, .h, :clone(), :contains(rect), .right, .bottom)
print('rect1:', rect1) -- rect1: {x=0,y=0,w=32,h=64}

local rect2 = bp:insert(100, 101)
print('rect2:', rect2) -- rect2: {x=0,y=64,w=100,h=101}

print('\n20 250x200 rects: '); for i = 1,20 do print(bp:insert(250, 200)) end

print('\nClearing; changing binpack instance to 1024x1024')
bp:clear(1024, 1024)  -- you MUST provide w,h again
print('10 370x430 rects in 1024x1024:'); for i = 1,10 do print(bp:insert(370, 430)) end

-- you can call binpack_new(w, h) again if you want 2 binpackers simultaneously. it's not an issue.

Example output

Code: Select all

pink:utils leaf$ lua
Lua 5.3.4  Copyright (C) 1994-2017 Lua.org, PUC-Rio
> dofile('./binpack_example.lua')
rect1:	{x=0,y=0,w=32,h=64}
rect2:	{x=0,y=64,w=100,h=101}

20 250x200 rects: 
{x=0,y=165,w=250,h=200}
{x=0,y=365,w=250,h=200}
{x=0,y=565,w=250,h=200}
{x=0,y=765,w=250,h=200}
{x=0,y=965,w=250,h=200}
{x=0,y=1165,w=250,h=200}
{x=0,y=1365,w=250,h=200}
{x=0,y=1565,w=250,h=200}
{x=0,y=1765,w=250,h=200}
{x=250,y=0,w=250,h=200}
{x=500,y=0,w=250,h=200}
{x=750,y=0,w=250,h=200}
{x=1000,y=0,w=250,h=200}
{x=1250,y=0,w=250,h=200}
{x=1500,y=0,w=250,h=200}
{x=1750,y=0,w=250,h=200}
{x=250,y=200,w=250,h=200}
{x=500,y=200,w=250,h=200}
{x=750,y=200,w=250,h=200}
{x=1000,y=200,w=250,h=200}

Clearing; changing binpack instance to 1024x1024
10 370x430 rects in 1024x1024:
{x=0,y=0,w=370,h=430}
{x=0,y=430,w=370,h=430}
{x=370,y=0,w=370,h=430}
{x=370,y=430,w=370,h=430}
nil
nil
nil
nil
nil
nil
> ^D

pink:utils leaf$ luajit
LuaJIT 2.1.0-beta3 -- Copyright (C) 2005-2017 Mike Pall. http://luajit.org/
JIT: ON SSE2 SSE3 SSE4.1 BMI2 fold cse dce fwd dse narrow loop abc sink fuse
> dofile('./binpack_example.lua')
rect1:	{x=0,y=0,w=32,h=64}
rect2:	{x=0,y=64,w=100,h=101}

20 250x200 rects: 
{x=0,y=165,w=250,h=200}
{x=0,y=365,w=250,h=200}
{x=0,y=565,w=250,h=200}
{x=0,y=765,w=250,h=200}
{x=0,y=965,w=250,h=200}
{x=0,y=1165,w=250,h=200}
{x=0,y=1365,w=250,h=200}
{x=0,y=1565,w=250,h=200}
{x=0,y=1765,w=250,h=200}
{x=250,y=0,w=250,h=200}
{x=500,y=0,w=250,h=200}
{x=750,y=0,w=250,h=200}
{x=1000,y=0,w=250,h=200}
{x=1250,y=0,w=250,h=200}
{x=1500,y=0,w=250,h=200}
{x=1750,y=0,w=250,h=200}
{x=250,y=200,w=250,h=200}
{x=500,y=200,w=250,h=200}
{x=750,y=200,w=250,h=200}
{x=1000,y=200,w=250,h=200}

Clearing; changing binpack instance to 1024x1024
10 370x430 rects in 1024x1024:
{x=0,y=0,w=370,h=430}
{x=0,y=430,w=370,h=430}
{x=370,y=0,w=370,h=430}
{x=370,y=430,w=370,h=430}
nil
nil
nil
nil
nil
nil
> ^D

The codez

binpack.lua: https://gist.github.com/leafi/c39489b97 ... b3c476df40

binpack.lua: (7.81 KiB) Downloaded 147 times

It's pretty easy to use. Read the big ol' comment block at the start of binpack.lua; it has a usage example of the three main functions & details of what they return.

binpack.lua contains its own implementation of a 2D rectangle. Swap it out if you want, or just get the data you want from the .x, .y, .w, .h fields of the returned table from binpack_instance:insert(w,h).

When the bin is full, bin:insert(w, h) returns nil instead of a rectangle.

Limitations

Some bin packing algorithms support rotating the rectangles to make them fit better. This doesn't.
It doesn't support dynamically growing the 'spritesheet' either. You state the lengths up-front.

Don't pass in negative or 0 for any widths or heights. It doesn't make sense and something bad will happen.
If you pass in floating point numbers, they will be coerced into integers. You can change this if you really want.

If your Lua environment is Lua 5.3, you should be able to use up to 64-bit integers for widths and heights (but why??). If not (e.g. LuaJIT in LOVE), avoid going above about 52-bit integers (< QUITE BIG NUMBER). IIRC that's the max you can have an integer before the 64-bit floating point numbers Lua uses cannot guarantee precise representation.

License

Just like the file says, this is MIT licensed. It was based on Mike Popoloski's MIT-licensed https://github.com/MikePopoloski/SharpF ... nPacker.cs, and uses the MAXRECTS algorithm developed by Jukka Jylänki http://clb.demon.fi/files/RectangleBinPack.pdf.

Now what?

Any questions/mistakes here, please tell me. I'm going to be using this myself so it'd be nice if it was actually right.

Posted: **Wed Feb 28, 2018 9:53 pm**

leafi wrote: ↑Wed Feb 28, 2018 3:52 pm I couldn't find a pure Lua bin packing library

I needed one a while ago, and I ended up implementing a BSP packer that can also grow if required. I use it to pack font glyphs into texture atlasses. I'm not really satisfied with the result, maybe I give this one a try. Although the limitation to a fixed output size is a huge downside for me.

avoid going above about 28-bit integers (< 268435456). IIRC that's the max you can have an integer before the 64-bit floating point numbers Lua uses cannot guarantee precise representation.

Not quite - integer representations are accurate up to 2^53.

Posted: **Wed Feb 28, 2018 10:58 pm**

There are at least three libraries for creating an image atlas in the forums. All three depend on Löve, though, so it's nice to have one that doesn't.

Why does it output as you insert? I expected it to wait until all rectangles were inserted.

Posted: **Wed Feb 28, 2018 11:12 pm**

pgimeno wrote: ↑Wed Feb 28, 2018 10:58 pm There are at least three libraries for Löve in the forums. All three depend on Löve, though, so it's nice to have one that doesn't.

Why does it output as you insert? I expected it to wait until all rectangles were inserted.

Oh... lmao. I didn't think of googling "texture packer", even though that's the most obvious application of a bin packer...

This rect packer expects rectangles to be added gradually - indeed, it was meant for a font texture sheet, glyphs being added to the texture as they are used in text for the first time.

I guess the advantage of having all the rectangles up front is you might be able to sort them, but I don't know if that even improves the layout done by this algorithm.

grump wrote: ↑Wed Feb 28, 2018 9:53 pm
leafi wrote: ↑Wed Feb 28, 2018 3:52 pm I couldn't find a pure Lua bin packing library
I needed one a while ago, and I ended up implementing a BSP packer that can also grow if required. I use it to pack font glyphs into texture atlasses. I'm not really satisfied with the result, maybe I give this one a try. Although the limitation to a fixed output size is a huge downside for me.

avoid going above about 28-bit integers (< 268435456). IIRC that's the max you can have an integer before the 64-bit floating point numbers Lua uses cannot guarantee precise representation.
Not quite - integer representations are accurate up to 2^53.

Thanks for the correction - I'll fix to say 52 / 53.

W.r.t. dynamically expanding... I know stb_rect_pack does dynamic growth, and there's a Java port somewhere which should be easier to port than the C. (Skyline Bottom-Left algorithm IIRC). Other than that, it would be easy to change this code to double one/both of the lengths of the "spritesheet" when the spritesheet becomes full, and add the new 1 or 3 rectangles to self.freelist... that would be an OK result if you really like power of two textures and each rectangle you add will definitely always fit within the smallest spritesheet size you started with.

(e.g. 512x512 spritesheet full, double lengths to 1024x1024, add to self.freelist { {x=512,y=0,w=512,h=512}, {x=0,y=512,w=512,h=512}, {x=512,y=512,w=512,h=512} } and run insert() again... where thing being inserted is always much less in size than 512x512)

LÖVE

Rectangle packer a.k.a. 2D bin packing library

Rectangle packer a.k.a. 2D bin packing library

Re: Rectangle packer a.k.a. 2D bin packing library

Re: Rectangle packer a.k.a. 2D bin packing library

Re: Rectangle packer a.k.a. 2D bin packing library