Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (499)
Games in Android Showcase (118)
games submitted by our members
Games in WIP (567)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  Cramming the most into a Sprite Atlas - (Bin Packing Problem)  (Read 12031 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Posted 2009-12-08 18:28:31 »

Hey all -

I am trying to make a perfectly optimized Sprite atlas. That means, given any collection of small sprites, I want to find (very quickly) a good way to cram them all into a big image with minimal waste. This essentially the same problem as the 2D cutting stock problem, for which I found this paper: http://www.inf.uos.de/papers_html/or_94/cutpaper.html . However, I don't want to be able to rotate my sprites 90º, so this algorithm doesn't fit my desires exactly.

So, I was wondering 2 things:
1) Has anyone implemented this Java before? If so, would you be willing to share source so I can save myself time?
or
2) Does anyone have ideas on a good way to do this, given that rotations are not allowed? Genetic and other learning algorithms won't really do the trick because they take a long time to get up to speed. At most, I want a wait of about 10 seconds for a 1024x1024 Atlas.

See my work:
OTC Software
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-12-08 19:29:28 »

Forgive me for asking, but why don't you want to rotate your images 90 degrees?

In OpenGL you will have exactly the same performance.
In Java2D you can just 'extract' your atlas sprites once.


But heck, you might have a very good reason Smiley


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #2 - Posted 2009-12-08 19:46:57 »

Forgive me for asking, but why don't you want to rotate your images 90 degrees?

In OpenGL you will have exactly the same performance.
In Java2D you can just 'extract' your atlas sprites once.


But heck, you might have a very good reason Smiley



It's all about time. Smiley These are images that exist already in an engine that exists already in a project that is supposed to be done in 10 days. Although it's obviously easy to rotate in OpenGL and there's no performance hit, it means another couple of hours of adjusting the SpriteAtlas code to allow for rotated sprites. I'm just trying to avoid the extra work at this juncture. If that's not an option, then by all means I can go for it.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jono
« Reply #3 - Posted 2009-12-08 19:52:06 »

This sounds more like the bin packing problem (though that usually assumes you've been given a fixed bin/image size to work with). A quick search doesn't turn up any Java code, but here are some discussions on simple greedy approaches: http://www.gamedev.net/community/forums/topic.asp?topic_id=392413
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #4 - Posted 2009-12-08 19:54:01 »

I am trying to make a perfectly optimized Sprite atlas. That means, given any collection of small sprites, I want to find (very quickly) a good way to cram them all into a big image with minimal waste.

This is basically 2d bin packing which means it's np-hard so you're not going to find a 'perfect' solution other than the brute-force method of trying every possible combination and taking the best one.

I've got a 2d atlas within Rebirth, which is implemented like a container so you could use that if you wanted (check out the Atlas class ).

If you wanted to do it yourself then there's a few different approaches. The one I settled on is to use a 2d bsp to divide the space, if you combine this with inserting rectangles from largest to smallest you get very little wasted space (since the smaller rectangles tend to fill up the awkward holes left by the bigger sprites).

Example atlas:



[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline princec

JGO Kernel


Medals: 389
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2009-12-08 20:26:23 »

Ooh, is that algorithm loads better than the one in SPGL? I've been wondering about getting a better one.

Cas Smiley

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #6 - Posted 2009-12-08 20:35:40 »

This is basically 2d bin packing which means it's np-hard so you're not going to find a 'perfect' solution other than the brute-force method of trying every possible combination and taking the best one.

I've got a 2d atlas within Rebirth, which is implemented like a container so you could use that if you wanted (check out the Atlas class ).

If you wanted to do it yourself then there's a few different approaches. The one I settled on is to use a 2d bsp to divide the space, if you combine this with inserting rectangles from largest to smallest you get very little wasted space (since the smaller rectangles tend to fill up the awkward holes left by the bigger sprites).

Example atlas:



That looks great, although I couldn't find any source for Atlas to take a look at.

So basically all you do is start with the biggest sprite, make your way to the right with progressively smaller sprites, and simply stick each sprite wherever it will fit at first? And is "2D BSP" a 2D binary-space partitioning tree? I guess the tree is the best way to determine what space is open and what isn't.

See my work:
OTC Software
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #7 - Posted 2009-12-08 20:45:05 »

That looks great, although I couldn't find any source for Atlas to take a look at.

Rebirth is a binary-only library at the moment until I get some distribution and licensing gubbins sorted out. Something I've been meaning to do for a while...

Quote
So basically all you do is start with the biggest sprite, make your way to the right with progressively smaller sprites, and simply stick each sprite wherever it will fit at first?

It's not quite that simple - basically the tree is a bunch of nodes with a 'first' and 'second' child nodes, which split the parent rect into two (where splitting alternates between horizontal and vertical at each level). To insert you find the first leaf that it can fit within, then split that into two and mark one half as allocated.

Alternative heristics are sorting by largest-edge or sorting by width then height, but I found by area gave the best results for sprite-like rectangles.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #8 - Posted 2009-12-08 22:43:41 »

Rebirth is a binary-only library at the moment until I get some distribution and licensing gubbins sorted out. Something I've been meaning to do for a while...

It's not quite that simple - basically the tree is a bunch of nodes with a 'first' and 'second' child nodes, which split the parent rect into two (where splitting alternates between horizontal and vertical at each level). To insert you find the first leaf that it can fit within, then split that into two and mark one half as allocated.

Alternative heristics are sorting by largest-edge or sorting by width then height, but I found by area gave the best results for sprite-like rectangles.
Right. I'm trying a sort of quad-tree implementation, like this:

1) If the added rect has a bigger size than this one, return.
2) If this one already has something in it, return.
3) If this one has no children, ether add directly to this node if the size is an exact match, or split this into 4 nodes, using both the horizontal and the vertical to do so, then add to the top-left node (which will be an exact match in size).
4) If this one has children, try to recursively add to each one in turn.

