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 "DataTypes.h" 9 #include "Intersections.h" 10 11 void Intersections::insertCoincidentPair(double s1, double e1, double s2, double e2, 12 const _Point& startPt, const _Point& endPt) { 13 if (fSwap) { 14 remove(s2, e2, startPt, endPt); 15 } else { 16 remove(s1, e1, startPt, endPt); 17 } 18 SkASSERT(coincidentUsed() == fUsed); 19 SkASSERT((coincidentUsed() & 1) != 1); 20 int i1 = 0; 21 int i2 = 0; 22 do { 23 while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) { 24 ++i1; 25 } 26 if (i1 == fUsed) { 27 break; 28 } 29 SkASSERT(i1 < fUsed); 30 int iEnd1 = i1 + 1; 31 while (!(fIsCoincident[fSwap] & (1 << iEnd1))) { 32 ++iEnd1; 33 } 34 SkASSERT(iEnd1 < fUsed); 35 double cs1 = fT[fSwap][i1]; 36 double ce1 = fT[fSwap][iEnd1]; 37 bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1]) 38 || startPt.approximatelyEqual(fPt[iEnd1]); 39 bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1]) 40 || endPt.approximatelyEqual(fPt[iEnd1]); 41 while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) { 42 ++i2; 43 } 44 int iEnd2 = i2 + 1; 45 while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) { 46 ++iEnd2; 47 } 48 SkASSERT(iEnd2 < fUsed); 49 double cs2 = fT[fSwap ^ 1][i2]; 50 double ce2 = fT[fSwap ^ 1][iEnd2]; 51 bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2]) 52 || startPt.approximatelyEqual(fPt[iEnd2]); 53 bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2]) 54 || endPt.approximatelyEqual(fPt[iEnd2]); 55 if ((s1in | e1in) & (s2in | e2in)) { 56 if (s1 < cs1) { 57 fT[fSwap][i1] = s1; 58 fPt[i1] = startPt; 59 } else if (e1 < cs1) { 60 fT[fSwap][i1] = e1; 61 fPt[i1] = endPt; 62 } 63 if (s1 > ce1) { 64 fT[fSwap][iEnd1] = s1; 65 fPt[iEnd1] = startPt; 66 } else if (e1 > ce1) { 67 fT[fSwap][iEnd1] = e1; 68 fPt[iEnd1] = endPt; 69 } 70 if (s2 > e2) { 71 SkTSwap(cs2, ce2); 72 SkTSwap(i2, iEnd2); 73 } 74 if (s2 < cs2) { 75 fT[fSwap ^ 1][i2] = s2; 76 } else if (e2 < cs2) { 77 fT[fSwap ^ 1][i2] = e2; 78 } 79 if (s2 > ce2) { 80 fT[fSwap ^ 1][iEnd2] = s2; 81 } else if (e2 > ce2) { 82 fT[fSwap ^ 1][iEnd2] = e2; 83 } 84 return; 85 } 86 } while (true); 87 SkASSERT(fUsed < 9); 88 insertCoincident(s1, s2, startPt); 89 insertCoincident(e1, e2, endPt); 90 } 91 92 int Intersections::insert(double one, double two, const _Point& pt) { 93 SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); 94 int index; 95 for (index = 0; index < fUsed; ++index) { 96 double oldOne = fT[0][index]; 97 double oldTwo = fT[1][index]; 98 if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) { 99 if ((precisely_zero(one) && !precisely_zero(oldOne)) 100 || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) 101 || (precisely_zero(two) && !precisely_zero(oldTwo)) 102 || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { 103 fT[0][index] = one; 104 fT[1][index] = two; 105 fPt[index] = pt; 106 } 107 return -1; 108 } 109 #if ONE_OFF_DEBUG 110 if (pt.roughlyEqual(fPt[index])) { 111 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); 112 } 113 #endif 114 if (fT[0][index] > one) { 115 break; 116 } 117 } 118 SkASSERT(fUsed < 9); 119 int remaining = fUsed - index; 120 if (remaining > 0) { 121 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); 122 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 123 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 124 fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); 125 fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); 126 } 127 fPt[index] = pt; 128 fT[0][index] = one; 129 fT[1][index] = two; 130 ++fUsed; 131 return index; 132 } 133 134 void Intersections::remove(double one, double two, const _Point& startPt, const _Point& endPt) { 135 for (int index = fUsed - 1; index >= 0; --index) { 136 if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two) 137 || startPt.approximatelyEqual(fPt[index]) 138 || endPt.approximatelyEqual(fPt[index]))) { 139 SkASSERT(fUsed > 0); 140 removeOne(index); 141 } 142 } 143 } 144 145 void Intersections::removeOne(int index) { 146 int remaining = --fUsed - index; 147 if (remaining <= 0) { 148 return; 149 } 150 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 151 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 152 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 153 SkASSERT(fIsCoincident[0] == 0); 154 int coBit = fIsCoincident[0] & (1 << index); 155 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 156 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 157 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 158 } 159
