Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (475)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (530)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Texture packer  (Read 5331 times)
0 Members and 1 Guest are viewing this topic.
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Posted 2007-12-15 17: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

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #1 - Posted 2007-12-15 17: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 Coder


Medals: 11


falling into the abyss of reality


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

Cheers for that, it might come in handy (i'll see if it out performs my naive implementation)

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #3 - Posted 2007-12-17 13: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 Coder


Medals: 11


falling into the abyss of reality


« Reply #4 - Posted 2007-12-19 23: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.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #5 - Posted 2007-12-19 23: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 Coder


Medals: 11


falling into the abyss of reality


« Reply #6 - Posted 2007-12-20 01:08:11 »

I'm not using it in a situation where power-of-2 textures are a consideration Wink

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #7 - Posted 2007-12-20 01:51:06 »

Ah well, good luck with that.
Offline krasse
« Reply #8 - Posted 2010-03-01 14:31:22 »

Thanks for sharing this! It deserves to be bumped Smiley

Offline Nate

JGO Kernel


Medals: 145
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #9 - Posted 2010-03-01 20: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]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

ctomni231 (37 views)
2014-07-18 06:55:21

Zero Volt (35 views)
2014-07-17 23:47:54

danieldean (28 views)
2014-07-17 23:41:23

MustardPeter (31 views)
2014-07-16 23:30:00

Cero (46 views)
2014-07-16 00:42:17

Riven (47 views)
2014-07-14 18:02:53

OpenGLShaders (36 views)
2014-07-14 16:23:47

Riven (36 views)
2014-07-14 11:51:35

quew8 (32 views)
2014-07-13 13:57:52

SHC (69 views)
2014-07-12 17:50:04
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!