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 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
102 if (!between(b0, a0, b1)) { | 102 if (!between(b0, a0, b1)) { |
103 return fUsed = 0; | 103 return fUsed = 0; |
104 } | 104 } |
105 fT[0][0] = fT[0][1] = 0; | 105 fT[0][0] = fT[0][1] = 0; |
106 } else { | 106 } else { |
107 double at0 = (a0 - b0) / aDenom; | 107 double at0 = (a0 - b0) / aDenom; |
108 double at1 = (a0 - b1) / aDenom; | 108 double at1 = (a0 - b1) / aDenom; |
109 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { | 109 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { |
110 return fUsed = 0; | 110 return fUsed = 0; |
111 } | 111 } |
112 fT[0][0] = SkTMax<double>(SkTMin<double>(at0, 1.0), 0.0); | 112 fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); |
113 fT[0][1] = SkTMax<double>(SkTMin<double>(at1, 1.0), 0.0); | 113 fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); |
114 } | 114 } |
115 double bDenom = b0 - b1; | 115 double bDenom = b0 - b1; |
116 if (approximately_zero(bDenom)) { | 116 if (approximately_zero(bDenom)) { |
117 fT[1][0] = fT[1][1] = 0; | 117 fT[1][0] = fT[1][1] = 0; |
118 } else { | 118 } else { |
119 int bIn = aDenom * bDenom < 0; | 119 int bIn = aDenom * bDenom < 0; |
120 fT[1][bIn] = SkTMax<double>(SkTMin<double>((b0 - a0) / bDenom, 1.0), 0.0
); | 120 fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0); |
121 fT[1][!bIn] = SkTMax<double>(SkTMin<double>((b0 - a1) / bDenom, 1.0), 0.
0); | 121 fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0); |
122 } | 122 } |
123 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; | 123 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; |
124 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); | 124 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); |
125 return computePoints(a, 1 + second); | 125 return computePoints(a, 1 + second); |
126 } | 126 } |
127 | 127 |
128 int SkIntersections::horizontal(const SkDLine& line, double y) { | 128 int SkIntersections::horizontal(const SkDLine& line, double y) { |
129 double min = line[0].fY; | 129 double min = line[0].fY; |
130 double max = line[1].fY; | 130 double max = line[1].fY; |
131 if (min > max) { | 131 if (min > max) { |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
182 double a0 = line[0].fX; | 182 double a0 = line[0].fX; |
183 double a1 = line[1].fX; | 183 double a1 = line[1].fX; |
184 double b0 = flipped ? right : left; | 184 double b0 = flipped ? right : left; |
185 double b1 = flipped ? left : right; | 185 double b1 = flipped ? left : right; |
186 // FIXME: share common code below | 186 // FIXME: share common code below |
187 double at0 = (a0 - b0) / (a0 - a1); | 187 double at0 = (a0 - b0) / (a0 - a1); |
188 double at1 = (a0 - b1) / (a0 - a1); | 188 double at1 = (a0 - b1) / (a0 - a1); |
189 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { | 189 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { |
190 return fUsed = 0; | 190 return fUsed = 0; |
191 } | 191 } |
192 fT[0][0] = SkTMax<double>(SkTMin<double>(at0, 1.0), 0.0); | 192 fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); |
193 fT[0][1] = SkTMax<double>(SkTMin<double>(at1, 1.0), 0.0); | 193 fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); |
194 int bIn = (a0 - a1) * (b0 - b1) < 0; | 194 int bIn = (a0 - a1) * (b0 - b1) < 0; |
195 fT[1][bIn] = SkTMax<double>(SkTMin<double>((b0 - a0) / (b0 - b1), 1.
0), 0.0); | 195 fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0); |
196 fT[1][!bIn] = SkTMax<double>(SkTMin<double>((b0 - a1) / (b0 - b1), 1
.0), 0.0); | 196 fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0); |
197 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; | 197 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; |
198 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); | 198 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); |
199 return computePoints(line, 1 + second); | 199 return computePoints(line, 1 + second); |
200 } | 200 } |
201 if (flipped) { | 201 if (flipped) { |
202 // OPTIMIZATION: instead of swapping, pass original line, use [1].fX - [
0].fX | 202 // OPTIMIZATION: instead of swapping, pass original line, use [1].fX - [
0].fX |
203 for (int index = 0; index < result; ++index) { | 203 for (int index = 0; index < result; ++index) { |
204 fT[1][index] = 1 - fT[1][index]; | 204 fT[1][index] = 1 - fT[1][index]; |
205 } | 205 } |
206 } | 206 } |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
243 double a0 = line[0].fY; | 243 double a0 = line[0].fY; |
244 double a1 = line[1].fY; | 244 double a1 = line[1].fY; |
245 double b0 = flipped ? bottom : top; | 245 double b0 = flipped ? bottom : top; |
246 double b1 = flipped ? top : bottom; | 246 double b1 = flipped ? top : bottom; |
247 // FIXME: share common code above | 247 // FIXME: share common code above |
248 double at0 = (a0 - b0) / (a0 - a1); | 248 double at0 = (a0 - b0) / (a0 - a1); |
249 double at1 = (a0 - b1) / (a0 - a1); | 249 double at1 = (a0 - b1) / (a0 - a1); |
250 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { | 250 if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { |
251 return fUsed = 0; | 251 return fUsed = 0; |
252 } | 252 } |
253 fT[0][0] = SkTMax<double>(SkTMin<double>(at0, 1.0), 0.0); | 253 fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); |
254 fT[0][1] = SkTMax<double>(SkTMin<double>(at1, 1.0), 0.0); | 254 fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); |
255 int bIn = (a0 - a1) * (b0 - b1) < 0; | 255 int bIn = (a0 - a1) * (b0 - b1) < 0; |
256 fT[1][bIn] = SkTMax<double>(SkTMin<double>((b0 - a0) / (b0 - b1), 1.
0), 0.0); | 256 fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 1.0), 0.0); |
257 fT[1][!bIn] = SkTMax<double>(SkTMin<double>((b0 - a1) / (b0 - b1), 1
.0), 0.0); | 257 fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 1.0), 0.0); |
258 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; | 258 bool second = fabs(fT[0][0] - fT[0][1]) > FLT_EPSILON; |
259 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); | 259 SkASSERT((fabs(fT[1][0] - fT[1][1]) <= FLT_EPSILON) ^ second); |
260 return computePoints(line, 1 + second); | 260 return computePoints(line, 1 + second); |
261 break; | 261 break; |
262 } | 262 } |
263 if (flipped) { | 263 if (flipped) { |
264 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [
0].fY | 264 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [
0].fY |
265 for (int index = 0; index < result; ++index) { | 265 for (int index = 0; index < result; ++index) { |
266 fT[1][index] = 1 - fT[1][index]; | 266 fT[1][index] = 1 - fT[1][index]; |
267 } | 267 } |
268 } | 268 } |
269 return computePoints(line, result); | 269 return computePoints(line, result); |
270 } | 270 } |
271 | 271 |
272 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.p
y | 272 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.p
y |
273 // 4 subs, 2 muls, 1 cmp | 273 // 4 subs, 2 muls, 1 cmp |
274 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { | 274 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { |
275 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); | 275 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); |
276 } | 276 } |
277 | 277 |
278 // 16 subs, 8 muls, 6 cmps | 278 // 16 subs, 8 muls, 6 cmps |
279 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { | 279 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { |
280 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) | 280 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) |
281 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); | 281 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); |
282 } | 282 } |
OLD | NEW |