[cairo] Avoiding seams

[Eric Hughes]

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 
bad), or linear but not conservative (just bad).  In either way, 
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