Created attachment 11798 [details] radial gradient test case The radial gradient code in Ghostscript produces rendering artifacts which would not occur with a better algorithm. A initial implementation is attached. Refer to input file <circle2.pdf>. This should produce a circle with radial shading from black at the centre to white at the circumference. Render it to a 48-bit PNG at resolution 1440x1440 (attached as <circle-gs.png>): gs -dSAFER -dBATCH -dNOPAUSE -sDEVICE=png48 -r144 -sOutputFile=circle-gs.png circle2.pdf This appears acceptable to the eye, but some basic image processing reveals several problems. The attached file <circle-gs-n.png> is the result of applying a Sobel edge-detection filter to it. (This is the same algorithm used by the gimp-normalmap program (<https://code.google.com/p/gimp-normalmap/>), but allowing for 16-bit colour resolution in the input.) After applying the filter, it is immediately apparent that the supposedly circular gradient is actually composed of an inner ring of 64 triangular patches, and an outer ring of 128 quadrilateral patches. The shading of these is not radial, but linear, as shown by the clearly visible edges between them. The filter makes obvious a significant gap between the inner and outer rings. There are other strange anomalies apparent in the eight patches immediately adjacent to the x-axis; it is not clear what the cause of these is. A similar problem has been reported for MuPDF: http://bugs.ghostscript.com/show_bug.cgi?id=694084 "I've tried an adaptive calculation of the number of segments based on the matrix scaling factor and gradient radius... the problem with this approach is that adjacent shadings (where the inner radius of one shading touches the outer radius of another) end up having different number of segments, and this leads to cracks between them." "The ideal approach would be to render radial shadings directly without tesselating them into triangles." We see exactly this problem of "different numbers of segments, leading to cracks" in the radial gradient produced by Ghostscript; this probably reflects a shared codebase. As stated, an actual radial gradient would be preferable to the existing tesselated implementation. A possible problem is that the obvious method of shading each pixel according to its radius from the center, would involve a per-pixel square root computation, and would therefore be unacceptably slow. The attached file <gradient.cc> solves this problem. It is implemented in terms of libPNG (<http://www.libpng.org/pub/png/libpng.html>), but presumably the same algorithm would be applicable to Ghostscript and MuPDF. This program depends on the following principles. First, it uses a pre-computed table of shade values, which are indexed according to the square of the pixel radius, thus avoiding the need for any square root calculation. Second, it computes successive pixel radii via the formula [ (x + 1)^2 = x^2 + 2*x + 1 ] -- thus avoiding even an integer multiply (presumably the compiler is smart enough to code "multiply by two" as "shift left"). The render loop contains no floating point computation at all. Performance seems to be not much worse than the existing implementation. The attached file <circle-sq.png> is the output of this program; the radius of the circle can be adjusted using the option "-r": $ gradient -r 360 circle-sq.png The file <circle-sq-n.png> is the result of applying the same edge filter to it. It clearly contains none of the artifacts produced by the current implementation, and is in every way an improvement. Hopefully, these edge-filtered images make clear the problems with the current Ghostscript radial gradient code. Please consider basing a new implementation on the algorithm I have provided.
Created attachment 11799 [details] Ghostscript render of radial gradient to PNG
Created attachment 11800 [details] edge filter applied to Ghostscript output
Created attachment 11801 [details] output to PNG of proposed new radial gradient algorithm
Created attachment 11802 [details] edge filter applied to new algorithm output
Created attachment 11803 [details] proposed new algorithm for radial gradients
Its not my area, but I'll make some general observations... If the artefacts are not visible to the eye, then I doubt we're going to want to change our current implementation, unless there's a very good reason. Improved performance would be a good reason, but you haven't suggested that this would be faster, indeed you say its 'not much worse' which isn't promising. Have you tried a comparison at a more realistic resolution, such as 600 dpi ? Remember, unlike MuPDF, Ghostscript's primary focus is on printing. The 'new algorithm' output does produce fewer radial steps in the blend, whcih is very nice, but then the Ghostscript output is at 144 dpi, which is rather coarse, so perhaps the stepping is to be expected. I suspect that Ghostscript deliberately degenerates shadings into trapezoids (or triangles) for a number of reasons (Ray might like to comment on this more authoritatively). One reason is performance, calculating and touching each pixel in a gradient is slow, especially as the resolution increases, so visually acceptable approximations are vital. Shadings are slow enough as it is. Also decomposing into trapezoids or triangles is the bottom level implementation in the graphics library, we don't generally deal with pixels (obviously the trapezoid or triangle rendering does). Hardware rendering implementations usually prefer to render triangles for instance. A patch in terms of libpng really isn't helpful, I don't know what half this code is doing, and there are NO comments whatever, so it would take me quite some time to find out what is actually going on if I were tasked with implementing it. I think this is really Ray's area, I imagine he'd like to comment as well. NB I've moved this from 'normal' to 'enhancement' as this is a proposed enhancement and not a bug.
Created attachment 11806 [details] 6000x6000 Ghostscript render
Created attachment 11807 [details] edge-filter 6000x6000 Ghostscript render
Created attachment 11808 [details] 6001x6001 new algorithm render
Created attachment 11809 [details] edge-filter 6001x6001 new algorithm render
> If the artefacts are not visible to the eye, then I doubt we're going > to want to change our current implementation, unless there's a very > good reason. They are visible; the output of my algorithm is noticeably smoother. The edge-filtering just makes it obvious WHY. > Improved performance would be a good reason, but you haven't suggested > that this would be faster, indeed you say its 'not much worse' which > isn't promising. It seems to be about 30% slower, independent of resolution. This is just an initial version; there are probably things that could be done to speed it up. > Have you tried a comparison at a more realistic resolution, such as > 600 dpi ? Remember, unlike MuPDF, Ghostscript's primary focus is on > printing. See new attachments. As before, the "gs" files are the product of Ghostscript, and the "sq" files are from my program. > The 'new algorithm' output does produce fewer radial steps in the > blend, whcih is very nice, but then the Ghostscript output is at 144 > dpi, which is rather coarse, so perhaps the stepping is to be > expected. The 600dpi version (attached) shows exactly the same artifacts. In any case, what's relevant is the image resolution in dots, not dots-per-inch. > I suspect that Ghostscript deliberately degenerates shadings into > trapezoids (or triangles) for a number of reasons (Ray might like to > comment on this more authoritatively). The MuPDF bug said "the ideal approach would be to render radial shadings directly without tesselating them into triangles", which suggests that the issue is more one of implementation, rather than deliberate design. > One reason is performance, calculating and touching each pixel in a > gradient is slow, especially as the resolution increases, so visually > acceptable approximations are vital. Shadings are slow enough as it > is. Touching each pixel seems unavoidable, if it's going to have any shade at all. I kept the per-pixel computation to a minimum -- a few integer additions and a table lookup. > Also decomposing into trapezoids or triangles is the bottom level > implementation in the graphics library, we don't generally deal with > pixels (obviously the trapezoid or triangle rendering does). Hardware > rendering implementations usually prefer to render triangles for > instance. Decomposition into edge-matching triangle and quadrilateral patches is a significant calculation in itself, which is probably why my initial implementation comes within 30% of the existing one. As far as hardware rendering is concerned, it's probably worth considering texture maps. Where that's not available, other methods are required. > A patch in terms of libpng really isn't helpful, It's helpful in that it runs and is available for testing NOW. > I don't know what half this code is doing, and there are NO comments > whatever, so it would take me quite some time to find out what is > actually going on if I were tasked with implementing it. The entire algorithm is contained in the three functions mkgradient(), getpx(), and circle(), for a total of 36 (nonblank) lines of code. The only libPNG dependency therein is set_pixel(), which is surely self-explanatory. The significant features of the algorithm were explained in my first post; two nested for-loops along the x- and y-axes presumably don't require comment. Whatever other explanation is needed, I'm happy to provide. > NB I've moved this from 'normal' to 'enhancement' as this is a > proposed enhancement and not a bug. The same problem in MuPDF qualified as a "bug". Why is this different?
As Ken mentions, indeed, the choice to tesselate the shading into linear color trapezoids and triangles is intentional and some work has been done to make the choice of vertices optimal to minimize 'gap' effects and double painting of pixels. The use of linear color traps/triangles reduces the size of the 'clist' display list and can be used with hardware Gouraud shaders (some of our high end customers have ASIC's to accelerate basic rendering). Also Ghostscript implements the smoothness control of PS and PDF (SM in a PDF ExtGState dictionary). This allows users to trade off the quality vs speed of shading (gradient) fills.
(In reply to Ian Bruce from comment #11) > > If the artefacts are not visible to the eye, then I doubt we're going > > to want to change our current implementation, unless there's a very > > good reason. > > They are visible; the output of my algorithm is noticeably smoother. I don't disagree, I'm just pointing out that 'good enough, and fast' often trumps' better but slow'. > > Improved performance would be a good reason, but you haven't suggested > > that this would be faster, indeed you say its 'not much worse' which > > isn't promising. > > It seems to be about 30% slower, independent of resolution. 30% is a lot, shadings are a significant overhead already (though possibly not specifically radial shadings). > > Have you tried a comparison at a more realistic resolution, such as > > 600 dpi ? Remember, unlike MuPDF, Ghostscript's primary focus is on > > printing. > > See new attachments. As before, the "gs" files are the product of > Ghostscript, and the "sq" files are from my program. I was really more interested in a performance comparison at the higher resolution, which you gave above. > The MuPDF bug said "the ideal approach would be to render radial > shadings directly without tesselating them into triangles", which > suggests that the issue is more one of implementation, rather than > deliberate design. For MuPDF possibly this is true, but this is a Ghostscript report. > > A patch in terms of libpng really isn't helpful, > > It's helpful in that it runs and is available for testing NOW. Well it doesn't help *me* because I don't understand it. > The entire algorithm is contained in the three functions mkgradient(), > getpx(), and circle(), for a total of 36 (nonblank) lines of code. With no comments..... > The significant features of the algorithm were explained in my first > post; two nested for-loops along the x- and y-axes presumably don't > require comment. Whatever other explanation is needed, I'm happy to > provide. Its been years since I wrote any C++, and I can't make head or tail of this. Possibly if it was commented I could. On the other hand, its not likely ot be me who does anything with it..... > > NB I've moved this from 'normal' to 'enhancement' as this is a > > proposed enhancement and not a bug. > > The same problem in MuPDF qualified as a "bug". Why is this different? Its clearly an enhancement, perhaps the MuPDF developers don't care about differentiating, I like to keep things tidy in the Ghostscript world.
Unfortunately, the "new algorithm" cannot be used directly in Ghostscript, but it requires a lot of extra development, which would far exceed the complexity of the submitted code. For instance, Ghostscript has the current transformation matrix, banding, and clipping. The submitted code doesn't have anything like this. If Ghostscript will ever add radial gradients to the set of supported primitive operations, coding something similar won't be too difficult. We value every contribution and permanently keep every bug report, but we would also like to reduce the number of open bug reports to focus on more urgent issues.