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

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

Issue 19543005: turn off debugging printfs (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Created 7 years, 5 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"
(...skipping 102 matching lines...) Expand 10 before | Expand all | Expand 10 after
113 } 113 }
114 return false; 114 return false;
115 } 115 }
116 116
117 // returns false if there's more than one intercept or the intercept doesn't mat ch the point 117 // returns false if there's more than one intercept or the intercept doesn't mat ch the point
118 // returns true if the intercept was successfully added or if the 118 // returns true if the intercept was successfully added or if the
119 // original quads need to be subdivided 119 // original quads need to be subdivided
120 static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou ble tMax, 120 static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou ble tMax,
121 SkIntersections* i, bool* subDivide) { 121 SkIntersections* i, bool* subDivide) {
122 double tMid = (tMin + tMax) / 2; 122 double tMid = (tMin + tMax) / 2;
123 SkDPoint mid = q2.xyAtT(tMid); 123 SkDPoint mid = q2.ptAtT(tMid);
124 SkDLine line; 124 SkDLine line;
125 line[0] = line[1] = mid; 125 line[0] = line[1] = mid;
126 SkDVector dxdy = q2.dxdyAtT(tMid); 126 SkDVector dxdy = q2.dxdyAtT(tMid);
127 line[0] -= dxdy; 127 line[0] -= dxdy;
128 line[1] += dxdy; 128 line[1] += dxdy;
129 SkIntersections rootTs; 129 SkIntersections rootTs;
130 rootTs.allowNear(false); 130 rootTs.allowNear(false);
131 int roots = rootTs.intersect(q1, line); 131 int roots = rootTs.intersect(q1, line);
132 if (roots == 0) { 132 if (roots == 0) {
133 if (subDivide) { 133 if (subDivide) {
134 *subDivide = true; 134 *subDivide = true;
135 } 135 }
136 return true; 136 return true;
137 } 137 }
138 if (roots == 2) { 138 if (roots == 2) {
139 return false; 139 return false;
140 } 140 }
141 SkDPoint pt2 = q1.xyAtT(rootTs[0][0]); 141 SkDPoint pt2 = q1.ptAtT(rootTs[0][0]);
142 if (!pt2.approximatelyEqualHalf(mid)) { 142 if (!pt2.approximatelyEqualHalf(mid)) {
143 return false; 143 return false;
144 } 144 }
145 i->insertSwap(rootTs[0][0], tMid, pt2); 145 i->insertSwap(rootTs[0][0], tMid, pt2);
146 return true; 146 return true;
147 } 147 }
148 148
149 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD Quad& q2, 149 static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD Quad& q2,
150 double t2s, double t2e, SkIntersections* i, bool* su bDivide) { 150 double t2s, double t2e, SkIntersections* i, bool* su bDivide) {
151 SkDQuad hull = q1.subDivide(t1s, t1e); 151 SkDQuad hull = q1.subDivide(t1s, t1e);
152 SkDLine line = {{hull[2], hull[0]}}; 152 SkDLine line = {{hull[2], hull[0]}};
153 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL ine*) &hull[1] }; 153 const SkDLine* testLines[] = { &line, (const SkDLine*) &hull[0], (const SkDL ine*) &hull[1] };
154 const size_t kTestCount = SK_ARRAY_COUNT(testLines); 154 const size_t kTestCount = SK_ARRAY_COUNT(testLines);
155 SkSTArray<kTestCount * 2, double, true> tsFound; 155 SkSTArray<kTestCount * 2, double, true> tsFound;
156 for (size_t index = 0; index < kTestCount; ++index) { 156 for (size_t index = 0; index < kTestCount; ++index) {
157 SkIntersections rootTs; 157 SkIntersections rootTs;
158 rootTs.allowNear(false); 158 rootTs.allowNear(false);
159 int roots = rootTs.intersect(q2, *testLines[index]); 159 int roots = rootTs.intersect(q2, *testLines[index]);
160 for (int idx2 = 0; idx2 < roots; ++idx2) { 160 for (int idx2 = 0; idx2 < roots; ++idx2) {
161 double t = rootTs[0][idx2]; 161 double t = rootTs[0][idx2];
162 #ifdef SK_DEBUG 162 #ifdef SK_DEBUG
163 SkDPoint qPt = q2.xyAtT(t); 163 SkDPoint qPt = q2.ptAtT(t);
164 SkDPoint lPt = testLines[index]->xyAtT(rootTs[1][idx2]); 164 SkDPoint lPt = testLines[index]->ptAtT(rootTs[1][idx2]);
165 SkASSERT(qPt.approximatelyEqual(lPt)); 165 SkASSERT(qPt.approximatelyEqual(lPt));
166 #endif 166 #endif
167 if (approximately_negative(t - t2s) || approximately_positive(t - t2 e)) { 167 if (approximately_negative(t - t2s) || approximately_positive(t - t2 e)) {
168 continue; 168 continue;
169 } 169 }
170 tsFound.push_back(rootTs[0][idx2]); 170 tsFound.push_back(rootTs[0][idx2]);
171 } 171 }
172 } 172 }
173 int tCount = tsFound.count(); 173 int tCount = tsFound.count();
174 if (tCount <= 0) { 174 if (tCount <= 0) {
175 return true; 175 return true;
176 } 176 }
177 double tMin, tMax; 177 double tMin, tMax;
178 if (tCount == 1) { 178 if (tCount == 1) {
179 tMin = tMax = tsFound[0]; 179 tMin = tMax = tsFound[0];
180 } else { 180 } else {
181 SkASSERT(tCount > 1); 181 SkASSERT(tCount > 1);
182 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1); 182 SkTQSort<double>(tsFound.begin(), tsFound.end() - 1);
183 tMin = tsFound[0]; 183 tMin = tsFound[0];
184 tMax = tsFound[tsFound.count() - 1]; 184 tMax = tsFound[tsFound.count() - 1];
185 } 185 }
186 SkDPoint end = q2.xyAtT(t2s); 186 SkDPoint end = q2.ptAtT(t2s);
187 bool startInTriangle = hull.pointInHull(end); 187 bool startInTriangle = hull.pointInHull(end);
188 if (startInTriangle) { 188 if (startInTriangle) {
189 tMin = t2s; 189 tMin = t2s;
190 } 190 }
191 end = q2.xyAtT(t2e); 191 end = q2.ptAtT(t2e);
192 bool endInTriangle = hull.pointInHull(end); 192 bool endInTriangle = hull.pointInHull(end);
193 if (endInTriangle) { 193 if (endInTriangle) {
194 tMax = t2e; 194 tMax = t2e;
195 } 195 }
196 int split = 0; 196 int split = 0;
197 SkDVector dxy1, dxy2; 197 SkDVector dxy1, dxy2;
198 if (tMin != tMax || tCount > 2) { 198 if (tMin != tMax || tCount > 2) {
199 dxy2 = q2.dxdyAtT(tMin); 199 dxy2 = q2.dxdyAtT(tMin);
200 for (int index = 1; index < tCount; ++index) { 200 for (int index = 1; index < tCount; ++index) {
201 dxy1 = dxy2; 201 dxy1 = dxy2;
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after
283 // each time through the loop, this computes values it had from the last loop 283 // each time through the loop, this computes values it had from the last loop
284 // if i == j == 1, the center values are still good 284 // if i == j == 1, the center values are still good
285 // otherwise, for i != 1 or j != 1, four of the values are still good 285 // otherwise, for i != 1 or j != 1, four of the values are still good
286 // and if i == 1 ^ j == 1, an additional value is good 286 // and if i == 1 ^ j == 1, an additional value is good
287 static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 Seed, 287 static bool binary_search(const SkDQuad& quad1, const SkDQuad& quad2, double* t1 Seed,
288 double* t2Seed, SkDPoint* pt) { 288 double* t2Seed, SkDPoint* pt) {
289 double tStep = ROUGH_EPSILON; 289 double tStep = ROUGH_EPSILON;
290 SkDPoint t1[3], t2[3]; 290 SkDPoint t1[3], t2[3];
291 int calcMask = ~0; 291 int calcMask = ~0;
292 do { 292 do {
293 if (calcMask & (1 << 1)) t1[1] = quad1.xyAtT(*t1Seed); 293 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed);
294 if (calcMask & (1 << 4)) t2[1] = quad2.xyAtT(*t2Seed); 294 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed);
295 if (t1[1].approximatelyEqual(t2[1])) { 295 if (t1[1].approximatelyEqual(t2[1])) {
296 *pt = t1[1]; 296 *pt = t1[1];
297 #if ONE_OFF_DEBUG 297 #if ONE_OFF_DEBUG
298 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __ FUNCTION__, 298 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __ FUNCTION__,
299 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); 299 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY);
300 #endif 300 #endif
301 return true; 301 return true;
302 } 302 }
303 if (calcMask & (1 << 0)) t1[0] = quad1.xyAtT(*t1Seed - tStep); 303 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep);
304 if (calcMask & (1 << 2)) t1[2] = quad1.xyAtT(*t1Seed + tStep); 304 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep);
305 if (calcMask & (1 << 3)) t2[0] = quad2.xyAtT(*t2Seed - tStep); 305 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep);
306 if (calcMask & (1 << 5)) t2[2] = quad2.xyAtT(*t2Seed + tStep); 306 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep);
307 double dist[3][3]; 307 double dist[3][3];
308 // OPTIMIZE: using calcMask value permits skipping some distance calcuat ions 308 // OPTIMIZE: using calcMask value permits skipping some distance calcuat ions
309 // if prior loop's results are moved to correct slot for reuse 309 // if prior loop's results are moved to correct slot for reuse
310 dist[1][1] = t1[1].distanceSquared(t2[1]); 310 dist[1][1] = t1[1].distanceSquared(t2[1]);
311 int best_i = 1, best_j = 1; 311 int best_i = 1, best_j = 1;
312 for (int i = 0; i < 3; ++i) { 312 for (int i = 0; i < 3; ++i) {
313 for (int j = 0; j < 3; ++j) { 313 for (int j = 0; j < 3; ++j) {
314 if (i == 1 && j == 1) { 314 if (i == 1 && j == 1) {
315 continue; 315 continue;
316 } 316 }
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after
416 bool flip1 = q1[2] == q2[0]; 416 bool flip1 = q1[2] == q2[0];
417 bool flip2 = q1[0] == q2[2]; 417 bool flip2 = q1[0] == q2[2];
418 bool useCubic = q1[0] == q2[0]; 418 bool useCubic = q1[0] == q2[0];
419 double roots1[4]; 419 double roots1[4];
420 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); 420 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
421 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 421 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1
422 double roots1Copy[4]; 422 double roots1Copy[4];
423 int r1Count = addValidRoots(roots1, rootCount, roots1Copy); 423 int r1Count = addValidRoots(roots1, rootCount, roots1Copy);
424 SkDPoint pts1[4]; 424 SkDPoint pts1[4];
425 for (index = 0; index < r1Count; ++index) { 425 for (index = 0; index < r1Count; ++index) {
426 pts1[index] = q1.xyAtT(roots1Copy[index]); 426 pts1[index] = q1.ptAtT(roots1Copy[index]);
427 } 427 }
428 double roots2[4]; 428 double roots2[4];
429 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); 429 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
430 double roots2Copy[4]; 430 double roots2Copy[4];
431 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); 431 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy);
432 SkDPoint pts2[4]; 432 SkDPoint pts2[4];
433 for (index = 0; index < r2Count; ++index) { 433 for (index = 0; index < r2Count; ++index) {
434 pts2[index] = q2.xyAtT(roots2Copy[index]); 434 pts2[index] = q2.ptAtT(roots2Copy[index]);
435 } 435 }
436 if (r1Count == r2Count && r1Count <= 1) { 436 if (r1Count == r2Count && r1Count <= 1) {
437 if (r1Count == 1) { 437 if (r1Count == 1) {
438 if (pts1[0].approximatelyEqualHalf(pts2[0])) { 438 if (pts1[0].approximatelyEqualHalf(pts2[0])) {
439 insert(roots1Copy[0], roots2Copy[0], pts1[0]); 439 insert(roots1Copy[0], roots2Copy[0], pts1[0]);
440 } else if (pts1[0].moreRoughlyEqual(pts2[0])) { 440 } else if (pts1[0].moreRoughlyEqual(pts2[0])) {
441 // experiment: try to find intersection by chasing t 441 // experiment: try to find intersection by chasing t
442 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); 442 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0);
443 (void) addValidRoots(roots1, rootCount, roots1Copy); 443 (void) addValidRoots(roots1, rootCount, roots1Copy);
444 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); 444 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0);
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after
501 } 501 }
502 if (lowestIndex < 0) { 502 if (lowestIndex < 0) {
503 break; 503 break;
504 } 504 }
505 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], 505 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]],
506 pts1[lowestIndex]); 506 pts1[lowestIndex]);
507 closest[lowestIndex] = -1; 507 closest[lowestIndex] = -1;
508 } while (++used < r1Count); 508 } while (++used < r1Count);
509 return fUsed; 509 return fUsed;
510 } 510 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698