This seems like it should work fairly well and was quick to implement, but I haven't tested it thoroughly yet. It will definitely appears like it will be less effective than alternating between vertical and horizontal, but good enough for my purposes. I'll try the other if this works shittily.

See my work:
OTC Software
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #9 - Posted 2009-12-08 22:51:04 »

From the sounds of it, I implemented the algorithm that Orangytang is talking about in this thread.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #10 - Posted 2009-12-09 04:32:19 »

Check out my image packer (originally inspired by the one in SPGL):
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-desktop/tools/com/esotericsoftware/skorpios/tools/ImagePacker.java
It strips transparent space off images and packs them using this algorithm:
http://www.blackpawn.com/texts/lightmaps/default.html
The resulting images and metadata file are loaded with this:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/opengl/PackedImages.java
It is super easy to make animations:
http://code.google.com/p/skorpios/source/browse/trunk/skorpios-common/src/com/esotericsoftware/skorpios/opengl/Animation.java
I can take the raw PNG sequence output from particleIllusion, run it through the image packer, and display the animation in my game with no other steps. Eg:
http://n4te.com/temp/explode1.png

The image packer is useful for anyone, the PackedImages and other classes are specific to the Skorpios Android/desktop OpenGL project, but are easily modified for use elsewhere. Eg, it was very easy to port the PackedImages class to the iPhone. It would be even easier to port to a different OpenGL binding in Java.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #11 - Posted 2009-12-09 14:58:09 »

Thanks so much for the source, bleb and Nate, and thanks for the help everyone. I finished my own implementation unfortunately before I saw your sources, but oh well, that's the breaks, right?

My next step is to take all the layers in a single PSD file and get the images out of those, then pack them. That would be useful and maybe fun. Smiley

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #12 - Posted 2009-12-09 19:36:13 »

FWIW, PS CS4 comes with an export layers script that can export to PNG. Not quite as cool though. Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 801
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2009-12-09 20:31:46 »

It's all about time. Smiley
...a project that is supposed to be done in 10 days.
...I'm just trying to avoid the extra work at this juncture.

My next step is to take all the layers in a single PSD file and get the images out of those, then pack them. That would be useful and maybe fun. Smiley

That would seem like the least efficient way to go here.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #14 - Posted 2009-12-09 23:25:42 »

That would seem like the least efficient way to go here.
Very true, but in what I'm doing the artists made the Atlases manually in a PSD. But I was more joking, I'm not about to do that unless I have free time (which I don't).

Here are my two implementations:

1) Uses the same method as Orangy Tang. Alternates between vertical and horizontal splitting. Does not allow 90 degree rotation.



2) Uses a slightly different method that splits a node into 4 pieces (both vertical and horizontal at the same time). Also does not allow 90 degree rotation.



The methods looks to be pretty comparable, surprisingly - it all really depends on the distribution of sprite sizes you've got.

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #15 - Posted 2009-12-10 00:19:58 »

Could you try running the same images through my ImagePacker?

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #16 - Posted 2009-12-10 01:10:05 »

Could you try running the same images through my ImagePacker?
Unfortunately, no. The distribution is totally random. Sad You'll notice it's slightly different in the two screenshots.

