Another side project that I've been meaning to write for years. Given a set of rectangles what is the minimum area rectangle they can be packed into?

It's a marginally useful question for packing 2D images. Marginal because todays graphics hardware has enough memory that's it's not necessary; but stuffing everything in one texture does reduce state changes.

The screen shot below shows each of the Star Control ships (and some Star Control 2 ships) rendered out with 72 frames of rotation at a resolution of 512 by 512 and then packed into a single 17375 by 5929 texture.

Transparent borders are clipped which produces a huge saving as small images - the nuclear missile, Ur Quan figter etc... - are packed very tightly. You can see them squashed into all the empty nooks and crannies around the larger ships. Note the screen is zoomed to 50% in the screenshot.

Clipping transparent borders has reduced the total area from 1.7 terrapixels to 412 megapixels. Almost an 80% saving.

ps: For those who can't post on account of blogger giving an error about post time: Illegal post time (format is: hh:mm AM/PM). Change your language from English (South Africa) to English (United Kingdom). It's under settings.