On Tue, Jan 18, 2011 at 4:31 PM, Thomas Freitag
<[email protected]> 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
<[email protected]> 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).
