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

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

Issue 686843002: Revert of harden pathops for pathological test (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 1 month 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
« no previous file with comments | « src/pathops/SkAddIntersections.cpp ('k') | src/pathops/SkDQuadIntersection.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2012 Google Inc. 2 * Copyright 2012 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 7
8 #include "SkIntersections.h" 8 #include "SkIntersections.h"
9 #include "SkPathOpsCubic.h" 9 #include "SkPathOpsCubic.h"
10 #include "SkPathOpsLine.h" 10 #include "SkPathOpsLine.h"
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after
102 SkReduceOrder s2; 102 SkReduceOrder s2;
103 int o2 = quadPart(cubic2, t2Start, t2, &s2); 103 int o2 = quadPart(cubic2, t2Start, t2, &s2);
104 #if ONE_OFF_DEBUG 104 #if ONE_OFF_DEBUG
105 char tab[] = " "; 105 char tab[] = " ";
106 if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1 106 if (tLimits1[0][0] >= t1Start && tLimits1[0][1] <= t1
107 && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) { 107 && tLimits1[1][0] >= t2Start && tLimits1[1][1] <= t2) {
108 SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()* 2, tab, 108 SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()* 2, tab,
109 __FUNCTION__, t1Start, t1, t2Start, t2); 109 __FUNCTION__, t1Start, t1, t2Start, t2);
110 SkIntersections xlocals; 110 SkIntersections xlocals;
111 xlocals.allowNear(false); 111 xlocals.allowNear(false);
112 xlocals.allowFlatMeasure(true);
113 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals); 112 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals);
114 SkDebugf(" xlocals.fUsed=%d\n", xlocals.used()); 113 SkDebugf(" xlocals.fUsed=%d\n", xlocals.used());
115 } 114 }
116 #endif 115 #endif
117 SkIntersections locals; 116 SkIntersections locals;
118 locals.allowNear(false); 117 locals.allowNear(false);
119 locals.allowFlatMeasure(true);
120 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals); 118 intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals);
121 int tCount = locals.used(); 119 int tCount = locals.used();
122 for (int tIdx = 0; tIdx < tCount; ++tIdx) { 120 for (int tIdx = 0; tIdx < tCount; ++tIdx) {
123 double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx]; 121 double to1 = t1Start + (t1 - t1Start) * locals[0][tIdx];
124 double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx]; 122 double to2 = t2Start + (t2 - t2Start) * locals[1][tIdx];
125 // if the computed t is not sufficiently precise, iterate 123 // if the computed t is not sufficiently precise, iterate
126 SkDPoint p1 = cubic1.ptAtT(to1); 124 SkDPoint p1 = cubic1.ptAtT(to1);
127 SkDPoint p2 = cubic2.ptAtT(to2); 125 SkDPoint p2 = cubic2.ptAtT(to2);
128 if (p1.approximatelyEqual(p2)) { 126 if (p1.approximatelyEqual(p2)) {
129 // FIXME: local edge may be coincident -- experiment with not propagating co incidence to caller 127 // FIXME: local edge may be coincident -- experiment with not propagating co incidence to caller
(...skipping 161 matching lines...) Expand 10 before | Expand all | Expand 10 after
291 double testT = (double) !start; 289 double testT = (double) !start;
292 bool swap = swapped(); 290 bool swap = swapped();
293 // quad/quad at this point checks to see if exact matches have already been found 291 // quad/quad at this point checks to see if exact matches have already been found
294 // cubic/cubic can't reject so easily since cubics can intersect same point more than once 292 // cubic/cubic can't reject so easily since cubics can intersect same point more than once
295 SkDLine tmpLine; 293 SkDLine tmpLine;
296 tmpLine[0] = tmpLine[1] = cubic2[t1Index]; 294 tmpLine[0] = tmpLine[1] = cubic2[t1Index];
297 tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY; 295 tmpLine[1].fX += cubic2[2 - start].fY - cubic2[t1Index].fY;
298 tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX; 296 tmpLine[1].fY -= cubic2[2 - start].fX - cubic2[t1Index].fX;
299 SkIntersections impTs; 297 SkIntersections impTs;
300 impTs.allowNear(false); 298 impTs.allowNear(false);
301 impTs.allowFlatMeasure(true);
302 impTs.intersectRay(cubic1, tmpLine); 299 impTs.intersectRay(cubic1, tmpLine);
303 for (int index = 0; index < impTs.used(); ++index) { 300 for (int index = 0; index < impTs.used(); ++index) {
304 SkDPoint realPt = impTs.pt(index); 301 SkDPoint realPt = impTs.pt(index);
305 if (!tmpLine[0].approximatelyEqual(realPt)) { 302 if (!tmpLine[0].approximatelyEqual(realPt)) {
306 continue; 303 continue;
307 } 304 }
308 if (swap) { 305 if (swap) {
309 cubicInsert(testT, impTs[0][index], tmpLine[0], cubic2, cubic1); 306 cubicInsert(testT, impTs[0][index], tmpLine[0], cubic2, cubic1);
310 } else { 307 } else {
311 cubicInsert(impTs[0][index], testT, tmpLine[0], cubic1, cubic2); 308 cubicInsert(impTs[0][index], testT, tmpLine[0], cubic1, cubic2);
(...skipping 240 matching lines...) Expand 10 before | Expand all | Expand 10 after
552 cubicNearEnd(c2, true, c1, c1Bounds); 549 cubicNearEnd(c2, true, c1, c1Bounds);
553 } 550 }
554 swap(); 551 swap();
555 } 552 }
556 if (cubicCheckCoincidence(c1, c2)) { 553 if (cubicCheckCoincidence(c1, c2)) {
557 SkASSERT(!selfIntersect); 554 SkASSERT(!selfIntersect);
558 return fUsed; 555 return fUsed;
559 } 556 }
560 SkIntersections i; 557 SkIntersections i;
561 i.fAllowNear = false; 558 i.fAllowNear = false;
562 i.fFlatMeasure = true;
563 i.fMax = 9; 559 i.fMax = 9;
564 ::intersect(c1, 0, 1, c2, 0, 1, 1, i); 560 ::intersect(c1, 0, 1, c2, 0, 1, 1, i);
565 int compCount = i.used(); 561 int compCount = i.used();
566 if (compCount) { 562 if (compCount) {
567 int exactCount = used(); 563 int exactCount = used();
568 if (exactCount == 0) { 564 if (exactCount == 0) {
569 *this = i; 565 *this = i;
570 } else { 566 } else {
571 // at least one is exact or near, and at least one was computed. Eli minate duplicates 567 // at least one is exact or near, and at least one was computed. Eli minate duplicates
572 for (int exIdx = 0; exIdx < exactCount; ++exIdx) { 568 for (int exIdx = 0; exIdx < exactCount; ++exIdx) {
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after
659 } 655 }
660 } 656 }
661 } 657 }
662 return fUsed; 658 return fUsed;
663 } 659 }
664 660
665 // Up promote the quad to a cubic. 661 // Up promote the quad to a cubic.
666 // OPTIMIZATION If this is a common use case, optimize by duplicating 662 // OPTIMIZATION If this is a common use case, optimize by duplicating
667 // the intersect 3 loop to avoid the promotion / demotion code 663 // the intersect 3 loop to avoid the promotion / demotion code
668 int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) { 664 int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) {
669 fMax = 7; 665 fMax = 6;
670 SkDCubic up = quad.toCubic(); 666 SkDCubic up = quad.toCubic();
671 (void) intersect(cubic, up); 667 (void) intersect(cubic, up);
672 return used(); 668 return used();
673 } 669 }
674 670
675 /* http://www.ag.jku.at/compass/compasssample.pdf 671 /* http://www.ag.jku.at/compass/compasssample.pdf
676 ( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen 672 ( Self-Intersection Problems and Approximate Implicitization by Jan B. Thomassen
677 Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no 673 Centre of Mathematics for Applications, University of Oslo http://www.cma.uio.no janbth@math.uio.no
678 SINTEF Applied Mathematics http://www.sintef.no ) 674 SINTEF Applied Mathematics http://www.sintef.no )
679 describes a method to find the self intersection of a cubic by taking the gradie nt of the implicit 675 describes a method to find the self intersection of a cubic by taking the gradie nt of the implicit
680 form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/ 676 form dotted with the normal, and solving for the roots. My math foo is too poor to implement this.*/
681 677
682 int SkIntersections::intersect(const SkDCubic& c) { 678 int SkIntersections::intersect(const SkDCubic& c) {
683 fMax = 1; 679 fMax = 1;
684 // check to see if x or y end points are the extrema. Are other quick reject s possible? 680 // check to see if x or y end points are the extrema. Are other quick reject s possible?
685 if (c.endsAreExtremaInXOrY()) { 681 if (c.endsAreExtremaInXOrY()) {
686 return false; 682 return false;
687 } 683 }
688 // OPTIMIZATION: could quick reject if neither end point tangent ray interse cted the line 684 // OPTIMIZATION: could quick reject if neither end point tangent ray interse cted the line
689 // segment formed by the opposite end point to the control point 685 // segment formed by the opposite end point to the control point
690 (void) intersect(c, c); 686 (void) intersect(c, c);
691 if (used() > 1) { 687 if (used() > 0) {
692 fUsed = 0;
693 } else if (used() > 0) {
694 if (approximately_equal_double(fT[0][0], fT[1][0])) { 688 if (approximately_equal_double(fT[0][0], fT[1][0])) {
695 fUsed = 0; 689 fUsed = 0;
696 } else { 690 } else {
697 SkASSERT(used() == 1); 691 SkASSERT(used() == 1);
698 if (fT[0][0] > fT[1][0]) { 692 if (fT[0][0] > fT[1][0]) {
699 swapPts(); 693 swapPts();
700 } 694 }
701 } 695 }
702 } 696 }
703 return used(); 697 return used();
704 } 698 }
OLDNEW
« no previous file with comments | « src/pathops/SkAddIntersections.cpp ('k') | src/pathops/SkDQuadIntersection.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698