# [cairo] Compositing benchmarks

Bill Spitzak spitzak at d2.com
Tue Mar 6 04:40:58 PST 2007

```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

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

```