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