[poppler] Radial shading in poppler

[Thomas Freitag]

Am 17.01.2011 20:13, schrieb Albert Astals Cid:
> A Dilluns, 17 de gener de 2011, Andrea Canciani va escriure:
>> On Mon, Jan 17, 2011 at 11:33 AM, Thomas Freitag
>>
>> <Thomas.Freitag at kabelmail.de>  wrote:
>>> Hi,
>>>
>>> It's once again me, this time without a patch :-). I just want to discuss
>>> some open issues that come into my mind after sleeping one night over it,
>>> and this don't really depends completely on radial shading in Splash,
>>> therefore I open a new thread:
>>>
>>> After digging really deep into radial shadings the last four weeks there
>>> are still a few open issues left:
>>>
>>> I. Gfx::doRadialShFill
>>> There were three different problems /  bugs which causes me to spend that
>>> enormous time implementing radial shading in Splash (probably wouldn't
>>> have done it, if I could estimate that before :-) ):
>>> a) Rendering artefacts because of overlapping circle clipping pathes in
>>> http://www.acquerra.com.au/poppler/img_0.pdf
>>> b) wrong calculation of extension range causing rendering regressions in
>>> https://bugs.freedesktop.org/attachment.cgi?id=41506
>>> c) wrong implementation of drawing larger extension circles causing
>>> rendering regressions in the same PDF
>>> These three problems cause rendering regression in each OutputDev which
>>> hasn't implented radialShadedFill by its own or if in case it has
>>> implemented it, it returns gFalse (this fits to CairoOutputDev, which
>>> uses its implementation just to setup some datastructure but let the
>>> rendering done by Gfx::doRadialShFill).
>>> I myself encounter three main output devices:
>>> 1. PSOutputDev implements radialShadedFill and therefore does not have
>>> the problems ahead (of course could have some other problems with it,
>>> but that's then a problem of its own implementation)
>>> 2. SplashOutputDev implements radialShadedFill now by its own and will
>>> not have these problems anymore after one of my patches will be
>>> committed. 3. CairoOutputDev will still have these problems.
>>> So have a quick look at CairoOutputDev. In my opinion there are two
>>> possible solutions for solving that:
>>> a) CairoOutputDev implements radialShadedFill by itself. I'm not deep
>>> enough in cairo to determine if this could be a possible way, perhaps
>>> with some hints from me and / or Andrea.
>> I'd be happy to try and help here. I don't know poppler internals, but
>> I should know cairo fairly well. I can already point out that cairo can
>> draw PDF type 2 shadings, but it requires the color function to be
>> piecewise linear.
I think, when cairo can draw PDF type 2 shadings, radialShadedFill 
should be implemented in CairoOutputDev. Regarding the restriction that 
the color function must be piecewise linear, see my comments below, 
where I explain how it is actual implemented in Gfx::doRadialShFill, so 
the actual implementation "makes" it piecewise linear :-)
>>> But if this would be too heavy and / or the rendering regressions with
>>> the first PDF (see here the wine glass) would be acceptable, I could
>>> suggest another way:
>>> b) I correct the bugs two and three in Gfx::doRadialShFill, the first one
>>> is unfortunately not correctable in Gfx. The second bug is simply
>>> correctable by a code fragment that already comes from cairo, which I
>>> already use adapted successfully in my both patches for splash, for the
>>> third bug I could adapt the different way of drawing larger extension
>>> circles of my patch from saturday (therefore, once again, Albert, this
>>> is an additional reason for regtest this older patch, too).
> In my opinion, the upper we fix the bugs, the better so they can shared
> amonsgt multiple implementations.
How I wrote, it's not such a great problem to fix it in 
Gfx::doRadialShFill, but why, when no one uses it anymore, and much mor 
important, how to test a bug fix for a piece of code that nobody uses.
>>> II. Speed an quality using radial shading in Splash:
>>> I uploaded last weekend two patches for it with two different
>>> implementation methods. The patch from sunday has definitely a better
>>> quality but in a very few cases sucks in rendering speed than the patch
>>> from saturday, which on the other hand has a poorer quality. Perhaps we
>>> can find somehow a threshold value on which we can decide, wether method
>>> should be used. This could be an additional reason to regtest both
>>> patches, but commit only the patch from sunday with the "undef"ed code
>>> so that it would be easy to implement this new behaviour later on.
>> I did some profiling and it looks like the problem is probably not in the
>> implementation of the parameter computation, but in the conversion of
>> the parameter to a color.
>> I profiled pdftoppm on http://www.acquerra.com.au/poppler/img_0.pdf and
>> found that about 37% of the time is spent in GfxAxialShading::getColor
>> and about 45% in GfxRadialShading::getColor.
Ohhhhh! If I had deeper look into it instead of estimate, I could 
probably see that by my own :). Thanks a lot, here You find a bottle 
neck which should be easy to solve, see explanations below.
>> I think that this can be improved by avoiding to fully evaluate the
>> function for each parameter value. Instead the function could be modified
>> to return a range in which a linear approximation is considered acceptable
>> (for example because the error would be below a chosen tolerance) and
>> getColor could cache this interval and avoid evaluating the function
>> whenever the parameter value is in its range.
Here a short explanation how Gfx implements all shading types, but here 
especially for radial shading, even if You probably already discovered that:
Gfx tries to determine the extension range for s (it's done wrong, how I 
already mentioned), and devide this interval through 256. Then it fills 
the area between this both vertexes with the average of the two colors 
of the vertexes.
Because t is linear dependant on s, we could not only say that Gfx 
estimates the colors are linear between 2 vertexes, but it estimates 
that the color is equal (!!!).

