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, |
(...skipping 17 matching lines...) Expand all Loading... |
28 | 28 |
29 int SkIntersections::computePoints(const SkDLine& line, int used) { | 29 int SkIntersections::computePoints(const SkDLine& line, int used) { |
30 fPt[0] = line.ptAtT(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.ptAtT(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 SkDVector aLen = a[1] - a[0]; |
39 double ayLen = a[1].fY - a[0].fY; | 39 SkDVector bLen = b[1] - b[0]; |
40 double bxLen = b[1].fX - b[0].fX; | |
41 double byLen = b[1].fY - b[0].fY; | |
42 /* Slopes match when denom goes to zero: | 40 /* Slopes match when denom goes to zero: |
43 axLen / ayLen == bxLen / byLen | 41 axLen / ayLen == bxLen / byLen |
44 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen | 42 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen |
45 byLen * axLen == ayLen * bxLen | 43 byLen * axLen == ayLen * bxLen |
46 byLen * axLen - ayLen * bxLen == 0 ( == denom ) | 44 byLen * axLen - ayLen * bxLen == 0 ( == denom ) |
47 */ | 45 */ |
48 double denom = byLen * axLen - ayLen * bxLen; | 46 double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX; |
49 double ab0y = a[0].fY - b[0].fY; | 47 SkDVector ab0 = a[0] - b[0]; |
50 double ab0x = a[0].fX - b[0].fX; | 48 double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX; |
51 double numerA = ab0y * bxLen - byLen * ab0x; | 49 double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX; |
52 double numerB = ab0y * axLen - ayLen * ab0x; | |
53 numerA /= denom; | 50 numerA /= denom; |
54 numerB /= denom; | 51 numerB /= denom; |
55 int used; | 52 int used; |
56 if (!approximately_zero(denom)) { | 53 if (!approximately_zero(denom)) { |
57 fT[0][0] = numerA; | 54 fT[0][0] = numerA; |
58 fT[1][0] = numerB; | 55 fT[1][0] = numerB; |
59 used = 1; | 56 used = 1; |
60 } else { | 57 } else { |
61 /* See if the axis intercepts match: | 58 /* See if the axis intercepts match: |
62 ay - ax * ayLen / axLen == by - bx * ayLen / axLen | 59 ay - ax * ayLen / axLen == by - bx * ayLen / axLen |
63 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) | 60 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) |
64 axLen * ay - ax * ayLen == axLen * by - bx * ayLen | 61 axLen * ay - ax * ayLen == axLen * by - bx * ayLen |
65 */ | 62 */ |
66 if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX, | 63 if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX, |
67 axLen * b[0].fY - ayLen * b[0].fX)) { | 64 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) { |
68 return fUsed = 0; | 65 return fUsed = 0; |
69 } | 66 } |
70 // there's no great answer for intersection points for coincident rays,
but return something | 67 // there's no great answer for intersection points for coincident rays,
but return something |
71 fT[0][0] = fT[1][0] = 0; | 68 fT[0][0] = fT[1][0] = 0; |
72 fT[1][0] = fT[1][1] = 1; | 69 fT[1][0] = fT[1][1] = 1; |
73 used = 2; | 70 used = 2; |
74 } | 71 } |
75 return computePoints(a, used); | 72 return computePoints(a, used); |
76 } | 73 } |
77 | 74 |
(...skipping 21 matching lines...) Expand all Loading... |
99 /* Slopes match when denom goes to zero: | 96 /* Slopes match when denom goes to zero: |
100 axLen / ayLen == bxLen / byLen | 97 axLen / ayLen == bxLen / byLen |
101 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen | 98 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen |
102 byLen * axLen == ayLen * bxLen | 99 byLen * axLen == ayLen * bxLen |
103 byLen * axLen - ayLen * bxLen == 0 ( == denom ) | 100 byLen * axLen - ayLen * bxLen == 0 ( == denom ) |
104 */ | 101 */ |
105 double axByLen = axLen * byLen; | 102 double axByLen = axLen * byLen; |
106 double ayBxLen = ayLen * bxLen; | 103 double ayBxLen = ayLen * bxLen; |
107 // detect parallel lines the same way here and in SkOpAngle operator < | 104 // detect parallel lines the same way here and in SkOpAngle operator < |
108 // so that non-parallel means they are also sortable | 105 // so that non-parallel means they are also sortable |
109 bool parallel = AlmostEqualUlps(axByLen, ayBxLen); | 106 bool unparallel = NotAlmostEqualUlps(axByLen, ayBxLen); |
110 if (!parallel) { | 107 if (unparallel) { |
111 double ab0y = a[0].fY - b[0].fY; | 108 double ab0y = a[0].fY - b[0].fY; |
112 double ab0x = a[0].fX - b[0].fX; | 109 double ab0x = a[0].fX - b[0].fX; |
113 double numerA = ab0y * bxLen - byLen * ab0x; | 110 double numerA = ab0y * bxLen - byLen * ab0x; |
114 double numerB = ab0y * axLen - ayLen * ab0x; | 111 double numerB = ab0y * axLen - ayLen * ab0x; |
115 double denom = axByLen - ayBxLen; | 112 double denom = axByLen - ayBxLen; |
116 if (between(0, numerA, denom) && between(0, numerB, denom)) { | 113 if (between(0, numerA, denom) && between(0, numerB, denom)) { |
117 fT[0][0] = numerA / denom; | 114 fT[0][0] = numerA / denom; |
118 fT[1][0] = numerB / denom; | 115 fT[1][0] = numerB / denom; |
119 computePoints(a, 1); | 116 computePoints(a, 1); |
120 } | 117 } |
121 } | 118 } |
122 if (fAllowNear || parallel) { | 119 if (fAllowNear || !unparallel) { |
123 for (int iA = 0; iA < 2; ++iA) { | 120 for (int iA = 0; iA < 2; ++iA) { |
124 if ((t = b.nearPoint(a[iA])) >= 0) { | 121 if ((t = b.nearPoint(a[iA])) >= 0) { |
125 insert(iA, t, a[iA]); | 122 insert(iA, t, a[iA]); |
126 } | 123 } |
127 } | 124 } |
128 for (int iB = 0; iB < 2; ++iB) { | 125 for (int iB = 0; iB < 2; ++iB) { |
129 if ((t = a.nearPoint(b[iB])) >= 0) { | 126 if ((t = a.nearPoint(b[iB])) >= 0) { |
130 insert(t, iB, b[iB]); | 127 insert(t, iB, b[iB]); |
131 } | 128 } |
132 } | 129 } |
133 } | 130 } |
| 131 while (fUsed > 2) { |
| 132 removeOne(1); |
| 133 } |
| 134 if (fUsed == 2 && unparallel) { |
| 135 bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; |
| 136 bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; |
| 137 if (!startMatch && !endMatch) { |
| 138 SkASSERT(startMatch || endMatch); |
| 139 removeOne(endMatch); |
| 140 } |
| 141 } |
134 return fUsed; | 142 return fUsed; |
135 } | 143 } |
136 | 144 |
137 static int horizontal_coincident(const SkDLine& line, double y) { | 145 static int horizontal_coincident(const SkDLine& line, double y) { |
138 double min = line[0].fY; | 146 double min = line[0].fY; |
139 double max = line[1].fY; | 147 double max = line[1].fY; |
140 if (min > max) { | 148 if (min > max) { |
141 SkTSwap(min, max); | 149 SkTSwap(min, max); |
142 } | 150 } |
143 if (min > y || max < y) { | 151 if (min > y || max < y) { |
(...skipping 162 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
306 // 4 subs, 2 muls, 1 cmp | 314 // 4 subs, 2 muls, 1 cmp |
307 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { | 315 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { |
308 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); | 316 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); |
309 } | 317 } |
310 | 318 |
311 // 16 subs, 8 muls, 6 cmps | 319 // 16 subs, 8 muls, 6 cmps |
312 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { | 320 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { |
313 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) | 321 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) |
314 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); | 322 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); |
315 } | 323 } |
OLD | NEW |