[cairo] Tessellator performance patch

[M Joonas Pihlaja]

Hi,

On Mon, 11 Dec 2006, chris nuernberger wrote:

> But in both of those cases you ascii'd out, you know that the sign of
> ax-bx changes if you take different end points of the segments.
> Really, you only need the sign of a subtracting at the oppose end from
> the point you are at from the intersection point, and you would know
> if a collision is possible.

If you mean a check like this:

 int dx1 = segment1->bot.x - segment1->top.x;
 int dx2 = segment2->bot.x - segment2->top.x;
 if (sign(dx1) != sign(dx2)) return NO_INTERSECTION;

then what you say is true.  It distinguishes the cases below,
where in the first the intersection must happen, if at all,
somewhere above the sweep line:

________________           <- sweep line
  /   \
 /     \
/       \

from cases like this, where it must happen, if at all, below:

______________            <- sweep line
\       /
 \     /
  \   /

If this is the test you mean, then you're right, it's a fair
speedup, and it's currently implemented as part of the
slope_check() function.

> This means that if you know the intersection point should lie
> below you, then you check the sign of the subtraction of the
> end x points at the lower y.  Or reverse this logic.

But this statement makes me think you mean checking the sign of a
subtraction like this:

	segment1->bot.x - segment2->bot.x

This test distinguishes the basic non-intersections above from
the intersection

______________
\  /
 \/
 /\
/  \

But consider the case below though, where there's no
intersection, yet the first segment's end point is to the right
of the second segment's end point.

_______________
\       \
  \      \
    \     \
      \
        \
          \
            \
              \

If any "does-intersect?" test relies on cross differences of
different segments' points, it should take into account the y
coordinates as well as the x coordinates.  Otherwise it'll be
giving out false negatives.

Cheers,

Joonas