Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
Functions
SkAddIntersections.cpp File Reference
#include "src/pathops/SkAddIntersections.h"
#include "include/core/SkPoint.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "src/pathops/SkIntersectionHelper.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkOpCoincidence.h"
#include "src/pathops/SkOpContour.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsBounds.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsTypes.h"
#include <cmath>
#include <utility>

Go to the source code of this file.

Functions

static void debugShowLineIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowQuadLineIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowQuadIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowConicLineIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowConicQuadIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowConicIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowCubicLineIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowCubicQuadIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowCubicConicIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
static void debugShowCubicIntersection (int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
 
bool AddIntersectTs (SkOpContour *test, SkOpContour *next, SkOpCoincidence *coincidence)
 

Function Documentation

◆ AddIntersectTs()

bool AddIntersectTs ( SkOpContour test,
SkOpContour next,
SkOpCoincidence coincidence 
)

Definition at line 275 of file SkAddIntersections.cpp.

275 {
276 if (test != next) {
277 if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
278 return false;
279 }
280 // OPTIMIZATION: outset contour bounds a smidgen instead?
281 if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
282 return true;
283 }
284 }
286 wt.init(test);
287 do {
289 wn.init(next);
290 test->debugValidate();
291 next->debugValidate();
292 if (test == next && !wn.startAfter(wt)) {
293 continue;
294 }
295 do {
296 if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
297 continue;
298 }
299 int pts = 0;
300 SkIntersections ts { SkDEBUGCODE(test->globalState()) };
301 bool swap = false;
302 SkDQuad quad1, quad2;
303 SkDConic conic1, conic2;
304 SkDCubic cubic1, cubic2;
305 switch (wt.segmentType()) {
307 swap = true;
308 switch (wn.segmentType()) {
312 pts = ts.lineHorizontal(wn.pts(), wt.left(),
313 wt.right(), wt.y(), wt.xFlipped());
314 debugShowLineIntersection(pts, wn, wt, ts);
315 break;
317 pts = ts.quadHorizontal(wn.pts(), wt.left(),
318 wt.right(), wt.y(), wt.xFlipped());
319 debugShowQuadLineIntersection(pts, wn, wt, ts);
320 break;
322 pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(),
323 wt.right(), wt.y(), wt.xFlipped());
324 debugShowConicLineIntersection(pts, wn, wt, ts);
325 break;
327 pts = ts.cubicHorizontal(wn.pts(), wt.left(),
328 wt.right(), wt.y(), wt.xFlipped());
329 debugShowCubicLineIntersection(pts, wn, wt, ts);
330 break;
331 default:
332 SkASSERT(0);
333 }
334 break;
336 swap = true;
337 switch (wn.segmentType()) {
341 pts = ts.lineVertical(wn.pts(), wt.top(),
342 wt.bottom(), wt.x(), wt.yFlipped());
343 debugShowLineIntersection(pts, wn, wt, ts);
344 break;
345 }
347 pts = ts.quadVertical(wn.pts(), wt.top(),
348 wt.bottom(), wt.x(), wt.yFlipped());
349 debugShowQuadLineIntersection(pts, wn, wt, ts);
350 break;
351 }
353 pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(),
354 wt.bottom(), wt.x(), wt.yFlipped());
355 debugShowConicLineIntersection(pts, wn, wt, ts);
356 break;
357 }
359 pts = ts.cubicVertical(wn.pts(), wt.top(),
360 wt.bottom(), wt.x(), wt.yFlipped());
361 debugShowCubicLineIntersection(pts, wn, wt, ts);
362 break;
363 }
364 default:
365 SkASSERT(0);
366 }
367 break;
369 switch (wn.segmentType()) {
371 pts = ts.lineHorizontal(wt.pts(), wn.left(),
372 wn.right(), wn.y(), wn.xFlipped());
373 debugShowLineIntersection(pts, wt, wn, ts);
374 break;
376 pts = ts.lineVertical(wt.pts(), wn.top(),
377 wn.bottom(), wn.x(), wn.yFlipped());
378 debugShowLineIntersection(pts, wt, wn, ts);
379 break;
381 pts = ts.lineLine(wt.pts(), wn.pts());
382 debugShowLineIntersection(pts, wt, wn, ts);
383 break;
385 swap = true;
386 pts = ts.quadLine(wn.pts(), wt.pts());
387 debugShowQuadLineIntersection(pts, wn, wt, ts);
388 break;
390 swap = true;
391 pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts());
392 debugShowConicLineIntersection(pts, wn, wt, ts);
393 break;
395 swap = true;
396 pts = ts.cubicLine(wn.pts(), wt.pts());
397 debugShowCubicLineIntersection(pts, wn, wt, ts);
398 break;
399 default:
400 SkASSERT(0);
401 }
402 break;
404 switch (wn.segmentType()) {
406 pts = ts.quadHorizontal(wt.pts(), wn.left(),
407 wn.right(), wn.y(), wn.xFlipped());
408 debugShowQuadLineIntersection(pts, wt, wn, ts);
409 break;
411 pts = ts.quadVertical(wt.pts(), wn.top(),
412 wn.bottom(), wn.x(), wn.yFlipped());
413 debugShowQuadLineIntersection(pts, wt, wn, ts);
414 break;
416 pts = ts.quadLine(wt.pts(), wn.pts());
417 debugShowQuadLineIntersection(pts, wt, wn, ts);
418 break;
420 pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
421 debugShowQuadIntersection(pts, wt, wn, ts);
422 break;
423 }
425 swap = true;
426 pts = ts.intersect(conic2.set(wn.pts(), wn.weight()),
427 quad1.set(wt.pts()));
428 debugShowConicQuadIntersection(pts, wn, wt, ts);
429 break;
430 }
432 swap = true;
433 pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
434 debugShowCubicQuadIntersection(pts, wn, wt, ts);
435 break;
436 }
437 default:
438 SkASSERT(0);
439 }
440 break;
442 switch (wn.segmentType()) {
444 pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(),
445 wn.right(), wn.y(), wn.xFlipped());
446 debugShowConicLineIntersection(pts, wt, wn, ts);
447 break;
449 pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(),
450 wn.bottom(), wn.x(), wn.yFlipped());
451 debugShowConicLineIntersection(pts, wt, wn, ts);
452 break;
454 pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts());
455 debugShowConicLineIntersection(pts, wt, wn, ts);
456 break;
458 pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
459 quad2.set(wn.pts()));
460 debugShowConicQuadIntersection(pts, wt, wn, ts);
461 break;
462 }
464 pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
465 conic2.set(wn.pts(), wn.weight()));
466 debugShowConicIntersection(pts, wt, wn, ts);
467 break;
468 }
470 swap = true;
471 pts = ts.intersect(cubic2.set(wn.pts()
472 SkDEBUGPARAMS(ts.globalState())),
473 conic1.set(wt.pts(), wt.weight()
474 SkDEBUGPARAMS(ts.globalState())));
475 debugShowCubicConicIntersection(pts, wn, wt, ts);
476 break;
477 }
478 }
479 break;
481 switch (wn.segmentType()) {
483 pts = ts.cubicHorizontal(wt.pts(), wn.left(),
484 wn.right(), wn.y(), wn.xFlipped());
485 debugShowCubicLineIntersection(pts, wt, wn, ts);
486 break;
488 pts = ts.cubicVertical(wt.pts(), wn.top(),
489 wn.bottom(), wn.x(), wn.yFlipped());
490 debugShowCubicLineIntersection(pts, wt, wn, ts);
491 break;
493 pts = ts.cubicLine(wt.pts(), wn.pts());
494 debugShowCubicLineIntersection(pts, wt, wn, ts);
495 break;
497 pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
498 debugShowCubicQuadIntersection(pts, wt, wn, ts);
499 break;
500 }
502 pts = ts.intersect(cubic1.set(wt.pts()
503 SkDEBUGPARAMS(ts.globalState())),
504 conic2.set(wn.pts(), wn.weight()
505 SkDEBUGPARAMS(ts.globalState())));
506 debugShowCubicConicIntersection(pts, wt, wn, ts);
507 break;
508 }
510 pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
511 debugShowCubicIntersection(pts, wt, wn, ts);
512 break;
513 }
514 default:
515 SkASSERT(0);
516 }
517 break;
518 default:
519 SkASSERT(0);
520 }
521#if DEBUG_T_SECT_LOOP_COUNT
522 test->globalState()->debugAddLoopCount(&ts, wt, wn);
523#endif
524 int coinIndex = -1;
525 SkOpPtT* coinPtT[2];
526 for (int pt = 0; pt < pts; ++pt) {
527 SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
528 SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
529 wt.segment()->debugValidate();
530 // if t value is used to compute pt in addT, error may creep in and
531 // rect intersections may result in non-rects. if pt value from intersection
532 // is passed in, current tests break. As a workaround, pass in pt
533 // value from intersection only if pt.x and pt.y is integral
534 SkPoint iPt = ts.pt(pt).asSkPoint();
535 bool iPtIsIntegral = iPt.fX == floor(iPt.fX) && iPt.fY == floor(iPt.fY);
536 SkOpPtT* testTAt = iPtIsIntegral ? wt.segment()->addT(ts[swap][pt], iPt)
537 : wt.segment()->addT(ts[swap][pt]);
538 wn.segment()->debugValidate();
539 SkOpPtT* nextTAt = iPtIsIntegral ? wn.segment()->addT(ts[!swap][pt], iPt)
540 : wn.segment()->addT(ts[!swap][pt]);
541 if (!testTAt->contains(nextTAt)) {
542 SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair
543 if (oppPrev) { // already share a pt-t loop.
544 testTAt->span()->mergeMatches(nextTAt->span());
545 testTAt->addOpp(nextTAt, oppPrev);
546 }
547 if (testTAt->fPt != nextTAt->fPt) {
548 testTAt->span()->unaligned();
549 nextTAt->span()->unaligned();
550 }
551 wt.segment()->debugValidate();
552 wn.segment()->debugValidate();
553 }
554 if (!ts.isCoincident(pt)) {
555 continue;
556 }
557 if (coinIndex < 0) {
558 coinPtT[0] = testTAt;
559 coinPtT[1] = nextTAt;
560 coinIndex = pt;
561 continue;
562 }
563 if (coinPtT[0]->span() == testTAt->span()) {
564 coinIndex = -1;
565 continue;
566 }
567 if (coinPtT[1]->span() == nextTAt->span()) {
568 coinIndex = -1; // coincidence span collapsed
569 continue;
570 }
571 if (swap) {
572 using std::swap;
573 swap(coinPtT[0], coinPtT[1]);
574 swap(testTAt, nextTAt);
575 }
576 SkASSERT(coincidence->globalState()->debugSkipAssert()
577 || coinPtT[0]->span()->t() < testTAt->span()->t());
578 if (coinPtT[0]->span()->deleted()) {
579 coinIndex = -1;
580 continue;
581 }
582 if (testTAt->span()->deleted()) {
583 coinIndex = -1;
584 continue;
585 }
586 coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt);
587 wt.segment()->debugValidate();
588 wn.segment()->debugValidate();
589 coinIndex = -1;
590 }
591 SkOPOBJASSERT(coincidence, coinIndex < 0); // expect coincidence to be paired
592 } while (wn.advance());
593 } while (wt.advance());
594 return true;
595}
static float next(float f)
static void debugShowConicQuadIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowQuadIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowQuadLineIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowCubicIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowCubicConicIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowLineIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowConicLineIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowConicIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowCubicLineIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
static void debugShowCubicQuadIntersection(int, const SkIntersectionHelper &, const SkIntersectionHelper &, const SkIntersections &)
#define SkASSERT(cond)
Definition SkAssert.h:116
#define SkDEBUGCODE(...)
Definition SkDebug.h:23
#define SkDEBUGPARAMS(...)
bool AlmostLessUlps(float a, float b)
#define SkOPOBJASSERT(obj, cond)
void swap(sk_sp< T > &a, sk_sp< T > &b)
Definition SkRefCnt.h:341
const SkPathOpsBounds & bounds() const
bool startAfter(const SkIntersectionHelper &after)
SkOpSegment * segment() const
void init(SkOpContour *contour)
SegmentType segmentType() const
const SkPoint * pts() const
void add(SkOpPtT *coinPtTStart, SkOpPtT *coinPtTEnd, SkOpPtT *oppPtTStart, SkOpPtT *oppPtTEnd)
SkOpGlobalState * globalState()
const SkOpSpanBase * span() const
Definition SkOpSpan.h:154
SkPoint fPt
Definition SkOpSpan.h:167
SkOpPtT * oppPrev(const SkOpPtT *opp) const
Definition SkOpSpan.h:104
void addOpp(SkOpPtT *opp, SkOpPtT *oppPrev)
Definition SkOpSpan.h:34
bool contains(const SkOpPtT *) const
Definition SkOpSpan.cpp:36
void debugValidate() const
SkOpPtT * addT(double t)
bool mergeMatches(SkOpSpanBase *opp)
Definition SkOpSpan.cpp:313
void unaligned()
Definition SkOpSpan.h:379
bool deleted() const
Definition SkOpSpan.h:261
double t() const
Definition SkOpSpan.h:375
SIN Vec< N, float > floor(const Vec< N, float > &x)
Definition SkVx.h:703
const SkDConic & set(const SkPoint pts[kPointCount], SkScalar weight SkDEBUGPARAMS(SkOpGlobalState *state=nullptr))
const SkDCubic & set(const SkPoint pts[kPointCount] SkDEBUGPARAMS(SkOpGlobalState *state=nullptr))
const SkDQuad & set(const SkPoint pts[kPointCount] SkDEBUGPARAMS(SkOpGlobalState *state=nullptr))
static bool Intersects(const SkPathOpsBounds &a, const SkPathOpsBounds &b)
float fX
x-axis value
float fY
y-axis value

