A little less than a week is left until the end of the Kickstarter campaign, but the graphical editor Krita has already raised funds for the two main tasks of this year: animation and drawing huge images. And if everything is more or less clear with the animation, then there are questions with large images. How to calculate and display an image of 100 million pixels on the screen? How to ensure that a brush of 1 million pixels is drawn without delays 500 times per second? I will try to answer these questions in this article.

Where do the drawing delays come from?

First you need to figure out how to draw in a modern graphic editor. Any brush is an image (“stroke” or “dab”), which is either loaded by the user directly or generated parametrically. When a user makes a stroke with a brush, this image is consistently superimposed on the canvas with a certain spacing (usually 10-20% of the brush size). The resulting image gets into the rendering pipeline, where it merges with all layers and is transferred to the user interface, where it is already drawn on the monitor screen. From the side it looks simple, but in fact, even for a simple brush, a user-made stroke will be processed about 7 (!) Times for a conveyor.

Example

So, each “stroke” undergoes at least 7 transformations. Is it a lot or a little? Let's look at a simple example. Imagine that we are painting with a brush of 300x300 pixels (300 * 300 * 4 = 312 KB) on an A4 300dpi format canvas (3508x2480 pixels).

The speed at which the artist can comfortably move the tablet's stylus (including zoom) is about 18 pixels per millisecond. Then (with a brush step of 10%), the average speed with which we must manage to draw the brush on the canvas will be 600 “strokes” per second.
')

Taking into account the size of the brush, it turns out that at each stage of the pipeline, the editor needs to process about 187 MB per second, which is more than 1.2 GB / s (!) For the entire conveyor. And this does not even take into account the fact that at almost all stages the conveyor does not just transform one region of 300x300, but takes two images, calculates their composition (at least one division by pixel) and writes the result back to memory. It turns out that even on such relatively small dimensions of the brush and the image, we are getting quite close to the theoretical limits of the speed of the RAM (10-20GB / s).

“WTF ?!”, an attentive reader will ask. “How does this work then at all ?!” Of course, many optimizations are applied at each stage of the pipeline. The whole area is divided into several streams, which, moreover, are executed in parallel, they also use SSE / AVX vector instructions, which allow processing up to 8 pixels simultaneously. In addition, in some particular cases (for example, one of the pixels is completely transparent or opaque), the composition degenerates into simple copying of bytes.

However, all these measures will help very little if we start talking about brushes of 1000 pixels or more. After all, if you increase the size of the brush by 3 times, the volume of data being processed will increase not by 3, but by 9 times! Handle 12 GB per second? Well, I do not! So how to be?

MIP texturing and detail levels

In three-dimensional graphics there is a well-known technique that allows you to increase the speed and quality of texturing objects that are far from the camera. The fact is that when the object is removed from the observer, it becomes smaller in size and, accordingly, its texture should also be scaled. To speed up this process, MIP texturing technology was invented. Its meaning lies in the fact that along with the texture itself, many of its reduced copies are stored: 2, 4, 8, 16, etc. time. And when the GPU needs to draw a smaller version of the texture, it no longer scans the original, but simply takes a previously prepared copy and works with it. This increases not only the speed of drawing objects, but also greatly improves their quality, since it is possible to use more accurate "slow" algorithms during pre-generation.

Levels of detail in Crete

Here it is worth considering one observation that if the user decides to draw on an image 10k wide in width, then most of the time he will use a scale of 20-15%. Otherwise, this image is technically not fit on the screen of its Full HD monitor, which is just as wide as 2k wide. We will use this fact!

Earlier this year, we made a prototype of the pending image rendering system for Krita. When the user draws a brush on the canvas, Crete is in no hurry to figure out all his actions. Instead, she takes a small copy of the image and draws all the strokes on it. Since the reduced copy is 2-4 times smaller than the original, drawing on it happens 4-16 times faster, and therefore there are no delays that distract the artist from his creative process. And since the artist cannot draw everything 100% of the time, Kryta will have plenty of time when it is possible in the background, without haste, to calculate the strokes on the original image.

Video showing 1k brush drawing on 8k image. Notice how a few seconds after the completion of the stroke comes a second wave of updates.



As a result, we solved the main task. Now we are not trying to process gigabytes of data in real time. In real time, we need to calculate only the preview, which will allow the user to work comfortably. And the original can be done later.

Preliminary findings

At the moment we have a ready-made prototype of the system of work with levels of detail. It works only one engine brushes, and then not with all the parameters. However, he already allows us to draw some conclusions:

1. We solved the main task: the user sees that he draws
2. Quality preview worthy. Problems arise only at the boundaries of update areas, where the interpolation algorithm used in openGl shaders is changing. Need to solve.
3. As a bonus, openGL 3.0 and above allows you to download / read information directly from a certain level of detail (GLSL 1.3: textureLod (). Ie we do not need to keep copies of all textures, just update a certain level, we tell the shader about it, and he reads directly
4. The main disadvantage of the approach is that this system has led to a serious complication of the Creta task scheduler. Need to solve a lot of problems. For example, two copies of the image (the original and a reduced copy) need to be synchronized regularly. And this is compounded by the fact that not all actions in Crete can be performed on a reduced copy. Many actions (so-called legacy-actions) require complete control over the image. They work like barriers: before their launch, all “forked” actions must be completed, and after they are completed, copies of the image must be synchronized.
5. Accordingly, if the user starts a legacy action, he will have to wait until all the background processing is complete. What can, of course, not very convenient. The only solution to this problem can only be reducing the number of legacy actions ...

Our Kickstarter project has already reached its minimum goal, so the next few months we will spend on the implementation of a complete system of work with levels of detail. And very soon, anyone can test drawing with huge brushes in Crete!

Links

Project page on Kickstarter: link
Group of Russian-speaking users in VK: http://vk.com/ilovefreeart
Official site: krita.org