| 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 #include "SkIntersections.h" | 7 #include "SkIntersections.h" |
| 8 #include "SkPathOpsLine.h" | 8 #include "SkPathOpsLine.h" |
| 9 | 9 |
| 10 /* Determine the intersection point of two lines. This assumes the lines are not
parallel, | 10 /* Determine the intersection point of two lines. This assumes the lines are not
parallel, |
| 11 and that that the lines are infinite. | 11 and that that the lines are infinite. |
| 12 From http://en.wikipedia.org/wiki/Line-line_intersection | 12 From http://en.wikipedia.org/wiki/Line-line_intersection |
| 13 */ | 13 */ |
| 14 SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { | 14 SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { |
| 15 double axLen = a[1].fX - a[0].fX; | 15 double axLen = a[1].fX - a[0].fX; |
| 16 double ayLen = a[1].fY - a[0].fY; | 16 double ayLen = a[1].fY - a[0].fY; |
| 17 double bxLen = b[1].fX - b[0].fX; | 17 double bxLen = b[1].fX - b[0].fX; |
| 18 double byLen = b[1].fY - b[0].fY; | 18 double byLen = b[1].fY - b[0].fY; |
| 19 double denom = byLen * axLen - ayLen * bxLen; | 19 double denom = byLen * axLen - ayLen * bxLen; |
| 20 SkASSERT(denom); | 20 SkASSERT(denom); |
| 21 double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; | 21 double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; |
| 22 double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; | 22 double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; |
| 23 SkDPoint p; | 23 SkDPoint p; |
| 24 p.fX = (term1 * bxLen - axLen * term2) / denom; | 24 p.fX = (term1 * bxLen - axLen * term2) / denom; |
| 25 p.fY = (term1 * byLen - ayLen * term2) / denom; | 25 p.fY = (term1 * byLen - ayLen * term2) / denom; |
| 26 return p; | 26 return p; |
| 27 } | 27 } |
| 28 | 28 |
| 29 int SkIntersections::computePoints(const SkDLine& line, int used) { | 29 int SkIntersections::computePoints(const SkDLine& line, int used) { |
| 30 fPt[0] = line.xyAtT(fT[0][0]); | 30 fPt[0] = line.ptAtT(fT[0][0]); |
| 31 if ((fUsed = used) == 2) { | 31 if ((fUsed = used) == 2) { |
| 32 fPt[1] = line.xyAtT(fT[0][1]); | 32 fPt[1] = line.ptAtT(fT[0][1]); |
| 33 } | 33 } |
| 34 return fUsed; | 34 return fUsed; |
| 35 } | 35 } |
| 36 | 36 |
| 37 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { | 37 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { |
| 38 double axLen = a[1].fX - a[0].fX; | 38 double axLen = a[1].fX - a[0].fX; |
| 39 double ayLen = a[1].fY - a[0].fY; | 39 double ayLen = a[1].fY - a[0].fY; |
| 40 double bxLen = b[1].fX - b[0].fX; | 40 double bxLen = b[1].fX - b[0].fX; |
| 41 double byLen = b[1].fY - b[0].fY; | 41 double byLen = b[1].fY - b[0].fY; |
| 42 /* Slopes match when denom goes to zero: | 42 /* Slopes match when denom goes to zero: |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 95 double axLen = a[1].fX - a[0].fX; | 95 double axLen = a[1].fX - a[0].fX; |
| 96 double ayLen = a[1].fY - a[0].fY; | 96 double ayLen = a[1].fY - a[0].fY; |
| 97 double bxLen = b[1].fX - b[0].fX; | 97 double bxLen = b[1].fX - b[0].fX; |
| 98 double byLen = b[1].fY - b[0].fY; | 98 double byLen = b[1].fY - b[0].fY; |
| 99 /* Slopes match when denom goes to zero: | 99 /* Slopes match when denom goes to zero: |
| 100 axLen / ayLen == bxLen / byLen | 100 axLen / ayLen == bxLen / byLen |
| 101 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen | 101 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen |
| 102 byLen * axLen == ayLen * bxLen | 102 byLen * axLen == ayLen * bxLen |
| 103 byLen * axLen - ayLen * bxLen == 0 ( == denom ) | 103 byLen * axLen - ayLen * bxLen == 0 ( == denom ) |
| 104 */ | 104 */ |
| 105 double denom = byLen * axLen - ayLen * bxLen; | 105 double axByLen = axLen * byLen; |
| 106 if (0 != denom) { | 106 double ayBxLen = ayLen * bxLen; |
| 107 // detect parallel lines the same way here and in SkOpAngle operator < |
| 108 // so that non-parallel means they are also sortable |
| 109 bool parallel = AlmostEqualUlps(axByLen, ayBxLen); |
| 110 if (!parallel) { |
| 107 double ab0y = a[0].fY - b[0].fY; | 111 double ab0y = a[0].fY - b[0].fY; |
| 108 double ab0x = a[0].fX - b[0].fX; | 112 double ab0x = a[0].fX - b[0].fX; |
| 109 double numerA = ab0y * bxLen - byLen * ab0x; | 113 double numerA = ab0y * bxLen - byLen * ab0x; |
| 110 double numerB = ab0y * axLen - ayLen * ab0x; | 114 double numerB = ab0y * axLen - ayLen * ab0x; |
| 115 double denom = axByLen - ayBxLen; |
| 111 if (between(0, numerA, denom) && between(0, numerB, denom)) { | 116 if (between(0, numerA, denom) && between(0, numerB, denom)) { |
| 112 fT[0][0] = numerA / denom; | 117 fT[0][0] = numerA / denom; |
| 113 fT[1][0] = numerB / denom; | 118 fT[1][0] = numerB / denom; |
| 114 return computePoints(a, 1); | 119 computePoints(a, 1); |
| 115 } | 120 } |
| 116 } | 121 } |
| 117 if (fAllowNear || 0 == denom) { | 122 if (fAllowNear || parallel) { |
| 118 for (int iA = 0; iA < 2; ++iA) { | 123 for (int iA = 0; iA < 2; ++iA) { |
| 119 if ((t = b.nearPoint(a[iA])) >= 0) { | 124 if ((t = b.nearPoint(a[iA])) >= 0) { |
| 120 insert(iA, t, a[iA]); | 125 insert(iA, t, a[iA]); |
| 121 } | 126 } |
| 122 } | 127 } |
| 123 for (int iB = 0; iB < 2; ++iB) { | 128 for (int iB = 0; iB < 2; ++iB) { |
| 124 if ((t = a.nearPoint(b[iB])) >= 0) { | 129 if ((t = a.nearPoint(b[iB])) >= 0) { |
| 125 insert(t, iB, b[iB]); | 130 insert(t, iB, b[iB]); |
| 126 } | 131 } |
| 127 } | 132 } |
| (...skipping 173 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 301 // 4 subs, 2 muls, 1 cmp | 306 // 4 subs, 2 muls, 1 cmp |
| 302 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { | 307 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { |
| 303 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); | 308 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); |
| 304 } | 309 } |
| 305 | 310 |
| 306 // 16 subs, 8 muls, 6 cmps | 311 // 16 subs, 8 muls, 6 cmps |
| 307 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { | 312 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { |
| 308 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) | 313 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) |
| 309 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); | 314 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); |
| 310 } | 315 } |
| OLD | NEW |