The Skyline algorithm for packing 2D rectangles

submited by
Style Pass
2024-11-18 15:30:04

Packing 2D rectangles into bigger fixed-size rectangles is a need for most multimedia projects. In GPU programming, changing textures ("binding") is expensive. Thus, when rendering text, you don't want to have one texture per glyph. Instead, it is desirable to pack the glyphs in a single texture, called the "atlas". In 2D-based games, atlas containing sprites are called spritesheets. Spritesheets are also used for websites, because a single, bigger file download is better than one file per icon / logo.

Initially, I thought this was quite a specific problem, but it happens to have industrial impacts too. How many ads can I fit on this newspaper page? How many shapes can I cut in this piece of wood? How many packages can I fit in the back of a delivery van? Thus, the 2D packing problem has been studied academically too.

The most valuable source I have found is this excellent survey from Jukka Jylänki. It presents 4 kinds of algorithms, and evaluates them in practice. Two of them stands out:

Leave a Comment