Your comments to [Bug 408222]

Sun Jun 9 09:55:30 BST 2019

Am 09.06.2019 00:41 schrieb David Hurka:
> Hi,
> 
> I knew Bresenham only from CNC controllers, and spotted it in QPainter
> documentation.

That's interesting, have you done the CNC machine implementation on your 
own?

> Could you maybe explain how it can be used for minification filtering, 
> and how
> it would be different to nearest-neighbour? (Focusing on Cairo.) Terms
> Bresenham and Filtering don’t yield results in DuckDuckGo...

I have little experience and should better not try to explain but rather
refer to wise articles :) There's an "Image Scaling With Bresenham"
by Thiadmer Riemersma on Dr. Dobbs and a related errata [1].
The actual implementation in Splash is
Splash::scaleImageYdXd [2], Splash::scaleImageYdXu [3],
Splash::scaleImageYuXd [4], Splash::scaleImageYuXu [5].

I haven't checked them in detail and don't know how related article
and implementation are. Implementation originates from xpdf. Seems 
there's
no version control history for xpdf, and that's a pity, because looking 
at the
original authors commit comments would have been interesting.

Afaikt, the competing nearest neighbor implementation in the glib 
frontend is
FAST_NEAREST_SCANLINE [6] and FAST_NEAREST_MAINLOOP_INT [7]
from the pixman library (cairo delegates to pixman for that stuff).

I'm tempted to do a prototype implementation of pixmans nearest neighbor
in Splash, mainly for curiosity/educational purpose. Don't know how much
sense this makes. Would you be interested to join?

[0] http://www.drdobbs.com/image-scaling-with-bresenham/184405045
[1] https://www.compuphase.com/graphic/scale1errata.htm
[2] 
https://gitlab.freedesktop.org/poppler/poppler/blob/master/splash/Splash.cc#L4220
[3] 
https://gitlab.freedesktop.org/poppler/poppler/blob/master/splash/Splash.cc#L4463
[4] 
https://gitlab.freedesktop.org/poppler/poppler/blob/master/splash/Splash.cc#L4613
[5] 
https://gitlab.freedesktop.org/poppler/poppler/blob/master/splash/Splash.cc#L4775
[6] 
https://gitlab.freedesktop.org/pixman/pixman/blob/master/pixman/pixman-inlines.h#L328
[7] 
https://gitlab.freedesktop.org/pixman/pixman/blob/master/pixman/pixman-inlines.h#L442

Cheers Tobias

