[cairo] Tessellator performance patch

[Rafael Villar Burke]

Baz wrote:
> This might be a daft question... the code that's being patched to call
> _cairo_may_intersect  at this point is working with sorted edges: "The
> names "left" and "right" here are correct descriptions of the order of
> the two edges within the active edge list. ". My understanding was
> that the top of the first edge is to the left of the top of the right
> edge.
>
> However, the intersection calculation looks completely general. I
> can't help but wonder if all of those multiplications are needed,
> since we already know some of the outcome?
I don't think we can skip some of the checks, and for now I've preferred
to have a more reliable solution.
If we can be sure that the top edge of the left edge is on the left to
the right edge we could just check wether its bottom edge is on the
right and if the bottom edge of the right edge is on the left of the
left edge. The improper intersection check needs those skipped
computations anyhow... so probably there isn't a lot of gain in skipping
them, and I'm not sure that whay you state is right. Would you try to
check it?
>
> I got to wondering about why this is placed before the call to
> _slope_compare() as well - to avoid the 64bit arithmetic? Couldn't the
> same lower precision check benefit slope_compare too? ie:
Yes, we could try to extend this logic to other parts of the
tessellator, and it'll mostly affect the most common cases, as it covers
from zero to very large coordinates.
> static int
> _slope_compare (cairo_bo_edge_t *a,
>                cairo_bo_edge_t *b)
> {
>    /* XXX: We're assuming here that dx and dy will still fit in 32
>     * bits. That's not true in general as there could be overflow. We
>     * should prevent that before the tessellation algorithm
>     * begins.
>     */
>    int32_t adx = a->bottom.x - a->top.x;
>    int32_t bdx = b->bottom.x - b->top.x;
>
>    /* Since the dy's are all positive by construction we can fast
>     * path the case where the two edges point in different directions
>     * with respect to x. */
>    if ((adx ^ bdx) < 0) {
>        return adx < 0 ? -1 : +1;
>    }
>    else {
>     if (not_top_precision(adx) &&
>        not_top_precision(ady) &&
>        not_top_precision(bdx) &&
>        not_top_precision(bdy) )
>    {
>        // faster slope check
>        int32_t adx_bdy = adx * bdy;
>        int32_t bdx_ady = bdx * ady;
>
>        if (adx_bdy > bdx_ady)
>            return 1;
>
>        if (adx_bdy * bdx_ady)
>            return -1;
>        return 0;
>    }
>    else {
>        int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
>        int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
>
>        /* if (adx * bdy > bdx * ady) */
>        if (_cairo_int64_gt (adx_bdy, bdx_ady))
>            return 1;
>
>        /* if (adx * bdy < bdx * ady) */
>        if (_cairo_int64_lt (adx_bdy, bdx_ady))
>            return -1;
>        return 0;
>    }
> }
I think the fast path could go also into may_intersect, as we can avoid
that way some false positives earlier without repeating the tests when
less precision can be used. Anyway, this should be useful too, as the
slope compare test is used in other parts of the code.
> Just askin', I don't understand the b-o code well enough to be sure
> about the sorted edges thing.
I'm not sure either how the ordering is done :S.
> Cheers,
> Baz
Regards,

Rafael Villar Burke