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::*CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = { 11 NULL, 12 &SkIntersections::verticalLine, 13 &SkIntersections::verticalQuad, 14 &SkIntersections::verticalCubic 15 }; 16 17 int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = { 18 NULL, 19 NULL, 20 &SkIntersections::quadRay, 21 &SkIntersections::cubicRay 22 }; 23 24 int SkIntersections::coincidentUsed() const { 25 if (!fIsCoincident[0]) { 26 SkASSERT(!fIsCoincident[1]); 27 return 0; 28 } 29 int count = 0; 30 SkDEBUGCODE(int count2 = 0;) 31 for (int index = 0; index < fUsed; ++index) { 32 if (fIsCoincident[0] & (1 << index)) { 33 ++count; 34 } 35 #ifdef SK_DEBUG 36 if (fIsCoincident[1] & (1 << index)) { 37 ++count2; 38 } 39 #endif 40 } 41 SkASSERT(count == count2); 42 return count; 43 } 44 45 int SkIntersections::cubicRay(const SkPoint pts[4], const SkDLine& line) { 46 SkDCubic cubic; 47 cubic.set(pts); 48 return intersectRay(cubic, line); 49 } 50 51 void SkIntersections::flip() { 52 for (int index = 0; index < fUsed; ++index) { 53 fT[1][index] = 1 - fT[1][index]; 54 } 55 } 56 57 int SkIntersections::insert(double one, double two, const SkDPoint& pt) { 58 if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { 59 // For now, don't allow a mix of coincident and non-coincident intersections 60 return -1; 61 } 62 SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); 63 int index; 64 for (index = 0; index < fUsed; ++index) { 65 double oldOne = fT[0][index]; 66 double oldTwo = fT[1][index]; 67 if (one == oldOne && two == oldTwo) { 68 return -1; 69 } 70 if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { 71 if ((precisely_zero(one) && !precisely_zero(oldOne)) 72 || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) 73 || (precisely_zero(two) && !precisely_zero(oldTwo)) 74 || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { 75 fT[0][index] = one; 76 fT[1][index] = two; 77 fPt[index] = pt; 78 } 79 return -1; 80 } 81 #if ONE_OFF_DEBUG 82 if (pt.roughlyEqual(fPt[index])) { 83 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); 84 } 85 #endif 86 if (fT[0][index] > one) { 87 break; 88 } 89 } 90 SkASSERT(fUsed < 9); 91 int remaining = fUsed - index; 92 if (remaining > 0) { 93 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); 94 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); 95 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); 96 fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); 97 fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); 98 } 99 fPt[index] = pt; 100 fT[0][index] = one; 101 fT[1][index] = two; 102 ++fUsed; 103 return index; 104 } 105 106 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { 107 int index = insertSwap(one, two, pt); 108 int bit = 1 << index; 109 fIsCoincident[0] |= bit; 110 fIsCoincident[1] |= bit; 111 } 112 113 void SkIntersections::offset(int base, double start, double end) { 114 for (int index = base; index < fUsed; ++index) { 115 double val = fT[fSwap][index]; 116 val *= end - start; 117 val += start; 118 fT[fSwap][index] = val; 119 } 120 } 121 122 int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) { 123 SkDQuad quad; 124 quad.set(pts); 125 return intersectRay(quad, line); 126 } 127 128 void SkIntersections::quickRemoveOne(int index, int replace) { 129 if (index < replace) { 130 fT[0][index] = fT[0][replace]; 131 } 132 } 133 134 #if 0 135 void SkIntersections::remove(double one, double two, const SkDPoint& startPt, 136 const SkDPoint& endPt) { 137 for (int index = fUsed - 1; index >= 0; --index) { 138 if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index], two) 139 || startPt.approximatelyEqual(fPt[index]) 140 || endPt.approximatelyEqual(fPt[index]))) { 141 SkASSERT(fUsed > 0); 142 removeOne(index); 143 } 144 } 145 } 146 #endif 147 148 void SkIntersections::removeOne(int index) { 149 int remaining = --fUsed - index; 150 if (remaining <= 0) { 151 return; 152 } 153 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); 154 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); 155 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); 156 SkASSERT(fIsCoincident[0] == 0); 157 int coBit = fIsCoincident[0] & (1 << index); 158 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; 159 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); 160 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; 161 } 162 163 void SkIntersections::swapPts() { 164 int index; 165 for (index = 0; index < fUsed; ++index) { 166 SkTSwap(fT[0][index], fT[1][index]); 167 } 168 } 169 170 int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, 171 SkScalar x, bool flipped) { 172 SkDLine line; 173 line.set(a); 174 return vertical(line, top, bottom, x, flipped); 175 } 176 177 int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, 178 SkScalar x, bool flipped) { 179 SkDQuad quad; 180 quad.set(a); 181 return vertical(quad, top, bottom, x, flipped); 182 } 183 184 int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, 185 SkScalar x, bool flipped) { 186 SkDCubic cubic; 187 cubic.set(a); 188 return vertical(cubic, top, bottom, x, flipped); 189 } 190
