gdalgorithms-list

[Algorithms] Allocation of 2D space

[Brian M. <br...@ga...>]

Hi,

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.

Search terms that yield google results are welcome answers (I tried,  
but I guess my google-fu proved too weak).

Regards,
Brian Meidell
The Game Equation

Re: [Algorithms] Allocation of 2D space

[Mike S. <mik...@gm...>]

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?

Mike

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

Re: [Algorithms] Allocation of 2D space

[Jon O. <ze...@gm...>]

Hi,

Think Tetris.

Find a spot in the texture which minimizes waste (unused holes) and the
horizon line.

Best,
Jon Olick

On Tue, Aug 11, 2009 at 2:41 PM, Brian Meidell <br...@ga...>wrote:

> Hi,
>
> 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.
>
> Search terms that yield google results are welcome answers (I tried,
> but I guess my google-fu proved too weak).
>
> Regards,
> Brian Meidell
> The Game Equation
>
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Allocation of 2D space

[Sebastian S. <seb...@gm...>]

On Tue, Aug 11, 2009 at 8:41 PM, Brian Meidell <br...@ga...>wrote:

> Hi,
>
> 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.
>
> Search terms that yield google results are welcome answers (I tried,
> but I guess my google-fu proved too weak).


"Rectangle packing" is probably a good search phrase.

One simple, quick and reasonably good algorithm (that I can't find the paper
for right now), is to first align all the rectangles so their longest axis
is pointing along y, then sort them by this height. Then you simply start
putting down rectangles left to right until you reach the right edge (you
have to guess how wide this is - if you're trying to optimize for
"squareness" a binary search can help), and then you go right-to-left
underneath that until you're back at the first edge. Then move this last row
of rectangles up so that it's as close to the first row as possible. Repeat
until you've run out of rectangles.

Hardly optimal, but at least it's simple!



>

-- 
Sebastian Sylvan

Re: [Algorithms] Allocation of 2D space

[James R. <ja...@fu...>]

That's very similar to how I pack font glyphs offline.  Although I don't 
rotate low, wide glyphs to the vertical.

Sort by height and then width and then place in rows across the 
texture.  One thing I do which doesn't make it very suitable for real 
time applications is to scan from the top left of the texture each time 
searching for a space to fit the next glyph.  That way I am usually able 
to fit smaller glyphs in the gaps left between the larger ones and down 
the right side of the texture.

And in my experience it actually turns out to be a reasonably optimal 
algorithm for similarly-sized, not-too-large rectangles.


Sebastian Sylvan wrote:
>
>
> On Tue, Aug 11, 2009 at 8:41 PM, Brian Meidell <br...@ga... 
> <mailto:br...@ga...>> wrote:
>
>     Hi,
>
>     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.
>
>     Search terms that yield google results are welcome answers (I tried,
>     but I guess my google-fu proved too weak).
>
>
> "Rectangle packing" is probably a good search phrase.
>
> One simple, quick and reasonably good algorithm (that I can't find the 
> paper for right now), is to first align all the rectangles so their 
> longest axis is pointing along y, then sort them by this height. Then 
> you simply start putting down rectangles left to right until you reach 
> the right edge (you have to guess how wide this is - if you're trying 
> to optimize for "squareness" a binary search can help), and then you 
> go right-to-left underneath that until you're back at the first edge. 
> Then move this last row of rectangles up so that it's as close to the 
> first row as possible. Repeat until you've run out of rectangles.
>
> Hardly optimal, but at least it's simple!
>
>  
>
>      
>
> -- 
> Sebastian Sylvan
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[<Bra...@pl...>]

Brian Meidell <br...@ga...> wrote on 08/11/2009 12:41:42 PM:

> Hi,
> 
> 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.
> 

Try this: http://www.blackpawn.com/texts/lightmaps/default.html

Brad...

Re: [Algorithms] Allocation of 2D space

[Ivan-Assen I. <iva...@gm...>]

> Try this: http://www.blackpawn.com/texts/lightmaps/default.html

+1

We use this to build a UI cache texture at runtime; packs reasonably
well and is very fast.

Re: [Algorithms] Allocation of 2D space

[Jim S. <Ji...@ar...>]

I can also vouch for this guy.  :)  Since using it for lightmaps there
I've also used it for more general texture atlases and for runtime font
glyph packing in Guild Wars.  It's definitely fast enough for runtime
use.

-----Original Message-----
From: Ivan-Assen Ivanov [mailto:iva...@gm...] 
Sent: Tuesday, August 11, 2009 3:01 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Allocation of 2D space

> Try this: http://www.blackpawn.com/texts/lightmaps/default.html

+1

We use this to build a UI cache texture at runtime; packs reasonably
well and is very fast.

Re: [Algorithms] Allocation of 2D space

[Nicholas F. <Nic...@un...>]

I'm looking at a related problem I've been banging my head against for  
a while, so seeing this, I figured I'd see if anyone here has some  
pointers.

I need a function to partition out a bunch of rects inside a fixed- 
size texture.It's basically for doing some deferred particle effects /  
billboards.

