michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkIntersections.h"
michael@0: 
michael@0: void SkIntersections::append(const SkIntersections& i) {
michael@0:     for (int index = 0; index < i.fUsed; ++index) {
michael@0:         insert(i[0][index], i[1][index], i.pt(index));
michael@0:     }
michael@0: }
michael@0: 
michael@0: int (SkIntersections::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
michael@0:     NULL,
michael@0:     &SkIntersections::verticalLine,
michael@0:     &SkIntersections::verticalQuad,
michael@0:     &SkIntersections::verticalCubic
michael@0: };
michael@0: 
michael@0: int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = {
michael@0:     NULL,
michael@0:     &SkIntersections::lineRay,
michael@0:     &SkIntersections::quadRay,
michael@0:     &SkIntersections::cubicRay
michael@0: };
michael@0: 
michael@0: int SkIntersections::coincidentUsed() const {
michael@0:     if (!fIsCoincident[0]) {
michael@0:         SkASSERT(!fIsCoincident[1]);
michael@0:         return 0;
michael@0:     }
michael@0:     int count = 0;
michael@0:     SkDEBUGCODE(int count2 = 0;)
michael@0:     for (int index = 0; index < fUsed; ++index) {
michael@0:         if (fIsCoincident[0] & (1 << index)) {
michael@0:             ++count;
michael@0:         }
michael@0: #ifdef SK_DEBUG
michael@0:         if (fIsCoincident[1] & (1 << index)) {
michael@0:             ++count2;
michael@0:         }
michael@0: #endif
michael@0:     }
michael@0:     SkASSERT(count == count2);
michael@0:     return count;
michael@0: }
michael@0: 
michael@0: int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
michael@0:     SkDCubic cubic;
michael@0:     cubic.set(pts);
michael@0:     fMax = 3;
michael@0:     return intersectRay(cubic, line);
michael@0: }
michael@0: 
michael@0: void SkIntersections::flip() {
michael@0:     for (int index = 0; index < fUsed; ++index) {
michael@0:         fT[1][index] = 1 - fT[1][index];
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
michael@0:     if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
michael@0:         // For now, don't allow a mix of coincident and non-coincident intersections
michael@0:         return -1;
michael@0:     }
michael@0:     SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
michael@0:     int index;
michael@0:     for (index = 0; index < fUsed; ++index) {
michael@0:         double oldOne = fT[0][index];
michael@0:         double oldTwo = fT[1][index];
michael@0:         if (one == oldOne && two == oldTwo) {
michael@0:             return -1;
michael@0:         }
michael@0:         if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
michael@0:             if ((precisely_zero(one) && !precisely_zero(oldOne))
michael@0:                     || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
michael@0:                     || (precisely_zero(two) && !precisely_zero(oldTwo))
michael@0:                     || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
michael@0:                 fT[0][index] = one;
michael@0:                 fT[1][index] = two;
michael@0:                 fPt[index] = pt;
michael@0:             }
michael@0:             return -1;
michael@0:         }
michael@0:     #if ONE_OFF_DEBUG
michael@0:         if (pt.roughlyEqual(fPt[index])) {
michael@0:             SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
michael@0:         }
michael@0:     #endif
michael@0:         if (fT[0][index] > one) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     if (fUsed >= fMax) {
michael@0:         SkASSERT(0);  // FIXME : this error, if it is to be handled at runtime in release, must
michael@0:                       // be propagated all the way back down to the caller, and return failure.
michael@0:         fUsed = 0;
michael@0:         return 0;
michael@0:     }
michael@0:     int remaining = fUsed - index;
michael@0:     if (remaining > 0) {
michael@0:         memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
michael@0:         memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
michael@0:         memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
michael@0:         int clearMask = ~((1 << index) - 1);
michael@0:         fIsCoincident[0] += fIsCoincident[0] & clearMask;
michael@0:         fIsCoincident[1] += fIsCoincident[1] & clearMask;
michael@0:     }
michael@0:     fPt[index] = pt;
michael@0:     fT[0][index] = one;
michael@0:     fT[1][index] = two;
michael@0:     ++fUsed;
michael@0:     return index;
michael@0: }
michael@0: 
michael@0: void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
michael@0:     int index = insertSwap(one, two, pt);
michael@0:     int bit = 1 << index;
michael@0:     fIsCoincident[0] |= bit;
michael@0:     fIsCoincident[1] |= bit;
michael@0: }
michael@0: 
michael@0: int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
michael@0:     SkDLine l;
michael@0:     l.set(pts);
michael@0:     fMax = 2;
michael@0:     return intersectRay(l, line);
michael@0: }
michael@0: 
michael@0: void SkIntersections::offset(int base, double start, double end) {
michael@0:     for (int index = base; index < fUsed; ++index) {
michael@0:         double val = fT[fSwap][index];
michael@0:         val *= end - start;
michael@0:         val += start;
michael@0:         fT[fSwap][index] = val;
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
michael@0:     SkDQuad quad;
michael@0:     quad.set(pts);
michael@0:     fMax = 2;
michael@0:     return intersectRay(quad, line);
michael@0: }
michael@0: 
michael@0: void SkIntersections::quickRemoveOne(int index, int replace) {
michael@0:     if (index < replace) {
michael@0:         fT[0][index] = fT[0][replace];
michael@0:     }
michael@0: }
michael@0: 
michael@0: #if 0
michael@0: void SkIntersections::remove(double one, double two, const SkDPoint& startPt,
michael@0:         const SkDPoint& endPt) {
michael@0:     for (int index = fUsed - 1; index >= 0; --index) {
michael@0:         if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two)
michael@0:                 || startPt.approximatelyEqual(fPt[index])
michael@0:                 || endPt.approximatelyEqual(fPt[index]))) {
michael@0:             SkASSERT(fUsed > 0);
michael@0:             removeOne(index);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: #endif
michael@0: 
michael@0: void SkIntersections::removeOne(int index) {
michael@0:     int remaining = --fUsed - index;
michael@0:     if (remaining <= 0) {
michael@0:         return;
michael@0:     }
michael@0:     memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
michael@0:     memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
michael@0:     memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
michael@0:     SkASSERT(fIsCoincident[0] == 0);
michael@0:     int coBit = fIsCoincident[0] & (1 << index);
michael@0:     fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
michael@0:     SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
michael@0:     fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
michael@0: }
michael@0: 
michael@0: void SkIntersections::swapPts() {
michael@0:     int index;
michael@0:     for (index = 0; index < fUsed; ++index) {
michael@0:         SkTSwap(fT[0][index], fT[1][index]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
michael@0:         SkScalar x, bool flipped) {
michael@0:     SkDLine line;
michael@0:     line.set(a);
michael@0:     return vertical(line, top, bottom, x, flipped);
michael@0: }
michael@0: 
michael@0: int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
michael@0:         SkScalar x, bool flipped) {
michael@0:     SkDQuad quad;
michael@0:     quad.set(a);
michael@0:     return vertical(quad, top, bottom, x, flipped);
michael@0: }
michael@0: 
michael@0: int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
michael@0:         SkScalar x, bool flipped) {
michael@0:     SkDCubic cubic;
michael@0:     cubic.set(a);
michael@0:     return vertical(cubic, top, bottom, x, flipped);
michael@0: }