[cairo] Tessellator performance patch

[chris nuernberger]

Oh.  That makes a lot of sense.

Thank you very very much for your time, this is something I was
wondering for a very long time.

Chris

On 12/11/06, M Joonas Pihlaja <jpihlaja at cc.helsinki.fi> wrote:
>
> 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
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://cairographics.org/cgi-bin/mailman/listinfo/cairo
>