Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(536)

Side by Side Diff: src/pathops/SkDQuadIntersection.cpp

Issue 14034014: path ops -- use standard SkTQSort (Closed) Base URL: http://skia.googlecode.com/svn/trunk/
Patch Set: Created 7 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698