[poppler] Radial shading in poppler

[Andrea Canciani]

On Tue, Jan 18, 2011 at 4:31 PM, Thomas Freitag
<Thomas.Freitag at kabelmail.de> wrote:
> 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.

I this this solution is suboptimal both in quality and in performance.
65536 samples are a lot for simple gradients. You don't want to add 65536
color stops to a cairo gradient if they can actually be replaced with just two
or three.

Even worse, this kind of sampling doesn't provide good quality guarantees.
Example: a gradient whose color goes from red to blue more than
2*sampling_rate times would be drawn incorrectly.
This is basically the same as the aliasing issue from
https://bugs.freedesktop.org/show_bug.cgi?id=30887

Somebody might say that such a gradient is unlikely to happen in practice,
but this is almost exactly what Cairo does when the user asks for a radial
gradient whose color repeats indefinitely. Future versions of Cairo will
probably create a tree of stitched functions to avoid wasting space when
doing this on huge domains.

>
> 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).

I'm not sure what the relationship between the sampling frequency and the
number of different RGB colors is, but I might be missing something in
your analysis.

The only guarantee I can see coming from the sampling frequency is a
"spatial" guarantee: axial shading whose points have a distance of at most
65536 should be drawn correctly (almost exactly). Radial shadings with a
would have a similar condition (something like radial gradients whose
start and end circle have an Hausdorff distance of at most 65536 would
be drawn correctly).

I think that uniform sampling approach is the only viable option for
PostScriptFunctions (otherwise we would probably end up with a
dependecy to an interval arithmetic library), because they can perform
arbitrary computations and provide no continuity guarantee. For these
functions I would suggest using a sampling frequency based on the
distance of the two extreme objects, because it allows to choose the
desired quality/performance tradeoff and should always provide higher
quality or higher performance (or both) than a fixed sampling.

For all the other function types, using a variable-rate sampling provides
better quality and will usually require fewer function evaluations.

>
>>> 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!

(I'm about to suggest some changes. Please ignore the names I'm
suggesting, I don't think they are any good beside for the concept)

I would suggest making Gfx1DShading a superclass of axial and radial
shadings and move getColor to it. For the Cairo backend, a slightly
different function would be better: getLinearApproximation.
getColor could then just use direct function evaluation (just like
poppler/master) or use getLinearApproximation to find a valid
approximation to compute the color. It could then cache this
approximation.

Summarizing:

If we just want to fix the performance regression, it looks like
we can keep the direct function evaluation in most cases and
only perform the sampling (at a fixed rate or, preferably, at
a rate which depends on the relative position of the extreme
objects of the pattern) for PS functions.

If we also want to fix the Cairo backend, we need to be able to
create linear approximation of functions. For PS functions, the
sampling provides a straightforward way to generate a linear
approximation of the function. For other function types, it is
easy to compute a good linear approximation (sampled
functions are currently considered piecewise linear,
exponential functions can be sampled to keep the error within
a given threshold).


Andrea

>
> 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
>>
>> .
>>
>
>
> _______________________________________________
> poppler mailing list
> poppler at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/poppler
>