src/pathops/SkIntersections.cpp

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkIntersections.h"

void SkIntersections::append(const SkIntersections& i) {
    for (int index = 0; index < i.fUsed; ++index) {
        insert(i[0][index], i[1][index], i.pt(index));
    }
}

int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
    NULL,
    &SkIntersections::verticalLine,
    &SkIntersections::verticalQuad,
    &SkIntersections::verticalCubic
};

int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
    NULL,
    &SkIntersections::lineRay,
    &SkIntersections::quadRay,
    &SkIntersections::cubicRay
};

int SkIntersections::coincidentUsed() const {
    if (!fIsCoincident[0]) {
        SkASSERT(!fIsCoincident[1]);
        return 0;
    }
    int count = 0;
    SkDEBUGCODE(int count2 = 0;)
    for (int index = 0; index < fUsed; ++index) {
        if (fIsCoincident[0] & (1 << index)) {
            ++count;
        }
#ifdef SK_DEBUG
        if (fIsCoincident[1] & (1 << index)) {
            ++count2;
        }
#endif
    }
    SkASSERT(count == count2);
    return count;
}

int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
    SkDCubic cubic;
    cubic.set(pts);
    fMax = 3;
    return intersectRay(cubic, line);
}

void SkIntersections::flip() {
    for (int index = 0; index < fUsed; ++index) {
        fT[1][index] = 1 - fT[1][index];
    }
}

int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
    if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
        // For now, don't allow a mix of coincident and non-coincident intersections
        return -1;
    }
    SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
    int index;
    for (index = 0; index < fUsed; ++index) {
        double oldOne = fT[0][index];
        double oldTwo = fT[1][index];
        if (one == oldOne && two == oldTwo) {
            return -1;
        }
        if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
            if ((precisely_zero(one) && !precisely_zero(oldOne))
                    || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
                    || (precisely_zero(two) && !precisely_zero(oldTwo))
                    || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
                fT[0][index] = one;
                fT[1][index] = two;
                fPt[index] = pt;
            }
            return -1;
        }
    #if ONE_OFF_DEBUG
        if (pt.roughlyEqual(fPt[index])) {
            SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
        }
    #endif
        if (fT[0][index] > one) {
            break;
        }
    }
    if (fUsed >= fMax) {
        SkASSERT(0);  // FIXME : this error, if it is to be handled at runtime in release, must
                      // be propagated all the way back down to the caller, and return failure.
        fUsed = 0;
        return 0;
    }
    int remaining = fUsed - index;
    if (remaining > 0) {
        memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
        memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
        memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
        int clearMask = ~((1 << index) - 1);
        fIsCoincident[0] += fIsCoincident[0] & clearMask;
        fIsCoincident[1] += fIsCoincident[1] & clearMask;
    }
    fPt[index] = pt;
    fT[0][index] = one;
    fT[1][index] = two;
    ++fUsed;
    return index;
}

void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
    int index = insertSwap(one, two, pt);
    int bit = 1 << index;
    fIsCoincident[0] |= bit;
    fIsCoincident[1] |= bit;
}

int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
    SkDLine l;
    l.set(pts);
    fMax = 2;
    return intersectRay(l, line);
}

void SkIntersections::offset(int base, double start, double end) {
    for (int index = base; index < fUsed; ++index) {
        double val = fT[fSwap][index];
        val *= end - start;
        val += start;
        fT[fSwap][index] = val;
    }
}

int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
    SkDQuad quad;
    quad.set(pts);
    fMax = 2;
    return intersectRay(quad, line);
}

void SkIntersections::quickRemoveOne(int index, int replace) {
    if (index < replace) {
        fT[0][index] = fT[0][replace];
    }
}

#if 0
void SkIntersections::remove(double one, double two, const SkDPoint& startPt,
        const SkDPoint& endPt) {
    for (int index = fUsed - 1; index >= 0; --index) {
        if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
                || startPt.approximatelyEqual(fPt[index])
                || endPt.approximatelyEqual(fPt[index]))) {
            SkASSERT(fUsed > 0);
            removeOne(index);
        }
    }
}
#endif

void SkIntersections::removeOne(int index) {
    int remaining = --fUsed - index;
    if (remaining <= 0) {
        return;
    }
    memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
    memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
    memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
    SkASSERT(fIsCoincident[0] == 0);
    int coBit = fIsCoincident[0] & (1 << index);
    fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
    SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
    fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
}

void SkIntersections::swapPts() {
    int index;
    for (index = 0; index < fUsed; ++index) {
        SkTSwap(fT[0][index], fT[1][index]);
    }
}

int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
        SkScalar x, bool flipped) {
    SkDLine line;
    line.set(a);
    return vertical(line, top, bottom, x, flipped);
}

int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
        SkScalar x, bool flipped) {
    SkDQuad quad;
    quad.set(a);
    return vertical(quad, top, bottom, x, flipped);
}

int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
        SkScalar x, bool flipped) {
    SkDCubic cubic;
    cubic.set(a);
    return vertical(cubic, top, bottom, x, flipped);
}