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 |