gdalgorithms-list

[Algorithms] Compose rectangles within another rectangle

[Arno G. <ar...@ag...>]

Hi,

I am looking for an algorithm that can help me to compose a number of 
rectangles, with different sizes, within a bigger rectangle. So I want 
to pack them most efficiently within the bigger rectangle. Does anybody 
know the best approach to this, except for just trial and error.

The background is that I want to compose a big texture sheet from a 
collection of smaller texture pieces automaticaly.

-- 
Arno

Re: [Algorithms] Compose rectangles within another rectangle

[Eric C. <er....@gm...>]

On Fri, Jan 22, 2010 at 2:18 PM, Arno Gerretsen <ar...@ag...> wrote:

> I am looking for an algorithm that can help me to compose a number of
> rectangles, with different sizes, within a bigger rectangle. So I want
> to pack them most efficiently within the bigger rectangle. Does anybody
> know the best approach to this, except for just trial and error.
>

This might be useful...

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

Re: [Algorithms] Compose rectangles within another rectangle

[Jason H. <jh...@st...>]

This is called bin packing.  You'll find much research on it, and even 
this very question has been answered a few times in the archives of this 
list.  To save you a few seconds, some folks suggest an approach similar 
to Tetris.  Personally, I sort rectangles by the longest axis and pack 
from longer to shorter, minimizing the distance to the origin of the 
texture sheet when placing them.  That tends to work pretty well.  If 
you can do it offline, slowly shuffling the order you submit the 
rectangles a little bit can get you some good gains over the simple 
sorting method, but it all depends on how much effort you want to put 
into it.

Best of luck,
JH

Jason Hughes
President
Steel Penny Games, Inc.
Austin, TX



Arno Gerretsen wrote:
> Hi,
>
> I am looking for an algorithm that can help me to compose a number of 
> rectangles, with different sizes, within a bigger rectangle. So I want 
> to pack them most efficiently within the bigger rectangle. Does anybody 
> know the best approach to this, except for just trial and error.
>
> The background is that I want to compose a big texture sheet from a 
> collection of smaller texture pieces automaticaly.
>
>   

Re: [Algorithms] Compose rectangles within another rectangle

[Arno G. <ar...@ag...>]

Thank you both for the reply. Knowing the exact scientific name makes it 
a lot easier to find more information on this. So thanks for putting me 
in the right direction. I am sure I will be able to find a way that I 
can implement on my tool.

Arno


On 22/01/2010 22:39, Jason Hughes wrote:
> This is called bin packing.  You'll find much research on it, and even
> this very question has been answered a few times in the archives of this
> list.  To save you a few seconds, some folks suggest an approach similar
> to Tetris.  Personally, I sort rectangles by the longest axis and pack
> from longer to shorter, minimizing the distance to the origin of the
> texture sheet when placing them.  That tends to work pretty well.  If
> you can do it offline, slowly shuffling the order you submit the
> rectangles a little bit can get you some good gains over the simple
> sorting method, but it all depends on how much effort you want to put
> into it.
>
> Best of luck,
> JH
>
> Jason Hughes
> President
> Steel Penny Games, Inc.
> Austin, TX
>
>
>
> Arno Gerretsen wrote:
>    
>> Hi,
>>
>> I am looking for an algorithm that can help me to compose a number of
>> rectangles, with different sizes, within a bigger rectangle. So I want
>> to pack them most efficiently within the bigger rectangle. Does anybody
>> know the best approach to this, except for just trial and error.
>>
>> The background is that I want to compose a big texture sheet from a
>> collection of smaller texture pieces automaticaly.
>>
>>
>>      
> ------------------------------------------------------------------------------
> Throughout its 18-year history, RSA Conference consistently attracts the
> world's best and brightest in the field, creating opportunities for Conference
> attendees to learn about information security's most important issues through
> interactions with peers, luminaries and emerging and established companies.
> http://p.sf.net/sfu/rsaconf-dev2dev
> _______________________________________________
> 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
>    


-- 
Arno

Re: [Algorithms] Compose rectangles within another rectangle

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

On Sat, Jan 23, 2010 at 2:46 AM, Arno Gerretsen <ar...@ag...> wrote:

> Thank you both for the reply. Knowing the exact scientific name makes it
> a lot easier to find more information on this. So thanks for putting me
> in the right direction. I am sure I will be able to find a way that I
> can implement on my tool.
>
> Arno
>
>
You might also want to search for references to the "knapsack problem,"
which is closely related. It is one of the canonical NP-complete problems,
meaning that there currently exists no know algorithm that will find the
optimal solution in polynomial time (like N^2 or N^3). Thus, most solutions
are approximations that give you "good enough" answers in relatively fast
time, or solutions that take a lot of time to try *all* (or a substantial
subset) of solutions, to get the optional solution.

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.

Re: [Algorithms] Compose rectangles within another rectangle

[Fabian G. <f.g...@49...>]

Arno Gerretsen schrieb:
> Hi,
> 
> I am looking for an algorithm that can help me to compose a number of 
> rectangles, with different sizes, within a bigger rectangle. So I want 
> to pack them most efficiently within the bigger rectangle. Does anybody 
> know the best approach to this, except for just trial and error.
> 
> The background is that I want to compose a big texture sheet from a 
> collection of smaller texture pieces automaticaly.

This might help you as well:

   http://www.flipcode.com/archives/Rectangle_Placement.shtml

-Fabian Giesen

Re: [Algorithms] Compose rectangles within another rectangle

[Jetro L. <jl...@gm...>]

In addition to the blackpawn & J.Arevalo references already mentioned,
John Ratcliff has also posted his take on texture atlas creation:
http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html

<http://codesuppository.blogspot.com/2009/04/texture-packing-code-snippet-to-compute.html>That
solution adds the twist that you can actually rotate rectangles so that all
rectangle
widths are always >= heights (just rotate uv coordinates as well).


If somebody does comparisons about how much that actually gives additional
help
for texture space usage, I'd be interested in hearing the results...


-- 
Jetro Lauha - http://jet.ro


On Fri, Jan 22, 2010 at 9:18 PM, Arno Gerretsen <ar...@ag...> wrote:

> Hi,
>
> I am looking for an algorithm that can help me to compose a number of
> rectangles, with different sizes, within a bigger rectangle. So I want
> to pack them most efficiently within the bigger rectangle. Does anybody
> know the best approach to this, except for just trial and error.
>
> The background is that I want to compose a big texture sheet from a
> collection of smaller texture pieces automaticaly.
>
> --
> Arno
>
>
>
> ------------------------------------------------------------------------------
> Throughout its 18-year history, RSA Conference consistently attracts the
> world's best and brightest in the field, creating opportunities for
> Conference
> attendees to learn about information security's most important issues
> through
> interactions with peers, luminaries and emerging and established companies.
> http://p.sf.net/sfu/rsaconf-dev2dev
> _______________________________________________
> 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
>