| 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 |