See my work:
OTC Software
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #17 - Posted 2009-12-10 10:08:15 »

Unfortunately, no. The distribution is totally random. Sad You'll notice it's slightly different in the two screenshots.
Use a Random object and hard-code the seed to get the same random sprites each time.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline princec

JGO Kernel


Medals: 389
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #18 - Posted 2009-12-10 10:52:01 »

It's worth noting that if you've got so many sprites you need multiple sprite sheets, that it's not necessarily the most efficient thing to do to find the best fit in any sheet for any one sprite. Often sprites are used in sequence or in clusters, and if you have each sprite in a sequence spread out over 16 4MB sprite sheets, you run the risk of texture thrashing on lower end cards. Just a thought.

Cas Smiley

Offline Markus_Persson

JGO Wizard


Medals: 15
Projects: 19


Mojang Specifications


« Reply #19 - Posted 2009-12-10 15:12:13 »

Sort sprites by texture?

Play Minecraft!
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #20 - Posted 2009-12-10 15:28:41 »

It's worth noting that if you've got so many sprites you need multiple sprite sheets, that it's not necessarily the most efficient thing to do to find the best fit in any sheet for any one sprite. Often sprites are used in sequence or in clusters, and if you have each sprite in a sequence spread out over 16 4MB sprite sheets, you run the risk of texture thrashing on lower end cards. Just a thought.

Cas Smiley
Yes indeed. This texture packing is for the iPhone, too, so it is doubly important for me to be efficient here. I am only packing like-images in each sprite sheet, and I have optimized the rendering pipeline so that pretty much everything will be drawn with just two or three texture binds.

Use a Random object and hard-code the seed to get the same random sprites each time.
I meant that I didn't save a seed of those specific objects in the screenshot above, so I can't get those objects back out no matter how hard I try. If I made a new one, then I could store the seed, but then I wouldn't be giving Nate the same images. Smiley

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #21 - Posted 2009-12-10 17:58:14 »

I was mostly just curious as to how well the algorithm I used packed something similar to your screenshots.

Most animations have transparency that can be stripped off to save space. This is nice to get more sprites per texture and especially important if you are using PVRTC on the iPhone.

Parsing my tools output on the iPhone goes like this:

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  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
@interface PackedImages : NSObject {
   NSMutableDictionary *_nameToImage;
}

- (id) init:(NSString*)packFileName;
- (Image*) getImageNamed:(NSString*)name;
- (BOOL) hasImageNamed:(NSString*)name;

@end


@implementation PackedImages

- (id) init:(NSString*)packFileName {
   self = [super init];
   if (!self) return nil;

   _nameToImage = [[NSMutableDictionary alloc] init];

   NSString *packPath = [[NSBundle mainBundle] pathForResource:packFileName ofType:@"pack"];
   NSLog(@"Loading packed images: %@", packPath);

   FILE *file = fopen([packPath UTF8String], "rt");
   Image *pageImage = nil;
   while (true) {
      char nameString[256];
      if (fscanf(file, "%s", &nameString) == EOF) {
         [pageImage release];
         break;
      }
      NSString *name = [NSString stringWithCString:nameString encoding:NSASCIIStringEncoding];
      if ([name length] == 0) {
         [pageImage release];
         pageImage = nil;
      } else if (pageImage == nil) {
         pageImage = [[Image alloc] initWithImageNamed:name];
      } else {
         int left, top, right, bottom, offsetX, offsetY, index;
         fscanf(file, "%d", &left);
         fscanf(file, "%d", &top);
         fscanf(file, "%d", &right);
         fscanf(file, "%d", &bottom);
         fscanf(file, "%d", &offsetX);
         fscanf(file, "%d", &offsetY);
         if (!fscanf(file, "%d", &index)) index = 9999999;
         Image *image = [[Image alloc] initWithSubImage:pageImage rect:CGRectMake(left, top, right - left, bottom - top)];
         [image setOffset:offsetX y:offsetY];
         [_nameToImage setValue:image forKey:name];
         [image release];
      }
   }

   return self;
}

- (Image*) getImageNamed:(NSString*)name {
   Image* image = [_nameToImage valueForKey:name];
   if (image == nil) NSLog(@"WARN: Packed image not found: %@", name);
   return image;
}

- (BOOL) hasImageNamed:(NSString*)name {
   return [_nameToImage valueForKey:name] != nil;
}

- (void) dealloc {
   [_nameToImage release];
   [super dealloc];
}

@end


