[cairo] Compositing benchmarks

[Bill Spitzak]

Carl Worth wrote:

> I think the reason is simply that we haven't gotten around to fixing
> it yet. I'd love to see someone implement a software "mipmap"-like
> approach for image scaling. It would eliminate one of the few
> visual-quality warts still left in cairo.

A mipmap is only useful if the image is going to be drawn many times. 
This perhaps could be done if the source surface could store it for 
reuse, but this would have to be a special mipmap-surface type and 
(similar to that jpeg->pdf stuff) would require the destination surface 
to recognize and use the mipmap source directly.

The more immediate and useful solution for Cairo is to do filtered 
sampling of more than 4 pixels of the source image. I believe that for 
Cairo, a pixel-aligned box filter is quite sufficient, and has the 
advantage of blending smoothly with how cairo enlarges images. The 
following will do it, there is just a small matter of optimizing it :-)

All variables are floating point.

Take the center of the destination pixel X,Y (this would be two numbers 
ending in .5).

Back-project X,Y to get x,y source coordinate.

Back-project X+1,Y and subtract x,y to get dux,duy.
Back-project X,Y+1 and subtract x,y to get dvx,dvy.
(above two steps can be simplified a lot if perspective is not done)

// Produce the pixel-aligned rectangle of approximately equal size:
A = fabs(dux*dvy-duy*dvx);
W = dux*dux+dvx*dvx;
H = duy*duy+dvy*dvy;
if (W>H) {
   W = sqrt(W);
   H = A/W;
} else if (H > 0) {
   H = sqrt(H);
   W = A/H;
}
// Box filter must be at least 1 in size.
if (W < 1) W = 1;
if (H < 1) H = 1;

Now consider the rectangle of size W,H centered on x,y. Multiply every 
pixel that intersects this rectangle by the area of the intersection, 
add all these together, and divide by W*H. This is the resulting sample.

optimizations:

The most useful optimization is to detect W==1 and H==1 as early as 
possible in the above and do the current cairo sampling, which is 
equivalent.

Less important, though it seems obvious, is to do a 2-pass algorithim, 
as the weight for each pixel is the horizontal weight times the vertical 
weight.

In each direction there are only 2 pixels with fractional weights 
(sometimes these "fractions" are 0 and 1) and floor(W-1) pixels that are 
multiplied by 1.

The next step down in quality is to round W and H to the nearest 
integers, making the division an integer and making the above two 
fractions always add to 1.

Further reductions in quality would be to round the edges of the 
rectangle to integers for any direction where the size is greater than 
1. This makes each pass be two cases: either average n pixels or do the 
current cairo weighted sum of 2 pixels.

Another reduction in quality is to set W==H==sqrt(A). I suspect OS/X 
quartz may be doing this.

Going the other way, the best way to improve quality is to sample a 
axis-aligned "parallelogram" by doing integer offsets to the nearest 
value. I would not try anything fancier (such as trying to figure out 
the intersection with an arbitrary parallelogram) as this is overkill, 
it is better to use better sampling filters (ie apply different weights 
to the pixels depending on how far they are from x,y).