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 SkASSERT(one >= 0 && one <= 1); 53 SkASSERT(two >= 0 && two <= 1); 54 fT[0][index] = one; 55 fT[1][index] = two; 56 fPt[index] = pt; 57 } 58 return -1; 59 } 60 #if ONE_OFF_DEBUG 61 if (pt.roughlyEqual(fPt[index])) { 62 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); 63 } 64 #endif 65 if (fT[0][index] > one) { 66 break; 67 } 68 } 69 if (fUsed >= fMax) { 70 SkOPASSERT(0); // FIXME : this error, if it is to be handled at runtime in release, must 71 // be propagated all the way back down to the caller, and return failure. 72 fUsed = 0; 73 return 0; 74 } 75 int remaining = fUsed - index; 76 if (remaining > 0) { 77 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); 78 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 79 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 80 int clearMask = ~((1 << index) - 1); 81 fIsCoincident[0] += fIsCoincident[0] & clearMask; 82 fIsCoincident[1] += fIsCoincident[1] & clearMask; 83 } 84 fPt[index] = pt; 85 if (one < 0 || one > 1) { 86 return -1; 87 } 88 if (two < 0 || two > 1) { 89 return -1; 90 } 91 fT[0][index] = one; 92 fT[1][index] = two; 93 ++fUsed; 94 SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt)); 95 return index; 96 } 97 98 void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { 99 SkASSERT(one == 0 || one == 1); 100 SkASSERT(two == 0 || two == 1); 101 SkASSERT(pt1 != pt2); 102 fNearlySame[one ? 1 : 0] = true; 103 (void) insert(one, two, pt1); 104 fPt2[one ? 1 : 0] = pt2; 105 } 106 107 int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 108 int index = insertSwap(one, two, pt); 109 if (index >= 0) { 110 setCoincident(index); 111 } 112 return index; 113 } 114 115 void SkIntersections::setCoincident(int index) { 116 SkASSERT(index >= 0); 117 int bit = 1 << index; 118 fIsCoincident[0] |= bit; 119 fIsCoincident[1] |= bit; 120 } 121 122 void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, 123 int bIndex) { 124 this->reset(); 125 fT[0][0] = a.fT[0][aIndex]; 126 fT[1][0] = b.fT[0][bIndex]; 127 fPt[0] = a.fPt[aIndex]; 128 fPt2[0] = b.fPt[bIndex]; 129 fUsed = 1; 130 } 131 132 int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const { 133 int result = -1; 134 for (int index = 0; index < fUsed; ++index) { 135 if (!between(rangeStart, fT[0][index], rangeEnd)) { 136 continue; 137 } 138 if (result < 0) { 139 result = index; 140 continue; 141 } 142 SkDVector best = fPt[result] - origin; 143 SkDVector test = fPt[index] - origin; 144 if (test.crossCheck(best) < 0) { 145 result = index; 146 } 147 } 148 return result; 149 } 150 151 void SkIntersections::removeOne(int index) { 152 int remaining = --fUsed - index; 153 if (remaining <= 0) { 154 return; 155 } 156 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 157 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 158 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 159 // SkASSERT(fIsCoincident[0] == 0); 160 int coBit = fIsCoincident[0] & (1 << index); 161 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 162 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 163 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 164 } 165
