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); | |
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 Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |