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 SkASSERT(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 SkASSERT(one >= 0 && one <= 1); 86 SkASSERT(two >= 0 && two <= 1); 87 fT[0][index] = one; 88 fT[1][index] = two; 89 ++fUsed; 90 SkASSERT(fUsed <= SK_ARRAY_COUNT(fPt)); 91 return index; 92 } 93 94 void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) { 95 SkASSERT(one == 0 || one == 1); 96 SkASSERT(two == 0 || two == 1); 97 SkASSERT(pt1 != pt2); 98 fNearlySame[one ? 1 : 0] = true; 99 (void) insert(one, two, pt1); 100 fPt2[one ? 1 : 0] = pt2; 101 } 102 103 int SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 104 int index = insertSwap(one, two, pt); 105 if (index >= 0) { 106 setCoincident(index); 107 } 108 return index; 109 } 110 111 void SkIntersections::setCoincident(int index) { 112 SkASSERT(index >= 0); 113 int bit = 1 << index; 114 fIsCoincident[0] |= bit; 115 fIsCoincident[1] |= bit; 116 } 117 118 void SkIntersections::merge(const SkIntersections& a, int aIndex, const SkIntersections& b, 119 int bIndex) { 120 this->reset(); 121 fT[0][0] = a.fT[0][aIndex]; 122 fT[1][0] = b.fT[0][bIndex]; 123 fPt[0] = a.fPt[aIndex]; 124 fPt2[0] = b.fPt[bIndex]; 125 fUsed = 1; 126 } 127 128 int SkIntersections::mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const { 129 int result = -1; 130 for (int index = 0; index < fUsed; ++index) { 131 if (!between(rangeStart, fT[0][index], rangeEnd)) { 132 continue; 133 } 134 if (result < 0) { 135 result = index; 136 continue; 137 } 138 SkDVector best = fPt[result] - origin; 139 SkDVector test = fPt[index] - origin; 140 if (test.crossCheck(best) < 0) { 141 result = index; 142 } 143 } 144 return result; 145 } 146 147 void SkIntersections::removeOne(int index) { 148 int remaining = --fUsed - index; 149 if (remaining <= 0) { 150 return; 151 } 152 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 153 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 154 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 155 // SkASSERT(fIsCoincident[0] == 0); 156 int coBit = fIsCoincident[0] & (1 << index); 157 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 158 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 159 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 160 } 161