SFML community forums

General => SFML projects => Topic started by: Glocke on December 20, 2014, 01:10:07 pm

Title: Image Atlas Generator
Post by: Glocke on December 20, 2014, 01:10:07 pm
This thread is out-dated. Please use this one (http://en.sfml-dev.org/forums/index.php?topic=17191.msg123626).

Hi there :)

Introduction:
we already know that using few, large textures with multiple sprite animation frames is more efficient than using many small textures with single frames. I was looking - I guess as most other hobby developers, too - for suitable sprite graphics. Some assets are using the frameset-approach (multiple frames within a larger texture), some are using single files per frame. But if you want to avoid using a mixture of both approaches, you are forced to convert all graphics to one format either used by the first or used by the second approach.
But simple merging (potentially diffently sized!) frames to a set of uniform sized frames isn't great. It implies some wasted memory (because of many empty/transparent pixels inside the image). On the other hand, merging them memory-efficient by hand isn't great either. To solve this, I wrote some piece of code ;)

How it's working:
The idea is straight-forward: try to find an empty spot for your images. But this implies some more work! The basic idea is to add lots of images to some kind of container. On each insertion the container (with a fixed size) returns whether it had free space. If yes, the image was added and it's offset (topleft position within the container) will be returned call-by-reference to the second argument given to add.

Here's a small (runnable) example code.. It's creating some random single-colored images with randomized size, sorting it by the images' size (desceding) and adding largest images first. After that, the final image is written to disk as example usage.

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>

#include <utils/image_atlas.hpp> // <-- see below

int main() {
        std::srand(std::time(0));

        // create images --- ugly - feel free to skip while reading^^
        std::size_t num = 40;
        std::vector<sf::Image> images{num};
        sf::Uint8 k = 0;
        int i = 0;
        for (auto& img: images) {
                sf::Color c;
                if (i < num/3) {
                        c = sf::Color{k, 0, 0};
                } else if (i < 2*num/3) {
                        c = sf::Color{0, k, 0};
                } else {
                        c = sf::Color{0, 0, k};
                }
                img.create(40 * (std::rand() % 10 + 1), 40 * (std::rand() % 10 + 1), c);
                k += (255/(num/3));
                ++i;
                if (k > 200) {
                        k = 40;
                }
        }

        // sort by size (descending)
        // --> helps to achieve a (at least nearly) well-constructed atlas
        std::sort(images.begin(), images.end(), [&](sf::Image const & a, sf::Image const & b) {
                auto size_a = a.getSize();
                auto size_b = b.getSize();
                return size_a.x * size_a.y > size_b.x * size_b.y;
        });
       
        // add to ImageAtlas -- here the actual work starts
        ImageAtlas target{1024u}; // or use default ctor for max size
        for (auto const & img: images) {
                sf::Vector2u pos;
                if (target.add(img, pos)) {    
                        auto size = img.getSize();
                        std::cout << "Added image sized " << size.x << "x" << size.y
                                << " added at (" << pos.x << "|" << pos.y << ")\n";
                }
        }
       
        // generate final image
        auto result = target.generate();
        result.saveToFile("out.png");
}
 

By the way: The included header for the image_atlas can be found here: https://github.com/cgloeckner/SfmlExt

What to do with?
The image atlas can be create once for the current machine (atlas' size might depend on the hardware's limitations), write it to disk and load it when starting the game. Of course you'll also need to store those initial-image-and-its-offset-relations to keep atlas and mapping consistent.
Possibly, the (resulting) texture and rectangles (computed offset with initial frame's size) could be used by Thor's animation handling system ;)

About the code:
It poorly documented, yet. Also some approaches (e.g. searching a free spot) are not that great... But it's working in the first place ;)

Please feel free to feedback!

Kind regards
Glocke

/EDIT: Some productive example: These offsets should be stored (mapping!) for the example frameset (graphics taken from "Battle for Wesnoth")
(click to show/hide)
Title: Re: Image Atlas Generator
Post by: eXpl0it3r on December 20, 2014, 02:30:18 pm
Sounds like some form of a scanline algorithm. Did you come up with it on your own or did you use some algorithm that has been proven to generate an optimal solution?
Title: Re: Image Atlas Generator
Post by: Glocke on December 20, 2014, 03:42:41 pm
Did you come up with it on your own or did you use some algorithm that has been proven to generate an optimal solution?
It's my own first-try nearly-intuitive algorithm. Therefore it might be slow in some cases.

It's scanning the entire x/y scope within the container while looking for a free spot. To make it faster, I'm using the gcd of each dimension of all previously added frames, to have a suitable step_x and step_y possibly larger than 1 ^^ E.g. if an image sized 120x80 and another image sized 96x72 where added, the step_x/step_y for adding a third image will be step_x=gcd(120,96)=24 and step_y=gcd(80,72)=8.

