[poppler] Radial shading in poppler

[Thomas Freitag]

Am 18.01.2011 18:40, schrieb 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).
>
Just a short answer, Andrea: I can follow Your remarks in  theorie, even 
if my mathematical education is a lot of years ago and this was not my 
main subject, and Your approach should be followed, so please keep me 
informed. I don't know, if we need to wait until Albert commit my last 
patch, at least we need it, when I have to call a different method than 
getColor.
Just one short additional note: perhaps my practical approach was 
explained to short, of course I woudn't want to cache 65536 colors in 
every case. In nearly almost cases we will not have either 65536 points 
in t-axis, so we aren't able to show that accuracy.
One last hint: In case of shading extension probably just caching the 
colors at t = t0 and t = t1 could increase perfomance for complex 
postscript functions.

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