How to optimize the game using polygon atlases
As everyone knows, the life of a mobile game developer is not easy. He must find his way on a very narrow path. On the one hand - the requirements of game designers, confidently rushing to infinity. More functionality, more beautiful graphics, more effects, more animations, more sounds. And on the other hand, the limited resources of a mobile device. And first of all, as a rule, RAM ends.
For example, the iPad 2 has a total of 512 MB RAM. However, the application is available only about 275 MB. When the memory occupied by the application approaches this boundary, the operating system will send the so-called “Memory warning” - gently but persistently offer to free the memory. And if the limit is still exceeded, the operating system will stop the application. The user will think that your game has fallen and will run to write an angry letter to support. The main consumer of memory is, of course, graphics. In this article, we will try to talk about a slightly complex but effective method that is used to reduce the memory occupied by textures, as well as to increase the speed of rendering.
As everyone again knows, drawing textures directly from source files is a bad idea. Instead, they are packaged in texture atlases.
Texture satin is a large image obtained by gluing small textures. This saves memory and, more importantly, reduces the number of batches during rendering. There are two videos that demonstrate why the atlas is good, and the individual textures are bad: one and two. Thus, the task of packing a texture atlas usually comes down to the following: take rectangles of different sizes (source textures) and fit them as tightly as possible into one large rectangle, or, more often, a square. We are not at the Olympics and we do not need perfect packaging, and writing an algorithm that densely packs textures in a reasonable amount of time is not at all difficult. For quite some time now we have been using an algorithm that generates texture atlases for us. Something like this:
As you can easily see, there is a lot of free space in it and I really want to pack the textures more tightly. The reason for the ineffective packaging is that many textures contain fairly large transparent areas. Therefore, one day we decided to try to abandon the usual rectangular packaging and do what was eventually called the "polygon atlas". To do this, you need to solve 2 problems:
1.For each source texture, you need to find such a set of triangles so that it contains all its opaque pixels. Then, if we draw all these triangles, the original texture will appear on the screen. There is an important limitation - there should not be too many triangles, otherwise the rendering will be very slow. Thus, a compromise is needed between the number of triangles and the area they occupy. Therefore, at first an algorithm was written with many parameters for fine tuning, and only then, conducting experiments on real textures, we selected these parameters.
2. The resulting figures of complex shape (those same polygons) should be packed as densely as possible in an atlas. Here one of the variants of the bee swarm algorithm was used., who, having made numerous attempts using a random number generator, tried to find a fairly dense packaging option. A different kind of compromise was required here - between the quality of the packaging and the time spent on packaging.
Having traveled a rather long way and having attempted to package the test atlas about 100,000 times, we finally achieved the result:
As you can see, the packaging is really much denser. Depending on the texture, the gain can be up to 1/4 of their area. You can also create a debug version of the atlas, which shows a breakdown of the texture into triangles.
In addition to the atlas itself, its description is generated, which indicates the names of the source textures and the coordinates of the resulting triangles.
When using polygonal atlases, the rendering process, on the one hand, is accelerated, on the other, it is slowed down. It is accelerated because the total area to be drawn has become smaller, and therefore the overdraw value has also become smaller. And it slows down because if before any texture was drawn with just two triangles, now, as you can see in the above example, there are much more of them. In general, with reasonable settings for the atlas packer, we did not have big changes in the speed of the rendering system.
There is another problem that we encountered when switching to new atlases. Often it is required to draw not a whole texture, but only a part of it. For example, if you want to make the gradual appearance of an object on the screen or some kind of progress indicator. Using ordinary atlases, the problem is easily solved by correcting uv coordinates. In the case of polygonal atlases, everything becomes more complicated. Let's look at an example. The blue part of the texture that needs to be drawn is highlighted in blue:
Required:
The solution to this problem will provide an opportunity to practice well in the school course of geometry. In addition, such an algorithm may not work very fast.
There are more complicated cases. For example, circular progress or some kind of distortion of the texture. Therefore, it turned out that it is easier to pack some textures into regular atlases or not to pack at all, so as not to complicate the rendering process.
Some technical details. The packaging time for a polygon satin depends heavily on the packaging quality setting. Since atlases need to be reassembled at any change in the texture set, this has to be done quite often. Therefore, usually we have the “minimum density, maximum speed” mode turned on. In this mode, 8 atlases of 2048x2048 size are packed in about 5 minutes. In general terms, the packaging process looks like this:
As a rule, pre-packing is already quite tight. When trying to improve quality, the packaging time increases very much - up to several hours per 1 atlas - and the gain can be 2-3 additionally packaged textures.
In games, we use a proprietary engine. To go to polygon atlases, I had to modify it a bit. Fortunately, we already had an abstract drawing entity - the Drawable class:
It already had functions for getting the size, checking the opacity of the pixel for processing clicks and rendering. All that was needed was to create another PolygonalSprite class that would correctly implement these functions, taking into account the splitting of the texture into triangles.
Also, so that the client code can get a list of texture triangles and make some transformations with them, a function was added to the interface
For regular textures and regular atlases, this function returns four vertices, forming a rectangle corresponding to the original texture. And for textures from polygonal atlases - an array of vertices of triangles into which the texture is divided.
Now polygonal atlases are used in many of our projects and we can assume that they have passed the test of time. For example, in our next free-to-play project, Gardenscapes, which will be released soon , the bulk of the gameplay takes place in the player’s garden.
For him, just a huge number of different textures are drawn, some of them are used in this article as examples. Now all these textures fit in 8 polygonal atlases 2048x2048. But if we packed the atlases in the usual way, they would have turned out to be 11. So, we get the memory savings, depending on the graphic format used, from 6 to 48 MB. And game designers can offer up to four beautiful textures more!
About the Author: Sergey Shestakov, CTO of Playrix.
For example, the iPad 2 has a total of 512 MB RAM. However, the application is available only about 275 MB. When the memory occupied by the application approaches this boundary, the operating system will send the so-called “Memory warning” - gently but persistently offer to free the memory. And if the limit is still exceeded, the operating system will stop the application. The user will think that your game has fallen and will run to write an angry letter to support. The main consumer of memory is, of course, graphics. In this article, we will try to talk about a slightly complex but effective method that is used to reduce the memory occupied by textures, as well as to increase the speed of rendering.
Textures and atlases
As everyone again knows, drawing textures directly from source files is a bad idea. Instead, they are packaged in texture atlases.
Texture satin is a large image obtained by gluing small textures. This saves memory and, more importantly, reduces the number of batches during rendering. There are two videos that demonstrate why the atlas is good, and the individual textures are bad: one and two. Thus, the task of packing a texture atlas usually comes down to the following: take rectangles of different sizes (source textures) and fit them as tightly as possible into one large rectangle, or, more often, a square. We are not at the Olympics and we do not need perfect packaging, and writing an algorithm that densely packs textures in a reasonable amount of time is not at all difficult. For quite some time now we have been using an algorithm that generates texture atlases for us. Something like this:
As you can easily see, there is a lot of free space in it and I really want to pack the textures more tightly. The reason for the ineffective packaging is that many textures contain fairly large transparent areas. Therefore, one day we decided to try to abandon the usual rectangular packaging and do what was eventually called the "polygon atlas". To do this, you need to solve 2 problems:
1.For each source texture, you need to find such a set of triangles so that it contains all its opaque pixels. Then, if we draw all these triangles, the original texture will appear on the screen. There is an important limitation - there should not be too many triangles, otherwise the rendering will be very slow. Thus, a compromise is needed between the number of triangles and the area they occupy. Therefore, at first an algorithm was written with many parameters for fine tuning, and only then, conducting experiments on real textures, we selected these parameters.
2. The resulting figures of complex shape (those same polygons) should be packed as densely as possible in an atlas. Here one of the variants of the bee swarm algorithm was used., who, having made numerous attempts using a random number generator, tried to find a fairly dense packaging option. A different kind of compromise was required here - between the quality of the packaging and the time spent on packaging.
Having traveled a rather long way and having attempted to package the test atlas about 100,000 times, we finally achieved the result:
As you can see, the packaging is really much denser. Depending on the texture, the gain can be up to 1/4 of their area. You can also create a debug version of the atlas, which shows a breakdown of the texture into triangles.
In addition to the atlas itself, its description is generated, which indicates the names of the source textures and the coordinates of the resulting triangles.
When using polygonal atlases, the rendering process, on the one hand, is accelerated, on the other, it is slowed down. It is accelerated because the total area to be drawn has become smaller, and therefore the overdraw value has also become smaller. And it slows down because if before any texture was drawn with just two triangles, now, as you can see in the above example, there are much more of them. In general, with reasonable settings for the atlas packer, we did not have big changes in the speed of the rendering system.
There is another problem that we encountered when switching to new atlases. Often it is required to draw not a whole texture, but only a part of it. For example, if you want to make the gradual appearance of an object on the screen or some kind of progress indicator. Using ordinary atlases, the problem is easily solved by correcting uv coordinates. In the case of polygonal atlases, everything becomes more complicated. Let's look at an example. The blue part of the texture that needs to be drawn is highlighted in blue:
Required:
- Exclude from drawing triangles that do not fall into the drawn part of the texture
- Find the intersections of the new texture border with the source triangles. The result may no longer be a triangle, and you may need to split it into 2 new triangles.
The solution to this problem will provide an opportunity to practice well in the school course of geometry. In addition, such an algorithm may not work very fast.
There are more complicated cases. For example, circular progress or some kind of distortion of the texture. Therefore, it turned out that it is easier to pack some textures into regular atlases or not to pack at all, so as not to complicate the rendering process.
Some technical details. The packaging time for a polygon satin depends heavily on the packaging quality setting. Since atlases need to be reassembled at any change in the texture set, this has to be done quite often. Therefore, usually we have the “minimum density, maximum speed” mode turned on. In this mode, 8 atlases of 2048x2048 size are packed in about 5 minutes. In general terms, the packaging process looks like this:
- textures are divided into triangles;
- textures are sorted in descending order of height;
- preliminary packaging of textures. All textures are selected in order and for each, free space in the atlas is searched;
- several attempts are made to more densely repack texture. The number of attempts depends on the quality settings;
- if it was possible to improve the original packaging, then additional textures are added to the atlas.
As a rule, pre-packing is already quite tight. When trying to improve quality, the packaging time increases very much - up to several hours per 1 atlas - and the gain can be 2-3 additionally packaged textures.
In games, we use a proprietary engine. To go to polygon atlases, I had to modify it a bit. Fortunately, we already had an abstract drawing entity - the Drawable class:
class Drawable {
virtual int Width() const;
virtual int Height() const;
virtual bool HitTest(int x, int y) const;
virtual void Draw(SpriteBatch* batch, const FPoint& position);
}It already had functions for getting the size, checking the opacity of the pixel for processing clicks and rendering. All that was needed was to create another PolygonalSprite class that would correctly implement these functions, taking into account the splitting of the texture into triangles.
Also, so that the client code can get a list of texture triangles and make some transformations with them, a function was added to the interface
virtual void GetGeometry(std::vector& geometry) const; For regular textures and regular atlases, this function returns four vertices, forming a rectangle corresponding to the original texture. And for textures from polygonal atlases - an array of vertices of triangles into which the texture is divided.
Now polygonal atlases are used in many of our projects and we can assume that they have passed the test of time. For example, in our next free-to-play project, Gardenscapes, which will be released soon , the bulk of the gameplay takes place in the player’s garden.
For him, just a huge number of different textures are drawn, some of them are used in this article as examples. Now all these textures fit in 8 polygonal atlases 2048x2048. But if we packed the atlases in the usual way, they would have turned out to be 11. So, we get the memory savings, depending on the graphic format used, from 6 to 48 MB. And game designers can offer up to four beautiful textures more!
About the Author: Sergey Shestakov, CTO of Playrix.