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::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = { 17 NULL, 18 &SkIntersections::verticalLine, 19 &SkIntersections::verticalQuad, 20 &SkIntersections::verticalCubic 21 }; 22 23 int (SkIntersections::*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(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 107 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 108 int clearMask = ~((1 << index) - 1); 109 fIsCoincident[0] += fIsCoincident[0] & clearMask; 110 fIsCoincident[1] += fIsCoincident[1] & clearMask; 111 } 112 fPt[index] = pt; 113 fT[0][index] = one; 114 fT[1][index] = two; 115 ++fUsed; 116 return index; 117 } 118 119 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 120 int index = insertSwap(one, two, pt); 121 int bit = 1 << index; 122 fIsCoincident[0] |= bit; 123 fIsCoincident[1] |= bit; 124 } 125 126 int SkIntersections::lineRay(const SkPoint pts[2], const SkDLine& line) { 127 SkDLine l; 128 l.set(pts); 129 fMax = 2; 130 return intersectRay(l, line); 131 } 132 133 void SkIntersections::offset(int base, double start, double end) { 134 for (int index = base; index < fUsed; ++index) { 135 double val = fT[fSwap][index]; 136 val *= end - start; 137 val += start; 138 fT[fSwap][index] = val; 139 } 140 } 141 142 int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) { 143 SkDQuad quad; 144 quad.set(pts); 145 fMax = 2; 146 return intersectRay(quad, line); 147 } 148 149 void SkIntersections::quickRemoveOne(int index, int replace) { 150 if (index < replace) { 151 fT[0][index] = fT[0][replace]; 152 } 153 } 154 155 #if 0 156 void SkIntersections::remove(double one, double two, const SkDPoint& startPt, 157 const SkDPoint& endPt) { 158 for (int index = fUsed - 1; index >= 0; --index) { 159 if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two) 160 || startPt.approximatelyEqual(fPt[index]) 161 || endPt.approximatelyEqual(fPt[index]))) { 162 SkASSERT(fUsed > 0); 163 removeOne(index); 164 } 165 } 166 } 167 #endif 168 169 void SkIntersections::removeOne(int index) { 170 int remaining = --fUsed - index; 171 if (remaining <= 0) { 172 return; 173 } 174 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 175 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 176 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 177 SkASSERT(fIsCoincident[0] == 0); 178 int coBit = fIsCoincident[0] & (1 << index); 179 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 180 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 181 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 182 } 183 184 void SkIntersections::swapPts() { 185 int index; 186 for (index = 0; index < fUsed; ++index) { 187 SkTSwap(fT[0][index], fT[1][index]); 188 } 189 } 190 191 int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, 192 SkScalar x, bool flipped) { 193 SkDLine line; 194 line.set(a); 195 return vertical(line, top, bottom, x, flipped); 196 } 197 198 int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, 199 SkScalar x, bool flipped) { 200 SkDQuad quad; 201 quad.set(a); 202 return vertical(quad, top, bottom, x, flipped); 203 } 204 205 int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, 206 SkScalar x, bool flipped) { 207 SkDCubic cubic; 208 cubic.set(a); 209 return vertical(cubic, top, bottom, x, flipped); 210 } 211
