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 "SkTDArray.h" |
13 #include "TSearch.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& q2, double roots[4
], | 22 static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4
], |
23 bool oneHint, int firstCubicRoot) { | 23 bool oneHint, int firstCubicRoot) { |
(...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
162 } | 162 } |
163 } | 163 } |
164 int tCount = tsFound.count(); | 164 int tCount = tsFound.count(); |
165 if (tCount <= 0) { | 165 if (tCount <= 0) { |
166 return true; | 166 return true; |
167 } | 167 } |
168 double tMin, tMax; | 168 double tMin, tMax; |
169 if (tCount == 1) { | 169 if (tCount == 1) { |
170 tMin = tMax = tsFound[0]; | 170 tMin = tMax = tsFound[0]; |
171 } else if (tCount > 1) { | 171 } else if (tCount > 1) { |
172 QSort<double>(tsFound.begin(), tsFound.end() - 1); | 172 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); |
173 tMin = tsFound[0]; | 173 tMin = tsFound[0]; |
174 tMax = tsFound[tsFound.count() - 1]; | 174 tMax = tsFound[tsFound.count() - 1]; |
175 } | 175 } |
176 SkDPoint end = q2.xyAtT(t2s); | 176 SkDPoint end = q2.xyAtT(t2s); |
177 bool startInTriangle = hull.pointInHull(end); | 177 bool startInTriangle = hull.pointInHull(end); |
178 if (startInTriangle) { | 178 if (startInTriangle) { |
179 tMin = t2s; | 179 tMin = t2s; |
180 } | 180 } |
181 end = q2.xyAtT(t2e); | 181 end = q2.xyAtT(t2e); |
182 bool endInTriangle = hull.pointInHull(end); | 182 bool endInTriangle = hull.pointInHull(end); |
(...skipping 306 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
489 } | 489 } |
490 if (lowestIndex < 0) { | 490 if (lowestIndex < 0) { |
491 break; | 491 break; |
492 } | 492 } |
493 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 493 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
494 pts1[lowestIndex]); | 494 pts1[lowestIndex]); |
495 closest[lowestIndex] = -1; | 495 closest[lowestIndex] = -1; |
496 } while (++used < r1Count); | 496 } while (++used < r1Count); |
497 return fUsed; | 497 return fUsed; |
498 } | 498 } |
OLD | NEW |