Therefore I suggest to implement and test the following approach:
We devide the intervall for t from [0..1] into 65536 equidistant pieces 
and suppose that the color in these pieces is linear dependant from t. 
We implement in GfxShading a cache with two new methods
a) GBool getCachedColor(int t, GfxColor *color);
which allocate an array of 65536 GfxColors, if not already done, and 
fills color with GfxColor[t] if it is already determined and returns 
gTrue, gFalse otherwise
b) void setCachedColor(int t, GfxColor *color)
set GfxColor[t] to the values of color (we could also allocate the array 
here, if You think, it is clearer.

Then we implement GfxRadialShading (and in GfxAxialShading, too) a new 
method getCachedColor(double t, GfxColor *color), which divides t in 
65536 equidistant pieces, get and if necessary set the cached colors of 
the two calculated vertexes and calculate the the resulting GfxColor in 
linear dependancy of the two vertixes.

This will limt the real calls of getColor to 65536 (I think, 65536 is a 
good value, estimating that in a square of 256 pts the new 
implementation, which calls getColor 256 * 256 times, is faster than the 
old method, but I myself would use a #define and try, if values less 
will still give a good quality), should have enough quality (see, that 
RGB has only 256 * 256 * 256 possible colors) and would be always faster 
than the old implementation (but this is a guess, perhaps we can live 
also with a smaller cache).

>> A similar approach could be used to fix the Cairo backend (and to improve
>> its quality, too), because if functions were able to provide piecewise
>> linear approximations of their colors, the approximation could be directly
>> fed into cairo in the form of color stops.
>>
>> Additional notes:
>> It looks like axial has the same performance problem as radial. You did not
>> have this performance problem with the bresenham rasterizer because
>> it evaluates the color function less times than the backward rasterizer.
Yes, of course axial shading has the same problem: the axial shading in 
Splash is from me, too, and has the same idea behind it :-)
>> In my profile, 70% of the time is spent in PostScriptFunction::transform.
>> It looks like it tries to do some caching, but it looks like it is not
>> doing it in an effective way (commenting the cache-related code in
>> PostScriptFunction::transform without even removing the cache data
>> structure and initialization elsewhere gives a small speed boost instead
>> of causing a slowdown). Replacing this cache with an interval-based cache
>> would probably be very effective in speeding up the Splash backend,
>> but it would still require additional code for the linear approximation
>> required by Cairo.
>>
>>> I need not necessarily do the work of I or II, but if the community means
>>> that I should do that, I suggest we open a new bug with this two PDF. I
>>> worked nearly every free minute on solving the problems in splash the
>>> last four weeks, and the patch is still not committed and there could of
>>> course be some work left (hopefully none or only a few), so I want to
>>> take time out, and therefore a bug report is reasonable.
>> I agree, I think that this is not actually the same bug but more of a
>> performance
>> glitch of Function (and/or of its usage).
>>
>> I can try to implement what I have proposed so far, but I might need
>> some guidance. Are there any objections/suggestions/complaints
>> regarding my plan?
>> In particular, is something in poppler relying on PostScriptFunction
>> being cached?
If we use the new method getCachedColor and call that in SplashOutputDev 
where axial and radial shading is implemented (so in the classes 
SplashAxialPattern and and SplashRadialPattern, no one else get problems 
with it. And You can use this new method in CairoOutputDev, too!

Thomas
> I have quite a few pdf where the caching of PostScriptFunction give (or at
> least gave when i introduced it) a substantial speed boost, so i'm quite
> hesitant to its complete removal (of course changing it for something better
> is cool :-))
>
> But no, there's nothing depending on it being cached.
>
> Albert
>
>> Andrea
>> _______________________________________________
>> poppler mailing list
>> poppler at lists.freedesktop.org
>> http://lists.freedesktop.org/mailman/listinfo/poppler
> _______________________________________________
> poppler mailing list
> poppler at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/poppler
>
> .
>