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

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

Issue 16951017: convert pathops to use SkSTArray where possible. (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: pathops use SkTArray Created 7 years, 6 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
« no previous file with comments | « src/pathops/SkDCubicToQuads.cpp ('k') | src/pathops/SkOpAngle.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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 "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
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
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 }
OLDNEW
« no previous file with comments | « src/pathops/SkDCubicToQuads.cpp ('k') | src/pathops/SkOpAngle.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698