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 } 208
