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