# [cairo] Avoiding seams

Eric Hughes eh-cairo at narthex.us
Thu Dec 15 10:01:42 PST 2005

```At 07:21 PM 12/12/2005, MenTaLguY wrote:
>There is a fundamental ambiguity:
>  http://lists.freedesktop.org/archives/cairo/2005-March/003481.html

My first response to this was to point out that the operator in the
above example wasn't linear.  Linearity is pretty much necessary to
get independently drawn shapes with coincident edges to match up
correctly.  But there's another issue.  I've tracked down enough of
it to identify a problem.

The linearity required is not in the compositing model (exemplified
by the operators) but also in the anti-aliasing algorithm
itself.  The requirement for anti-aliasing is another form of
linearity, this time in the convolution function.  Mathematically,
the convolution must be linear over images.  That is, the sum of the
convolution of two images must be equal to the convolution of the sum
of the images.  (Linearity, when looked at functorially, is a form of
commutativity.)

A typical kind of convolution function does local weighted
averaging.  First take a locality, say, a 3x3 pixel
neighborhood.  Now assign weights to each element in the
neighborhood.  Multiply each neighbor by its weight, add them up, and
then divide by a normalizing constant.  Now, such a discrete
convolution is linear over images if it's conservative, that is, if
the sum of the weights is equal to the normalizing constant.  This is
typical, though not universal.

The anti-aliasing cairo does is to provide a hint to the back end
(see cairo_antialias_t).  The back end, though, can be unsuitable
(for this use case) by offering a non-linear anti-aliasing
service.  Either the convolution function can be non-linear (very
though, whether two co-incident edges match up exactly would be
dependent upon the back-end working right, and that's in addition to
cairo proper having the correct behavior.

This issue will certainly have larger repercussions than simply
matching up coincident lines.  I see three activities to address this
problem.  This is only a work description; I remain silent on
priority and scheduling.
1) Characterize existing back-ends as to the nature of their
anti-aliasing algorithms.  The three types I mentioned are linear,
locally linear but non-conservative, and fully non-linear.
2) Write unit tests to verify the behavior of the back-ends.  Because
the back-ends themselves are not under cairo development control,
their behavior may change without notice.
3) Add to cairo a linear anti-aliasing facility to override a faulty
back-end.  There would be a modest API change, perhaps a new
cairo_antialias_t with the tag "MANDATORY" on it (or something like that).

Eric

```