[cairo] downscaling capabilities

[Frédéric Plourde]

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.
-fred-


Bill Spitzak a écrit :
> I'm not sure about calling this "prefiltering". I think it is 
> generally done in a single step and that step replaces the current 
> bilinear filtering. In a general sense:
>
> For a given output pixel, the center point of that pixel (X+.5, Y+.5) 
> is back-transformed to the input image location, and then .5 is 
> subtracted from each to get the source x,y.
>
> Also the derivatives of this back-transformation are used to figure 
> out two vectors (these vectors when drawn from the x,y go to the 
> back-transform of X+1,Y and X,Y+1)..
>
> Then "some algorithim" is used to assign weights to the pixels near 
> the center point based on the fractional value of the center point and 
> the derivative vectors. This weighted sum is then returned as the 
> value for the output pixel.
>
> The "some algorithim" is the variable part:
>
> The current bilinear algorithm appears to be: ignore the derivatives, 
> and use the fractional part of the x/y to weigh the four pixels at 
> floor() and ceil() of the x/y.
>
> A very popular algorithim is box filtering, which has the primary 
> advantage that it is identical to bilinear if the scale is 1, and only 
> three weights for each direction need to be calculated:
>
> The vectors are converted to an axis-aligned rectangle with the same 
> area as the parallogram they define, and as much as possible the same 
> shape. This is then centered on the x/y. The weight for a pixel is the 
> area of it that intersects this rectangle, divided by the area of the 
> rectangle.
>
> Any real implementation does not literally do the above, but is 
> optimized by doing a "two pass" algorithim: you apply the horizontal 
> weight first to a bunch of rows, then apply the vertical weight only 
> once to all those sums. Also any real implementation takes advantage 
> of constant derivatives or fractional portions of x/y from one pixel 
> to another.
>
> It is extremely common to enlarge the rectangle to be at least 1 in 
> each direction. This makes any scaling up identical to bilinear 
> filtering. OS/X Quartz seems to *not* do this, however, and lots of 
> people like that, it will produce large antialiased squares for the 
> pixels rather than blurriness, and that appears to be much less 
> objectionable. It's slower than bilinear so you may only want to do 
> this if the scale is large enough that it looks better.
>
> You will also see "filter functions" mentioned a lot. These use some 
> method to convert the distance from the center of a pixel to the x,y 
> position to a number, and that number is then passed through this 
> function to get the weight. You will see truncated sync, gaussian, 
> Mitchell, and all kinds of other ones, there are books full of these. 
> Often for speed the source is reduced to a rectangle and the x/y are 
> used independently in the filter formula and the two results 
> multiplied to get the weight. For many filters this is quite close to 
> the same result, and allows a much faster two-pass algorithim 
> described above.
>
> The other thing you are going to see is mip-mapping. This means you 
> precalculate powers-of-two scales of the image (1/2, 1/4, etc). You 
> then can bilinearly filter the one that is just below the size you 
> want. The problem with this is that the precalculation takes time and 
> memory and must be redone whenever the source changes, there are 
> artifacts when the horizontal & vertical scale are different and when 
> they pass thorough the powers of two, and that the padding must be 
> pre-decided if the source is not a power of 2 in size. My belief is 
> that mipmapping is a poor fit to Cairo and pixman's usage. However it 
> is possible that mipmaping is what you are thinking of when you said 
> "prefiltering".
>