Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(234)

Side by Side Diff: src/pathops/SkOpAngle.cpp

Issue 2321973005: Rewriting path writer (Closed)
Patch Set: revert unneeded test changes Created 4 years, 3 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/pathops/SkOpAngle.h ('k') | src/pathops/SkOpBuilder.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « src/pathops/SkOpAngle.h ('k') | src/pathops/SkOpBuilder.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698