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 |