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 "SkOpAngle.h" | 7 #include "SkOpAngle.h" |
8 #include "SkOpSegment.h" | 8 #include "SkOpSegment.h" |
9 #include "SkPathOpsCurve.h" | 9 #include "SkPathOpsCurve.h" |
10 #include "SkTSort.h" | 10 #include "SkTSort.h" |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
55 20 | 26 | 55 20 | 26 |
56 21 | 25 | 56 21 | 25 |
57 22 23 24 | 57 22 23 24 |
58 */ | 58 */ |
59 | 59 |
60 // return true if lh < this < rh | 60 // return true if lh < this < rh |
61 bool SkOpAngle::after(SkOpAngle* test) { | 61 bool SkOpAngle::after(SkOpAngle* test) { |
62 SkOpAngle* lh = test; | 62 SkOpAngle* lh = test; |
63 SkOpAngle* rh = lh->fNext; | 63 SkOpAngle* rh = lh->fNext; |
64 SkASSERT(lh != rh); | 64 SkASSERT(lh != rh); |
65 fCurvePart = fOriginalCurvePart; | 65 fPart.fCurve = fOriginalCurvePart; |
66 lh->fCurvePart = lh->fOriginalCurvePart; | 66 lh->fPart.fCurve = lh->fOriginalCurvePart; |
67 lh->fCurvePart.offset(lh->segment()->verb(), fCurvePart[0] - lh->fCurvePart[
0]); | 67 lh->fPart.fCurve.offset(lh->segment()->verb(), fPart.fCurve[0] - lh->fPart.f
Curve[0]); |
68 rh->fCurvePart = rh->fOriginalCurvePart; | 68 rh->fPart.fCurve = rh->fOriginalCurvePart; |
69 rh->fCurvePart.offset(rh->segment()->verb(), fCurvePart[0] - rh->fCurvePart[
0]); | 69 rh->fPart.fCurve.offset(rh->segment()->verb(), fPart.fCurve[0] - rh->fPart.f
Curve[0]); |
70 | 70 |
71 #if DEBUG_ANGLE | 71 #if DEBUG_ANGLE |
72 SkString bugOut; | 72 SkString bugOut; |
73 bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" | 73 bugOut.printf("%s [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
74 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" | 74 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g" |
75 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, | 75 " < [%d/%d] %d/%d tStart=%1.9g tEnd=%1.9g ", __FUNCTION__, |
76 lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSect
orEnd, | 76 lh->segment()->debugID(), lh->debugID(), lh->fSectorStart, lh->fSect
orEnd, |
77 lh->fStart->t(), lh->fEnd->t(), | 77 lh->fStart->t(), lh->fEnd->t(), |
78 segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t
(), fEnd->t(), | 78 segment()->debugID(), debugID(), fSectorStart, fSectorEnd, fStart->t
(), fEnd->t(), |
79 rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSect
orEnd, | 79 rh->segment()->debugID(), rh->debugID(), rh->fSectorStart, rh->fSect
orEnd, |
(...skipping 90 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
170 return COMPARE_RESULT(11, trOrder); | 170 return COMPARE_RESULT(11, trOrder); |
171 } | 171 } |
172 return COMPARE_RESULT(12, ltOrder); | 172 return COMPARE_RESULT(12, ltOrder); |
173 } | 173 } |
174 return COMPARE_RESULT(13, !lrOrder); | 174 return COMPARE_RESULT(13, !lrOrder); |
175 } | 175 } |
176 | 176 |
177 // given a line, see if the opposite curve's convex hull is all on one side | 177 // given a line, see if the opposite curve's convex hull is all on one side |
178 // returns -1=not on one side 0=this CW of test 1=this CCW of test | 178 // returns -1=not on one side 0=this CW of test 1=this CCW of test |
179 int SkOpAngle::allOnOneSide(const SkOpAngle* test) { | 179 int SkOpAngle::allOnOneSide(const SkOpAngle* test) { |
180 SkASSERT(!fIsCurve); | 180 SkASSERT(!fPart.isCurve()); |
181 SkASSERT(test->fIsCurve); | 181 SkASSERT(test->fPart.isCurve()); |
182 SkDPoint origin = fCurvePart[0]; | 182 SkDPoint origin = fPart.fCurve[0]; |
183 SkDVector line = fCurvePart[1] - origin; | 183 SkDVector line = fPart.fCurve[1] - origin; |
184 double crosses[3]; | 184 double crosses[3]; |
185 SkPath::Verb testVerb = test->segment()->verb(); | 185 SkPath::Verb testVerb = test->segment()->verb(); |
186 int iMax = SkPathOpsVerbToPoints(testVerb); | 186 int iMax = SkPathOpsVerbToPoints(testVerb); |
187 // SkASSERT(origin == test.fCurveHalf[0]); | 187 // SkASSERT(origin == test.fCurveHalf[0]); |
188 const SkDCurve& testCurve = test->fCurvePart; | 188 const SkDCurve& testCurve = test->fPart.fCurve; |
189 for (int index = 1; index <= iMax; ++index) { | 189 for (int index = 1; index <= iMax; ++index) { |
190 double xy1 = line.fX * (testCurve[index].fY - origin.fY); | 190 double xy1 = line.fX * (testCurve[index].fY - origin.fY); |
191 double xy2 = line.fY * (testCurve[index].fX - origin.fX); | 191 double xy2 = line.fY * (testCurve[index].fX - origin.fX); |
192 crosses[index - 1] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2; | 192 crosses[index - 1] = AlmostBequalUlps(xy1, xy2) ? 0 : xy1 - xy2; |
193 } | 193 } |
194 if (crosses[0] * crosses[1] < 0) { | 194 if (crosses[0] * crosses[1] < 0) { |
195 return -1; | 195 return -1; |
196 } | 196 } |
197 if (SkPath::kCubic_Verb == testVerb) { | 197 if (SkPath::kCubic_Verb == testVerb) { |
198 if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { | 198 if (crosses[0] * crosses[2] < 0 || crosses[1] * crosses[2] < 0) { |
(...skipping 16 matching lines...) Expand all Loading... |
215 bool SkOpAngle::checkCrossesZero() const { | 215 bool SkOpAngle::checkCrossesZero() const { |
216 int start = SkTMin(fSectorStart, fSectorEnd); | 216 int start = SkTMin(fSectorStart, fSectorEnd); |
217 int end = SkTMax(fSectorStart, fSectorEnd); | 217 int end = SkTMax(fSectorStart, fSectorEnd); |
218 bool crossesZero = end - start > 16; | 218 bool crossesZero = end - start > 16; |
219 return crossesZero; | 219 return crossesZero; |
220 } | 220 } |
221 | 221 |
222 bool SkOpAngle::checkParallel(SkOpAngle* rh) { | 222 bool SkOpAngle::checkParallel(SkOpAngle* rh) { |
223 SkDVector scratch[2]; | 223 SkDVector scratch[2]; |
224 const SkDVector* sweep, * tweep; | 224 const SkDVector* sweep, * tweep; |
225 if (!this->fUnorderedSweep) { | 225 if (this->fPart.isOrdered()) { |
226 sweep = this->fSweep; | 226 sweep = this->fPart.fSweep; |
227 } else { | 227 } else { |
228 scratch[0] = this->fCurvePart[1] - this->fCurvePart[0]; | 228 scratch[0] = this->fPart.fCurve[1] - this->fPart.fCurve[0]; |
229 sweep = &scratch[0]; | 229 sweep = &scratch[0]; |
230 } | 230 } |
231 if (!rh->fUnorderedSweep) { | 231 if (rh->fPart.isOrdered()) { |
232 tweep = rh->fSweep; | 232 tweep = rh->fPart.fSweep; |
233 } else { | 233 } else { |
234 scratch[1] = rh->fCurvePart[1] - rh->fCurvePart[0]; | 234 scratch[1] = rh->fPart.fCurve[1] - rh->fPart.fCurve[0]; |
235 tweep = &scratch[1]; | 235 tweep = &scratch[1]; |
236 } | 236 } |
237 double s0xt0 = sweep->crossCheck(*tweep); | 237 double s0xt0 = sweep->crossCheck(*tweep); |
238 if (tangentsDiverge(rh, s0xt0)) { | 238 if (tangentsDiverge(rh, s0xt0)) { |
239 return s0xt0 < 0; | 239 return s0xt0 < 0; |
240 } | 240 } |
241 // compute the perpendicular to the endpoints and see where it intersects th
e opposite curve | 241 // compute the perpendicular to the endpoints and see where it intersects th
e opposite curve |
242 // if the intersections within the t range, do a cross check on those | 242 // if the intersections within the t range, do a cross check on those |
243 bool inside; | 243 bool inside; |
244 if (!fEnd->contains(rh->fEnd)) { | 244 if (!fEnd->contains(rh->fEnd)) { |
245 if (this->endToSide(rh, &inside)) { | 245 if (this->endToSide(rh, &inside)) { |
246 return inside; | 246 return inside; |
247 } | 247 } |
248 if (rh->endToSide(this, &inside)) { | 248 if (rh->endToSide(this, &inside)) { |
249 return !inside; | 249 return !inside; |
250 } | 250 } |
251 } | 251 } |
252 if (this->midToSide(rh, &inside)) { | 252 if (this->midToSide(rh, &inside)) { |
253 return inside; | 253 return inside; |
254 } | 254 } |
255 if (rh->midToSide(this, &inside)) { | 255 if (rh->midToSide(this, &inside)) { |
256 return !inside; | 256 return !inside; |
257 } | 257 } |
258 // compute the cross check from the mid T values (last resort) | 258 // compute the cross check from the mid T values (last resort) |
259 SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fCurvePart[0]; | 259 SkDVector m0 = segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0]; |
260 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fCurvePart[0]; | 260 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0]; |
261 double m0xm1 = m0.crossCheck(m1); | 261 double m0xm1 = m0.crossCheck(m1); |
262 if (m0xm1 == 0) { | 262 if (m0xm1 == 0) { |
263 this->fUnorderable = true; | 263 this->fUnorderable = true; |
264 rh->fUnorderable = true; | 264 rh->fUnorderable = true; |
265 return true; | 265 return true; |
266 } | 266 } |
267 return m0xm1 < 0; | 267 return m0xm1 < 0; |
268 } | 268 } |
269 | 269 |
270 // the original angle is too short to get meaningful sector information | 270 // the original angle is too short to get meaningful sector information |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
314 } | 314 } |
315 SkOpSpanBase* saveEnd = fEnd; | 315 SkOpSpanBase* saveEnd = fEnd; |
316 fComputedEnd = fEnd = computedEnd; | 316 fComputedEnd = fEnd = computedEnd; |
317 setSpans(); | 317 setSpans(); |
318 setSector(); | 318 setSector(); |
319 fEnd = saveEnd; | 319 fEnd = saveEnd; |
320 return !fUnorderable; | 320 return !fUnorderable; |
321 } | 321 } |
322 | 322 |
323 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const { | 323 int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) const { |
324 const SkDVector* sweep = this->fSweep; | 324 const SkDVector* sweep = this->fPart.fSweep; |
325 const SkDVector* tweep = rh->fSweep; | 325 const SkDVector* tweep = rh->fPart.fSweep; |
326 double s0xs1 = sweep[0].crossCheck(sweep[1]); | 326 double s0xs1 = sweep[0].crossCheck(sweep[1]); |
327 double s0xt0 = sweep[0].crossCheck(tweep[0]); | 327 double s0xt0 = sweep[0].crossCheck(tweep[0]); |
328 double s1xt0 = sweep[1].crossCheck(tweep[0]); | 328 double s1xt0 = sweep[1].crossCheck(tweep[0]); |
329 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0
; | 329 bool tBetweenS = s0xs1 > 0 ? s0xt0 > 0 && s1xt0 < 0 : s0xt0 < 0 && s1xt0 > 0
; |
330 double s0xt1 = sweep[0].crossCheck(tweep[1]); | 330 double s0xt1 = sweep[0].crossCheck(tweep[1]); |
331 double s1xt1 = sweep[1].crossCheck(tweep[1]); | 331 double s1xt1 = sweep[1].crossCheck(tweep[1]); |
332 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; | 332 tBetweenS |= s0xs1 > 0 ? s0xt1 > 0 && s1xt1 < 0 : s0xt1 < 0 && s1xt1 > 0; |
333 double t0xt1 = tweep[0].crossCheck(tweep[1]); | 333 double t0xt1 = tweep[0].crossCheck(tweep[1]); |
334 if (tBetweenS) { | 334 if (tBetweenS) { |
335 return -1; | 335 return -1; |
336 } | 336 } |
337 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1
equals t0 to t1 | 337 if ((s0xt0 == 0 && s1xt1 == 0) || (s1xt0 == 0 && s0xt1 == 0)) { // s0 to s1
equals t0 to t1 |
338 return -1; | 338 return -1; |
339 } | 339 } |
340 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0
; | 340 bool sBetweenT = t0xt1 > 0 ? s0xt0 < 0 && s0xt1 > 0 : s0xt0 > 0 && s0xt1 < 0
; |
341 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; | 341 sBetweenT |= t0xt1 > 0 ? s1xt0 < 0 && s1xt1 > 0 : s1xt0 > 0 && s1xt1 < 0; |
342 if (sBetweenT) { | 342 if (sBetweenT) { |
343 return -1; | 343 return -1; |
344 } | 344 } |
345 // if all of the sweeps are in the same half plane, then the order of any pa
ir is enough | 345 // if all of the sweeps are in the same half plane, then the order of any pa
ir is enough |
346 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { | 346 if (s0xt0 >= 0 && s0xt1 >= 0 && s1xt0 >= 0 && s1xt1 >= 0) { |
347 return 0; | 347 return 0; |
348 } | 348 } |
349 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { | 349 if (s0xt0 <= 0 && s0xt1 <= 0 && s1xt0 <= 0 && s1xt1 <= 0) { |
350 return 1; | 350 return 1; |
351 } | 351 } |
352 // if the outside sweeps are greater than 180 degress: | 352 // if the outside sweeps are greater than 180 degress: |
353 // first assume the inital tangents are the ordering | 353 // first assume the inital tangents are the ordering |
354 // if the midpoint direction matches the inital order, that is enough | 354 // if the midpoint direction matches the inital order, that is enough |
355 SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fCurvePart[0]; | 355 SkDVector m0 = this->segment()->dPtAtT(this->midT()) - this->fPart.fCurve[0]
; |
356 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fCurvePart[0]; | 356 SkDVector m1 = rh->segment()->dPtAtT(rh->midT()) - rh->fPart.fCurve[0]; |
357 double m0xm1 = m0.crossCheck(m1); | 357 double m0xm1 = m0.crossCheck(m1); |
358 if (s0xt0 > 0 && m0xm1 > 0) { | 358 if (s0xt0 > 0 && m0xm1 > 0) { |
359 return 0; | 359 return 0; |
360 } | 360 } |
361 if (s0xt0 < 0 && m0xm1 < 0) { | 361 if (s0xt0 < 0 && m0xm1 < 0) { |
362 return 1; | 362 return 1; |
363 } | 363 } |
364 if (tangentsDiverge(rh, s0xt0)) { | 364 if (tangentsDiverge(rh, s0xt0)) { |
365 return s0xt0 < 0; | 365 return s0xt0 < 0; |
366 } | 366 } |
(...skipping 18 matching lines...) Expand all Loading... |
385 } | 385 } |
386 } | 386 } |
387 return sqrt(longest) / dist; | 387 return sqrt(longest) / dist; |
388 } | 388 } |
389 | 389 |
390 bool SkOpAngle::endsIntersect(SkOpAngle* rh) { | 390 bool SkOpAngle::endsIntersect(SkOpAngle* rh) { |
391 SkPath::Verb lVerb = this->segment()->verb(); | 391 SkPath::Verb lVerb = this->segment()->verb(); |
392 SkPath::Verb rVerb = rh->segment()->verb(); | 392 SkPath::Verb rVerb = rh->segment()->verb(); |
393 int lPts = SkPathOpsVerbToPoints(lVerb); | 393 int lPts = SkPathOpsVerbToPoints(lVerb); |
394 int rPts = SkPathOpsVerbToPoints(rVerb); | 394 int rPts = SkPathOpsVerbToPoints(rVerb); |
395 SkDLine rays[] = {{{this->fCurvePart[0], rh->fCurvePart[rPts]}}, | 395 SkDLine rays[] = {{{this->fPart.fCurve[0], rh->fPart.fCurve[rPts]}}, |
396 {{this->fCurvePart[0], this->fCurvePart[lPts]}}}; | 396 {{this->fPart.fCurve[0], this->fPart.fCurve[lPts]}}}; |
397 if (this->fEnd->contains(rh->fEnd)) { | 397 if (this->fEnd->contains(rh->fEnd)) { |
398 return checkParallel(rh); | 398 return checkParallel(rh); |
399 } | 399 } |
400 double smallTs[2] = {-1, -1}; | 400 double smallTs[2] = {-1, -1}; |
401 bool limited[2] = {false, false}; | 401 bool limited[2] = {false, false}; |
402 for (int index = 0; index < 2; ++index) { | 402 for (int index = 0; index < 2; ++index) { |
403 SkPath::Verb cVerb = index ? rVerb : lVerb; | 403 SkPath::Verb cVerb = index ? rVerb : lVerb; |
404 // if the curve is a line, then the line and the ray intersect only at t
heir crossing | 404 // if the curve is a line, then the line and the ray intersect only at t
heir crossing |
405 if (cVerb == SkPath::kLine_Verb) { | 405 if (cVerb == SkPath::kLine_Verb) { |
406 continue; | 406 continue; |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
457 sRayLonger = rayLonger; | 457 sRayLonger = rayLonger; |
458 sCept = cept; | 458 sCept = cept; |
459 sCeptT = smallTs[index]; | 459 sCeptT = smallTs[index]; |
460 sIndex = index; | 460 sIndex = index; |
461 break; | 461 break; |
462 } | 462 } |
463 double delta = fabs(rayDist - endDist); | 463 double delta = fabs(rayDist - endDist); |
464 double minX, minY, maxX, maxY; | 464 double minX, minY, maxX, maxY; |
465 minX = minY = SK_ScalarInfinity; | 465 minX = minY = SK_ScalarInfinity; |
466 maxX = maxY = -SK_ScalarInfinity; | 466 maxX = maxY = -SK_ScalarInfinity; |
467 const SkDCurve& curve = index ? rh->fCurvePart : this->fCurvePart; | 467 const SkDCurve& curve = index ? rh->fPart.fCurve : this->fPart.fCurve; |
468 int ptCount = index ? rPts : lPts; | 468 int ptCount = index ? rPts : lPts; |
469 for (int idx2 = 0; idx2 <= ptCount; ++idx2) { | 469 for (int idx2 = 0; idx2 <= ptCount; ++idx2) { |
470 minX = SkTMin(minX, curve[idx2].fX); | 470 minX = SkTMin(minX, curve[idx2].fX); |
471 minY = SkTMin(minY, curve[idx2].fY); | 471 minY = SkTMin(minY, curve[idx2].fY); |
472 maxX = SkTMax(maxX, curve[idx2].fX); | 472 maxX = SkTMax(maxX, curve[idx2].fX); |
473 maxY = SkTMax(maxY, curve[idx2].fY); | 473 maxY = SkTMax(maxY, curve[idx2].fY); |
474 } | 474 } |
475 double maxWidth = SkTMax(maxX - minX, maxY - minY); | 475 double maxWidth = SkTMax(maxX - minX, maxY - minY); |
476 delta /= maxWidth; | 476 delta /= maxWidth; |
477 if (delta > 1e-3 && (useIntersect ^= true)) { // FIXME: move this magic
number | 477 if (delta > 1e-3 && (useIntersect ^= true)) { // FIXME: move this magic
number |
478 sRayLonger = rayLonger; | 478 sRayLonger = rayLonger; |
479 sCept = cept; | 479 sCept = cept; |
480 sCeptT = smallTs[index]; | 480 sCeptT = smallTs[index]; |
481 sIndex = index; | 481 sIndex = index; |
482 } | 482 } |
483 } | 483 } |
484 if (useIntersect) { | 484 if (useIntersect) { |
485 const SkDCurve& curve = sIndex ? rh->fCurvePart : this->fCurvePart; | 485 const SkDCurve& curve = sIndex ? rh->fPart.fCurve : this->fPart.fCurve; |
486 const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment(); | 486 const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment(); |
487 double tStart = sIndex ? rh->fStart->t() : fStart->t(); | 487 double tStart = sIndex ? rh->fStart->t() : fStart->t(); |
488 SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0
]; | 488 SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0
]; |
489 double septDir = mid.crossCheck(sCept); | 489 double septDir = mid.crossCheck(sCept); |
490 if (!septDir) { | 490 if (!septDir) { |
491 return checkParallel(rh); | 491 return checkParallel(rh); |
492 } | 492 } |
493 return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); | 493 return sRayLonger ^ (sIndex == 0) ^ (septDir < 0); |
494 } else { | 494 } else { |
495 return checkParallel(rh); | 495 return checkParallel(rh); |
(...skipping 21 matching lines...) Expand all Loading... |
517 } | 517 } |
518 if (!endDist) { | 518 if (!endDist) { |
519 return false; | 519 return false; |
520 } | 520 } |
521 SkDPoint start; | 521 SkDPoint start; |
522 start.set(this->fStart->pt()); | 522 start.set(this->fStart->pt()); |
523 // OPTIMIZATION: multiple times in the code we find the max scalar | 523 // OPTIMIZATION: multiple times in the code we find the max scalar |
524 double minX, minY, maxX, maxY; | 524 double minX, minY, maxX, maxY; |
525 minX = minY = SK_ScalarInfinity; | 525 minX = minY = SK_ScalarInfinity; |
526 maxX = maxY = -SK_ScalarInfinity; | 526 maxX = maxY = -SK_ScalarInfinity; |
527 const SkDCurve& curve = rh->fCurvePart; | 527 const SkDCurve& curve = rh->fPart.fCurve; |
528 int oppPts = SkPathOpsVerbToPoints(oppVerb); | 528 int oppPts = SkPathOpsVerbToPoints(oppVerb); |
529 for (int idx2 = 0; idx2 <= oppPts; ++idx2) { | 529 for (int idx2 = 0; idx2 <= oppPts; ++idx2) { |
530 minX = SkTMin(minX, curve[idx2].fX); | 530 minX = SkTMin(minX, curve[idx2].fX); |
531 minY = SkTMin(minY, curve[idx2].fY); | 531 minY = SkTMin(minY, curve[idx2].fY); |
532 maxX = SkTMax(maxX, curve[idx2].fX); | 532 maxX = SkTMax(maxX, curve[idx2].fX); |
533 maxY = SkTMax(maxY, curve[idx2].fY); | 533 maxY = SkTMax(maxY, curve[idx2].fY); |
534 } | 534 } |
535 double maxWidth = SkTMax(maxX - minX, maxY - minY); | 535 double maxWidth = SkTMax(maxX - minX, maxY - minY); |
536 endDist /= maxWidth; | 536 endDist /= maxWidth; |
537 if (endDist < 5e-12) { // empirically found | 537 if (endDist < 5e-12) { // empirically found |
(...skipping 219 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
757 return true; | 757 return true; |
758 } | 758 } |
759 | 759 |
760 bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const { | 760 bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const { |
761 int startSpan = SkTAbs(rh->fSectorStart - fSectorStart); | 761 int startSpan = SkTAbs(rh->fSectorStart - fSectorStart); |
762 return startSpan >= 8; | 762 return startSpan >= 8; |
763 } | 763 } |
764 | 764 |
765 bool SkOpAngle::orderable(SkOpAngle* rh) { | 765 bool SkOpAngle::orderable(SkOpAngle* rh) { |
766 int result; | 766 int result; |
767 if (!fIsCurve) { | 767 if (!fPart.isCurve()) { |
768 if (!rh->fIsCurve) { | 768 if (!rh->fPart.isCurve()) { |
769 double leftX = fTangentHalf.dx(); | 769 double leftX = fTangentHalf.dx(); |
770 double leftY = fTangentHalf.dy(); | 770 double leftY = fTangentHalf.dy(); |
771 double rightX = rh->fTangentHalf.dx(); | 771 double rightX = rh->fTangentHalf.dx(); |
772 double rightY = rh->fTangentHalf.dy(); | 772 double rightY = rh->fTangentHalf.dy(); |
773 double x_ry = leftX * rightY; | 773 double x_ry = leftX * rightY; |
774 double rx_y = rightX * leftY; | 774 double rx_y = rightX * leftY; |
775 if (x_ry == rx_y) { | 775 if (x_ry == rx_y) { |
776 if (leftX * rightX < 0 || leftY * rightY < 0) { | 776 if (leftX * rightX < 0 || leftY * rightY < 0) { |
777 return true; // exactly 180 degrees apart | 777 return true; // exactly 180 degrees apart |
778 } | 778 } |
779 goto unorderable; | 779 goto unorderable; |
780 } | 780 } |
781 SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- wo
rth finding earlier | 781 SkASSERT(x_ry != rx_y); // indicates an undetected coincidence -- wo
rth finding earlier |
782 return x_ry < rx_y; | 782 return x_ry < rx_y; |
783 } | 783 } |
784 if ((result = this->allOnOneSide(rh)) >= 0) { | 784 if ((result = this->allOnOneSide(rh)) >= 0) { |
785 return result; | 785 return result; |
786 } | 786 } |
787 if (fUnorderable || approximately_zero(rh->fSide)) { | 787 if (fUnorderable || approximately_zero(rh->fSide)) { |
788 goto unorderable; | 788 goto unorderable; |
789 } | 789 } |
790 } else if (!rh->fIsCurve) { | 790 } else if (!rh->fPart.isCurve()) { |
791 if ((result = rh->allOnOneSide(this)) >= 0) { | 791 if ((result = rh->allOnOneSide(this)) >= 0) { |
792 return !result; | 792 return !result; |
793 } | 793 } |
794 if (rh->fUnorderable || approximately_zero(fSide)) { | 794 if (rh->fUnorderable || approximately_zero(fSide)) { |
795 goto unorderable; | 795 goto unorderable; |
796 } | 796 } |
797 } else if ((result = this->convexHullOverlaps(rh)) >= 0) { | 797 } else if ((result = this->convexHullOverlaps(rh)) >= 0) { |
798 return result; | 798 return result; |
799 } | 799 } |
800 return this->endsIntersect(rh); | 800 return this->endsIntersect(rh); |
(...skipping 24 matching lines...) Expand all Loading... |
825 fStart = start; | 825 fStart = start; |
826 fComputedEnd = fEnd = end; | 826 fComputedEnd = fEnd = end; |
827 SkASSERT(start != end); | 827 SkASSERT(start != end); |
828 fNext = nullptr; | 828 fNext = nullptr; |
829 fComputeSector = fComputedSector = fCheckCoincidence = false; | 829 fComputeSector = fComputedSector = fCheckCoincidence = false; |
830 setSpans(); | 830 setSpans(); |
831 setSector(); | 831 setSector(); |
832 SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1); | 832 SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1); |
833 } | 833 } |
834 | 834 |
835 void SkOpAngle::setCurveHullSweep() { | |
836 fUnorderedSweep = false; | |
837 fSweep[0] = fCurvePart[1] - fCurvePart[0]; | |
838 const SkOpSegment* segment = fStart->segment(); | |
839 if (SkPath::kLine_Verb == segment->verb()) { | |
840 fSweep[1] = fSweep[0]; | |
841 return; | |
842 } | |
843 fSweep[1] = fCurvePart[2] - fCurvePart[0]; | |
844 // OPTIMIZE: I do the following float check a lot -- probably need a | |
845 // central place for this val-is-small-compared-to-curve check | |
846 double maxVal = 0; | |
847 for (int index = 0; index < SkPathOpsVerbToPoints(segment->verb()); ++index)
{ | |
848 maxVal = SkTMax(maxVal, SkTMax(SkTAbs(fCurvePart[index].fX), | |
849 SkTAbs(fCurvePart[index].fY))); | |
850 } | |
851 | |
852 if (SkPath::kCubic_Verb != segment->verb()) { | |
853 if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal) | |
854 && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) { | |
855 fSweep[0] = fSweep[1]; | |
856 } | |
857 return; | |
858 } | |
859 SkDVector thirdSweep = fCurvePart[3] - fCurvePart[0]; | |
860 if (fSweep[0].fX == 0 && fSweep[0].fY == 0) { | |
861 fSweep[0] = fSweep[1]; | |
862 fSweep[1] = thirdSweep; | |
863 if (roughly_zero_when_compared_to(fSweep[0].fX, maxVal) | |
864 && roughly_zero_when_compared_to(fSweep[0].fY, maxVal)) { | |
865 fSweep[0] = fSweep[1]; | |
866 fCurvePart[1] = fCurvePart[3]; | |
867 fIsCurve = false; | |
868 } | |
869 return; | |
870 } | |
871 double s1x3 = fSweep[0].crossCheck(thirdSweep); | |
872 double s3x2 = thirdSweep.crossCheck(fSweep[1]); | |
873 if (s1x3 * s3x2 >= 0) { // if third vector is on or between first two vecto
rs | |
874 return; | |
875 } | |
876 double s2x1 = fSweep[1].crossCheck(fSweep[0]); | |
877 // FIXME: If the sweep of the cubic is greater than 180 degrees, we're in tr
ouble | |
878 // probably such wide sweeps should be artificially subdivided earlier so th
at never happens | |
879 SkASSERT(s1x3 * s2x1 < 0 || s1x3 * s3x2 < 0); | |
880 if (s3x2 * s2x1 < 0) { | |
881 SkASSERT(s2x1 * s1x3 > 0); | |
882 fSweep[0] = fSweep[1]; | |
883 fUnorderedSweep = true; | |
884 } | |
885 fSweep[1] = thirdSweep; | |
886 } | |
887 | |
888 void SkOpAngle::setSpans() { | 835 void SkOpAngle::setSpans() { |
889 fUnorderable = false; | 836 fUnorderable = false; |
890 fLastMarked = nullptr; | 837 fLastMarked = nullptr; |
891 if (!fStart) { | 838 if (!fStart) { |
892 fUnorderable = true; | 839 fUnorderable = true; |
893 return; | 840 return; |
894 } | 841 } |
895 const SkOpSegment* segment = fStart->segment(); | 842 const SkOpSegment* segment = fStart->segment(); |
896 const SkPoint* pts = segment->pts(); | 843 const SkPoint* pts = segment->pts(); |
897 SkDEBUGCODE(fCurvePart.fVerb = SkPath::kCubic_Verb); | 844 SkDEBUGCODE(fPart.fCurve.fVerb = SkPath::kCubic_Verb); |
898 SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurveP
art[3].fY | 845 SkDEBUGCODE(fPart.fCurve[2].fX = fPart.fCurve[2].fY = fPart.fCurve[3].fX = f
Part.fCurve[3].fY |
899 = SK_ScalarNaN); | 846 = SK_ScalarNaN); |
900 SkDEBUGCODE(fCurvePart.fVerb = segment->verb()); | 847 SkDEBUGCODE(fPart.fCurve.fVerb = segment->verb()); |
901 segment->subDivide(fStart, fEnd, &fCurvePart); | 848 segment->subDivide(fStart, fEnd, &fPart.fCurve); |
902 fOriginalCurvePart = fCurvePart; | 849 fOriginalCurvePart = fPart.fCurve; |
903 setCurveHullSweep(); | |
904 const SkPath::Verb verb = segment->verb(); | 850 const SkPath::Verb verb = segment->verb(); |
905 if (verb != SkPath::kLine_Verb | 851 fPart.setCurveHullSweep(verb); |
906 && !(fIsCurve = fSweep[0].crossCheck(fSweep[1]) != 0)) { | 852 if (SkPath::kLine_Verb != verb && !fPart.isCurve()) { |
907 SkDLine lineHalf; | 853 SkDLine lineHalf; |
908 fCurvePart[1] = fCurvePart[SkPathOpsVerbToPoints(verb)]; | 854 fPart.fCurve[1] = fPart.fCurve[SkPathOpsVerbToPoints(verb)]; |
909 fOriginalCurvePart[1] = fCurvePart[1]; | 855 fOriginalCurvePart[1] = fPart.fCurve[1]; |
910 lineHalf[0].set(fCurvePart[0].asSkPoint()); | 856 lineHalf[0].set(fPart.fCurve[0].asSkPoint()); |
911 lineHalf[1].set(fCurvePart[1].asSkPoint()); | 857 lineHalf[1].set(fPart.fCurve[1].asSkPoint()); |
912 fTangentHalf.lineEndPoints(lineHalf); | 858 fTangentHalf.lineEndPoints(lineHalf); |
913 fSide = 0; | 859 fSide = 0; |
914 } | 860 } |
915 switch (verb) { | 861 switch (verb) { |
916 case SkPath::kLine_Verb: { | 862 case SkPath::kLine_Verb: { |
917 SkASSERT(fStart != fEnd); | 863 SkASSERT(fStart != fEnd); |
918 const SkPoint& cP1 = pts[fStart->t() < fEnd->t()]; | 864 const SkPoint& cP1 = pts[fStart->t() < fEnd->t()]; |
919 SkDLine lineHalf; | 865 SkDLine lineHalf; |
920 lineHalf[0].set(fStart->pt()); | 866 lineHalf[0].set(fStart->pt()); |
921 lineHalf[1].set(cP1); | 867 lineHalf[1].set(cP1); |
922 fTangentHalf.lineEndPoints(lineHalf); | 868 fTangentHalf.lineEndPoints(lineHalf); |
923 fSide = 0; | 869 fSide = 0; |
924 fIsCurve = false; | |
925 } return; | 870 } return; |
926 case SkPath::kQuad_Verb: | 871 case SkPath::kQuad_Verb: |
927 case SkPath::kConic_Verb: { | 872 case SkPath::kConic_Verb: { |
928 SkLineParameters tangentPart; | 873 SkLineParameters tangentPart; |
929 (void) tangentPart.quadEndPoints(fCurvePart.fQuad); | 874 (void) tangentPart.quadEndPoints(fPart.fCurve.fQuad); |
930 fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized --
compare sign only | 875 fSide = -tangentPart.pointDistance(fPart.fCurve[2]); // not normalized
-- compare sign only |
931 } break; | 876 } break; |
932 case SkPath::kCubic_Verb: { | 877 case SkPath::kCubic_Verb: { |
933 SkLineParameters tangentPart; | 878 SkLineParameters tangentPart; |
934 (void) tangentPart.cubicPart(fCurvePart.fCubic); | 879 (void) tangentPart.cubicPart(fPart.fCurve.fCubic); |
935 fSide = -tangentPart.pointDistance(fCurvePart[3]); | 880 fSide = -tangentPart.pointDistance(fPart.fCurve[3]); |
936 double testTs[4]; | 881 double testTs[4]; |
937 // OPTIMIZATION: keep inflections precomputed with cubic segment? | 882 // OPTIMIZATION: keep inflections precomputed with cubic segment? |
938 int testCount = SkDCubic::FindInflections(pts, testTs); | 883 int testCount = SkDCubic::FindInflections(pts, testTs); |
939 double startT = fStart->t(); | 884 double startT = fStart->t(); |
940 double endT = fEnd->t(); | 885 double endT = fEnd->t(); |
941 double limitT = endT; | 886 double limitT = endT; |
942 int index; | 887 int index; |
943 for (index = 0; index < testCount; ++index) { | 888 for (index = 0; index < testCount; ++index) { |
944 if (!::between(startT, testTs[index], limitT)) { | 889 if (!::between(startT, testTs[index], limitT)) { |
945 testTs[index] = -1; | 890 testTs[index] = -1; |
(...skipping 11 matching lines...) Expand all Loading... |
957 index <<= 1; | 902 index <<= 1; |
958 for (; index < testCases; ++index) { | 903 for (; index < testCases; ++index) { |
959 int testIndex = index >> 1; | 904 int testIndex = index >> 1; |
960 double testT = testTs[testIndex]; | 905 double testT = testTs[testIndex]; |
961 if (index & 1) { | 906 if (index & 1) { |
962 testT = (testT + testTs[testIndex + 1]) / 2; | 907 testT = (testT + testTs[testIndex + 1]) / 2; |
963 } | 908 } |
964 // OPTIMIZE: could avoid call for t == startT, endT | 909 // OPTIMIZE: could avoid call for t == startT, endT |
965 SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT); | 910 SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT); |
966 SkLineParameters tangentPart; | 911 SkLineParameters tangentPart; |
967 tangentPart.cubicEndPoints(fCurvePart.fCubic); | 912 tangentPart.cubicEndPoints(fPart.fCurve.fCubic); |
968 double testSide = tangentPart.pointDistance(pt); | 913 double testSide = tangentPart.pointDistance(pt); |
969 if (fabs(bestSide) < fabs(testSide)) { | 914 if (fabs(bestSide) < fabs(testSide)) { |
970 bestSide = testSide; | 915 bestSide = testSide; |
971 } | 916 } |
972 } | 917 } |
973 fSide = -bestSide; // compare sign only | 918 fSide = -bestSide; // compare sign only |
974 } break; | 919 } break; |
975 default: | 920 default: |
976 SkASSERT(0); | 921 SkASSERT(0); |
977 } | 922 } |
978 } | 923 } |
979 | 924 |
980 void SkOpAngle::setSector() { | 925 void SkOpAngle::setSector() { |
981 if (!fStart) { | 926 if (!fStart) { |
982 fUnorderable = true; | 927 fUnorderable = true; |
983 return; | 928 return; |
984 } | 929 } |
985 const SkOpSegment* segment = fStart->segment(); | 930 const SkOpSegment* segment = fStart->segment(); |
986 SkPath::Verb verb = segment->verb(); | 931 SkPath::Verb verb = segment->verb(); |
987 fSectorStart = this->findSector(verb, fSweep[0].fX, fSweep[0].fY); | 932 fSectorStart = this->findSector(verb, fPart.fSweep[0].fX, fPart.fSweep[0].fY
); |
988 if (fSectorStart < 0) { | 933 if (fSectorStart < 0) { |
989 goto deferTilLater; | 934 goto deferTilLater; |
990 } | 935 } |
991 if (!fIsCurve) { // if it's a line or line-like, note that both sectors are
the same | 936 if (!fPart.isCurve()) { // if it's a line or line-like, note that both sect
ors are the same |
992 SkASSERT(fSectorStart >= 0); | 937 SkASSERT(fSectorStart >= 0); |
993 fSectorEnd = fSectorStart; | 938 fSectorEnd = fSectorStart; |
994 fSectorMask = 1 << fSectorStart; | 939 fSectorMask = 1 << fSectorStart; |
995 return; | 940 return; |
996 } | 941 } |
997 SkASSERT(SkPath::kLine_Verb != verb); | 942 SkASSERT(SkPath::kLine_Verb != verb); |
998 fSectorEnd = this->findSector(verb, fSweep[1].fX, fSweep[1].fY); | 943 fSectorEnd = this->findSector(verb, fPart.fSweep[1].fX, fPart.fSweep[1].fY); |
999 if (fSectorEnd < 0) { | 944 if (fSectorEnd < 0) { |
1000 deferTilLater: | 945 deferTilLater: |
1001 fSectorStart = fSectorEnd = -1; | 946 fSectorStart = fSectorEnd = -1; |
1002 fSectorMask = 0; | 947 fSectorMask = 0; |
1003 fComputeSector = true; // can't determine sector until segment length c
an be found | 948 fComputeSector = true; // can't determine sector until segment length c
an be found |
1004 return; | 949 return; |
1005 } | 950 } |
1006 if (fSectorEnd == fSectorStart | 951 if (fSectorEnd == fSectorStart |
1007 && (fSectorStart & 3) != 3) { // if the sector has no span, it can't
be an exact angle | 952 && (fSectorStart & 3) != 3) { // if the sector has no span, it can't
be an exact angle |
1008 fSectorMask = 1 << fSectorStart; | 953 fSectorMask = 1 << fSectorStart; |
(...skipping 29 matching lines...) Expand all Loading... |
1038 } | 983 } |
1039 // if the ctrl tangents are not nearly parallel, use them | 984 // if the ctrl tangents are not nearly parallel, use them |
1040 // solve for opposite direction displacement scale factor == m | 985 // solve for opposite direction displacement scale factor == m |
1041 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x | 986 // initial dir = v1.cross(v2) == v2.x * v1.y - v2.y * v1.x |
1042 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] | 987 // displacement of q1[1] : dq1 = { -m * v1.y, m * v1.x } + q1[1] |
1043 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x
) | 988 // straight angle when : v2.x * (dq1.y - q1[0].y) == v2.y * (dq1.x - q1[0].x
) |
1044 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.
x) | 989 // v2.x * (m * v1.x + v1.y) == v2.y * (-m * v1.y + v1.
x) |
1045 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x | 990 // - m * (v2.x * v1.x + v2.y * v1.y) == v2.x * v1.y - v2.y * v1.x |
1046 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) | 991 // m = (v2.y * v1.x - v2.x * v1.y) / (v2.x * v1.x + v2.y * v1.y) |
1047 // m = v1.cross(v2) / v1.dot(v2) | 992 // m = v1.cross(v2) / v1.dot(v2) |
1048 const SkDVector* sweep = fSweep; | 993 const SkDVector* sweep = fPart.fSweep; |
1049 const SkDVector* tweep = rh->fSweep; | 994 const SkDVector* tweep = rh->fPart.fSweep; |
1050 double s0dt0 = sweep[0].dot(tweep[0]); | 995 double s0dt0 = sweep[0].dot(tweep[0]); |
1051 if (!s0dt0) { | 996 if (!s0dt0) { |
1052 return true; | 997 return true; |
1053 } | 998 } |
1054 SkASSERT(s0dt0 != 0); | 999 SkASSERT(s0dt0 != 0); |
1055 double m = s0xt0 / s0dt0; | 1000 double m = s0xt0 / s0dt0; |
1056 double sDist = sweep[0].length() * m; | 1001 double sDist = sweep[0].length() * m; |
1057 double tDist = tweep[0].length() * m; | 1002 double tDist = tweep[0].length() * m; |
1058 bool useS = fabs(sDist) < fabs(tDist); | 1003 bool useS = fabs(sDist) < fabs(tDist); |
1059 double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tD
ist)); | 1004 double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tD
ist)); |
1060 return mFactor < 50; // empirically found limit | 1005 return mFactor < 50; // empirically found limit |
1061 } | 1006 } |
OLD | NEW |