Now the thing is: The source areas can be too large to fit inside my  
fixed-size buffer. I'd like to have an upper bound on the total size  
usage - so if we have a lot of particle effects, I'd like them to  
share the preallocated buffer - so we lose some res in the offscreen  
stuff making the final rendering more blurry. Ideally, I'd like to  
have a notion of importance so I can lose more texture resolution for  
e.g. a faraway cloud, while only losing a bit for a nearby explosion.

This need to be evaluated on a per-frame basis as well, just to make  
the problem a bit more annoying. However, there won't be hundreds of  
these going on at the same time.

Any ideas?

Nicholas

On 13/08/2009, at 23.24, Jim Scott wrote:

> I can also vouch for this guy.  :)  Since using it for lightmaps there
> I've also used it for more general texture atlases and for runtime  
> font
> glyph packing in Guild Wars.  It's definitely fast enough for runtime
> use.
>
> -----Original Message-----
> From: Ivan-Assen Ivanov [mailto:iva...@gm...]
> Sent: Tuesday, August 11, 2009 3:01 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Allocation of 2D space
>
>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>
> +1
>
> We use this to build a UI cache texture at runtime; packs reasonably
> well and is very fast.
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> 30-Day
> trial. Simplify your report design, integration and deployment - and  
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[Brian M. <br...@ga...>]

I ended up using this algorithm, and I'm quite happy with it.

Thanks again for the suggestions!

/Brian

On 2009-08-13, at 23.24, Jim Scott wrote:

> I can also vouch for this guy.  :)  Since using it for lightmaps there
> I've also used it for more general texture atlases and for runtime  
> font
> glyph packing in Guild Wars.  It's definitely fast enough for runtime
> use.
>
> -----Original Message-----
> From: Ivan-Assen Ivanov [mailto:iva...@gm...]
> Sent: Tuesday, August 11, 2009 3:01 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Allocation of 2D space
>
>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>
> +1
>
> We use this to build a UI cache texture at runtime; packs reasonably
> well and is very fast.
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> 30-Day
> trial. Simplify your report design, integration and deployment - and  
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[Jon W. <jw...@gm...>]

Bra...@pl... wrote:
> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>   


I implemented pretty much the same thing for real-time packing of 
dynamic light maps for an XNA/Xbox program, and it did work very well. 
Leakage/loss was generally less than for a typical power-of-two 
quad-tree based allocator.

Sincerely,

jw



-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Allocation of 2D space

[Brian M. <br...@ga...>]

Thanks to everyone for the answers, I'll read up on the suggestions and 
make a choice.

Regards,
Brian Meidell

Jon Watte wrote:
> Bra...@pl... wrote:
>   
>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>>   
>>     
>
>
> I implemented pretty much the same thing for real-time packing of 
> dynamic light maps for an XNA/Xbox program, and it did work very well. 
> Leakage/loss was generally less than for a typical power-of-two 
> quad-tree based allocator.
>
> Sincerely,
>
> jw
>
>
>
>   

Re: [Algorithms] Allocation of 2D space

[David B. <dbe...@na...>]

One aspect of this algorithm that I'm curious about is:

Does the input texture need to be square?

If it turns out that you can pack all the rectangles into a k*(k/2) sized texture rather than a k*k texture (where k is a power-of-2) that would be a significant savings.

Thanks,

David Bennett
NAMCO BANDAI Games America Inc.

-----Original Message-----
From: Brian Meidell [mailto:br...@ga...]
Sent: Friday, August 14, 2009 11:21 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Allocation of 2D space


I ended up using this algorithm, and I'm quite happy with it.

Thanks again for the suggestions!

/Brian

On 2009-08-13, at 23.24, Jim Scott wrote:

> I can also vouch for this guy.  :)  Since using it for lightmaps there
> I've also used it for more general texture atlases and for runtime
> font
> glyph packing in Guild Wars.  It's definitely fast enough for runtime
> use.
>
> -----Original Message-----
> From: Ivan-Assen Ivanov [mailto:iva...@gm...]
> Sent: Tuesday, August 11, 2009 3:01 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Allocation of 2D space
>
>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>
> +1
>
> We use this to build a UI cache texture at runtime; packs reasonably
> well and is very fast.
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> 30-Day
> trial. Simplify your report design, integration and deployment - and
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list


------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[Brian M. <br...@ga...>]

I've been using it like that, and it works just fine.

On 2009-08-14, at 20.51, David Bennett wrote:

