Krita 2.9 (pre-alpha): Updated Fill Tool!

Preface

The Fill Tool was present in Krita since the ancient days. Its was first implemented back in 2004, and since then there were only minor changes to the algorithm it used. Now we are glad to announce a major update of it!

The old implementation used a, though a bit optimized, but still conventional, flood-fill algorithm that iterated through all the pixels recursively using a huge array as a map to store which pixels were visited and which not. It had two obvious drawbacks: it ate your memory (~100MiB for a map for an 10k x 10k image) and it was rather slow. The new algorithm is free from these disadvantages!

Scanline Flood Fill Algorithm

The new algorithm uses larger entities than just a single pixel. It uses "scanlines", which is effectively a chunk of a row of the image. The process of filling looks like a game. Several scanlines traveling throughout the image and checking or filling the pixel data. Each scanline can travel in either upward or downward direction. When two scanlines of opposite directions meet, they eat each other and both disappear! The process continues while there is at least one scanline alive :)

The rules for breeding and eating scanlines are a bit complicated, but they guarantee that not a single pixel will ever be visited twice! And that is without keeping any map of visited pixels, and therefore without oppressing your RAM! The experiments we conducted showed that to flood-fill an image of 10k by 10k pixels one would need only about 1MiB of memory! Just compare that to the 100MiB demanded by the conventional algo!

Real Performance Tests

The tests showed that the performance of the new Fill Tool greatly depends on whether the user needs some complex compositioning or not. That is why we introduced two new modes for the Fill Tool:

• Advanced Mode — the mode supporting all the features of the tool, such as applying a selection, rendering the result with a user-supplied composite op, growing or feathering the selection area. This mode works about 1.4 times faster than the old implementation;


• Fast Mode — just fill the area with color! No compositioning or selections are supported, but thanks to these limitations it is capable of up to 2 times better performance than the Advanced Mode. Which is almost 3 times faster that the old conventional algorithm!

And, of course, these speed benefits are nothing in comparison to the economy of memory we achieve!

Conclusion

The new Flood Fill algorithm is already present in Krita master and is available for all the users having Krita Lime [0] installed! Just update and have fun with your painting!

And yes, this work would be impossible without the support from Krita Foundation! Become a sponsor of the Krita Project and help us move the painting world further!

Monthly Donation through Paypal Krita Development Funding Bronze : €5,00 EUR - monthly Sliver : €10,00 EUR - monthly Gold : €25,00 EUR - monthly Platinum : €100,00 EUR - monthly Diamond : €250,00 EUR - monthly

One-time donation through Paypal

 

[0] -  http://dimula73.blogspot.ru/2013/05/krita-lime-ppa-always-fresh-versions.html

PS:

Thanks Timothée Giet for a nice title image!

Krita: new extended tablet support!

Traditionally Krita supported various types of tablets on Linux, but this support was limited to the tablets handled by wacom driver. The list of the supported hardware included (obviously) all the Wacom-branded tablets and some rare species that were trying to resemble the branded devices. It was the best that one could get form the Qt's tablet code. From now on Krita can also work with all the devices which are handled by the evdev X11 driver!

The list of the devices supported by evdev is really vast. It includes such not-very-expensive brands like Monoprice, Bosto, Huion and Genius. By the moment we tested Krita on two devices: Bosto 19MA [0] and Genius G-Pen 560. Both work fine with Krita and have really nice pressure support! Right now we are also working on support for the Huion tablet supplied by huiontablet.com to the Krita project as well!

Bosto kingtee 19MA now works with Krita!

So if you have a tablet device which used to refuse to work with Krita on Linux, test it now!

I also did a small cross-test of my old Wacom Graphire2 device and Genius G-Pen 560. What I noticed is that the lines generated by the Wacom tablet are more stable and smooth, whereas the lines by the Genius tablet are a bit dizzy. I don't know what is the exact reason for it, but I have a feeling that Wacom does some internal filtering of the coordinates generated by the hardware, which gives us better lines. Anyway, even if you own this Genius device, Krita allows you to workaround the issue. Just enable Weighted Smoothing painting algorithm and it will produce the results just like Wacom does!

And if you would like to know the technical details about why Qt's tablet code supports wacom-driver-based tablets only...

Qt's code doesn't fully support the interface of the XDeviceMotionEvent. Qt expects that the values of all six axes of the tablet will be sent to the client in each event. This is true for wacom driver, but it is not guaranteed to be true for other XInput devices. The motion event can also send the values that changed since the last event only. It even has special fields for that:

typedef struct
    {
    /* ... skipped ... */
    unsigned char axes_count;
    unsigned char first_axis;
    int           axis_data[6];
    } XDeviceMotionEvent;

axes_count field tells us how many axes are really delivered to the client and first_axis tells to what absolute axis the first element of axis_data corresponds to.

Now Krita can handle that effectively, as well as recognize to what sensor each axis is assigned to! [1]

[0] - https://groups.google.com/forum/#!topic/bosto-user-group/sL_O4VoopVk
[1] - unlike Gimp's way, where the user must manually investigate to which sensor each axis is connected to ;P

Krita Lime: Localization Support

After some time of really hard work we are happy to announce that our Krita Lime packages now support localization!

If you want to see Krita in your own language, just install a corresponding package...

apt-get install krita-testing-l10n-[your_language_id]

... and run Krita!

If you want to see Krita is a language that differs from your system one, type

KDE_LANG=[your_language_id] krita

Happy painting with Krita! :)

PS:
And for some languages the help of translators is really needed! Join our KDE translators team on l10n.kde.org and we will move KDE forward together! :)