But if the frames' dimensions' gcd is 1, searching will be painful. But for dimensions with factor 2^n it works pretty fast. To evaluate, whether an image can be added, I'm using sf::Rect and it's intersects-method to check for "collision".

But I haven't thought about mathematical correctness and whether there's a optimal solution, yet. As a first approach, it works pretty well ;D
Title: Re: Image Atlas Generator
Post by: BZep on December 20, 2014, 04:31:58 pm
Great project!

Is it on GitHub? :)

Would like to follow this, so I can quickly find it if I found a need for it.
Title: Re: Image Atlas Generator
Post by: eXpl0it3r on December 20, 2014, 05:00:45 pm
By the way: The included header for the image_atlas can be found here: https://github.com/cgloeckner/SfmlExt
Title: Re: Image Atlas Generator
Post by: BZep on December 20, 2014, 05:01:40 pm
By the way: The included header for the image_atlas can be found here: https://github.com/cgloeckner/SfmlExt

Errr...
Title: Re: Image Atlas Generator
Post by: Glocke on December 21, 2014, 09:53:24 am
Great project!
Thanks! ;D

Would like to follow this, so I can quickly find it if I found a need for it.
Feel free to do so ;)
Title: Re: Image Atlas Generator
Post by: Mutoh on December 21, 2014, 05:54:38 pm
This is great! I was almost writing something like this myself, but you saved me a lot of time. Followed as well, because I'll be needing it in the future. :D
Title: Re: Image Atlas Generator
Post by: Glocke on December 22, 2014, 09:27:27 am
This is great! I was almost writing something like this myself, but you saved me a lot of time. Followed as well, because I'll be needing it in the future. :D
That's great to hear! 8)
If there's something missing to the atlas, feel free to mention it :)

/EDIT: I just built another example using Thor for animation handling.
Extract from the example (full example: https://github.com/cgloeckner/SfmlExt/blob/master/atlas_example.cpp (https://github.com/cgloeckner/SfmlExt/blob/master/atlas_example.cpp)) using a customizable MyPacker class
// Create Image Atlas
MyPacker packer;
for (auto i = 1u; i <= 5; ++i) {
        packer.addImage("wraith-s-attack-"+std::to_string(i)+".png");
}
auto atlas = packer.generate(256u);
atlas.saveToFile("out.png");

// Create Animation
thor::FrameAnimation attack;
for (auto i = 1u; i <= 5; ++i) {
        std::string fname{"wraith-s-attack-"+std::to_string(i)+".png"};
        attack.addFrame(1.f, static_cast<sf::IntRect>(packer.getClipping(fname)));
}

thor::Animator<sf::Sprite, std::string> animator;
animator.addAnimation("attack", attack, sf::milliseconds(625)); // 5*125ms
Title: Re: Image Atlas Generator
Post by: BlueCobold on December 22, 2014, 10:45:44 am
Sounds like some form of a scanline algorithm. Did you come up with it on your own or did you use some algorithm that has been proven to generate an optimal solution?
Since the problem is np-hard, I doubt it is the optimal solution ;)
Some problem remains though. The images get saved in some wonky order, so where's the file to look up the position and size for each sprite in the final atlas? Without such a mapping, the atlas itself isn't of much help.
Title: Re: Image Atlas Generator
Post by: Glocke on December 22, 2014, 10:52:08 am
Without such a mapping, the atlas itself isn't of much help.
The mapping is given by
bool ImageAtlas::add(sf::Image const & image, sf::Vector2u& pos)
when querying the (call-by-ref-passed) pos argument after a successful add.
When sorting, you should track some kind of information to identify the images (e.g. by filename). View the latest example for this: When adding a pair of std::string and sf::Image, the image can be identified by it's previous filename. The MyPacker implementation also provides querying clipping rectangle by the original filename of each frame which was added.

/EDIT: But yes, I'll need to provide a (more or less generic) packer implementation (generic referring to the identification of the image). Scheduled! 8)
Title: Re: Image Atlas Generator
Post by: BlueCobold on December 24, 2014, 08:17:08 am
I'd be curious to see given on a fixed set of sprites if your algorithm is better than mine. :P
Title: Re: Image Atlas Generator
Post by: Glocke on January 13, 2015, 09:57:36 am
My image atlas generator has evolved and is now part of a framework project of mine. This framework is discussed at this thread (http://en.sfml-dev.org/forums/index.php?topic=17191.msg123626). Feel free to join discussion!

Kind regards
Glocke