OLD | NEW |
(Empty) | |
| 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, SkS
calar, 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[0]); |
| 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 void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub
le e2, |
| 58 const SkDPoint& startPt, const SkDPoint& endPt) { |
| 59 if (fSwap) { |
| 60 remove(s2, e2, startPt, endPt); |
| 61 } else { |
| 62 remove(s1, e1, startPt, endPt); |
| 63 } |
| 64 SkASSERT(coincidentUsed() == fUsed); |
| 65 SkASSERT((coincidentUsed() & 1) != 1); |
| 66 int i1 = 0; |
| 67 int i2 = 0; |
| 68 do { |
| 69 while (i1 < fUsed && !(fIsCoincident[fSwap] & (1 << i1))) { |
| 70 ++i1; |
| 71 } |
| 72 if (i1 == fUsed) { |
| 73 break; |
| 74 } |
| 75 SkASSERT(i1 < fUsed); |
| 76 int iEnd1 = i1 + 1; |
| 77 while (!(fIsCoincident[fSwap] & (1 << iEnd1))) { |
| 78 ++iEnd1; |
| 79 } |
| 80 SkASSERT(iEnd1 < fUsed); |
| 81 double cs1 = fT[fSwap][i1]; |
| 82 double ce1 = fT[fSwap][iEnd1]; |
| 83 bool s1in = between(cs1, s1, ce1) || startPt.approximatelyEqual(fPt[i1]) |
| 84 || startPt.approximatelyEqual(fPt[iEnd1]); |
| 85 bool e1in = between(cs1, e1, ce1) || endPt.approximatelyEqual(fPt[i1]) |
| 86 || endPt.approximatelyEqual(fPt[iEnd1]); |
| 87 while (i2 < fUsed && !(fIsCoincident[fSwap ^ 1] & (1 << i2))) { |
| 88 ++i2; |
| 89 } |
| 90 int iEnd2 = i2 + 1; |
| 91 while (!(fIsCoincident[fSwap ^ 1] & (1 << iEnd2))) { |
| 92 ++iEnd2; |
| 93 } |
| 94 SkASSERT(iEnd2 < fUsed); |
| 95 double cs2 = fT[fSwap ^ 1][i2]; |
| 96 double ce2 = fT[fSwap ^ 1][iEnd2]; |
| 97 bool s2in = between(cs2, s2, ce2) || startPt.approximatelyEqual(fPt[i2]) |
| 98 || startPt.approximatelyEqual(fPt[iEnd2]); |
| 99 bool e2in = between(cs2, e2, ce2) || endPt.approximatelyEqual(fPt[i2]) |
| 100 || endPt.approximatelyEqual(fPt[iEnd2]); |
| 101 if ((s1in | e1in) & (s2in | e2in)) { |
| 102 if (s1 < cs1) { |
| 103 fT[fSwap][i1] = s1; |
| 104 fPt[i1] = startPt; |
| 105 } else if (e1 < cs1) { |
| 106 fT[fSwap][i1] = e1; |
| 107 fPt[i1] = endPt; |
| 108 } |
| 109 if (s1 > ce1) { |
| 110 fT[fSwap][iEnd1] = s1; |
| 111 fPt[iEnd1] = startPt; |
| 112 } else if (e1 > ce1) { |
| 113 fT[fSwap][iEnd1] = e1; |
| 114 fPt[iEnd1] = endPt; |
| 115 } |
| 116 if (s2 > e2) { |
| 117 SkTSwap(cs2, ce2); |
| 118 SkTSwap(i2, iEnd2); |
| 119 } |
| 120 if (s2 < cs2) { |
| 121 fT[fSwap ^ 1][i2] = s2; |
| 122 } else if (e2 < cs2) { |
| 123 fT[fSwap ^ 1][i2] = e2; |
| 124 } |
| 125 if (s2 > ce2) { |
| 126 fT[fSwap ^ 1][iEnd2] = s2; |
| 127 } else if (e2 > ce2) { |
| 128 fT[fSwap ^ 1][iEnd2] = e2; |
| 129 } |
| 130 return; |
| 131 } |
| 132 } while (true); |
| 133 SkASSERT(fUsed < 9); |
| 134 insertCoincident(s1, s2, startPt); |
| 135 insertCoincident(e1, e2, endPt); |
| 136 } |
| 137 |
| 138 int SkIntersections::insert(double one, double two, const SkDPoint& pt) { |
| 139 SkASSERT(fUsed <= 1 || fT[0][0] <= fT[0][1]); |
| 140 int index; |
| 141 for (index = 0; index < fUsed; ++index) { |
| 142 double oldOne = fT[0][index]; |
| 143 double oldTwo = fT[1][index]; |
| 144 if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) { |
| 145 if ((precisely_zero(one) && !precisely_zero(oldOne)) |
| 146 || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) |
| 147 || (precisely_zero(two) && !precisely_zero(oldTwo)) |
| 148 || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1)))
{ |
| 149 fT[0][index] = one; |
| 150 fT[1][index] = two; |
| 151 fPt[index] = pt; |
| 152 } |
| 153 return -1; |
| 154 } |
| 155 #if ONE_OFF_DEBUG |
| 156 if (pt.roughlyEqual(fPt[index])) { |
| 157 SkDebugf("%s t=%1.9g pts roughly equal\n", __FUNCTION__, one); |
| 158 } |
| 159 #endif |
| 160 if (fT[0][index] > one) { |
| 161 break; |
| 162 } |
| 163 } |
| 164 SkASSERT(fUsed < 9); |
| 165 int remaining = fUsed - index; |
| 166 if (remaining > 0) { |
| 167 memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining); |
| 168 memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining); |
| 169 memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining); |
| 170 fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); |
| 171 fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); |
| 172 } |
| 173 fPt[index] = pt; |
| 174 fT[0][index] = one; |
| 175 fT[1][index] = two; |
| 176 ++fUsed; |
| 177 return index; |
| 178 } |
| 179 |
| 180 void SkIntersections::insertCoincident(double one, double two, const SkDPoint& p
t) { |
| 181 int index = insertSwap(one, two, pt); |
| 182 int bit = 1 << index; |
| 183 fIsCoincident[0] |= bit; |
| 184 fIsCoincident[1] |= bit; |
| 185 } |
| 186 |
| 187 void SkIntersections::offset(int base, double start, double end) { |
| 188 for (int index = base; index < fUsed; ++index) { |
| 189 double val = fT[fSwap][index]; |
| 190 val *= end - start; |
| 191 val += start; |
| 192 fT[fSwap][index] = val; |
| 193 } |
| 194 } |
| 195 |
| 196 int SkIntersections::quadRay(const SkPoint pts[3], const SkDLine& line) { |
| 197 SkDQuad quad; |
| 198 quad.set(pts); |
| 199 return intersectRay(quad, line); |
| 200 } |
| 201 |
| 202 void SkIntersections::quickRemoveOne(int index, int replace) { |
| 203 if (index < replace) { |
| 204 fT[0][index] = fT[0][replace]; |
| 205 } |
| 206 } |
| 207 |
| 208 void SkIntersections::remove(double one, double two, const SkDPoint& startPt, |
| 209 const SkDPoint& endPt) { |
| 210 for (int index = fUsed - 1; index >= 0; --index) { |
| 211 if (!(fIsCoincident[0] & (1 << index)) && (between(one, fT[fSwap][index]
, two) |
| 212 || startPt.approximatelyEqual(fPt[index]) |
| 213 || endPt.approximatelyEqual(fPt[index]))) { |
| 214 SkASSERT(fUsed > 0); |
| 215 removeOne(index); |
| 216 } |
| 217 } |
| 218 } |
| 219 |
| 220 void SkIntersections::removeOne(int index) { |
| 221 int remaining = --fUsed - index; |
| 222 if (remaining <= 0) { |
| 223 return; |
| 224 } |
| 225 memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining); |
| 226 memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining); |
| 227 memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining); |
| 228 SkASSERT(fIsCoincident[0] == 0); |
| 229 int coBit = fIsCoincident[0] & (1 << index); |
| 230 fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit; |
| 231 SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index)))); |
| 232 fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit; |
| 233 } |
| 234 |
| 235 void SkIntersections::swapPts() { |
| 236 int index; |
| 237 for (index = 0; index < fUsed; ++index) { |
| 238 SkTSwap(fT[0][index], fT[1][index]); |
| 239 } |
| 240 } |
| 241 |
| 242 int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bot
tom, |
| 243 SkScalar x, bool flipped) { |
| 244 SkDLine line; |
| 245 line.set(a); |
| 246 return vertical(line, top, bottom, x, flipped); |
| 247 } |
| 248 |
| 249 int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bot
tom, |
| 250 SkScalar x, bool flipped) { |
| 251 SkDQuad quad; |
| 252 quad.set(a); |
| 253 return vertical(quad, top, bottom, x, flipped); |
| 254 } |
| 255 |
| 256 int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bo
ttom, |
| 257 SkScalar x, bool flipped) { |
| 258 SkDCubic cubic; |
| 259 cubic.set(a); |
| 260 return vertical(cubic, top, bottom, x, flipped); |
| 261 } |
OLD | NEW |