Of course, you need a nice Image class. Smiley This doesn't preserve the order that the Java PackedImages class does. The nice part is the upper left of the image before transparency is stripped is preserved.

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #22 - Posted 2009-12-10 18:07:49 »

I was mostly just curious as to how well the algorithm I used packed something similar to your screenshots.

Most animations have transparency that can be stripped off to save space. This is nice to get more sprites per texture and especially important if you are using PVRTC on the iPhone.

Parsing my tools output on the iPhone goes like this:

Of course, you need a nice Image class. Smiley This doesn't preserve the order that the Java PackedImages class does. The nice part is the upper left of the image before transparency is stripped is preserved.

My tool already strips transparency. It also gives you the option to force every sprite to be a square, if you so desire, and also saves an animation and atlas file detailing the data in the sheet. Perfect for my exact purpose. Smiley I've already got several sprite loaders, atlas loaders, and animation loaders written in ObjC.

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #23 - Posted 2009-12-10 18:15:40 »

Good for you. That doesn't help anyone else though.

Offline princec

JGO Kernel


Medals: 389
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #24 - Posted 2009-12-10 20:37:58 »

Sort sprites by texture?
Can't - have to sort by layer first. And Y coordinate. And sublayer.

Cas Smiley

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #25 - Posted 2009-12-10 23:50:30 »

Good for you. That doesn't help anyone else though.
Did you not notice this thread is about what I needed to do? I wasn't seeking a way to make something that would be useful for everyone else. Smiley

See my work:
OTC Software
Offline Nate

JGO Kernel


Medals: 149
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #26 - Posted 2009-12-11 02:03:39 »

No problem. I'll just avoid you and your threads in the future.

Offline CommanderKeith
« Reply #27 - Posted 2009-12-11 11:13:18 »

This stuff's pretty cool, I heard that texture binds are expensive so these tools are very useful.

By the way Nate, I think Demonpants/Eli must have had a bad day, he's not an egotist. Like you, he's helped me a lot with code and pointers plenty of times  Cool

Offline princec

JGO Kernel


Medals: 389
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #28 - Posted 2009-12-11 12:01:11 »

Haha. Sulky Grumples  Kiss

Cas Smiley

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #29 - Posted 2009-12-11 16:09:46 »

This stuff's pretty cool, I heard that texture binds are expensive so these tools are very useful.

By the way Nate, I think Demonpants/Eli must have had a bad day, he's not an egotist. Like you, he's helped me a lot with code and pointers plenty of times  Cool
You got it. I did indeed have quite a bad day. More a bad week. Or month. Let me put it this way... this game was originally supposed to be released in June. Due to a large variety of factors, including feature creep, having to work on other projects to raise money, employees getting fired and others getting hired, and more, we are still working on this game (although this time I think the Christmas release date is sound). I am supposed to get a pay bump, health insurance, etc. when the game gets released (depending on how well it does), but most importantly I have been busting my ass for months now (when you have a new release date every month, then every month becomes "crunch time" when you are working too many hours a week and tiring yourself and pissing off your fiancée Tongue) trying to hit a release date that inevitably gets put off. So it feels a bit like I've been wasting time and spinning my wheels for this whole time, not getting anything to actually add to my resume. This week was particularly bad because my computer crashed on Monday so I spent the entire day fixing it, then on Wednesday and Thursday I had to go to a bunch of meetings about yet another project that isn't this one.

The stress is  pouring out of my ear-holes.

Now as for this texture packing tool, I was indeed thinking I would share my source at some point when I had time to fix it up, given that the examples I've seen have had many more features than appear to be necessary. Mine is very short, and also uses generics so you can use it to pack anything that has a width and a height. The whitespace trimmer I have in there is external to the actual packing - I only put it in because the images I was given for this particular scenario are 128x128 but only use about 64x64. So I just did what I needed to for my scenario - I'm not trying to make something that is publicly useful yet. Smiley

Thanks for the kiss, Cas.  Kiss

Wink
Eli

See my work:
OTC Software
Pages: [1] 2
  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.

Pippogeek (39 views)
2014-09-24 16:13:29

Pippogeek (30 views)
2014-09-24 16:12:22

Pippogeek (19 views)
2014-09-24 16:12:06

Grunnt (45 views)
2014-09-23 14:38:19

radar3301 (27 views)
2014-09-21 23:33:17

BurntPizza (63 views)
2014-09-21 02:42:18

BurntPizza (33 views)
2014-09-21 01:30:30

moogie (41 views)
2014-09-21 00:26:15

UprightPath (50 views)
2014-09-20 20:14:06

BurntPizza (54 views)
2014-09-19 03:14:18
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!