Chart rendering: not as easy as it sounds

What is more difficult: to render a scene with exploding helicopters or to draw a dull graph of the function y = x ² ? Yes, that's right, it is expensive and difficult to blow up helicopters - but people cope using such powerful things as OpenGL or DirectX. And drawing a graph, it seems, is simple. And if you want a beautiful interactive chart, can you draw it with the same powerful pieces? Spit time, probably?

And no. To make the dull graphics look sane and at the same time work without brakes, we had to sweat: almost at every step unexpected difficulties lurched.

Objective: to develop a cross-platform charting library that would be interactive, support animated transitions from the box and, most importantly, would not slow down.
')

Problem 1: float and pixel matches

It would seem that a first grader can also divide a segment into n equal parts. What is our problem? Mathematically, that's right. Life spoils float accuracy. Combining two lines of a pixel into a pixel, if they are equivalent, but different transformations, it is almost impossible: in the bowels of the graphics processor errors occur, which appear in the process of rasterization, each time in different ways. And a pixel to the left is a pixel to the right - quite noticeable when it comes to contours, elevations on axes, etc. It is practically impossible to debug, since it is impossible to predict the presence of an error, nor affect the rasterization mechanism in which it occurs. At the same time, the error is different depending on whether the Scissor Test is enabled (which we use to limit the drawing area of ​​the graph).

We have to make crutches. For example, we round off the offset values ​​in a transfer transform to 10 ^–4 . Where does this number come from? Picked up! The code looks scary, but it works:

const float m[16] = { 1.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f, 0.0f, (float)(ceil(tx() * 10000.0f) / 10000.0), (float)(ceil(ty() * 10000.0f) / 10000.0), (float)(ceil(tz() * 10000.0f) / 10000.0), 1.0f }; 

As a result, for the majority of cases arising in practice, we selected the necessary values ​​to compensate for errors. It remains to hope that nothing critical was missed.

Problem 2: docking perpendicular lines

Here it is not a matter of error, but how the “hardware accelerated” lines are implemented. The thickness is 2 px, the coordinates are the same, the intersection is in the center. And - the magnificent "bitten" corner, as a result. The solution is, again, the crutch offset X or Y coordinates of one of the ends by one pixel. But shifting something by a pixel, working with the coordinates of polygons is a whole problem. The coordinates of the scene and the coordinates of the screen are related to each other by transformations riddled with an error - especially if the size of the scope that the projection matrix describes is not equal to the size of the screen.

In the end, we picked up the displacements, which give acceptable results, “but the sediment remained”: the solution is still unreliable and there is always a chance that users will find the corners chipped. It looks like this:

 m_border->setFrame(NRect(rect.origin.x + 0.5f, rect.origin.y + 0.5f, rect.size.width - 3.5f, rect.size.height - 3.0f)); m_xAxisLine->setFrame(NRect(rect.origin.x, rect.origin.y, rect.size.width - 1.5f, rect.size.height - 1.0f)); m_yAxisLine->setFrame(NRect(rect.origin.x, rect.origin.y, rect.size.width - 1.5f, rect.size.height - 0.5f)); 

Problem 3: lines in general

And again the line. In any diagram there are quite a few lines - regular lines, no frills. These are axes, grid, and divisions on axes, and borders of graph elements, sometimes the graph itself. And these lines need to somehow draw. It would seem that easier? Paradoxically, the modern graphic APIs the farther, the more confidently they throw out the support of regular lines: proof for OpenGL , proof for Direct3D .

So far, the lines are still supported, but their allowable thickness is severely limited. Practice has shown that on iOS devices it is 8 px, and on some androids even less. The former function of setting the dotted pattern ( glLineStipple ) in the OpenGL specification is no longer supported, it is not available on mobile devices in OpenGLES 2.0. The lines themselves - even those that fit the permissible boundaries in thickness - look terrifying:


So far, we put up with what we have, but everything goes to the fact that you have to write your own line visualizer, which would maintain a constant thickness on the screen, independent of the scale of the contour (as GL_LINES does now), but know how to make beautiful bends . You will probably need to build them from polygons:

Problem 4: holes between polygons

And again, the problem of accuracy. The screenshot shows the bright "blotches" on the pie chart. This is nothing but the result of the error of rasterization (again!), And here no crutches save anymore. It becomes a little better if you enable smoothing of borders:


At the moment, resigned and left in this form.

Problem 5: system anti-aliasing features

Without the smoothing of the borders, the rendering result hurts the eye even on retina displays. But the MSAA system smoothing algorithm, available on any modern platform, has three serious problems:

1. Decreased performance: according to our observations, on mobile phones it drops on average three times, and when playing animation on complex scenes tangible lags appear.
2. The difficulty of multiplatform (and we are chasing it): on different platforms, system anti-aliasing is turned on differently, but we are trying to unify the code to the maximum.
3. Image artifacts: objects whose sides are parallel to the sides of the screen (for example, the grid lines on the graph) are blurred by system anti-aliasing (if they have fractional coordinates as a result of all transformations), although they should remain sharp:

Because of all this, we had to abandon the standard smoothing and reinvent the next bike to implement its own algorithm. As a result, we have assembled the SSAA and FXAA hybrid optimized for mobile phones , which:

1. Able to automatically turn off for periods of animation playback (when animating, the user needs smooth movement, and in statics - smoothing of borders).
2. In terms of performance, anti-aliasing coincides with system anti-aliasing, and it is implemented exclusively by the internal mechanisms of our graphics engine (that is, it retains multiplatform).
3. It can affect a part of the scene, and not the whole one (this is how you manage to avoid blur artifacts: we just exclude from the set of objects being smoothed those that it obviously will not do).

The impact on a part of the scene is organized through layer-by-layer rendering, when the entire set of objects is divided into groups (layers) according to their mutual arrangement (front, middle, background, etc.) and the need for smoothing. Layers are drawn sequentially, and anti-aliasing is applied only to those with the corresponding attribute.

Issue 6: Multithreading and Energy Saving

A good tone is to handle user interface events and render a graphic scene in different streams. However, user actions affect the appearance of the scene, which means synchronization is necessary. We decided that placing mutexes in all visual objects was too much, and instead implemented transactional memory.

The idea is that there are two property hash tables: for the main thread (MTT) and for the rendering stream (RTT). All changes to the appearance settings of objects fall into MTT. The next entry into it leads to the planning of a “synchronization tick” (if it has not yet been scheduled), which will occur at the beginning of the next iteration of the main thread (it is assumed that the user interface is processed in the main thread). During the synchronization tick, the MTT content is moved to RTT (this action is protected by a mutex - the only one for the entire graphic scene). At the beginning of each iteration of the rendering stream, it is checked whether there are any records in the RTT, and if they exist, they are applied to the corresponding objects.

It also implements the installation of certain properties with animation. For example, you can specify a scale change from 0 to 1 for a certain time, and an entry from RTT will not be applied immediately, but in several steps, each of which will result in an interpolation of the scale value from 0 to 1 according to a given law.

The same mechanism provides the ability to render on demand: the actual rendering is performed only if there are records in the RTT (that is, the state of the scene has changed). Visualization on demand is very relevant for mobile devices, as it unloads the processor and thus saves precious battery power.

Something like this. Of course, there were enough tasks for the ability to use Google - but we sort of listed the most unexpected rakes. As a result, despite the efforts of the organizers, the holiday took place , however, managed to get pictures, for which it is not very ashamed