| OLD | NEW |
| 1 // Another approach is to start with the implicit form of one curve and solve | 1 // Another approach is to start with the implicit form of one curve and solve |
| 2 // (seek implicit coefficients in QuadraticParameter.cpp | 2 // (seek implicit coefficients in QuadraticParameter.cpp |
| 3 // by substituting in the parametric form of the other. | 3 // by substituting in the parametric form of the other. |
| 4 // The downside of this approach is that early rejects are difficult to come by. | 4 // The downside of this approach is that early rejects are difficult to come by. |
| 5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step | 5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step |
| 6 | 6 |
| 7 | 7 |
| 8 #include "SkDQuadImplicit.h" | 8 #include "SkDQuadImplicit.h" |
| 9 #include "SkIntersections.h" | 9 #include "SkIntersections.h" |
| 10 #include "SkPathOpsLine.h" | 10 #include "SkPathOpsLine.h" |
| (...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 113 } | 113 } |
| 114 return false; | 114 return false; |
| 115 } | 115 } |
| 116 | 116 |
| 117 // returns false if there's more than one intercept or the intercept doesn't mat
ch the point | 117 // returns false if there's more than one intercept or the intercept doesn't mat
ch the point |
| 118 // returns true if the intercept was successfully added or if the | 118 // returns true if the intercept was successfully added or if the |
| 119 // original quads need to be subdivided | 119 // original quads need to be subdivided |
| 120 static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou
ble tMax, | 120 static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou
ble tMax, |
| 121 SkIntersections* i, bool* subDivide) { | 121 SkIntersections* i, bool* subDivide) { |
| 122 double tMid = (tMin + tMax) / 2; | 122 double tMid = (tMin + tMax) / 2; |
| 123 SkDPoint mid = q2.xyAtT(tMid); | 123 SkDPoint mid = q2.ptAtT(tMid); |
| 124 SkDLine line; | 124 SkDLine line; |
| 125 line[0] = line[1] = mid; | 125 line[0] = line[1] = mid; |
| 126 SkDVector dxdy = q2.dxdyAtT(tMid); | 126 SkDVector dxdy = q2.dxdyAtT(tMid); |
| 127 line[0] -= dxdy; | 127 line[0] -= dxdy; |
| 128 line[1] += dxdy; | 128 line[1] += dxdy; |
| 129 SkIntersections rootTs; | 129 SkIntersections rootTs; |
| 130 rootTs.allowNear(false); | 130 rootTs.allowNear(false); |
| 131 int roots = rootTs.intersect(q1, line); | 131 int roots = rootTs.intersect(q1, line); |
| 132 if (roots == 0) { | 132 if (roots == 0) { |
| 133 if (subDivide) { | 133 if (subDivide) { |
| 134 *subDivide = true; | 134 *subDivide = true; |
| 135 } | 135 } |
| 136 return true; | 136 return true; |
| 137 } | 137 } |
| 138 if (roots == 2) { | 138 if (roots == 2) { |
| 139 return false; | 139 return false; |
| 140 } | 140 } |
| 141 SkDPoint pt2 = q1.xyAtT(rootTs[0][0]); | 141 SkDPoint pt2 = q1.ptAtT(rootTs[0][0]); |
| 142 if (!pt2.approximatelyEqualHalf(mid)) { | 142 if (!pt2.approximatelyEqualHalf(mid)) { |
| 143 return false; | 143 return false; |
| 144 } | 144 } |
| 145 i->insertSwap(rootTs[0][0], tMid, pt2); | 145 i->insertSwap(rootTs[0][0], tMid, pt2); |
| 146 return true; | 146 return true; |
| 147 } | 147 } |
| 148 | 148 |
| 149 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
Quad& q2, | 149 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
Quad& q2, |
| 150 double t2s, double t2e, SkIntersections* i, bool* su
bDivide) { | 150 double t2s, double t2e, SkIntersections* i, bool* su
bDivide) { |
| 151 SkDQuad hull = q1.subDivide(t1s, t1e); | 151 SkDQuad hull = q1.subDivide(t1s, t1e); |
| 152 SkDLine line = {{hull[2], hull[0]}}; | 152 SkDLine line = {{hull[2], hull[0]}}; |
| 153 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL
ine*) &hull[1] }; | 153 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL
ine*) &hull[1] }; |
| 154 const size_t kTestCount = SK_ARRAY_COUNT(testLines); | 154 const size_t kTestCount = SK_ARRAY_COUNT(testLines); |
| 155 SkSTArray<kTestCount * 2, double, true> tsFound; | 155 SkSTArray<kTestCount * 2, double, true> tsFound; |
| 156 for (size_t index = 0; index < kTestCount; ++index) { | 156 for (size_t index = 0; index < kTestCount; ++index) { |
| 157 SkIntersections rootTs; | 157 SkIntersections rootTs; |
| 158 rootTs.allowNear(false); | 158 rootTs.allowNear(false); |
| 159 int roots = rootTs.intersect(q2, *testLines[index]); | 159 int roots = rootTs.intersect(q2, *testLines[index]); |
| 160 for (int idx2 = 0; idx2 < roots; ++idx2) { | 160 for (int idx2 = 0; idx2 < roots; ++idx2) { |
| 161 double t = rootTs[0][idx2]; | 161 double t = rootTs[0][idx2]; |
| 162 #ifdef SK_DEBUG | 162 #ifdef SK_DEBUG |
| 163 SkDPoint qPt = q2.xyAtT(t); | 163 SkDPoint qPt = q2.ptAtT(t); |
| 164 SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]); | 164 SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]); |
| 165 SkASSERT(qPt.approximatelyEqual(lPt)); | 165 SkASSERT(qPt.approximatelyEqual(lPt)); |
| 166 #endif | 166 #endif |
| 167 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { | 167 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { |
| 168 continue; | 168 continue; |
| 169 } | 169 } |
| 170 tsFound.push_back(rootTs[0][idx2]); | 170 tsFound.push_back(rootTs[0][idx2]); |
| 171 } | 171 } |
| 172 } | 172 } |
| 173 int tCount = tsFound.count(); | 173 int tCount = tsFound.count(); |
| 174 if (tCount <= 0) { | 174 if (tCount <= 0) { |
| 175 return true; | 175 return true; |
| 176 } | 176 } |
| 177 double tMin, tMax; | 177 double tMin, tMax; |
| 178 if (tCount == 1) { | 178 if (tCount == 1) { |
| 179 tMin = tMax = tsFound[0]; | 179 tMin = tMax = tsFound[0]; |
| 180 } else { | 180 } else { |
| 181 SkASSERT(tCount > 1); | 181 SkASSERT(tCount > 1); |
| 182 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); | 182 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); |
| 183 tMin = tsFound[0]; | 183 tMin = tsFound[0]; |
| 184 tMax = tsFound[tsFound.count() - 1]; | 184 tMax = tsFound[tsFound.count() - 1]; |
| 185 } | 185 } |
| 186 SkDPoint end = q2.xyAtT(t2s); | 186 SkDPoint end = q2.ptAtT(t2s); |
| 187 bool startInTriangle = hull.pointInHull(end); | 187 bool startInTriangle = hull.pointInHull(end); |
| 188 if (startInTriangle) { | 188 if (startInTriangle) { |
| 189 tMin = t2s; | 189 tMin = t2s; |
| 190 } | 190 } |
| 191 end = q2.xyAtT(t2e); | 191 end = q2.ptAtT(t2e); |
| 192 bool endInTriangle = hull.pointInHull(end); | 192 bool endInTriangle = hull.pointInHull(end); |
| 193 if (endInTriangle) { | 193 if (endInTriangle) { |
| 194 tMax = t2e; | 194 tMax = t2e; |
| 195 } | 195 } |
| 196 int split = 0; | 196 int split = 0; |
| 197 SkDVector dxy1, dxy2; | 197 SkDVector dxy1, dxy2; |
| 198 if (tMin != tMax || tCount > 2) { | 198 if (tMin != tMax || tCount > 2) { |
| 199 dxy2 = q2.dxdyAtT(tMin); | 199 dxy2 = q2.dxdyAtT(tMin); |
| 200 for (int index = 1; index < tCount; ++index) { | 200 for (int index = 1; index < tCount; ++index) { |
| 201 dxy1 = dxy2; | 201 dxy1 = dxy2; |
| (...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 283 // each time through the loop, this computes values it had from the last loop | 283 // each time through the loop, this computes values it had from the last loop |
| 284 // if i == j == 1, the center values are still good | 284 // if i == j == 1, the center values are still good |
| 285 // otherwise, for i != 1 or j != 1, four of the values are still good | 285 // otherwise, for i != 1 or j != 1, four of the values are still good |
| 286 // and if i == 1 ^ j == 1, an additional value is good | 286 // and if i == 1 ^ j == 1, an additional value is good |
| 287 static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1
Seed, | 287 static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1
Seed, |
| 288 double* t2Seed, SkDPoint* pt) { | 288 double* t2Seed, SkDPoint* pt) { |
| 289 double tStep = ROUGH_EPSILON; | 289 double tStep = ROUGH_EPSILON; |
| 290 SkDPoint t1[3], t2[3]; | 290 SkDPoint t1[3], t2[3]; |
| 291 int calcMask = ~0; | 291 int calcMask = ~0; |
| 292 do { | 292 do { |
| 293 if (calcMask & (1 << 1)) t1[1] = quad1.xyAtT(*t1Seed); | 293 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); |
| 294 if (calcMask & (1 << 4)) t2[1] = quad2.xyAtT(*t2Seed); | 294 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); |
| 295 if (t1[1].approximatelyEqual(t2[1])) { | 295 if (t1[1].approximatelyEqual(t2[1])) { |
| 296 *pt = t1[1]; | 296 *pt = t1[1]; |
| 297 #if ONE_OFF_DEBUG | 297 #if ONE_OFF_DEBUG |
| 298 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, | 298 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, |
| 299 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); | 299 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); |
| 300 #endif | 300 #endif |
| 301 return true; | 301 return true; |
| 302 } | 302 } |
| 303 if (calcMask & (1 << 0)) t1[0] = quad1.xyAtT(*t1Seed - tStep); | 303 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); |
| 304 if (calcMask & (1 << 2)) t1[2] = quad1.xyAtT(*t1Seed + tStep); | 304 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); |
| 305 if (calcMask & (1 << 3)) t2[0] = quad2.xyAtT(*t2Seed - tStep); | 305 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); |
| 306 if (calcMask & (1 << 5)) t2[2] = quad2.xyAtT(*t2Seed + tStep); | 306 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); |
| 307 double dist[3][3]; | 307 double dist[3][3]; |
| 308 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions | 308 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions |
| 309 // if prior loop's results are moved to correct slot for reuse | 309 // if prior loop's results are moved to correct slot for reuse |
| 310 dist[1][1] = t1[1].distanceSquared(t2[1]); | 310 dist[1][1] = t1[1].distanceSquared(t2[1]); |
| 311 int best_i = 1, best_j = 1; | 311 int best_i = 1, best_j = 1; |
| 312 for (int i = 0; i < 3; ++i) { | 312 for (int i = 0; i < 3; ++i) { |
| 313 for (int j = 0; j < 3; ++j) { | 313 for (int j = 0; j < 3; ++j) { |
| 314 if (i == 1 && j == 1) { | 314 if (i == 1 && j == 1) { |
| 315 continue; | 315 continue; |
| 316 } | 316 } |
| (...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 416 bool flip1 = q1[2] == q2[0]; | 416 bool flip1 = q1[2] == q2[0]; |
| 417 bool flip2 = q1[0] == q2[2]; | 417 bool flip2 = q1[0] == q2[2]; |
| 418 bool useCubic = q1[0] == q2[0]; | 418 bool useCubic = q1[0] == q2[0]; |
| 419 double roots1[4]; | 419 double roots1[4]; |
| 420 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); | 420 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); |
| 421 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 | 421 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 |
| 422 double roots1Copy[4]; | 422 double roots1Copy[4]; |
| 423 int r1Count = addValidRoots(roots1, rootCount, roots1Copy); | 423 int r1Count = addValidRoots(roots1, rootCount, roots1Copy); |
| 424 SkDPoint pts1[4]; | 424 SkDPoint pts1[4]; |
| 425 for (index = 0; index < r1Count; ++index) { | 425 for (index = 0; index < r1Count; ++index) { |
| 426 pts1[index] = q1.xyAtT(roots1Copy[index]); | 426 pts1[index] = q1.ptAtT(roots1Copy[index]); |
| 427 } | 427 } |
| 428 double roots2[4]; | 428 double roots2[4]; |
| 429 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); | 429 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); |
| 430 double roots2Copy[4]; | 430 double roots2Copy[4]; |
| 431 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); | 431 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); |
| 432 SkDPoint pts2[4]; | 432 SkDPoint pts2[4]; |
| 433 for (index = 0; index < r2Count; ++index) { | 433 for (index = 0; index < r2Count; ++index) { |
| 434 pts2[index] = q2.xyAtT(roots2Copy[index]); | 434 pts2[index] = q2.ptAtT(roots2Copy[index]); |
| 435 } | 435 } |
| 436 if (r1Count == r2Count && r1Count <= 1) { | 436 if (r1Count == r2Count && r1Count <= 1) { |
| 437 if (r1Count == 1) { | 437 if (r1Count == 1) { |
| 438 if (pts1[0].approximatelyEqualHalf(pts2[0])) { | 438 if (pts1[0].approximatelyEqualHalf(pts2[0])) { |
| 439 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | 439 insert(roots1Copy[0], roots2Copy[0], pts1[0]); |
| 440 } else if (pts1[0].moreRoughlyEqual(pts2[0])) { | 440 } else if (pts1[0].moreRoughlyEqual(pts2[0])) { |
| 441 // experiment: try to find intersection by chasing t | 441 // experiment: try to find intersection by chasing t |
| 442 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); | 442 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); |
| 443 (void) addValidRoots(roots1, rootCount, roots1Copy); | 443 (void) addValidRoots(roots1, rootCount, roots1Copy); |
| 444 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); | 444 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); |
| (...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 501 } | 501 } |
| 502 if (lowestIndex < 0) { | 502 if (lowestIndex < 0) { |
| 503 break; | 503 break; |
| 504 } | 504 } |
| 505 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 505 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
| 506 pts1[lowestIndex]); | 506 pts1[lowestIndex]); |
| 507 closest[lowestIndex] = -1; | 507 closest[lowestIndex] = -1; |
| 508 } while (++used < r1Count); | 508 } while (++used < r1Count); |
| 509 return fUsed; | 509 return fUsed; |
| 510 } | 510 } |
| OLD | NEW |