xfcRS - original laconic, nimble rendering of smoothed tiles, "expansion fast cell - Rounded Squares"

xfcRS is a multifunctional fast algorithm, for a tile render with smooth transitions / to build an isosurface / to select an edge in a raster / for postprocessing as a pixel shader - for pixel art 8x8 scaling (for fast rasterization of fonts, other material for upscale'ing without modifications is not recommended) . The acronym 'eXpansion Fast Cell - Rounded Squares'

In this article we will consider it mainly in the context of the rendering of smoothed tiles:
')
If you have any questions about the terms, take a look here.

Looking ahead, I will say straight away: this is not improved Marshing Squares,

A very simple scheme for smoothing tiles is used. This is achieved due to the “Diffuse Circle”, parts of which are superimposed at the junction of different cells, or at the junction of any cell with an empty one. The “diffuse circle” should be drawn for all cell types and reflect in their texture a smooth transition into an empty cell.

That is, all the textures pass one into the other through the texture of an empty cell. This speeds up the work of the artist!

The algorithm breaks the cells into quarters 2x2, each of them fills with a smaller oriented tile from the prepared set. But this is the result. In fact, xfcRS is a post-processing algorithm. And the viewer is an external addition. The xfcRS itself only collapses the cell map into an index table, which can be used in a wide variety of ways. What is this table, how is it built and how is it used later?

Here the article will give an example of a simple post-render. By “post” render, I mean that it is some kind of another passage in a view and does not display the entire map from scratch, but draws only additional sub-tiles where they are needed.

Let's not hurry, I will start an explanation in the order in which it was thought up:

1.Texture texture
We look at the "Topology", we see 16 pieces of tiles, from which a cell can be composed depending on its neighbors.
The simplest situation: all neighbors are equal (the cell is made up of edge pieces) can be remembered by analogy, - that the pieces stick to the neighbors
(Let it be the initial state from which we change).
If a neighbor is not equal, he pushes away a piece from himself to two positions.

When all the neighbors are checked and all pieces of the tile are repulsed accordingly, you can remove the cage with these four pieces.
(For efficiency, you can check for bulk conditions, for example, if the cell is completely intact or completely empty).

The first thing to think about is how to choose the formulation of the task of smoothing tiles so that it is implemented more easily, but without significant qualitative differences.
It is clear that “smoothing” regular cells visually, some will creep onto others. But not all "creeping" is equally minimal in terms of labor costs of the renderer.
You can see that you can round a cell in two ways - by crawling a common texture onto it, or vice versa - by pulling the cell out of its original boundaries. Two options give us little visually. We choose one - only the narrowing of the cells when meeting with strangers or with zero texture. It also means that we exclude interaction with diagonal cells, which is also useful for further optimization.

In this case, the transition contour is best taken close to the ideal circle (although this is not a limitation, but the closer to it, the smoother the rounding will seem). The ideal circle is accurately described around the cell — it passes through its corners (this is already a restriction for smooth transitions). Symmetry is also important, it should be bi-radial. This allows smoothing bends on thin sections. If your transition texture is not uniform - draw a torus (see the figure on the original texture, you can take it as a template. This application can be considered a creative commons license).


On the picture:
The black grid shows the original cells. The marginal area where smoothing cannot be calculated due to the lack of neighbors is shaded. Those. the width and height of the resulting grid is reduced by the cell. The remaining white grid is positioned indented in the half-cell - the resulting sub-cell indices will be written into it.

In the lower left corner the original transition texture is added, from which all the curves in the figure are gathered.

If you want to experiment with a curve, look at the picture on the left “topology of diffusion zones of textures”. The white line shows a logical contour. The black lines on either side of it are the permissible displacement ranges (with this, the transition points of the tile connections are pairwise left - right, upper - lower, must be equidistant from the center). For example, you can draw an ellipse, and get an isometric effect (tilting the camera view).

2.Two Checks - Four cells
A naive approach would be to bypass all sub-cells with a test for equality with the current cell of its 2 neighbors. The result of the check is the shift of the coordinates of the vibrated piece of the texture to the center (see fig.). Initially, all quarters are accepted as angular pieces of texture and form a blue circle when connecting (the neighbors are blue on all sides). Inequality with a neighbor vertically shifts the selected piece of texture to the center vertically (by two positions, so it follows the opposite angle in the vertical direction). Horizontal uses the same test and shift. The case when after checks nothing moved (there was a whole blue circle) it is desirable to process as an exception and to display the whole cell at once and not in quarters.
Here the naive method ends.
(further in the code, the initial position of the tiles will have the constant 0xfc30. And the shifts along the horizontals / verticals will work with the corresponding HEX bits of the desired cells of the array)
It is important to note that any verification of the equality of 2 cells in fact always affects 4 sub-cells, and 2 already 8 respectively! So let's get this eightfold acceleration (from the method to the forehead) and process them in bulk. see figure



So we will bypass the desired cells instead of each sub-cell, just in the resulting array we will add the changes in place. We also note that the combination of presence / absence of neighbors can be perceived as 2 independent factors (the presence of a neighbor on top shifts the texture in x, the neighbor on the left in y). And since the factors are independent, there is no need to rest on synchronicity, you can handle them asynchronously. By the way, xfcRS generally perfectly parallelized!
When finding factors, we simply put down the appropriate X / igriki in the resulting array (all this is cunning, but, if you look, it is very conveniently stored in the index bits).

-! IMPORTANT! For the same reasons, the zone for which xfcRS gives the resulting array is MOVED by half a cell (one sub-cell). And the fact that it is impossible to calculate the edge cells is not the main thing. The main thing is that by moving (and rearranging) the indices accordingly, we get blocks that are convenient for checking and quickly determining completely filled 2x2 sub-cells. - example: if a 2x2 block of the desired cells is present on the incoming map, as a result it will be smoothed along the contour by half of the cell, and there will be one whole cell in the middle (half-shifted of the cell), so you want to easily determine it from the index. The definition of empty cells is not required, because (according to the definition of a pass-through algorithm) they should already be drawn by a standard tile algorithm. The render code from the example just skips them.

3. Implementation Comments
For the complete source code, see github.com/impfromliga/xfcRS
When implementing it is important to take into account that the returned date goes for sub-cells (which are grouped 2x2 between the available ones), since there is no possibility to calculate the value of the edge (there are not enough neighbors) - the size of the returned field will be less per cell (half cells from each edge).
As you handle it, xfcRS does not concern. The edge can be drawn without sub-cells by itself, but if the map involves scrolling, on the edge of the screen the terrain will visually “tremble” (when there are influencing neighbors). In this case, it is recommended to cut the output to half cells from the source data or to give xfcRS per cell more input data in advance.

A group of subbolic 2x2 is packed into one value in the order of big-endian, i.e. Values ​​of cells
AB
CD
- are in bits numbers starting from the lowest to the highest. And the index value = ((D * 16 + C) * 16 + B) * 16 + A
so on there is one hexadecimal digit per cell (it contains the index of the desired blur tile).



5. Combinations:
- When implementing scrolling, xfcRS is easily placed on the 2D buffer that I disassembled in the previous article. => habrahabr.ru/post/280830
- In addition, as you have already seen from the image for the post - it draws wonderful original fonts (which can be styled raster).

6.For history
I was born (not without difficulty, but only because it was more pleasant), I liked the algorithm so much that I decided to name it loudly.
I began to look for an abbreviation, I wanted something similar to the algorithms of either FXAA –analytical, or xBR or EPX - scaling pixel art graphics (by the way, after a recent inspection of the latter, it was found out that it has some quite tangible similarity with mine).
So came to the two options "eXpansion Fast Cell Rounder" or simply "Rounded Squares", as a result, began to lean more towards the latter.
But you know what else struck me? As a result, in the code, after the name, I came to the constant 0xfc30.
(I'm sure everyone will understand and support me as I am an IT-Nerd, even if it’s a single name, good for SEO, without hyphens, but in this case the two cannot be avoided!)

Another gift of fate was the earlier discovery of an interesting pattern on the transition texture:
- It displays a beautiful ball of texture (just like in the 3D editors materials)
- The fact is that pixel by pixel this ball can be turned inside out using only a permutation of 4x4 tiles. Those. no matter what the texture basis, they can be flipped.

In fact, xfcRS did not turn out so slim right away - in the old tests, for example, I didn’t see the remarkable layout of the tileset, in which the smoothness of the addition is simply visually checked.

By the way, there is another aesthetic task for the layout, although it is not a task, rather a question that bothers me. In view of such an unusually remarkable opportunity to turn the circle inside out, is there any more concise way of storing textures ... any ideas?

Well, for dessert:
Screenshots:







and live demo codepen.io/impfromliga/pen/qNOazj

That's all. I wanted to write articles more often, but firstly, the conscience does not allow to lay out something not worked through, and secondly, a clear description takes more time than the implementation itself, but not always it is enough ...

Comments, criticism, suggestions, thanks in advance for any constructive!

And by the way, time tends to be the faster, the more people are kicking you, and you are interested in your findings.

If you have read to here, Thank you very much for your attention!
And see you soon.