> One aspect of this algorithm that I'm curious about is:
>
> Does the input texture need to be square?
>
> If it turns out that you can pack all the rectangles into a k*(k/2)  
> sized texture rather than a k*k texture (where k is a power-of-2)  
> that would be a significant savings.
>
> Thanks,
>
> David Bennett
> NAMCO BANDAI Games America Inc.
>
> -----Original Message-----
> From: Brian Meidell [mailto:br...@ga...]
> Sent: Friday, August 14, 2009 11:21 AM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Allocation of 2D space
>
>
> I ended up using this algorithm, and I'm quite happy with it.
>
> Thanks again for the suggestions!
>
> /Brian
>
> On 2009-08-13, at 23.24, Jim Scott wrote:
>
>> I can also vouch for this guy.  :)  Since using it for lightmaps  
>> there
>> I've also used it for more general texture atlases and for runtime
>> font
>> glyph packing in Guild Wars.  It's definitely fast enough for runtime
>> use.
>>
>> -----Original Message-----
>> From: Ivan-Assen Ivanov [mailto:iva...@gm...]
>> Sent: Tuesday, August 11, 2009 3:01 PM
>> To: Game Development Algorithms
>> Subject: Re: [Algorithms] Allocation of 2D space
>>
>>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>>
>> +1
>>
>> We use this to build a UI cache texture at runtime; packs reasonably
>> well and is very fast.
>>
>> ------------------------------------------------------------------------------
>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
>> 30-Day
>> trial. Simplify your report design, integration and deployment - and
>> focus on
>> what you do best, core application coding. Discover what's new with
>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> 30-Day
> trial. Simplify your report design, integration and deployment - and  
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008  
> 30-Day
> trial. Simplify your report design, integration and deployment - and  
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[Steve L. <sm...@go...>]

+1 for this algorithm.  I've used it for quick and dirty lightmap packing
(for first pass - after rendering I use D3DX to create high quality texture
atlas).  You can make this algorithm run extremely fast since you can remove
all of the recursion and it just becomes:

class cLightmapPage
{
	std::list<Rect> m_FreeList;

public:
	cLightmapPage(const int w, const int h)
	{
		m_FreeList.push_back(Rect(0,0,w,h));
	}

	bool InsertRect(Rect *r)
	{
		for (std::list<Rect>::iterator rect_it=m_FreeList.begin();
rect_it!=m_FreeList.end(); ++rect_it)
		{
			if ((rect_it->w>=r->w) && (rect_it->h>=r->h))
			{
				while (1)
				{
					if ((rect_it->w==r->w) &&
(rect_it->h==r->h))
					{
						break;
					}

					int dw=rect_it->w-r->w,
						dh=rect_it->h-r->h;

					if (dw>dh)
					{
	
m_FreeList.push_back(Rect(rect_it->x+r->w,rect_it->y,dw,rect_it->h));
						rect_it->w=r->w;
					} else
					{
	
m_FreeList.push_back(Rect(rect_it->x,rect_it->y+r->h,rect_it->w,dh));
						rect_it->h=r->h;
					}
				}

				r->x=rect_it->x;
				r->y=rect_it->y;
				m_FreeList.erase(rect_it);
				return true;
			}
		}
		return false;
	}

	unsigned int GetFreePixels() const
	{
		unsigned int ret=0;
		for (std::list<Rect>::const_iterator
rect_it=m_FreeList.begin(); rect_it!=m_FreeList.end(); ++rect_it)
		{
			ret+=(rect_it->w*rect_it->h);
		}
		return ret;
	}
};

The while(1) loop runs at most 3 times iirc.  This is obviously not the
fastest implementation because you could probably make the outer search
quicker by sorting the rectangles somehow (or maybe by bucketing).

-----Original Message-----
From: David Bennett [mailto:dbe...@na...] 
Sent: Friday, August 14, 2009 7:51 PM
To: 'Game Development Algorithms'
Subject: Re: [Algorithms] Allocation of 2D space

One aspect of this algorithm that I'm curious about is:

Does the input texture need to be square?

If it turns out that you can pack all the rectangles into a k*(k/2) sized
texture rather than a k*k texture (where k is a power-of-2) that would be a
significant savings.

Thanks,

David Bennett
NAMCO BANDAI Games America Inc.

-----Original Message-----
From: Brian Meidell [mailto:br...@ga...]
Sent: Friday, August 14, 2009 11:21 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] Allocation of 2D space


I ended up using this algorithm, and I'm quite happy with it.

Thanks again for the suggestions!

/Brian

On 2009-08-13, at 23.24, Jim Scott wrote:

> I can also vouch for this guy.  :)  Since using it for lightmaps there
> I've also used it for more general texture atlases and for runtime
> font
> glyph packing in Guild Wars.  It's definitely fast enough for runtime
> use.
>
> -----Original Message-----
> From: Ivan-Assen Ivanov [mailto:iva...@gm...]
> Sent: Tuesday, August 11, 2009 3:01 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Allocation of 2D space
>
>> Try this: http://www.blackpawn.com/texts/lightmaps/default.html
>
> +1
>
> We use this to build a UI cache texture at runtime; packs reasonably
> well and is very fast.
>
>
----------------------------------------------------------------------------
--
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> 30-Day
> trial. Simplify your report design, integration and deployment - and
> focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list


----------------------------------------------------------------------------
--
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus
on
what you do best, core application coding. Discover what's new with
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list


----------------------------------------------------------------------------
--
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
trial. Simplify your report design, integration and deployment - and focus
on 
what you do best, core application coding. Discover what's new with 
Crystal Reports now.  http://p.sf.net/sfu/bobj-july
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Allocation of 2D space

[Ivan-Assen I. <iva...@gm...>]

> Does the input texture need to be square?

No, we pack rectangles into a rectangular texture.