◆ debugShowConicIntersection()

static void debugShowConicIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 254 of file SkAddIntersections.cpp.

255 {
256}

◆ debugShowConicLineIntersection()

static void debugShowConicLineIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 246 of file SkAddIntersections.cpp.

247 {
248}

◆ debugShowConicQuadIntersection()

static void debugShowConicQuadIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 250 of file SkAddIntersections.cpp.

251 {
252}

◆ debugShowCubicConicIntersection()

static void debugShowCubicConicIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 266 of file SkAddIntersections.cpp.

267 {
268}

◆ debugShowCubicIntersection()

static void debugShowCubicIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 270 of file SkAddIntersections.cpp.

271 {
272}

◆ debugShowCubicLineIntersection()

static void debugShowCubicLineIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 258 of file SkAddIntersections.cpp.

259 {
260}

◆ debugShowCubicQuadIntersection()

static void debugShowCubicQuadIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 262 of file SkAddIntersections.cpp.

263 {
264}

◆ debugShowLineIntersection()

static void debugShowLineIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 234 of file SkAddIntersections.cpp.

235 {
236}

◆ debugShowQuadIntersection()

static void debugShowQuadIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 242 of file SkAddIntersections.cpp.

243 {
244}

◆ debugShowQuadLineIntersection()

static void debugShowQuadLineIntersection ( int  ,
const SkIntersectionHelper ,
const SkIntersectionHelper ,
const SkIntersections  
)
static

Definition at line 238 of file SkAddIntersections.cpp.

239 {
240}