[cairo] Tessellator performance patch

Baz brian.ewins at gmail.com
Sun Dec 10 15:32:14 PST 2006

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

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 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:

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;

Just askin', I don't understand the b-o code well enough to be sure
about the sorted edges thing.


More information about the cairo mailing list