Saturday, April 9, 2016

Texture packing algorithm


I was exporting some textures from an old game, and needed an algorithm to pack many small textures into a texture atlas. I found a very nicely explained algorithm on this page and wanted to share, if someone might need something like this:

http://www.blackpawn.com/texts/lightmaps/default.html

There are some other interesting articles from the same guy here:

http://www.blackpawn.com/texts

The packing algorithm is so simple, I didn't think it would work. You just create a node with the output texture size and loop trough your images and call Insert() with individual texture's width and height. The node recursively splits itself if its size doesn't match the input, and calls Insert() of the child nodes. The node that gets returned holds the final [x,y] position, and if it returns NULL it means the image couldn't fit.

The grey lines mark individual textures and animations that I grouped together in code, so it doesn't all get mixed, but that is another story.



Tip 1.

In the example above I sorted my images according to their size(width*height) before I started to call Insert().

Tip 2.

If you look at the examples from the link, you will see the images are stored in an upside-down L pattern starting from top left, so if your output image is too big the input images will be positioned in the L pattern and the rest of the space(bottom right) is left unused. To avoid that;
- I sum the size of all the textures and set node width and height to sqrt(sum), so I have a minimum square output.
- Then I check if some image has width higher than that, if so I take that value for the final node width, so it can fit.
- The final height is some arbitrary huge value. While calling Insert() I keep track of where the bottom corners of the images end up and take the maximum value when creating the actual output image, which, after all this mess, should be more or less a square.

C++

Here is my implementation in C++ to spare you 2 minutes of converting the pseudocode. Unfortunately Blogger doesn't have code tags or something to format it properly.

#include <vector>

class AR_Node
{
public:
    std::vector<AR_Node> child;    //child nodes
    int x, y, w, h;                //position and node size
    bool image;                    //image stored in the node

    AR_Node* Insert(int img_w, int img_h);

    AR_Node()
    {
        this->x = y = w = h = 0;
        this->image = false;
    }
};

AR_Node* AR_Node::Insert(int img_w, int img_h)
{
    //if we are not a leaf then
    if(!this->child.empty())
    {
        //try inserting into first child
        AR_Node *newNode = this->child[0].Insert(img_w,img_h);
        if(newNode!=NULL) return newNode;

        //no room in first child, insert into second
        return this->child[1].Insert(img_w,img_h);
    }
    else
    {
        //if there is already a image here, return
        if(this->image) return NULL;

        //if image doesn't fit, return
        if(this->w<img_w || this->h<img_h) return NULL;

        //if we're just right, accept
        if(this->w==img_w && this->h==img_h)
        {
            this->image = true;
            return this;
        }

        //otherwise split this node and create some children
        this->child.push_back(AR_Node());
        this->child.push_back(AR_Node());

        //decide which way to split
        int dw = this->w - img_w;
        int dh = this->h - img_h;

        if(dw>dh)
        {
            //vertical split           
            //left

            this->child[0].x = this->x;
            this->child[0].y = this->y;
            this->child[0].w = img_w;
            this->child[0].h = this->h;
            //right
            this->child[1].x = this->x + img_w;
            this->child[1].y = this->y;
            this->child[1].w = this->w - img_w;
            this->child[1].h = this->h;
        }
        else
        {
            //horizontal split
            //up

            this->child[0].x = this->x;
            this->child[0].y = this->y;
            this->child[0].w = this->w;
            this->child[0].h = img_h;
            //down
            this->child[1].x = this->x;
            this->child[1].y = this->y + img_h;
            this->child[1].w = this->w;
            this->child[1].h = this->h - img_h;
        }

        //insert into first child we created
        return this->child[0].Insert(img_w,img_h);
    }
}

Tuesday, April 5, 2016

Random #6 - Youtube channel statistics

This January my YouTube channel exploded ! Well, at least one video did. My "The Bloodcrafter - Minecraft 2D shooter" video is getting in average almost 1000 views DAILY, and is rapidly approaching 400 000 views, with the channel surpassing 500 000 total views. If I were monetizing this I might have made enough money to buy the actual game :/


Other videos are not that successful, and the total view count of all the videos I uploaded in the last two years is only around 15 000, and that number would be much, much lower if Bloodcrafter wasn't attracting so much attention to the channel.

Since the most popular videos are based on Minecraft, Serious Sam and Quake, and with so many views in the period of over 5 years, the channel statistics are worth looking at to see some trends. I think it would make sense to say that the viewer demographics represent the actual player base.

The most significant change in the last 5 years is how Minecraft has become more popular among female players. In the first year(2011-2012) only 5 percent of players were female, and the data from last year (2015-2016) shows it is currently at almost 40%.


The percentage of Serious Sam female viewers/players jumped from 5% to around 16%. Quake 2 continues to be a "man's" game, probably because 90s girls weren't interested in it, and new generations don't even know about it, since the series is dead since 2005. But, looking at Serious Sam, which is a similar game, the new entries don't help much. Serious Sam continues to be most popular in Eastern Europe.


Other videos share the same faith like Quake, it's such a sausage festival that YouTube doesn't even want to display the statistics and it shows an error. Since most of them are about video game development, and are shared on some game development and gaming forums, my conclusion would be that we wont see a rapid increase in the number of female game developers any time soon... unless it is forced.

Another sad statistic is Linux. I only have the data starting from January 2013, and they show only 1.3% of PC viewers are on Linux, and 1.8% use Mac. The stats from this blog are a bit more positive, where 5% of readers are on Linux, and 5% on Mac (but these are overall numbers, not just for PC).