[cairo] New tessellator available for playing

[Carl Worth]

On Wed, 20 Sep 2006 16:40:10 -0700, Carl Worth wrote:
> There are significant (buggy) differences in three tests (bitmap-font,
> close-path, and rectangle-rounding error). In the first case, this is
> the case where we use cairo_text_path;cairo_fill on a bitmap font and
> cairo traces little squares out around every pixel, (did you know it
> did that?). That's actually a great test case as it shoves lots of
> coincident edges at the tessellator---and it's exposing a bad bug in
> the new tessellator as it's leaking the fill out all over, (oops!).
>
> The other two bugs show cases where a portion of the path that should
> be filled is not getting filled (oops!).

It turns out that one simple fix was enough to fix all of these
bugs. I had added a check to prevent an identical intersection event
from getting scheduled multiple times, but it was mistakenly also
prevent identical edges (from separate polygons) schedule their start
and stop events.

So the simple fix has been pushed out to my new-tessellator2 branch:

http://gitweb.freedesktop.org/?p=users/cworth/cairo.git;a=commit;h=80f0c309fc357621b

> So there are still bugs here---and that's why it's not merged to
> master yet. But I thought people might want to start looking at it
> already even in the current state.

I think I'd feel pretty good about merging this in soon, (and then
generating a 1.3 snapshot to make it easier for people to start
testing it). I would be interested in hearing from anyone that has
tried out the code already, (if at all).

Next I'll tackle the fairly simple performance optimization of
preferring 64-bit arithmetic over 128-bit arithmetic when
possible. This should also allow me to address the potential 32-bit
overflows that are mentioned several times in the code.

Then there's adding back the multi-pass aspect and eliminating a
couple of other performance-wasting things the code is doing, (like
_cairo_sweep_line_validate and some useless compares as mentioned in
_cairo_bo_edge_contains_point_quorem128).

I think I'll also put the tessellator stress-case with O(N**2)
validation into a standalone C program so that we can continue to run
that whenever we are hacking the algorithm in the future.

Oh, and there are a couple of cleanups that could be done like giving
the skiplist functions a proper _cairo namespace, etc.

Anyway, I'm feeling quite good about the code now, and will be most
interested to hear from someone who is able to get incorrect results
out of the new tessellator, (particularly after I add back the
multiple-pass thing and fix the 32-bit overflows).

-Carl
-------------- 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/20060922/01b502d4/attachment.pgp