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
|
One-time donation through Paypal |
[0] - http://dimula73.blogspot.ru/2013/05/krita-lime-ppa-always-fresh-versions.html
PS:
PS:
Thanks Timothée Giet for a nice title image!
This sounds really awesome! :3
ReplyDeletegood job as always Dmitry. tht looks very promising. i have to test it.
ReplyDelete