[cairo] Tessellator performance patch

[Carl Worth]

On Sun, 10 Dec 2006 23:32:14 +0000, Baz wrote:
> "The names "left" and "right" here are correct descriptions of the order of
> the two edges within the active edge list. ".

Yes, that's correct.

>                                               My understanding was
> that the top of the first edge is to the left of the top of the right
> edge.

No. That's not correct. Here's what's happening:

First, imagine two edges that intersect like so [*]:

a     b
 \   /
  \ /
   x
  / \
 /   \

The sweep line is a horizontal line that sweeps from top to
bottom. So, when the sweep line first encounters these edges it will
sort the edges according to their top coordinates. So a will become
"left" and b will be "right" in any intersection test.

The intersection of these two edges will be found and scheduled for
some future Y-position of the sweep line. When that intersection event
is processed, a and b will be swapped within the sweep line. So, if
these two edges were ever processed again, (not that the algorithm
should actually do that), a would be "right" and b would be "left".

So the names "left" and "right" have nothing to do with the top
coordinates of the edges. They have to do with the points formed by
the intersection of the sweep line with the edges. But also note that
we don't use these intersection points directly in any of the
calculations, (such as slope comparison and intersection calculation)
since they are necessarily inexact. Instead, we always use the
original input coordinates of each edge, (named "top" and "bottom").

-Carl

[*] Please be careful to not burn that simple intersection into your
head too much. If you think only in terms of edges with slopes of
opposite sign then you will think you can optimize things in ways that
will fail in cases like the following:

a   b
 \   \
   \  \
     \ \
       \\
         \
          \\
           \ \
            \  \
             \   \

as well as many other variations where one edge begins or ends before
the other, (or where they are coincident, collinear, where one edge
begins or ends at the intersection, etc. etc.).

We've been using randomly generated coordinates in a small region, (at
the scale of our finest sub-pixel precision), to try to hit as many of
these as possible, (see the commented-out main() function in
cairo-bentley-ottmann.c). But I'd like to see that testing graduate
into a real test inside our test suite itself.
-------------- 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/20061211/7a312f31/attachment.pgp