# [cairo] Details of revised rendering equation

Owen Taylor otaylor at redhat.com
Fri Aug 5 11:07:12 PDT 2005

```In preparation for implementing the clipping TODO item, I went
back through the details in written things up in a lot of detail here
with the thought of being able to adapt this for documentation.

The main interesting thing in this beyond what was discussed before
is the discussion of SATURATE. I make the the case below that we
want to use:

dest' = (source IN clip) SATURATE dest

even though that *does not* exactly match the revised clipping
equation:

dest' = ((source OP dest) IN clip) ADD (dest OUT clip)

I'll proceed with implementing it the simple way; it will be
easy to switch it over to the other code path if people disagree
with my conclusion.

Regards,
Owen

Basic rendering equations
=========================

Compositing in cairo is based on the Porter-Duff equations.

The operation

dest' = source OP dest

Is given by:

(Cs is one of the color components of the source in premultiplied
form, As is the alpha component of the source, and so forth).

The functions for the different operators in cairo are defined
as:

Fa(Aa,Ab)            Fb(Aa,Ab)
------------------------------
CLEAR           0                    0
SOURCE          1                    0
OVER            1                    1 - Aa
IN              Ab                   0
OUT             1 - Ab               0
ATOP            Ab                   1 - Aa

DEST            0                    1
DEST_OVER       1 - Ab               1
DEST_IN         0                    Aa
DEST_OUT        0                    1 - Aa
DEST_ATOP       1 - Ab               Aa

XOR             1 - Ab               1 - Aa
SATURATE        min(1,(1-Ab)/Aa)     1

Shaping and Clipping
====================

The above equation just handles source and destination. But for
cairo, we need to add two more elements, the shape (the mask for
cairo_mask(), the glyphs for cairo_show_text(), the path for
cairo_stroke() or cairo_fill()), and the clip.

The shape is easy to add to the Port-Duff equation; we just
combine it with the source:

dest' = (source IN shape) OP dest

The clip is a bit harder to handle; we want the effect that the
the operation has no effect where the clip is 0 and is the same
as the unclipped operation where the clip is 1. An equation that
clearly meets this is:

dest' = ((source OP dest) IN clip) ADD (dest OUT clip)

In other words, we use the clip as an interpolating factor
between the result value and the original value. (In all the
discussion of clipping I've omitted showing the shape since
it simply modifies the source and does not interact with
the other terms.)

The main problem with the above equation is that it is expensive
to compute; using the RENDER extension, for example, we need four
separate operations:

1. Copy dest to temporary buffer
2. Compute (source OP dest)
3. Compute (dest OUT clip)
4. Compute (((source IN mask) OP dest) in clip) ADD (dest OUT clip)

Simplifying the clip computations
=================================

A simpler way of defining clipping is to apply the clipping to
the source:

dest' = (source IN clip) OP dest

This definition clearly doesn't meet our requirements for
clipping for all operators since if OP is, say, CLEAR, then we
clear the *entire* destination, not just the part inside the clip
mask. However, maybe it works for some of our operators?

If we write out the two equations in component form:

Simple: (source IN clip) OP dest
Cd' = Cs * Ac * Fa(As*Ac, Ad) + Cd * Fb(As*Ac, Ad)

Complex: ((source OP dest) IN clip) ADD (dest OUT clip)
Cd' = Cs * Fa(As, Ad) * Ac + Cd * Fb(As, Ad) * Ac + Cd * (1 - Ac)
= Cs * Fa(As, Ad) * Ac + Cd * [Fb(As, Ad) * Ac + (1 - Ac)]

To have these be the same for all Cs, Cd, we need both factors to
be equal:

This is clearly true for all operators other than SATURATE, since
Fa is independent of Aa.

2) Fb(As * Ac, Ad) == Fb(As, Ad) * Ac + (1 - Ac)

This is true for the operators where

Fb(Ab, Ac) == 1
1 ?= 1 * Ac + 1 - Ac
1 == 1
Fb(Ab, Ac) == 1 - Aa
1 - As * Ac =?

But false for those operators where

Fb(Ab, Ac) == 0
0 ?= 0 * Ac + 1 - Ac
0 != 1 - Ac
Fb(Ab, Ac) == Aa
As * Ac ?= As * Ac + 1 - Ac

So, for:

OVER, ATOP, DEST, DEST_OVER, DEST_OUT, XOR, ADD

We can use the simpler equation, however for:

CLEAR, SOURCE, IN, OUT, DEST_IN, DEST_ATOP

We need to use the more complex equation. SATURATE will be
examined in more detail below. There are a few simplifications we
can make among these as well:

CLEAR:

((source CLEAR dest) IN clip) ADD (dest OUT clip)

simplifies to:

clip DEST_OUT dest

SOURCE

((source SOURCE dest) IN clip) ADD (dest OUT clip)

simplifies to:

(source IN CLIP) ADD (dest OUT clip)

The case of SATURATE
=====================

While in most of the failures above, the simple equation doesn't
meet our basic requirement of:

No effect where the clip is 0 and is the same as the unclipped
operation where the clip is 1

The SATURATE operator fails more subtly. Let's write out the
equations in full; to simplify, write Cs = cs * As - so cs is the
unpremultiplied color.

Simple:

Cd' = Cs * Ac * min(1,(1 - Ad)/As*Ac) + Cd
= cs * min (As*Ac, (1 - Ad)) + Cd

Complex

Cd' = Cs * Ac * min(1,(1 - Ad)/As) + Cd * Ac + (1 - Ac) * Cd
= cs * min(As*Ac,Ac*(1 - Ad)) + Cd

If Ac == 1, then both simplify to :

Cd' = cs * min(As,(1 - Ad)) + Cd

If Ac == 0, then both simpify to

Cd' = Cd

At other values, the difference between the two is:

cs * [min(As * Ac, (1 - Ad)) - min(As * Ac, Ac*(1 - Ad))]

Since this is piecewise linear in As, Ad, and Ac, the maximum of
this value must occur either at the corners of the unit cube:
{As=[0,1], Ac=[0,1], Ad=[0,1]} or at one of the surfaces that
divide the linear pieces:

As * Ac == Ac * (1 - Ad)
As * Ac == 1 - Ad

We've shown above that for Ac=0, or Ac=1, then the difference is
0, so it is zero at all 8 corners.

On the first surface:

diff = cs * [min(As * Ac, (1 - Ad)) - min(As * Ac, Ac * (1 - Ad))]
= cs * [min(As * Ac, As) - min(As * Ac, As * Ac)]
= cs * [As * Ac - As * Ac]
= 0.

On the second surface:

diff = cs * [min(As * Ac, (1 - Ad)) - min(As * Ac, Ac * (1 - Ad))]
= cs * [min(As * Ac, As * Ac) - min (As * Ac, As * Ac * Ac)]
= cs * [As * Ac - As * Ac * Ac]
= cs * As * Ac * (1 - Ac)

This is maximized for As == 1, Ac = 0.5, Ad == 0.5, which is in
fact the global maximum. To turn this back into intuitive terms,
the maximally divergent situation is:

Solid source, half clipped, over empty situation

By the simple method, we get:

Cd' = Cs * Ac * min(1,(1 - Ad)/As*Ac) + Cd
= cs * min (As * Ac, (1 - Ad)) + cd * Ad
= cs * 0.5 + cd * 0.5

= 0.5 + 0.5
= 1

So we get a solid destination; all of the clipped source was

By the complex method we get:

Cd' = Cs * Ac * min(1,(1 - Ad)/As) + Cd * Ac + (1 - Ac) * Cd
= cs * 0.25 + cd * 0.5

Ad' = As * Ac * min(1,(1 - Ad)/As) + Cd * Ac + (1 - Ac) * Ad
= 0.25 + 0.5
= 0.75

A destination that is not quite solid: we have an average of the
result without clipping (solid) and the original (50%
transparent)

There are a number of arguments why we should be using the simple
method, even though it *does not* match the equation we use to
define clipping for other operands:

- It almost matches; we only get minor deviations with half-occupied
pixels at the edge of the clipping shape.

- Performance; most of the other operations where we have to
fall back to full complex equation are unusual; SATURATE is
intended to be used as a base rendering mode.

- User expectations; the typical reason to use SATURATE is to
avoid seams between antialiased shapes. It seems unexpected
to not get seams between shapes coming from cairo_stroke()
or cairo_fill() but to get seams when the shapes come from
cairo_clip().

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050805/39a271d9/attachment.pgp
```