From 73e597d0eddeaaa466101d5bb7da537c0066166a Mon Sep 17 00:00:00 2001 From: Cary Clark Date: Tue, 18 Apr 2017 12:08:58 -0400 Subject: [PATCH] keep integral rectangle intersections integral A pair of coincident lines can generate multiple intersection points. Path ops is more stable when the intersection T value is used to recompute the intersection point, but this has the side-effect of making integral edges intersect at non-integral values. While it's worthwhile to fix this, for the moment it is less disruptive to only worry about keeping intersection values integral if the original intersection point is integral in both axes. Also, fix some debugging code that bit-rotted. R=msarett@google.com Change-Id: Iefd27b25d1d21c22b224c174bd59bc6c105033c4 Reviewed-on: https://skia-review.googlesource.com/13721 Reviewed-by: Matt Sarett Commit-Queue: Cary Clark --- src/pathops/SkAddIntersections.cpp | 12 +- src/pathops/SkOpSegment.cpp | 7 +- src/pathops/SkOpSegment.h | 1 + src/pathops/SkPathOpsDebug.cpp | 6 +- tests/PathOpsOpTest.cpp | 19 + tools/pathops_visualizer.htm | 1758 ++++-------------------------------- 6 files changed, 232 insertions(+), 1571 deletions(-) diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index b47e7df..b9f2d8d 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -509,9 +509,17 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); wt.segment()->debugValidate(); - SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt]); + // if t value is used to compute pt in addT, error may creep in and + // rect intersections may result in non-rects. if pt value from intersection + // is passed in, current tests break. As a workaround, pass in pt + // value from intersection only if pt.x and pt.y is integral + SkPoint iPt = ts.pt(pt).asSkPoint(); + bool iPtIsIntegral = iPt.fX == floor(iPt.fX) && iPt.fY == floor(iPt.fY); + SkOpPtT* testTAt = iPtIsIntegral ? wt.segment()->addT(ts[swap][pt], iPt) + : wt.segment()->addT(ts[swap][pt]); wn.segment()->debugValidate(); - SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt]); + SkOpPtT* nextTAt = iPtIsIntegral ? wn.segment()->addT(ts[!swap][pt], iPt) + : wn.segment()->addT(ts[!swap][pt]); if (!testTAt->contains(nextTAt)) { SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair if (oppPrev) { // already share a pt-t loop. diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 5502688..1dbeaf6 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -244,9 +244,8 @@ bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* start } // Please keep this in sync with debugAddT() -SkOpPtT* SkOpSegment::addT(double t) { +SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { debugValidate(); - SkPoint pt = this->ptAtT(t); SkOpSpanBase* spanBase = &fHead; do { SkOpPtT* result = spanBase->ptT(); @@ -274,6 +273,10 @@ SkOpPtT* SkOpSegment::addT(double t) { return nullptr; // we never get here, but need this to satisfy compiler } +SkOpPtT* SkOpSegment::addT(double t) { + return addT(t, this->ptAtT(t)); +} + void SkOpSegment::calcAngles() { bool activePrior = !fHead.isCanceled(); if (activePrior && !fHead.simple()) { diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 20b0956..4bde816 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -93,6 +93,7 @@ public: } SkOpPtT* addT(double t); + SkOpPtT* addT(double t, const SkPoint& pt); template T* allocateArray(int count) { return SkOpTAllocator::AllocateArray(this->globalState()->allocator(), count); diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 45a1138..755ce5c 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -1089,7 +1089,11 @@ void SkOpSegment::debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const { spanBase = &fHead; do { // iterate through all spans associated with start const SkOpSpanBase* test = spanBase->upCast()->next(); - if (this->spansNearby(spanBase, test)) { + bool found; + if (!this->spansNearby(spanBase, test, &found)) { + glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test); + } + if (found) { if (test->final()) { if (spanBase->prev()) { glitches->record(SkPathOpsDebug::kMoveNearbyMergeFinal_Glitch, test); diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 365409d..6cc9dc7 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -5409,6 +5409,24 @@ path.close(); testPathOp(reporter, path, path, kUnion_SkPathOp, filename); } +static void android1(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; +path.moveTo(SkBits2Float(0xc0a00000), SkBits2Float(0x00000000)); // -5, 0 +path.lineTo(SkBits2Float(0x44866000), SkBits2Float(0x00000000)); // 1075, 0 +path.lineTo(SkBits2Float(0x44866000), SkBits2Float(0x43720000)); // 1075, 242 +path.lineTo(SkBits2Float(0xc0a00000), SkBits2Float(0x43720000)); // -5, 242 +path.lineTo(SkBits2Float(0xc0a00000), SkBits2Float(0x00000000)); // -5, 0 +path.close(); +pathB.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000)); // 0, 0 +pathB.lineTo(SkBits2Float(0x44870000), SkBits2Float(0x00000000)); // 1080, 0 +pathB.lineTo(SkBits2Float(0x44870000), SkBits2Float(0x43720000)); // 1080, 242 +pathB.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x43720000)); // 0, 242 +pathB.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000)); // 0, 0 +pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_SkPathOp, filename); +} + + static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0; static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; @@ -5416,6 +5434,7 @@ static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; #define TEST(name) { name, #name } static struct TestDesc tests[] = { + TEST(android1), TEST(bug5240), TEST(circlesOp4), TEST(loop17), diff --git a/tools/pathops_visualizer.htm b/tools/pathops_visualizer.htm index 1844dfd..99acb76 100644 --- a/tools/pathops_visualizer.htm +++ b/tools/pathops_visualizer.htm @@ -2,1596 +2,222 @@