[cairo] Tessellator performance patch
M Joonas Pihlaja
jpihlaja at cc.helsinki.fi
Mon Dec 11 14:40:12 PST 2006
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
> 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
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.
More information about the cairo