> On Friday, 7 June 2019 17:47:36 GMT Tobias Deiminger wrote:
>> Hi David,
>> 
>> Am 07.06.2019 15:37 schrieb David Hurka:
>> > Hi Tobias,
>> >
>> > On Friday, 7 June 2019 08:15:06 GMT Tobias Deiminger wrote:
>> >> Am 05.06.2019 09:36 schrieb David Hurka:
>> >> > Evince and Okular have to request pixmaps at some time, and have to
>> >> > [...]
>> >> > offset, hitting or missing pixels differently, so the input for
>> >> > [...]
>> >>
>> >> Do you mean it like that (arbitrary guessed examples):
>> >> page.renderToImage( dpiX, dpiY, 0.1000, 0.1000, width, height, ...);
>> >> //
>> >> looks better
>> >> page.renderToImage( dpiX, dpiY, 0.1001, 0.1001, width, height, ...);
>> >> //
>> >> looks worse
>> >
>> > Yes, that’s what I mean.
>> 
>> Ok, but then changing these offsets happens all the time,
>> during one single Okular session. Okular always requests
>> a whole page or a crop region from it, determined by where
>> the viewport is and what's the current zoom level.
>> It never tries to extract a single object like an image or an
>> annotation.
>> So if a) is right, image quality would change frequently while
>> you scroll/zoom around.
>> 
>> >> At a first glance I don't see subpixel stuff when looking
>> >> at how Splash::drawImage fills Splash::bitmap, but I'm
>> >> far from understanding it completely.
>> >
>> > Hmm, what are you thinking about? RGB/VRGB/... subpixel rendering?
>> > That’s not
>> > what I mean.
>> 
>> No, just tried to guess your guess, maybe something
>> about denormalization :-) But I see that's not the case (is it?).
>> 
>> > What I mean here would be a difference between Evince and Okular, not
>> > between
>> > Cairo and Splash.
>> >
>> >> > So, Evince probably uses Cairo, which uses nearest neighbour in the
>> >> > case of
>> >> > the screenshot, and Okular probably uses Splash, which apparently does
>> >> > not
>> >> > only minification filtering.
>> >>
>> >> Afaikt it's like this:
>> >>
>> >> Qt5 frontend: In Splash::scaleImage, if an image is scaled down
>> >> relative
>> >> to its embedded size, or scaled up by more than 400% it uses
>> >> bresenham.
>> >> Else, if interpolation is explicitly wanted by the PDF image XObject,
>> >> or if image is scaled in the range of 100% .. 400%, it uses bilinear
>> >> interpolation.
>> >>
>> >> Glib/cairo frontend: CairoOutputDev::getFilterForSurfac has same
>> >> logic.
>> >> It chooses between CAIRO_FILTER_NEAREST (= nearest neighbor)
>> >> if scaled down, or scaled up by more than 400%. It use
>> >> CAIRO_FILTER_GOOD (= box filter when < 75%, bilinear otherwise) for
>> >> explicitly wanted interpolation or when scaled up in the range of 100%
>> >> .. 400%.
>> >
>> > Ok, if both work the same, the effect probably comes from somewhere
>> > else.
>> 
>> They *do* differ in scaling algorithm (bresenham vs. nearest neighbor,
>> bilinear vs. mostly bilinear). But they share the same logic to
>> decide if a cheap or expensive algorithm shall be used. For the
>> bug documents, we mostly see bresenham at work.
>> 
>> I think it could indeed make a visible difference.
>> 
>> >> > At least here I’m sure:
>> >> > With nearest neighbour, the glyph edges are pixel edges. But with
>> >> > magnification filtering, the pixel edges are widened to neighbouring
>> >> > rendered
>> >> > pixels, so the glyph edge becomes wider (smeared).
>> >>
>> >> Guess glyphs are another story again. Both Qt5 and Glib frontend (via
>> >> cairo)
>> >> use freetype to render glyhps. But render settings may be different,
>> >> don't know how they differ.
>> >
>> > I didn’t mean freetype outlines or such. I said glyphs because I don’t
>> > know
>> > whether these signs may be called letters. I don’t know the language,
>> > although
>> > surrounding people think that when they see it on my screen. ;)
>> 
>> *gg*
>> 
>> >> > Cheers, David
>> >>
>> >> After all, I see there's a subtle difference in the images in bug
>> >> 408222, but
>> >> honestly I couldn't even tell what looks better by only staring at it,
>> >
>> > Yes, in the screenshot sections I have uploaded, the g-shaped glyph
>> > looks
>> > clearly better in Evince, but other glyphs look better in Okular.
>> >
>> > Now it would be interesting whether the displayed zoom is close to the
>> > native
>> > resolution of the scan. If so, the effect would much certainly be
>> > caused by
>> > a).
>> 
>> pdfimage from poppler tools can give more insight here:
>> 
>> $ pdfimages -list test-1.pdf
>> page   num  type   width height color comp bpc  enc interp  object ID
>> x-ppi y-ppi size ratio
>> ----------------------------------------------------------------------------
>> ---------------- 1     0 image    1894  2798  gray    1   8  jpeg   no
>>   8  0 301   300  285K 5.5%
>> 
>> I.e., the image inside test-1.pdf has good resolution,
>> and size is 1894 x 2798. We can also extract the image
>> and view it to talk about the original quality:
>> 
>> $ pdfimages -all test-1.pdf ./ && gwenview ./-000.jpg
>> 
>> Because the rather big size, the images is actually downscaled
>> when viewing it in Okular (at least on a non-HiDPI screen).
>> For me, upscaling starts only when I view it
>> at document zoom levels > ~390%.
>> 
>> >> and I would never have noticed a bug-worthy difference on my own.
>> >
>> > Same for me, if a PDF is hard to read (like because it has serif
>> > fonts), I
>> > copy the text to Kate and reat it there. But I usually don’t read
>> > scanned
>> > PDFs.
>> >
>> >> Shall we proceed there at all? Do we have means to quantify rasterized
>> >> image quality?
>> >
>> > I don’t know such means. A good workarround would possibly be to
>> > provide a
>> > zoom mode “Optimal for Scan”, which zooms to the native resolution of
>> > the scan
>> > (and makes sure that a) does not happen).
>> 
>> I think before taking measures we should figure out
>> if there is actually a problem for > 1 users.
>> But how can we figure it out?
>> 
>> Cheers Tobias