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 int SkIntersections::closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, 11 double* closestDist) const { 12 int closest = -1; 13 *closestDist = SK_ScalarMax; 14 for (int index = 0; index < fUsed; ++index) { 15 if (!between(rangeStart, fT[0][index], rangeEnd)) { 16 continue; 17 } 18 const SkDPoint& iPt = fPt[index]; 19 double dist = testPt.distanceSquared(iPt); 20 if (*closestDist > dist) { 21 *closestDist = dist; 22 closest = index; 23 } 24 } 25 return closest; 26 } 27 28 void SkIntersections::flip() { 29 for (int index = 0; index < fUsed; ++index) { 30 fT[1][index] = 1 - fT[1][index]; 31 } 32 } 33 34 int SkIntersections::insert(double one, double two, const SkDPoint& pt) { 35 if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { 36 // For now, don't allow a mix of coincident and non-coincident intersections 37 return -1; 38 } 39 SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); 40 int index; 41 for (index = 0; index < fUsed; ++index) { 42 double oldOne = fT[0][index]; 43 double oldTwo = fT[1][index]; 44 if (one == oldOne && two == oldTwo) { 45 return -1; 46 } 47 if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { 48 if ((!precisely_zero(one) || precisely_zero(oldOne)) 49 && (!precisely_equal(one, 1) || precisely_equal(oldOne, 1)) 50 && (!precisely_zero(two) || precisely_zero(oldTwo)) 51 && (!precisely_equal(two, 1) || precisely_equal(oldTwo, 1))) { 52 return -1; 53 } 54 SkASSERT(one >= 0 && one <= 1); 55 SkASSERT(two >= 0 && two <= 1); 56 // remove this and reinsert below in case replacing would make list unsorted 57 int remaining = fUsed - index - 1; 58 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 59 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 60 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 61 int clearMask = ~((1 << index) - 1); 62 fIsCoincident[0] -= (fIsCoincident[0] >> 1) & clearMask; 63 fIsCoincident[1] -= (fIsCoincident[1] >> 1) & clearMask; 64 --fUsed; 65 break; 66 } 67 #if ONE_OFF_DEBUG 68 if (pt.roughlyEqual(fPt[index])) { 69 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); 70 } 71 #endif 72 } 73 for (index = 0; index < fUsed; ++index) { 74 if (fT[0][index] > one) { 75 break; 76 } 77 } 78 if (fUsed >= fMax) { 79 SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must 80 // be propagated all the way back down to the caller, and return failure. 81 fUsed = 0; 82 return 0; 83 } 84 int remaining = fUsed - index; 85 if (remaining > 0) { 86 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); 87 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 88 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 89 int clearMask = ~((1 << index) - 1); 90 fIsCoincident[0] += fIsCoincident[0] & clearMask; 91 fIsCoincident[1] += fIsCoincident[1] & clearMask; 92 } 93 fPt[index] = pt; 94 if (one < 0 || one > 1) { 95 return -1; 96 } 97 if (two < 0 || two > 1) { 98 return -1; 99 } 100 fT[0][index] = one; 101 fT[1][index] = two; 102 ++fUsed; 103 SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt)); 104 return index; 105 } 106 107 void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { 108 SkASSERT(one == 0 || one == 1); 109 SkASSERT(two == 0 || two == 1); 110 SkASSERT(pt1 != pt2); 111 fNearlySame[one ? 1 : 0] = true; 112 (void) insert(one, two, pt1); 113 fPt2[one ? 1 : 0] = pt2; 114 } 115 116 int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 117 int index = insertSwap(one, two, pt); 118 if (index >= 0) { 119 setCoincident(index); 120 } 121 return index; 122 } 123 124 void SkIntersections::setCoincident(int index) { 125 SkASSERT(index >= 0); 126 int bit = 1 << index; 127 fIsCoincident[0] |= bit; 128 fIsCoincident[1] |= bit; 129 } 130 131 void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, 132 int bIndex) { 133 this->reset(); 134 fT[0][0] = a.fT[0][aIndex]; 135 fT[1][0] = b.fT[0][bIndex]; 136 fPt[0] = a.fPt[aIndex]; 137 fPt2[0] = b.fPt[bIndex]; 138 fUsed = 1; 139 } 140 141 int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const { 142 int result = -1; 143 for (int index = 0; index < fUsed; ++index) { 144 if (!between(rangeStart, fT[0][index], rangeEnd)) { 145 continue; 146 } 147 if (result < 0) { 148 result = index; 149 continue; 150 } 151 SkDVector best = fPt[result] - origin; 152 SkDVector test = fPt[index] - origin; 153 if (test.crossCheck(best) < 0) { 154 result = index; 155 } 156 } 157 return result; 158 } 159 160 void SkIntersections::removeOne(int index) { 161 int remaining = --fUsed - index; 162 if (remaining <= 0) { 163 return; 164 } 165 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 166 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 167 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 168 // SkASSERT(fIsCoincident[0] == 0); 169 int coBit = fIsCoincident[0] & (1 << index); 170 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 171 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 172 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 173 } 174
