[cairo] Incorrect rendering of the edges of overlapping polygons

[Carl Worth]

On Sun, 4 Dec 2005 19:14:13 -0500, David Benbennick wrote:
> <polygon points="0,0 0,1 1,0" fill="red" />
> <polygon points="0,0 0,1 1,0" fill="white" />
...
> It seems that Cairo is using a naive / simplified algorithm for
> determing the color of edge pixels.  In particular, for the example
> above, it seems to say to itself:
> 
> 1) First, make the pixel half-red, since the first triangle takes up
> half the pixel's area.
> 2) Second, add half-white to the pixel, making it one-quarter-red,
> since the second triangle takes up half the pixel's area.

Yes, that's roughly what is going on here if you render the above two
triangles in sequence to cairo. What's happening is that the result of
rendering each object is incrementally captured in the target surface.

So, after rendering the red triangle, cairo has color and alpha
information for each affected pixel, but no longer has any geometry.

So, when the white triangle is to be rendered, it can see that the
pixel here is "50% red" but it doesn't know if the geometry of the
shape that contributed that red value is correlated in any way with
the white shape about to be drawn.

In the absence of any additional information, it's quite reasonable to
assume "nothing special" about the correlation. That is, assume that
the 50% red is spread out uniformly across the pixel. In the case you
describe above, that's the wrong assumption and you see the incorrect
result.

This assumption of "nothing special" was put forth by Porter and
Duff[*] in their seminal work on image compositing and is the basis
for the equations they present, which are exactly what cairo
provides. The assumption does allow for treating partial coverage of
pixels by opaque objects as equivalent to complete coverage by
translucent objects. But they also mention an interesting point:

	The assumption is quite good for most mattes, though
	it can be improved if we know that the coverage
	seldom overlaps (adjacent segments of a continuous
	line) or always overlaps (repeated application of a
	picture). For ease in presentation throughout this
	paper, let us make this assumption and consider the
	alpha values as representing subpixel coverage of
	opaque objects.

The Render extension implements variants of all of the Porter-Duff
compositing operators for each of these two cases. The "disjoint"
variants provide the "seldom overlaps" interpretation while the
"conjoint" variants provide the "always overlaps". In the case of your
two triangles, the "always overlaps" interpretation applies and using
CONJOINT_OVER rather than the default OVER operator would provide the
desired result.

However, in cairo we don't yet export the disjoint and conjoint
operators, (I think the motivation was that most backends can't handle
them directly), but they still might be worth exporting. The more
difficult problem in this case is that a library like librsvg would
not have sufficient information in the SVG snippet you provide above
to know that the conjoint operator would be appropriate.

Cairo does provide OpenGL's SATURATE operator, which Keith discovered
is equivalent to one of the variants of the basic Porter-Duff
operators. It can be used to good effect to eliminate the "seams"
problem that people have brought up in this thread, (which would be if
you were drawing two triangles that partition the pixel rather than
covering identical portions). The correct use of SATURATE can be
counter-intuitive as it requires rendering object front-to-back rather
than back-to-front.

I mention SATURATE here for completeness. It won't directly help with
the problem you've presented, but it might play a part in a more
complete solution that intersects polygons to remove hidden portions
and then uses SATURATE to merge polygons in a seam-free fashion.

Finally, another approach, (as advocated by mental later in this
thread already), is to simply not use the alpha value to represent
partial coverage at all. The idea there is to instead render
non-antialiased shapes into a higher-resolution intermediate
surface. The result will then have several color samples per final
pixel which can be filtered to achieve a nicely anti-aliased
result. This technique is known as full-scene anti-aliasing (FSAA).

FSAA has the benefit of solving both the hidden geometry problems as
well as the seams problems. It has the downside of requiring more
memory and processing, and resulting in lesser-quality anti-aliasing,
(unless a _lot_ more memory and processing is applied).

FSAA has been brought up several times on this list, but I'm not sure
if anyone has yet implemented it. It should be a fairly simple matter
to implement it on top of cairo itself, (be warned that cairo's
current bilinear filter won't provide adequate results for the
down-sampling stage of FSAA at a level of more than 2x2 per pixel).

And if someone experiments with that and finds it adequate, it could
make sense to provide the option of FSAA within cairo somehow.

I hope these ramblings of mine have been somewhat useful,

-Carl

[*] http://keithp.com/~keithp/porterduff/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20051205/7d8dab5f/attachment-0001.pgp