src/third_party/skia/src/pathops/SkIntersections.cpp

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #include "SkIntersections.h"
   9
  10 void SkIntersections::append(const SkIntersections& i) {
  11     for (int index = 0; index < i.fUsed; ++index) {
  12         insert(i[0][index], i[1][index], i.pt(index));
  13     }
  14 }
  15
  16 int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
  17     NULL,
  18     &SkIntersections::verticalLine,
  19     &SkIntersections::verticalQuad,
  20     &SkIntersections::verticalCubic
  21 };
  22
  23 int ( SkIntersections::* const CurveRay[])(const SkPoint[], const SkDLine&) = {
  24     NULL,
  25     &SkIntersections::lineRay,
  26     &SkIntersections::quadRay,
  27     &SkIntersections::cubicRay
  28 };
  29
  30 int SkIntersections::coincidentUsed() const {
  31     if (!fIsCoincident[0]) {
  32         SkASSERT(!fIsCoincident[1]);
  33         return 0;
  34     }
  35     int count = 0;
  36     SkDEBUGCODE(int count2 = 0;)
  37     for (int index = 0; index < fUsed; ++index) {
  38         if (fIsCoincident[0] & (1 << index)) {
  39             ++count;
  40         }
  41 #ifdef SK_DEBUG
  42         if (fIsCoincident[1] & (1 << index)) {
  43             ++count2;
  44         }
  45 #endif
  46     }
  47     SkASSERT(count == count2);
  48     return count;
  49 }
  50
  51 int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) {
  52     SkDCubic cubic;
  53     cubic.set(pts);
  54     fMax = 3;
  55     return intersectRay(cubic, line);
  56 }
  57
  58 void SkIntersections::flip() {
  59     for (int index = 0; index < fUsed; ++index) {
  60         fT[1][index] = 1 - fT[1][index];
  61     }
  62 }
  63
  64 int SkIntersections::insert(double one, double two, const SkDPoint& pt) {
  65     if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) {
  66         // For now, don't allow a mix of coincident and non-coincident intersections
  67         return -1;
  68     }
  69     SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]);
  70     int index;
  71     for (index = 0; index < fUsed; ++index) {
  72         double oldOne = fT[0][index];
  73         double oldTwo = fT[1][index];
  74         if (one == oldOne && two == oldTwo) {
  75             return -1;
  76         }
  77         if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) {
  78             if ((precisely_zero(one) && !precisely_zero(oldOne))
  79                     || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1))
  80                     || (precisely_zero(two) && !precisely_zero(oldTwo))
  81                     || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) {
  82                 fT[0][index] = one;
  83                 fT[1][index] = two;
  84                 fPt[index] = pt;
  85             }
  86             return -1;
  87         }
  88     #if ONE_OFF_DEBUG
  89         if (pt.roughlyEqual(fPt[index])) {
  90             SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one);
  91         }
  92     #endif
  93         if (fT[0][index] > one) {
  94             break;
  95         }
  96     }
  97     if (fUsed >= fMax) {
  98         SkASSERT(0);  // FIXME : this error, if it is to be handled at runtime in release, must
  99                       // be propagated all the way back down to the caller, and return failure.
 100         fUsed = 0;
 101         return 0;
 102     }
 103     int remaining = fUsed - index;
 104     if (remaining > 0) {
 105         memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
 106         memmove(&fPt2[index + 1], &fPt2[index], sizeof(fPt2[0]) * remaining);
 107         memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
 108         memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
 109         int clearMask = ~((1 << index) - 1);
 110         fIsCoincident[0] += fIsCoincident[0] & clearMask;
 111         fIsCoincident[1] += fIsCoincident[1] & clearMask;
 112     }
 113     fPt[index] = pt;
 114     fT[0][index] = one;
 115     fT[1][index] = two;
 116     ++fUsed;
 117     return index;
 118 }
 119
 120 void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
 121     SkASSERT(one == 0 || one == 1);
 122     SkASSERT(two == 0 || two == 1);
 123     SkASSERT(pt1 != pt2);
 124     SkASSERT(fNearlySame[(int) one]);
 125     (void) insert(one, two, pt1);
 126     fPt2[one ? fUsed - 1 : 0] = pt2;
 127 }
 128
 129 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
 130     int index = insertSwap(one, two, pt);
 131     int bit = 1 << index;
 132     fIsCoincident[0] |= bit;
 133     fIsCoincident[1] |= bit;
 134 }
 135
 136 int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) {
 137     SkDLine l;
 138     l.set(pts);
 139     fMax = 2;
 140     return intersectRay(l, line);
 141 }
 142
 143 void SkIntersections::offset(int base, double start, double end) {
 144     for (int index = base; index < fUsed; ++index) {
 145         double val = fT[fSwap][index];
 146         val *= end - start;
 147         val += start;
 148         fT[fSwap][index] = val;
 149     }
 150 }
 151
 152 int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) {
 153     SkDQuad quad;
 154     quad.set(pts);
 155     fMax = 2;
 156     return intersectRay(quad, line);
 157 }
 158
 159 void SkIntersections::quickRemoveOne(int index, int replace) {
 160     if (index < replace) {
 161         fT[0][index] = fT[0][replace];
 162     }
 163 }
 164
 165 void SkIntersections::removeOne(int index) {
 166     int remaining = --fUsed - index;
 167     if (remaining <= 0) {
 168         return;
 169     }
 170     memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
 171     memmove(&fPt2[index], &fPt2[index + 1], sizeof(fPt2[0]) * remaining);
 172     memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
 173     memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
 174     SkASSERT(fIsCoincident[0] == 0);
 175     int coBit = fIsCoincident[0] & (1 << index);
 176     fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
 177     SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
 178     fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
 179 }
 180
 181 void SkIntersections::swapPts() {
 182     int index;
 183     for (index = 0; index < fUsed; ++index) {
 184         SkTSwap(fT[0][index], fT[1][index]);
 185     }
 186 }
 187
 188 int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
 189         SkScalar x, bool flipped) {
 190     SkDLine line;
 191     line.set(a);
 192     return vertical(line, top, bottom, x, flipped);
 193 }
 194
 195 int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
 196         SkScalar x, bool flipped) {
 197     SkDQuad quad;
 198     quad.set(a);
 199     return vertical(quad, top, bottom, x, flipped);
 200 }
 201
 202 int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
 203         SkScalar x, bool flipped) {
 204     SkDCubic cubic;
 205     cubic.set(a);
 206     return vertical(cubic, top, bottom, x, flipped);
 207 }