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