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 "SkPathOpsCubic.h" | 8 #include "SkPathOpsCubic.h" |
9 #include "SkPathOpsLine.h" | 9 #include "SkPathOpsLine.h" |
10 | 10 |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
69 a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j, | 69 a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j, |
70 e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] | 70 e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] |
71 (out) e - j - | 71 (out) e - j - |
72 3 e t + 3 f t + | 72 3 e t + 3 f t + |
73 3 e t^2 - 6 f t^2 + 3 g t^2 - | 73 3 e t^2 - 6 f t^2 + 3 g t^2 - |
74 e t^3 + 3 f t^3 - 3 g t^3 + h t^3 | 74 e t^3 + 3 f t^3 - 3 g t^3 + h t^3 |
75 */ | 75 */ |
76 | 76 |
77 class LineCubicIntersections { | 77 class LineCubicIntersections { |
78 public: | 78 public: |
79 | 79 enum PinTPoint { |
80 LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i) | 80 kPointUninitialized, |
81 : cubic(c) | 81 kPointInitialized |
82 , line(l) | 82 }; |
83 , intersections(i) | 83 |
84 , fAllowNear(true) { | 84 LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections*
i) |
85 } | 85 : fCubic(c) |
86 | 86 , fLine(l) |
87 void allowNear(bool allow) { | 87 , fIntersections(i) |
88 fAllowNear = allow; | 88 , fAllowNear(true) { |
89 } | 89 } |
90 | 90 |
91 // see parallel routine in line quadratic intersections | 91 void allowNear(bool allow) { |
92 int intersectRay(double roots[3]) { | 92 fAllowNear = allow; |
93 double adj = line[1].fX - line[0].fX; | 93 } |
94 double opp = line[1].fY - line[0].fY; | 94 |
95 SkDCubic r; | 95 // see parallel routine in line quadratic intersections |
96 for (int n = 0; n < 4; ++n) { | 96 int intersectRay(double roots[3]) { |
97 r[n].fX = (cubic[n].fY - line[0].fY) * adj - (cubic[n].fX - line[0].fX)
* opp; | 97 double adj = fLine[1].fX - fLine[0].fX; |
98 } | 98 double opp = fLine[1].fY - fLine[0].fY; |
99 double A, B, C, D; | 99 SkDCubic r; |
100 SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D); | 100 for (int n = 0; n < 4; ++n) { |
101 return SkDCubic::RootsValidT(A, B, C, D, roots); | 101 r[n].fX = (fCubic[n].fY - fLine[0].fY) * adj - (fCubic[n].fX - fLine
[0].fX) * opp; |
102 } | 102 } |
103 | 103 double A, B, C, D; |
104 int intersect() { | 104 SkDCubic::Coefficients(&r[0].fX, &A, &B, &C, &D); |
105 addExactEndPoints(); | 105 return SkDCubic::RootsValidT(A, B, C, D, roots); |
106 double rootVals[3]; | 106 } |
107 int roots = intersectRay(rootVals); | 107 |
108 for (int index = 0; index < roots; ++index) { | 108 int intersect() { |
109 double cubicT = rootVals[index]; | 109 addExactEndPoints(); |
110 double lineT = findLineT(cubicT); | 110 double rootVals[3]; |
111 if (pinTs(&cubicT, &lineT)) { | 111 int roots = intersectRay(rootVals); |
112 SkDPoint pt = line.xyAtT(lineT); | 112 for (int index = 0; index < roots; ++index) { |
113 #if ONE_OFF_DEBUG | 113 double cubicT = rootVals[index]; |
114 SkDPoint cPt = cubic.xyAtT(cubicT); | 114 double lineT = findLineT(cubicT); |
115 SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt
.fX, pt.fY, | 115 SkDPoint pt; |
116 cPt.fX, cPt.fY); | 116 if (pinTs(&cubicT, &lineT, &pt, kPointUninitialized)) { |
117 #endif | 117 #if ONE_OFF_DEBUG |
118 intersections.insert(cubicT, lineT, pt); | 118 SkDPoint cPt = fCubic.ptAtT(cubicT); |
119 } | 119 SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__
, pt.fX, pt.fY, |
120 } | 120 cPt.fX, cPt.fY); |
121 if (fAllowNear) { | 121 #endif |
122 addNearEndPoints(); | 122 fIntersections->insert(cubicT, lineT, pt); |
123 } | 123 } |
124 return intersections.used(); | 124 } |
125 } | 125 if (fAllowNear) { |
126 | 126 addNearEndPoints(); |
127 int horizontalIntersect(double axisIntercept, double roots[3]) { | 127 } |
128 double A, B, C, D; | 128 return fIntersections->used(); |
129 SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D); | 129 } |
130 D -= axisIntercept; | 130 |
131 return SkDCubic::RootsValidT(A, B, C, D, roots); | 131 int horizontalIntersect(double axisIntercept, double roots[3]) { |
132 } | 132 double A, B, C, D; |
133 | 133 SkDCubic::Coefficients(&fCubic[0].fY, &A, &B, &C, &D); |
134 int horizontalIntersect(double axisIntercept, double left, double right, bool fl
ipped) { | 134 D -= axisIntercept; |
135 addExactHorizontalEndPoints(left, right, axisIntercept); | 135 return SkDCubic::RootsValidT(A, B, C, D, roots); |
136 double rootVals[3]; | 136 } |
137 int roots = horizontalIntersect(axisIntercept, rootVals); | 137 |
138 for (int index = 0; index < roots; ++index) { | 138 int horizontalIntersect(double axisIntercept, double left, double right, boo
l flipped) { |
139 double cubicT = rootVals[index]; | 139 addExactHorizontalEndPoints(left, right, axisIntercept); |
140 SkDPoint pt = cubic.xyAtT(cubicT); | 140 double rootVals[3]; |
141 double lineT = (pt.fX - left) / (right - left); | 141 int roots = horizontalIntersect(axisIntercept, rootVals); |
142 if (pinTs(&cubicT, &lineT)) { | 142 for (int index = 0; index < roots; ++index) { |
143 intersections.insert(cubicT, lineT, pt); | 143 double cubicT = rootVals[index]; |
144 } | 144 SkDPoint pt = fCubic.ptAtT(cubicT); |
145 } | 145 double lineT = (pt.fX - left) / (right - left); |
146 if (fAllowNear) { | 146 if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) { |
147 addNearHorizontalEndPoints(left, right, axisIntercept); | 147 fIntersections->insert(cubicT, lineT, pt); |
148 } | 148 } |
149 if (flipped) { | 149 } |
150 intersections.flip(); | 150 if (fAllowNear) { |
151 } | 151 addNearHorizontalEndPoints(left, right, axisIntercept); |
152 return intersections.used(); | 152 } |
153 } | 153 if (flipped) { |
154 | 154 fIntersections->flip(); |
155 int verticalIntersect(double axisIntercept, double roots[3]) { | 155 } |
156 double A, B, C, D; | 156 return fIntersections->used(); |
157 SkDCubic::Coefficients(&cubic[0].fX, &A, &B, &C, &D); | 157 } |
158 D -= axisIntercept; | 158 |
159 return SkDCubic::RootsValidT(A, B, C, D, roots); | 159 int verticalIntersect(double axisIntercept, double roots[3]) { |
160 } | 160 double A, B, C, D; |
161 | 161 SkDCubic::Coefficients(&fCubic[0].fX, &A, &B, &C, &D); |
162 int verticalIntersect(double axisIntercept, double top, double bottom, bool flip
ped) { | 162 D -= axisIntercept; |
163 addExactVerticalEndPoints(top, bottom, axisIntercept); | 163 return SkDCubic::RootsValidT(A, B, C, D, roots); |
164 double rootVals[3]; | 164 } |
165 int roots = verticalIntersect(axisIntercept, rootVals); | 165 |
166 for (int index = 0; index < roots; ++index) { | 166 int verticalIntersect(double axisIntercept, double top, double bottom, bool
flipped) { |
167 double cubicT = rootVals[index]; | 167 addExactVerticalEndPoints(top, bottom, axisIntercept); |
168 SkDPoint pt = cubic.xyAtT(cubicT); | 168 double rootVals[3]; |
169 double lineT = (pt.fY - top) / (bottom - top); | 169 int roots = verticalIntersect(axisIntercept, rootVals); |
170 if (pinTs(&cubicT, &lineT)) { | 170 for (int index = 0; index < roots; ++index) { |
171 intersections.insert(cubicT, lineT, pt); | 171 double cubicT = rootVals[index]; |
172 } | 172 SkDPoint pt = fCubic.ptAtT(cubicT); |
173 } | 173 double lineT = (pt.fY - top) / (bottom - top); |
174 if (fAllowNear) { | 174 if (pinTs(&cubicT, &lineT, &pt, kPointInitialized)) { |
175 addNearVerticalEndPoints(top, bottom, axisIntercept); | 175 fIntersections->insert(cubicT, lineT, pt); |
176 } | 176 } |
177 if (flipped) { | 177 } |
178 intersections.flip(); | 178 if (fAllowNear) { |
179 } | 179 addNearVerticalEndPoints(top, bottom, axisIntercept); |
180 return intersections.used(); | 180 } |
181 } | 181 if (flipped) { |
182 | 182 fIntersections->flip(); |
183 protected: | 183 } |
184 | 184 return fIntersections->used(); |
185 void addExactEndPoints() { | 185 } |
186 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 186 |
187 double lineT = line.exactPoint(cubic[cIndex]); | 187 protected: |
188 if (lineT < 0) { | 188 |
189 continue; | 189 void addExactEndPoints() { |
190 } | 190 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
191 double cubicT = (double) (cIndex >> 1); | 191 double lineT = fLine.exactPoint(fCubic[cIndex]); |
192 intersections.insert(cubicT, lineT, cubic[cIndex]); | 192 if (lineT < 0) { |
193 } | 193 continue; |
194 } | 194 } |
195 | 195 double cubicT = (double) (cIndex >> 1); |
196 void addNearEndPoints() { | 196 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
197 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 197 } |
198 double cubicT = (double) (cIndex >> 1); | 198 } |
199 if (intersections.hasT(cubicT)) { | 199 |
200 continue; | 200 void addNearEndPoints() { |
201 } | 201 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
202 double lineT = line.nearPoint(cubic[cIndex]); | 202 double cubicT = (double) (cIndex >> 1); |
203 if (lineT < 0) { | 203 if (fIntersections->hasT(cubicT)) { |
204 continue; | 204 continue; |
205 } | 205 } |
206 intersections.insert(cubicT, lineT, cubic[cIndex]); | 206 double lineT = fLine.nearPoint(fCubic[cIndex]); |
207 } | 207 if (lineT < 0) { |
208 } | 208 continue; |
209 | 209 } |
210 void addExactHorizontalEndPoints(double left, double right, double y) { | 210 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
211 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 211 } |
212 double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y); | 212 } |
213 if (lineT < 0) { | 213 |
214 continue; | 214 void addExactHorizontalEndPoints(double left, double right, double y) { |
215 } | 215 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
216 double cubicT = (double) (cIndex >> 1); | 216 double lineT = SkDLine::ExactPointH(fCubic[cIndex], left, right, y); |
217 intersections.insert(cubicT, lineT, cubic[cIndex]); | 217 if (lineT < 0) { |
218 } | 218 continue; |
219 } | 219 } |
220 | 220 double cubicT = (double) (cIndex >> 1); |
221 void addNearHorizontalEndPoints(double left, double right, double y) { | 221 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
222 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 222 } |
223 double cubicT = (double) (cIndex >> 1); | 223 } |
224 if (intersections.hasT(cubicT)) { | 224 |
225 continue; | 225 void addNearHorizontalEndPoints(double left, double right, double y) { |
226 } | 226 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
227 double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y); | 227 double cubicT = (double) (cIndex >> 1); |
228 if (lineT < 0) { | 228 if (fIntersections->hasT(cubicT)) { |
229 continue; | 229 continue; |
230 } | 230 } |
231 intersections.insert(cubicT, lineT, cubic[cIndex]); | 231 double lineT = SkDLine::NearPointH(fCubic[cIndex], left, right, y); |
232 } | 232 if (lineT < 0) { |
233 // FIXME: see if line end is nearly on cubic | 233 continue; |
234 } | 234 } |
235 | 235 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
236 void addExactVerticalEndPoints(double top, double bottom, double x) { | 236 } |
237 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 237 // FIXME: see if line end is nearly on cubic |
238 double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x); | 238 } |
239 if (lineT < 0) { | 239 |
240 continue; | 240 void addExactVerticalEndPoints(double top, double bottom, double x) { |
241 } | 241 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
242 double cubicT = (double) (cIndex >> 1); | 242 double lineT = SkDLine::ExactPointV(fCubic[cIndex], top, bottom, x); |
243 intersections.insert(cubicT, lineT, cubic[cIndex]); | 243 if (lineT < 0) { |
244 } | 244 continue; |
245 } | 245 } |
246 | 246 double cubicT = (double) (cIndex >> 1); |
247 void addNearVerticalEndPoints(double top, double bottom, double x) { | 247 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
248 for (int cIndex = 0; cIndex < 4; cIndex += 3) { | 248 } |
249 double cubicT = (double) (cIndex >> 1); | 249 } |
250 if (intersections.hasT(cubicT)) { | 250 |
251 continue; | 251 void addNearVerticalEndPoints(double top, double bottom, double x) { |
252 } | 252 for (int cIndex = 0; cIndex < 4; cIndex += 3) { |
253 double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x); | 253 double cubicT = (double) (cIndex >> 1); |
254 if (lineT < 0) { | 254 if (fIntersections->hasT(cubicT)) { |
255 continue; | 255 continue; |
256 } | 256 } |
257 intersections.insert(cubicT, lineT, cubic[cIndex]); | 257 double lineT = SkDLine::NearPointV(fCubic[cIndex], top, bottom, x); |
258 } | 258 if (lineT < 0) { |
259 // FIXME: see if line end is nearly on cubic | 259 continue; |
260 } | 260 } |
261 | 261 fIntersections->insert(cubicT, lineT, fCubic[cIndex]); |
262 double findLineT(double t) { | 262 } |
263 SkDPoint xy = cubic.xyAtT(t); | 263 // FIXME: see if line end is nearly on cubic |
264 double dx = line[1].fX - line[0].fX; | 264 } |
265 double dy = line[1].fY - line[0].fY; | 265 |
266 if (fabs(dx) > fabs(dy)) { | 266 double findLineT(double t) { |
267 return (xy.fX - line[0].fX) / dx; | 267 SkDPoint xy = fCubic.ptAtT(t); |
268 } | 268 double dx = fLine[1].fX - fLine[0].fX; |
269 return (xy.fY - line[0].fY) / dy; | 269 double dy = fLine[1].fY - fLine[0].fY; |
270 } | 270 if (fabs(dx) > fabs(dy)) { |
271 | 271 return (xy.fX - fLine[0].fX) / dx; |
272 static bool pinTs(double* cubicT, double* lineT) { | 272 } |
273 if (!approximately_one_or_less(*lineT)) { | 273 return (xy.fY - fLine[0].fY) / dy; |
274 return false; | 274 } |
275 } | 275 |
276 if (!approximately_zero_or_more(*lineT)) { | 276 bool pinTs(double* cubicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { |
277 return false; | 277 if (!approximately_one_or_less(*lineT)) { |
278 } | 278 return false; |
279 if (precisely_less_than_zero(*cubicT)) { | 279 } |
280 *cubicT = 0; | 280 if (!approximately_zero_or_more(*lineT)) { |
281 } else if (precisely_greater_than_one(*cubicT)) { | 281 return false; |
282 *cubicT = 1; | 282 } |
283 } | 283 double cT = *cubicT = SkPinT(*cubicT); |
284 if (precisely_less_than_zero(*lineT)) { | 284 double lT = *lineT = SkPinT(*lineT); |
285 *lineT = 0; | 285 if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && cT != 0 && cT
!= 1)) { |
286 } else if (precisely_greater_than_one(*lineT)) { | 286 *pt = fLine.ptAtT(lT); |
287 *lineT = 1; | 287 } else if (ptSet == kPointUninitialized) { |
288 } | 288 *pt = fCubic.ptAtT(cT); |
289 return true; | 289 } |
290 } | 290 return true; |
| 291 } |
291 | 292 |
292 private: | 293 private: |
293 | 294 const SkDCubic& fCubic; |
294 const SkDCubic& cubic; | 295 const SkDLine& fLine; |
295 const SkDLine& line; | 296 SkIntersections* fIntersections; |
296 SkIntersections& intersections; | 297 bool fAllowNear; |
297 bool fAllowNear; | |
298 }; | 298 }; |
299 | 299 |
300 int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right
, double y, | 300 int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right
, double y, |
301 bool flipped) { | 301 bool flipped) { |
302 LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this); | 302 SkDLine line = {{{ left, y }, { right, y }}}; |
| 303 LineCubicIntersections c(cubic, line, this); |
303 return c.horizontalIntersect(y, left, right, flipped); | 304 return c.horizontalIntersect(y, left, right, flipped); |
304 } | 305 } |
305 | 306 |
306 int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom,
double x, | 307 int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom,
double x, |
307 bool flipped) { | 308 bool flipped) { |
308 LineCubicIntersections c(cubic, *(static_cast<SkDLine*>(0)), *this); | 309 SkDLine line = {{{ x, top }, { x, bottom }}}; |
| 310 LineCubicIntersections c(cubic, line, this); |
309 return c.verticalIntersect(x, top, bottom, flipped); | 311 return c.verticalIntersect(x, top, bottom, flipped); |
310 } | 312 } |
311 | 313 |
312 int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { | 314 int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { |
313 LineCubicIntersections c(cubic, line, *this); | 315 LineCubicIntersections c(cubic, line, this); |
314 c.allowNear(fAllowNear); | 316 c.allowNear(fAllowNear); |
315 return c.intersect(); | 317 return c.intersect(); |
316 } | 318 } |
317 | 319 |
318 int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) { | 320 int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) { |
319 LineCubicIntersections c(cubic, line, *this); | 321 LineCubicIntersections c(cubic, line, this); |
320 fUsed = c.intersectRay(fT[0]); | 322 fUsed = c.intersectRay(fT[0]); |
321 for (int index = 0; index < fUsed; ++index) { | 323 for (int index = 0; index < fUsed; ++index) { |
322 fPt[index] = cubic.xyAtT(fT[0][index]); | 324 fPt[index] = cubic.ptAtT(fT[0][index]); |
323 } | 325 } |
324 return fUsed; | 326 return fUsed; |
325 } | 327 } |
OLD | NEW |