[cairo] downscaling capabilities

[Owen Taylor]

On Sat, 2008-04-19 at 09:35 -0400, Frédéric Plourde wrote:
> Thanks Bill for that "state of the art" about resampling techniques ;-)
> 
>    Just to answer your last question and to be sure we understand each 
> other, .. no, no... I was not thinking about MipMaping at all. I don't 
> think it's well suited to cairo/pixman neither.
> 
> I said that I was going to implement a simple low-pass filter (surely 
> gaussian) in space-domain... it means : a convolution kernel (just like 
> your "box filtering" that you mentionned). I just used another term to 
> refer to it.
> 
> However, the important thing is to adaptively adapt the size of that 
> gaussian convolution kernel to the scaling factor...
> let's keep in touch 'bout that.

I'm going to directly disagree here and suggest that for
CAIRO_FILTER_GOOD, the right algorithm is:

 - Scale down by factors of 2 repeatedly until you are less than 2 times
   the target scale factor
 - Bilinearly sample from the result

There are certainly disadvantages to this to this approach:

 - Works worse with non-uniform scales (that contract more in one
   direction than others)
 - Produces discontinuities at powers of two (this is why people use
   trilinear filtering)
 - Produces noticeable aliasing just above powers of two (another
   reason to use trilinear filtering)

It's not good filtering in any sense. But:

 - It has a cost that's O(num pixels in source), which is hard to do
   with convolution techniques. (Not going to say impossible, but
   hard, and especially hard for anything but a pure scale.)
 - It's easy to make fast in C and optimize with mmx/sse/etc.
 - It has good memory locality for the scale-down phase
 - It is easy to apply to transforms that aren't pure scales

There are certainly all sorts of better things you can do .. use better
ways of scaling down the image, use better sampling from the scaled
down image; there may be some interesting things to do with non-uniform
/ random sampling that would allow doing better than O(number of pixels
in source), but but given the constraints of real-time software
rendering (and CAIRO_FILTER_GOOD should be shooting for real-time) I'm
not sure that they are feasible. What we should worry about in the
short term is improving the worst case appearance (cairo does a really
bad job here) and keeping the worst case performance within bounds
(gdk-pixbuf does a really bad job with that.)

- Owen