Patch for speeding up the painting of the autobrush

[Dmitry Kazakov]

On Tue, Feb 2, 2010 at 5:15 PM, LukasT.dev at gmail.com
<lukast.dev at gmail.com>wrote:

> Hello,
>
> I was inspecting some code in our auto brush paintop.
>
> The code path I wanted to optimize starts in
> KisAutoBrush::generateMaskAndApplyMaskOrCreateDab
>
> the important part is here:
> ....
>    for (int y = 0; y < dstHeight; y++) {
>        for (int x = 0; x < dstWidth; x++) {
>
>            double x_ = (x - centerX) * invScaleX;
>            double y_ = (y - centerY) * invScaleY;
>            double maskX = cosa * x_ - sina * y_;
>            double maskY = sina * x_ + cosa * y_;
>
>            if (coloringInformation) {
>            }
>            //cs->setAlpha(dabPointer, OPACITY_OPAQUE - d->shape-
> >interpolatedValueAt(maskX, maskY), 1);
>            dabPointer += pixelSize;
>        }
>
>
> You can see that we compute the brush mask rotated and the mask is computed
> with function interpolatedValueAt(maskX, maskY);
>
> The interpolation function computes bilinear interpolation of values from
> function KisCircleMaskGenerator::valueAt(double x, double y).
>
> So I decided to not to use the interpolatedValueAt(maskX, maskY ) but using
> directly the KisCircleMaskGenerator::valueAt(double x, double y). The speed
> is
> like 4x faster drawing now. We don't call valueAt 4-times per pixel but
> just
> once.
>
> But the result is somehow shifted by 1px or so. Now the question is if the
> patch introduces the bug or the bug was present somewhere and this fix just
> un-
> hides it.
>

Maybe, there is some bug in the interpolation code?


>
> I suppose this patch as performance fix and as fix towards sub-pixel
> precision.
> I suppose that linear interpolation just introduced the rounding errors and
> that's why the results differs about 1 pixel. I did not take subpixel
> precision
> away because I did not remove any code which would do it for us.
>
> There is a reason why interpolation was used. The function valueAt a long
> long
> time ago used to take integer inputs like you can see
>
> http://websvn.kde.org/trunk/koffice/krita/image/kis_auto_brush.cpp?r1=746489&r2=746490&pathrev=788424&
>
> Cyrille supposed that it is the reason interpolatedValueAt was used for. To
> break x and y into integer coordinates, compute the values at integer
> coordinates and interpolate between them.
>
> Here is the patch (git, but it is one line ;) )
> http://lukast.mediablog.sk/patches/dont-interpolate-to-not-call-
> valueAt-4times.patch<http://lukast.mediablog.sk/patches/dont-interpolate-to-not-call-%0AvalueAt-4times.patch>
>

I'll try to test it tonight.




> Here are the results:
> http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-new-randomLines.png
> http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-old-randomLines.png
>
> Could you please test with and without patch and report issues?
>
> What I want to implement futher:
> o There are settings where the brush is symmetrical so I plan to compute
> 1/4
> of the brush mask
>

Btw, all the brushes are center-symmetrical. And the brushes before rotation
are axis-symmetrical.
So this ca be generalized for all the brushes:

axis-symmetrical (1/4 of the brush):
0<i<width/2; 0<j<height/2;
pixelAt(i,j) -> pixelAt(width-i, height-j)
pixelAt(i,j) -> pixelAt(width-i, j)
pixelAt(i,j) -> pixelAt(i, height-j)

center-symmetrical (1/2 of the brush):
0<i<width/2; 0<j<height;
pixelAt(i,j) -> pixelAt(width-i, height-j)



> o Lookup table for atan2 ( lookup table for valueAt??? :) seems also
> possible)
>

I think you need to get the maths equation for the valueAt, or approximate
your own first. This can ease the following optimizations much.
E.g. you will be able to build n-dimensional spline for this function, that
will be much more efficient than a lookup table, or use tan(angle) instead
of angle.


> o move the rotation to the end of the pipeline so we will be computing the
> brush mask unrotated and rotate when compositing
>

Isn't rotation included into valueAt? If not, i think it's bad. Constructing
the spline will take care for all the sin/cos calls as well.



> o if that's not enough mip mapping (like we do in gbr brush)
>

As a last resort only. It is quite expensive as well.



-- 
Dmitry Kazakov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.kde.org/pipermail/kimageshop/attachments/20100202/d5d881f1/attachment.htm