Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes
Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  Print  
  Texture packer  (Read 4181 times)
0 Members and 1 Guest are viewing this topic.
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb


« on: 2007-12-15 11:26:24 »

Want to pack loads of images into one large texture, without wading through loads of academic bin-packing papers?
So did I, so I implemented the algorithm from this page. It's not terribly clever, but it is quick and easy.

Just throw an item with width and height dimensions at it, and it's return a rectangle in which the item can reside. Later you can delete the item, and the space will be returned to usable, barring fragmentation.

The only import is java.util.List, and even that's only for visualisation in the test app. Find the code here.

Free to a good home etc...
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb


« Reply #1 on: 2007-12-15 11:48:44 »

I'd like to attach the test app, but the forum won't let me - says the upload folder is full Undecided

Anyhoo, this is what it looks like


From playing around with this, you get best performance by sorting the input items and inserting them in descending order of area.

If anyone's interested I can email you the jar if you PM me.
Offline Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality


« Reply #2 on: 2007-12-15 15:55:14 »

Cheers for that, it might come in handy (i'll see if it out performs my naive implementation)
Games published by our own members! Go get 'em!
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb


« Reply #3 on: 2007-12-17 07:02:01 »

Download the test app here.
You can click on the rectangles to remove them from the tree and exhibit the fragmentation behaviour.
Offline Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality


« Reply #4 on: 2007-12-19 17:02:04 »

ah, my problem is the other way around.

I have a known set of rectangles, and need to find the smallest texture size (within a given set of min/max dimensions) that will encompass them all.
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb


« Reply #5 on: 2007-12-19 17:50:37 »

The power-of-two dimension restriction on textures really cuts down the size of the search space, so it might be feasible to simply try progressively bigger textures until you find one that fits.

For instance, here's how I'm finding a minimal texture to pack a font into (the glyphs have been sorted for size previously)

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
   private Dimension calculateTextureSize()
   {
      // mean glyph size
     float mean = 0;
      for( Glyph g : glyphs )
      {
         mean += g.image.getWidth();
         mean += g.image.getHeight();
      }
      mean /= glyphs.size() * 2;

      // initial guess
     int dim = GLUtil.nextPowerOf2( ( int ) ( mean * Math.sqrt( glyphs.size() ) ) ) / 2;
      dim = Math.max( 2, dim );

      Dimension d = new Dimension( dim / 2, dim );
      boolean growWidth = true;

      boolean success = false;

      do
      {
         // alternate expanding horizontally and vertically
        if( growWidth )
         {
            d.setWidth( d.getWidth() * 2 );
         }
         else
         {
            d.setHeight( d.getHeight() * 2 );
         }
         growWidth = !growWidth;

         RectanglePacker<Glyph> packer = new RectanglePacker<Glyph>( d.getWidth(), d.getHeight() );
         Iterator<Glyph> iter = glyphs.iterator();
         boolean fit = true;
         while( fit && iter.hasNext() )
         {
            Glyph g = iter.next();

            fit &= packer.insert( g.image.getWidth(), g.image.getHeight(), g ) != null;
         }

         success = fit;
      }
      while( !success );

      return d;
   }


See this post for an example of the packed texture.
Offline Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality


« Reply #6 on: 2007-12-19 19:08:11 »

I'm not using it in a situation where power-of-2 textures are a consideration Wink
Offline ryanm
« League of Dukes »

JGO Strike Force
*****

Posts: 788
Medals: 4


Used to be bleb


« Reply #7 on: 2007-12-19 19:51:06 »

Ah well, good luck with that.
Offline krasse

Sr. Member
**

Posts: 287
Medals: 14



« Reply #8 on: 2010-03-01 08:31:22 »

Thanks for sharing this! It deserves to be bumped Smiley

Offline Nate

JGO Neuromancer
****

Posts: 1063
Medals: 30


mooooo


« Reply #9 on: 2010-03-01 14:03:26 »

Too bad I didn't find bleb's post before I set out! Smiley Here is another implementation of the same algorithm:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-desktop/tools/com/esotericsoftware/skorpios/tools/ImagePacker.java
This one tries increasingly larger POT textures.

I have a bastardized version that aims to find the smallest texture that all the images fit on. Bin packing is an NP-hard problem so you can't brute force for the best solution. My algorithm tries the images sorted a few different ways before giving up on a size. It also grows only in the X direction for a while, then goes back, increases the Y by one, grows the Y for a while, goes back, increases X by one, grows X for a while, etc.

Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.481 seconds with 20 queries.