[cairo] The problem of seams, again

[Elia Cogodi]

Mail monster ate my Dec 30 post, so here it is again...

Disclaimer: I don't know the insides of Cairo or X or RENDER _at all_.
I am merely a curious, grateful reader and end-user, intrigued enough to 
go and read the Porter-Duff article referenced, I think, by keithp. 
Thus the things I say might not have much sense code-wise, given the 
current structure of the code, the needs to resort to given data formats
for hw acceleration and so on. By reading this disclaimer you silently
agreed to not kick me if I say something totally useless :) 

I've often seen supersampling suggested as a viable tradeoff in the
direction of: more memory needed, less seams/border problems

But as someone pointed out, we're just losing information about the
geometry of covering colours at sub-pixel level each time we use AA 
to render to a final RGB. Even by adding alpha channel in intermediate
state doesn't work well enough in some cases, as it only measures the
average covering. By supersampling we're just reducing this problem,
but it's intrinsic into this way of rasterizing arbitrary geometries
to a pixel grid. But shouldn't we better invest the extra memory 
consumption in a smarter way, closer to the source of the problem?
Basically it's mostly about polygon edges, so why can't we bring a
little amount of quantized geometry information with every pixel, 
detailing the simplest significant entity, ie a covering semiplane?

I suck at ASCII art, but the idea is simple: here's a pixel

    0    .08       .25
1.0 +----+---------+
    |     \########|
    |      \#######| 
    |       \######|              R,G,B,A, P=(.08,.55)      
    |        \#####|
    |         \####|
    |          \###|
    +-----------+--+
    .75        .55 .50
    
Parametrize the edge of the pixel with a float, for example clockwise, 
in the range of a semi-closed interval [0,1.0[. Define the P channel of a 
pixel with an ordered couple of numbers in this range. The idea is that
the couple of numbers defines the intersecting segment of a coloured 
semiplan over the pixel. The ordering guarantees we know the
orientation,
for example defining it so that the covered part is on the left when 
going from P1 to P2.

Thus, in the intermediate internal states we would add not only the A 
channel to the RGB components, but we would also have to bring along the
P channel (its esact bitwise coding and size is not that important. It
is more expensive memory-wise than A in describing the average covering,
but less expensive than a detailed enough NxN supersampling)

Then all Porter-Duff operators would have to be extended so that they
output not only the resulting alphas, but also a 'resulting average
geometry' P for the output pixel. So given two colors with different
P coverages:

    
 +-+------+             +--------+         +--------+ 
 |  \#####|             |@@@@@@@@|         |$$$$$$$$|
 |   \####|    OVER     |--------|   ->    |  ^$$$$$|
 |    \###|             |        |         |     ^$$|
 +-----+--+             +--------+         +--------+

(well, I don't have the ascii to draw the slope in the resulting pixel,
but I have faith in your good will and imagination :) )

The 'average geometry' can surely be formalized with weights based 
on the alpha components etc... I'm pretty sure a reasonable formula can
be figured out for each operator. 

You see where I'm going: in the intermediate step this extra information
solves some of our problems.
1) seams between exactly adjoining polygons simply disappear, because 
there's enough geometric information to know when a pixel is exactly 
covered.
2) drawing B OVER A no longer has the color A 'polluting' the
antialiased borders of B even when B completely covers A, save for
errors introduced by quantizing the geometry. 
No mathematical proof here, but if you think about it a bit, I think it
would give us anyway better results than the current alpha-only AA.

-- 
Elia Cogodi <eliacogodi at tin.it>