Re: Allocation of 2D space

+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:[email protected]] 
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:[email protected]]
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:[email protected]]
> 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
> [email protected]
> 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
[email protected]
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
[email protected]
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list