Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
on:
2009-12-08 13: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<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Riven
« League of Dukes » JGO Kernel      Posts: 5866 Medals: 255
Hand over your head.
|
 |
«
Reply #1 on:
2009-12-08 14: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 
|
Hi, appreciate more people! Σ ♥ = ¾ Learn how to award medals... and work your way up the social rankings
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #2 on:
2009-12-08 14: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  It's all about time.  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<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Games published by our own members! Go get 'em!
|
|
Jono
Full Member   Posts: 143 Medals: 1
|
 |
«
Reply #3 on:
2009-12-08 14: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
|
|
|
|
|
Orangy Tang
JGO Kernel      Posts: 2960 Medals: 37
Monkey for a head
|
 |
«
Reply #4 on:
2009-12-08 14: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: 
|
|
|
|
princec
« League of Dukes » JGO Kernel      Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
 |
«
Reply #5 on:
2009-12-08 15:26:23 » |
|
Ooh, is that algorithm loads better than the one in SPGL? I've been wondering about getting a better one. Cas 
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #6 on:
2009-12-08 15: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<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Orangy Tang
JGO Kernel      Posts: 2960 Medals: 37
Monkey for a head
|
 |
«
Reply #7 on:
2009-12-08 15: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... 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.
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #8 on:
2009-12-08 17: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<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
ryanm
« League of Dukes » JGO Strike Force      Posts: 788 Medals: 4
Used to be bleb
|
 |
«
Reply #9 on:
2009-12-08 17: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! Go get 'em!
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #11 on:
2009-12-09 09: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. 
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Nate
JGO Neuromancer     Posts: 1062 Medals: 30
mooooo
|
 |
«
Reply #12 on:
2009-12-09 14:36:13 » |
|
FWIW, PS CS4 comes with an export layers script that can export to PNG. Not quite as cool though. 
|
|
|
|
Riven
« League of Dukes » JGO Kernel      Posts: 5866 Medals: 255
Hand over your head.
|
 |
«
Reply #13 on:
2009-12-09 15:31:46 » |
|
It's all about time. ...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.  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
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #14 on:
2009-12-09 18: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<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Nate
JGO Neuromancer     Posts: 1062 Medals: 30
mooooo
|
 |
«
Reply #15 on:
2009-12-09 19:19:58 » |
|
Could you try running the same images through my ImagePacker?
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #16 on:
2009-12-09 20:10:05 » |
|
Could you try running the same images through my ImagePacker?
Unfortunately, no. The distribution is totally random.  You'll notice it's slightly different in the two screenshots.
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Orangy Tang
JGO Kernel      Posts: 2960 Medals: 37
Monkey for a head
|
 |
«
Reply #17 on:
2009-12-10 05:08:15 » |
|
Unfortunately, no. The distribution is totally random.  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.
|
|
|
|
princec
« League of Dukes » JGO Kernel      Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
 |
«
Reply #18 on:
2009-12-10 05: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 
|
|
|
|
Markus_Persson
JGO Kernel      Posts: 2092 Medals: 10
Mojang Specifications
|
 |
«
Reply #19 on:
2009-12-10 10:12:13 » |
|
Sort sprites by texture?
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #20 on:
2009-12-10 10: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  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. 
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Nate
JGO Neuromancer     Posts: 1062 Medals: 30
mooooo
|
 |
«
Reply #21 on:
2009-12-10 12: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.  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.
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #22 on:
2009-12-10 13: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.  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.  I've already got several sprite loaders, atlas loaders, and animation loaders written in ObjC.
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Nate
JGO Neuromancer     Posts: 1062 Medals: 30
mooooo
|
 |
«
Reply #23 on:
2009-12-10 13:15:40 » |
|
Good for you. That doesn't help anyone else though.
|
|
|
|
princec
« League of Dukes » JGO Kernel      Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
 |
«
Reply #24 on:
2009-12-10 15:37:58 » |
|
Sort sprites by texture?
Can't - have to sort by layer first. And Y coordinate. And sublayer. Cas 
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #25 on:
2009-12-10 18: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. 
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
Nate
JGO Neuromancer     Posts: 1062 Medals: 30
mooooo
|
 |
«
Reply #26 on:
2009-12-10 21:03:39 » |
|
No problem. I'll just avoid you and your threads in the future.
|
|
|
|
CommanderKeith
JGO Wizard     Posts: 1455 Medals: 9
|
 |
«
Reply #27 on:
2009-12-11 06: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 
|
|
|
|
princec
« League of Dukes » JGO Kernel      Posts: 8076 Medals: 91
Eh? Who? What? ... Me?
|
 |
«
Reply #28 on:
2009-12-11 07:01:11 » |
|
Haha. Sulky Grumples  Cas 
|
|
|
|
Eli Delventhal
« League of Dukes » JGO Kernel      Posts: 3573 Medals: 44
Game Engineer
|
 |
«
Reply #29 on:
2009-12-11 11: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  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  ) 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.  Thanks for the kiss, Cas.   Eli
|
See my work:OTC Software<br /> Currently Working On:Secret project... I edit JGO in production, because I simply don't waste time writing bugs
|
|
|
|