| 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" |
| 11 #include "SkQuarticRoot.h" | 11 #include "SkQuarticRoot.h" |
| 12 #include "SkTDArray.h" | 12 #include "SkTArray.h" |
| 13 #include "SkTSort.h" | 13 #include "SkTSort.h" |
| 14 | 14 |
| 15 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F | 15 /* given the implicit form 0 = Ax^2 + Bxy + Cy^2 + Dx + Ey + F |
| 16 * and given x = at^2 + bt + c (the parameterized form) | 16 * and given x = at^2 + bt + c (the parameterized form) |
| 17 * y = dt^2 + et + f | 17 * y = dt^2 + et + f |
| 18 * then | 18 * then |
| 19 * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D
(at^2+bt+c)+E(dt^2+et+f)+F | 19 * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D
(at^2+bt+c)+E(dt^2+et+f)+F |
| 20 */ | 20 */ |
| 21 | 21 |
| 22 static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots
[4], | 22 static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots
[4], |
| (...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 143 } | 143 } |
| 144 i->insertSwap(rootTs[0][0], tMid, pt2); | 144 i->insertSwap(rootTs[0][0], tMid, pt2); |
| 145 return true; | 145 return true; |
| 146 } | 146 } |
| 147 | 147 |
| 148 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
Quad& q2, | 148 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD
Quad& q2, |
| 149 double t2s, double t2e, SkIntersections* i, bool* su
bDivide) { | 149 double t2s, double t2e, SkIntersections* i, bool* su
bDivide) { |
| 150 SkDQuad hull = q1.subDivide(t1s, t1e); | 150 SkDQuad hull = q1.subDivide(t1s, t1e); |
| 151 SkDLine line = {{hull[2], hull[0]}}; | 151 SkDLine line = {{hull[2], hull[0]}}; |
| 152 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL
ine*) &hull[1] }; | 152 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL
ine*) &hull[1] }; |
| 153 size_t testCount = SK_ARRAY_COUNT(testLines); | 153 const size_t kTestCount = SK_ARRAY_COUNT(testLines); |
| 154 SkTDArray<double> tsFound; | 154 SkSTArray<kTestCount * 2, double, true> tsFound; |
| 155 for (size_t index = 0; index < testCount; ++index) { | 155 for (size_t index = 0; index < kTestCount; ++index) { |
| 156 SkIntersections rootTs; | 156 SkIntersections rootTs; |
| 157 int roots = rootTs.intersect(q2, *testLines[index]); | 157 int roots = rootTs.intersect(q2, *testLines[index]); |
| 158 for (int idx2 = 0; idx2 < roots; ++idx2) { | 158 for (int idx2 = 0; idx2 < roots; ++idx2) { |
| 159 double t = rootTs[0][idx2]; | 159 double t = rootTs[0][idx2]; |
| 160 #ifdef SK_DEBUG | 160 #ifdef SK_DEBUG |
| 161 SkDPoint qPt = q2.xyAtT(t); | 161 SkDPoint qPt = q2.xyAtT(t); |
| 162 SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]); | 162 SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]); |
| 163 SkASSERT(qPt.approximatelyEqual(lPt)); | 163 SkASSERT(qPt.approximatelyEqual(lPt)); |
| 164 #endif | 164 #endif |
| 165 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { | 165 if (approximately_negative(t - t2s) || approximately_positive(t - t2
e)) { |
| 166 continue; | 166 continue; |
| 167 } | 167 } |
| 168 *tsFound.append() = rootTs[0][idx2]; | 168 tsFound.push_back(rootTs[0][idx2]); |
| 169 } | 169 } |
| 170 } | 170 } |
| 171 int tCount = tsFound.count(); | 171 int tCount = tsFound.count(); |
| 172 if (tCount <= 0) { | 172 if (tCount <= 0) { |
| 173 return true; | 173 return true; |
| 174 } | 174 } |
| 175 double tMin, tMax; | 175 double tMin, tMax; |
| 176 if (tCount == 1) { | 176 if (tCount == 1) { |
| 177 tMin = tMax = tsFound[0]; | 177 tMin = tMax = tsFound[0]; |
| 178 } else if (tCount > 1) { | 178 } else if (tCount > 1) { |
| (...skipping 319 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 498 } | 498 } |
| 499 if (lowestIndex < 0) { | 499 if (lowestIndex < 0) { |
| 500 break; | 500 break; |
| 501 } | 501 } |
| 502 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 502 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
| 503 pts1[lowestIndex]); | 503 pts1[lowestIndex]); |
| 504 closest[lowestIndex] = -1; | 504 closest[lowestIndex] = -1; |
| 505 } while (++used < r1Count); | 505 } while (++used < r1Count); |
| 506 return fUsed; | 506 return fUsed; |
| 507 } | 507 } |
| OLD | NEW |