<br><br><div class="gmail_quote">On Tue, Feb 2, 2010 at 5:15 PM, <a href="mailto:LukasT.dev@gmail.com">LukasT.dev@gmail.com</a> <span dir="ltr"><<a href="mailto:lukast.dev@gmail.com">lukast.dev@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hello,<br>
<br>
I was inspecting some code in our auto brush paintop.<br>
<br>
The code path I wanted to optimize starts in<br>
KisAutoBrush::generateMaskAndApplyMaskOrCreateDab<br>
<br>
the important part is here:<br>
....<br>
for (int y = 0; y < dstHeight; y++) {<br>
for (int x = 0; x < dstWidth; x++) {<br>
<br>
double x_ = (x - centerX) * invScaleX;<br>
double y_ = (y - centerY) * invScaleY;<br>
double maskX = cosa * x_ - sina * y_;<br>
double maskY = sina * x_ + cosa * y_;<br>
<br>
if (coloringInformation) {<br>
}<br>
//cs->setAlpha(dabPointer, OPACITY_OPAQUE - d->shape-<br>
>interpolatedValueAt(maskX, maskY), 1);<br>
dabPointer += pixelSize;<br>
}<br>
<br>
<br>
You can see that we compute the brush mask rotated and the mask is computed<br>
with function interpolatedValueAt(maskX, maskY);<br>
<br>
The interpolation function computes bilinear interpolation of values from<br>
function KisCircleMaskGenerator::valueAt(double x, double y).<br>
<br>
So I decided to not to use the interpolatedValueAt(maskX, maskY ) but using<br>
directly the KisCircleMaskGenerator::valueAt(double x, double y). The speed is<br>
like 4x faster drawing now. We don't call valueAt 4-times per pixel but just<br>
once.<br>
<br>
But the result is somehow shifted by 1px or so. Now the question is if the<br>
patch introduces the bug or the bug was present somewhere and this fix just un-<br>
hides it.<br></blockquote><div><br>Maybe, there is some bug in the interpolation code?<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
I suppose this patch as performance fix and as fix towards sub-pixel precision.<br>
I suppose that linear interpolation just introduced the rounding errors and<br>
that's why the results differs about 1 pixel. I did not take subpixel precision<br>
away because I did not remove any code which would do it for us.<br>
<br>
There is a reason why interpolation was used. The function valueAt a long long<br>
time ago used to take integer inputs like you can see<br>
<a href="http://websvn.kde.org/trunk/koffice/krita/image/kis_auto_brush.cpp?r1=746489&r2=746490&pathrev=788424&" target="_blank">http://websvn.kde.org/trunk/koffice/krita/image/kis_auto_brush.cpp?r1=746489&r2=746490&pathrev=788424&</a><br>
<br>
Cyrille supposed that it is the reason interpolatedValueAt was used for. To<br>
break x and y into integer coordinates, compute the values at integer<br>
coordinates and interpolate between them.<br>
<br>
Here is the patch (git, but it is one line ;) )<br>
<a href="http://lukast.mediablog.sk/patches/dont-interpolate-to-not-call-%0AvalueAt-4times.patch" target="_blank">http://lukast.mediablog.sk/patches/dont-interpolate-to-not-call-<br>
valueAt-4times.patch</a><br></blockquote><div><br>I'll try to test it tonight. <br></div><div><br><br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Here are the results:<br>
<a href="http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-new-randomLines.png" target="_blank">http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-new-randomLines.png</a><br>
<a href="http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-old-randomLines.png" target="_blank">http://lukast.mediablog.sk/i/AutoBrush_70px_rotated-old-randomLines.png</a><br>
<br>
Could you please test with and without patch and report issues?<br>
<br>
What I want to implement futher:<br>
o There are settings where the brush is symmetrical so I plan to compute 1/4<br>
of the brush mask<br></blockquote><div><br>Btw, all the brushes are center-symmetrical. And the brushes before rotation are axis-symmetrical.<br>So this ca be generalized for all the brushes: <br><br>axis-symmetrical (1/4 of the brush):<br>
0<i<width/2; 0<j<height/2;<br>pixelAt(i,j) -> pixelAt(width-i, height-j)<br>pixelAt(i,j) -> pixelAt(width-i, j)<br>pixelAt(i,j) -> pixelAt(i, height-j)<br><br>center-symmetrical (1/2 of the brush):<br>
0<i<width/2; 0<j<height;<br>pixelAt(i,j) -> pixelAt(width-i, height-j)<br><br> <br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
o Lookup table for atan2 ( lookup table for valueAt??? :) seems also possible)<br></blockquote><div><br>I think you need to get the maths equation for the valueAt, or approximate your own first. This can ease the following optimizations much.<br>
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.<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
o move the rotation to the end of the pipeline so we will be computing the<br>
brush mask unrotated and rotate when compositing<br></blockquote><div><br>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.<br>
<br> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
o if that's not enough mip mapping (like we do in gbr brush)<br></blockquote><div><br>As a last resort only. It is quite expensive as well.<br> </div><br clear="all"></div><br>-- <br>Dmitry Kazakov<br>