Re: [Algorithms] Allocation of 2D space

[Kenneth R. <kbr...@al...>]

Mike Shaver wrote:
> On Tue, Aug 11, 2009 at 3:41 PM, Brian Meidell<br...@ga...> wrote:
>> I'm looking for an algorithm to allocate 2d rectangles of different
>> sizes from a larger 2d rectangle (small areas out of a large texture),
>> while wasting as little space as possible without being insanely slow.
> 
> Sounds like you want a texture atlas, so something like
> http://www.gamasutra.com/view/feature/2530/practical_texture_atlases.php
> might be a good start?

If you're looking for a run-time rather than ahead-of-time algorithm, 
there's some Java code you could use as a start at 
http://kenai.com/projects/jogl/ in the JOGL SCM, under 
src/jogl/classes/com/sun/opengl/util/packrect/ . It divides the larger 
2d rectangle into variable-size "levels" and allocates out of those 
levels, performing compaction as necessary. It's far from optimal but 
has been pretty well tested.

-Ken