diff options
author | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-10-26 21:03:50 +0000 |
---|---|---|
committer | caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2012-10-26 21:03:50 +0000 |
commit | f839c0359c308fd06895d9f73fc12c4f3869e399 (patch) | |
tree | 0c5821437bb8d2eefc6a2e7f9c476b1b865f783f /experimental | |
parent | 0c5f3762e863411798b1d6c55157d24c69d5bc25 (diff) |
shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@6159 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'experimental')
-rw-r--r-- | experimental/Intersection/EdgeDemo.cpp | 55 | ||||
-rw-r--r-- | experimental/Intersection/EdgeDemoApp.mm | 2 | ||||
-rw-r--r-- | experimental/Intersection/MiniSimplify_Test.cpp | 8 | ||||
-rw-r--r-- | experimental/Intersection/ShapeOps.cpp | 32 | ||||
-rw-r--r-- | experimental/Intersection/Simplify.cpp | 751 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyFindTop_Test.cpp | 4 | ||||
-rw-r--r-- | experimental/Intersection/SimplifyNew_Test.cpp | 98 | ||||
-rw-r--r-- | experimental/Intersection/as.htm | 488 | ||||
-rw-r--r-- | experimental/Intersection/bc.htm | 5 | ||||
-rw-r--r-- | experimental/Intersection/op.htm | 330 |
10 files changed, 1581 insertions, 192 deletions
diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp index 09701ce049..00eac48f93 100644 --- a/experimental/Intersection/EdgeDemo.cpp +++ b/experimental/Intersection/EdgeDemo.cpp @@ -228,25 +228,35 @@ static void tryRoncoOnce(const SkPath& path, const SkRect& target, bool show) { } static void tryRonco(const SkPath& path) { - const SkRect& overall = path.getBounds(); - const int divs = 64; - SkScalar cellWidth = overall.width() / divs * 2; - SkScalar cellHeight = overall.height() / divs * 2; - SkRect target; + int divMax = 17; + int divMin = 1; + int xDivMin = 0; + int yDivMin = 0; + bool allYs = true; + bool allXs = true; if (1) { - int xDiv = 27; - int yDiv = 11; - target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs, - overall.fTop + (overall.height() - cellHeight) * yDiv / divs, - cellWidth, cellHeight); - tryRoncoOnce(path, target, true); - } else { - for (int xDiv = 0; xDiv < divs; ++xDiv) { - for (int yDiv = 0; yDiv < divs; ++yDiv) { + divMax = divMin = 3; + xDivMin = 0; + yDivMin = 0; + allXs = true; + allYs = true; + } + for (int divs = divMax; divs >= divMin; divs -= 2) { + SkDebugf("divs=%d\n",divs); + const SkRect& overall = path.getBounds(); + SkScalar cellWidth = overall.width() / divs * 2; + SkScalar cellHeight = overall.height() / divs * 2; + SkRect target; + int xDivMax = divMax == divMin && !allXs ? xDivMin + 1 : divs; + int yDivMax = divMax == divMin && !allYs ? yDivMin + 1 : divs; + for (int xDiv = xDivMin; xDiv < xDivMax; ++xDiv) { + SkDebugf("xDiv=%d\n",xDiv); + for (int yDiv = yDivMin; yDiv < yDivMax; ++yDiv) { + SkDebugf("yDiv=%d\n",yDiv); target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs, overall.fTop + (overall.height() - cellHeight) * yDiv / divs, cellWidth, cellHeight); - tryRoncoOnce(path, target, true); + tryRoncoOnce(path, target, divMax == divMin); } } } @@ -277,10 +287,15 @@ static bool drawLetters(SkCanvas* canvas, int step, bool useOld) textPos[x].fY = height / 2; } paint.setTextSize(40 + step / 100.0f); -#if 0 +#if 1 + bool oneShot = false; for (int mask = 0; mask < 1 << testStrLen; ++mask) { char maskStr[testStrLen]; - mask = 15; +#if 1 + mask = 3; + oneShot = true; +#endif + SkDebugf("mask=%d\n", mask); for (int letter = 0; letter < testStrLen; ++letter) { maskStr[letter] = mask & (1 << letter) ? testStr[letter] : ' '; } @@ -288,12 +303,16 @@ static bool drawLetters(SkCanvas* canvas, int step, bool useOld) // showPath(path, NULL); // SkDebugf("%d simplified:\n", mask); tryRonco(path); - testSimplifyx(path); + // testSimplifyx(path); + if (oneShot) { + break; + } } #endif paint.getPosTextPath(testStr, testStrLen, textPos, &path); #if 1 tryRonco(path); + SkDebugf("RoncoDone!\n"); #endif #if 0 showPath(path, NULL); diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm index a3b9c5789d..67dc6138a6 100644 --- a/experimental/Intersection/EdgeDemoApp.mm +++ b/experimental/Intersection/EdgeDemoApp.mm @@ -16,7 +16,7 @@ public: }; protected: virtual void onDraw(SkCanvas* canvas) { - static int step = 17909 ; // drawLetters first error + static int step = 9658; // 17909 ; // drawLetters first error // drawStars triggers error at 23275 // drawStars error not easy to debug last time I checked static double seconds; diff --git a/experimental/Intersection/MiniSimplify_Test.cpp b/experimental/Intersection/MiniSimplify_Test.cpp index 4662381ec3..6d6036c0ff 100644 --- a/experimental/Intersection/MiniSimplify_Test.cpp +++ b/experimental/Intersection/MiniSimplify_Test.cpp @@ -18,7 +18,15 @@ struct curve test1[] = { {SkPath::kDone_Verb} }; +struct curve test2[] = { +{SkPath::kQuad_Verb, {{366.608826f, 151.196014f}, {378.803101f, 136.674606f}, {398.164948f, 136.674606f}}}, +{SkPath::kQuad_Verb, {{359.978058f, 136.581512f}, {378.315979f, 136.581512f}, {388.322723f, 149.613556f}}}, +{SkPath::kQuad_Verb, {{364.390686f, 157.898193f}, {375.281769f, 136.674606f}, {396.039917f, 136.674606f}}}, +{SkPath::kDone_Verb} +}; + struct curve* testSet[] = { + test2, test1 }; diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp index 4785e86129..669fa6d14d 100644 --- a/experimental/Intersection/ShapeOps.cpp +++ b/experimental/Intersection/ShapeOps.cpp @@ -17,8 +17,9 @@ static bool windingIsActive(int winding, int spanWinding, int oppWinding, } static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, - const int aXorMask, const int bXorMask, SkPath& simple) { + const int aXorMask, const int bXorMask, PathWrapper& simple) { bool firstContour = true; + SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; do { #if SORTABLE_CONTOURS // old way @@ -32,7 +33,7 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, Segment* current = topStart->findTop(index, endIndex); #else // new way: iterate while top is unsortable int index, endIndex; - Segment* current = findSortableTop(contourList, index, endIndex); + Segment* current = findSortableTop(contourList, index, endIndex, topLeft); if (!current) { break; } @@ -68,7 +69,7 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); #endif } - SkPoint lastPt; + // SkPoint lastPt; int winding = contourWinding; int spanWinding = current->spanSign(index, endIndex); int oppWinding = current->oppSign(index, endIndex); @@ -81,7 +82,7 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, __FUNCTION__, active ? "true" : "false", winding, spanWinding); #endif - const SkPoint* firstPt = NULL; + // const SkPoint* firstPt = NULL; do { SkASSERT(!current->done()); int nextStart = index; @@ -93,21 +94,23 @@ static void bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op, // FIXME: if unsortable, allow partial paths to be later // assembled SkASSERT(!unsortable); - if (active && firstPt && current->verb() != SkPath::kLine_Verb && *firstPt != lastPt) { - lastPt = current->addCurveTo(index, endIndex, simple, true); - SkASSERT(*firstPt == lastPt); + if (active && simple.hasMove() + && current->verb() != SkPath::kLine_Verb + && !simple.isClosed()) { + /* lastPt = */ current->addCurveTo(index, endIndex, simple, true); + SkASSERT(simple.isClosed()); } break; } - if (!firstPt) { - firstPt = ¤t->addMoveTo(index, simple, active); - } - lastPt = current->addCurveTo(index, endIndex, simple, active); + // if (!firstPt) { + // firstPt = ¤t->addMoveTo(index, simple, active); + // } + /* lastPt = */ current->addCurveTo(index, endIndex, simple, active); current = next; index = nextStart; endIndex = nextEnd; - } while (*firstPt != lastPt && (active || !current->done())); - if (firstPt && active) { + } while (!simple.isClosed() && (active || !current->done())); + if (simple.hasMove() && active) { #if DEBUG_PATH_CONSTRUCTION SkDebugf("%s close\n", __FUNCTION__); #endif @@ -175,5 +178,6 @@ void operate(const SkPath& one, const SkPath& two, ShapeOp op, SkPath& result) { coincidenceCheck(contourList); fixOtherTIndex(contourList); // construct closed contours - bridgeOp(contourList, op, aXorMask, bXorMask, result); + Op::PathWrapper wrapper(result); + bridgeOp(contourList, op, aXorMask, bXorMask, wrapper); } diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index 513f2e22a1..3ecb164971 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -27,9 +27,10 @@ int gDebugMaxWindValue = SK_MaxS32; #define PRECISE_T_SORT 1 #define SORTABLE_CONTOURS 0 // set to 1 for old code that works most of the time +#define PIN_ADD_T 0 #define DEBUG_UNUSED 0 // set to expose unused functions -#define FORCE_RELEASE 1 +#define FORCE_RELEASE 0 #if FORCE_RELEASE || defined SK_RELEASE // set force release to 1 for multiple thread -- no debugging @@ -42,7 +43,7 @@ const bool gRunTestsInOneThread = false; #define DEBUG_CONCIDENT 0 #define DEBUG_CROSS 0 #define DEBUG_MARK_DONE 0 -#define DEBUG_PATH_CONSTRUCTION 1 +#define DEBUG_PATH_CONSTRUCTION 0 #define DEBUG_SORT 0 #define DEBUG_WIND_BUMP 0 #define DEBUG_WINDING 0 @@ -485,6 +486,7 @@ struct Span { bool fDone; // if set, this span to next higher T has been processed bool fUnsortableStart; // set when start is part of an unsortable pair bool fUnsortableEnd; // set when end is part of an unsortable pair + bool fTiny; // if set, span may still be considered once for edge following }; // sorting angles @@ -679,6 +681,7 @@ public: LineSubDivideHD(fPts, startT, endT, l); // OPTIMIZATION: for pure line compares, we never need fTangent1.c fTangent1.lineEndPoints(l); + fUnsortable = dx() == 0 && dy() == 0; fSide = 0; break; case SkPath::kQuad_Verb: @@ -695,6 +698,21 @@ public: default: SkASSERT(0); } + if (fUnsortable) { + return; + } + SkASSERT(fStart != fEnd); + int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? + for (int index = fStart; index != fEnd; index += step) { + if ((*fSpans)[index].fUnsortableStart) { + fUnsortable = true; + return; + } + if (index != fStart && (*fSpans)[index].fUnsortableEnd) { + fUnsortable = true; + return; + } + } } Segment* segment() const { @@ -822,6 +840,147 @@ static bool activeOp(bool angleIsOp, int otherNonZero, ShapeOp op) { return opLookup[op][otherNonZero][angleIsOp]; } + +// wrap path to keep track of whether the contour is initialized and non-empty +class PathWrapper { +public: + PathWrapper(SkPath& path) + : fPathPtr(&path) + { + init(); + } + + void close() { + if (!fHasMove) { + return; + } + bool callClose = isClosed(); + lineTo(); + if (fEmpty) { + return; + } + if (callClose) { + #if DEBUG_PATH_CONSTRUCTION + SkDebugf("path.close();\n"); + #endif + fPathPtr->close(); + } + init(); + } + + void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) { + lineTo(); + moveTo(); +#if DEBUG_PATH_CONSTRUCTION + SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", + pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY); +#endif + fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, pt3.fX, pt3.fY); + fDefer[0] = fDefer[1] = pt3; + fEmpty = false; + } + + void deferredLine(const SkPoint& pt) { + if (pt == fDefer[1]) { + return; + } + if (changedSlopes(pt)) { + lineTo(); + fDefer[0] = fDefer[1]; + } + fDefer[1] = pt; + } + + void deferredMove(const SkPoint& pt) { + fMoved = true; + fHasMove = true; + fEmpty = true; + fDefer[0] = fDefer[1] = pt; + } + + void deferredMoveLine(const SkPoint& pt) { + if (!fHasMove) { + deferredMove(pt); + } + deferredLine(pt); + } + + bool hasMove() const { + return fHasMove; + } + + void init() { + fEmpty = true; + fHasMove = false; + fMoved = false; + } + + bool isClosed() const { + return !fEmpty && fFirstPt == fDefer[1]; + } + + void lineTo() { + if (fDefer[0] == fDefer[1]) { + return; + } + moveTo(); + fEmpty = false; +#if DEBUG_PATH_CONSTRUCTION + SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY); +#endif + fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY); + fDefer[0] = fDefer[1]; + } + + const SkPath* nativePath() const { + return fPathPtr; + } + + void quadTo(const SkPoint& pt1, const SkPoint& pt2) { + lineTo(); + moveTo(); +#if DEBUG_PATH_CONSTRUCTION + SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", + pt1.fX, pt1.fY, pt2.fX, pt2.fY); +#endif + fPathPtr->quadTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY); + fDefer[0] = fDefer[1] = pt2; + fEmpty = false; + } + +protected: + bool changedSlopes(const SkPoint& pt) const { + if (fDefer[0] == fDefer[1]) { + return false; + } + SkScalar deferDx = fDefer[1].fX - fDefer[0].fX; + SkScalar deferDy = fDefer[1].fY - fDefer[0].fY; + SkScalar lineDx = pt.fX - fDefer[1].fX; + SkScalar lineDy = pt.fY - fDefer[1].fY; + return deferDx * lineDy != deferDy * lineDx; + } + + void moveTo() { + if (!fMoved) { + return; + } + fFirstPt = fDefer[0]; +#if DEBUG_PATH_CONSTRUCTION + SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY); +#endif + fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY); + fMoved = false; + } + +private: + SkPath* fPathPtr; + SkPoint fDefer[2]; + SkPoint fFirstPt; + bool fEmpty; + bool fHasMove; + bool fMoved; +}; + class Segment { public: Segment() { @@ -866,7 +1025,7 @@ public: const Span& upSpan = fTs[index]; if (upSpan.fWindValue) { addAngle(angles, index, next); - if (upSpan.fDone) { + if (upSpan.fDone || upSpan.fUnsortableEnd) { done++; } else if (upSpan.fWindSum != SK_MinS32) { return true; @@ -889,23 +1048,32 @@ public: return false; } - SkScalar activeTop() const { + void activeLeftTop(SkPoint& result) const { SkASSERT(!done()); int count = fTs.count(); - SkScalar result = SK_ScalarMax; + result.fY = SK_ScalarMax; bool lastDone = true; + bool lastUnsortable = false; for (int index = 0; index < count; ++index) { - bool done = fTs[index].fDone; - if (!done || !lastDone) { - SkScalar y = yAtT(index); - if (result > y) { - result = y; + const Span& span = fTs[index]; + if (span.fUnsortableStart | lastUnsortable) { + goto next; + } + if (!span.fDone | !lastDone) { + const SkPoint& xy = xyAtT(index); + if (result.fY < xy.fY) { + goto next; + } + if (result.fY == xy.fY && result.fX < xy.fX) { + goto next; } + result = xy; } - lastDone = done; + next: + lastDone = span.fDone; + lastUnsortable = span.fUnsortableEnd; } - SkASSERT(result < SK_ScalarMax); - return result; + SkASSERT(result.fY < SK_ScalarMax); } void addAngle(SkTDArray<Angle>& angles, int start, int end) const { @@ -1037,40 +1205,54 @@ public: init(pts, SkPath::kCubic_Verb, operand); fBounds.setCubicBounds(pts); } - - // FIXME: this needs to defer add for aligned consecutive line segments - SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { + + /* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const { SkPoint edge[4]; + const SkPoint* ePtr; + int lastT = fTs.count() - 1; + if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) { + ePtr = fPts; + } else { // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) - (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); + ePtr = edge; + } if (active) { - #if DEBUG_PATH_CONSTRUCTION - SkDebugf("path.%sTo(%1.9g,%1.9g", - kLVerbStr[fVerb], edge[1].fX, edge[1].fY); - if (fVerb > 1) { - SkDebugf(", %1.9g,%1.9g", edge[2].fX, edge[2].fY); - } - if (fVerb > 2) { - SkDebugf(", %1.9g,%1.9g", edge[3].fX, edge[3].fY); - } - SkDebugf(");\n"); - #endif - switch (fVerb) { - case SkPath::kLine_Verb: - path.lineTo(edge[1].fX, edge[1].fY); - break; - case SkPath::kQuad_Verb: - path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); - break; - case SkPath::kCubic_Verb: - path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, - edge[3].fX, edge[3].fY); - break; - default: - SkASSERT(0); + bool reverse = ePtr == fPts && start != 0; + if (reverse) { + path.deferredMoveLine(ePtr[fVerb]); + switch (fVerb) { + case SkPath::kLine_Verb: + path.deferredLine(ePtr[0]); + break; + case SkPath::kQuad_Verb: + path.quadTo(ePtr[1], ePtr[0]); + break; + case SkPath::kCubic_Verb: + path.cubicTo(ePtr[2], ePtr[1], ePtr[0]); + break; + default: + SkASSERT(0); + } + // return ePtr[0]; + } else { + path.deferredMoveLine(ePtr[0]); + switch (fVerb) { + case SkPath::kLine_Verb: + path.deferredLine(ePtr[1]); + break; + case SkPath::kQuad_Verb: + path.quadTo(ePtr[1], ePtr[2]); + break; + case SkPath::kCubic_Verb: + path.cubicTo(ePtr[1], ePtr[2], ePtr[3]); + break; + default: + SkASSERT(0); + } } } - return edge[fVerb]; + // return ePtr[fVerb]; } void addLine(const SkPoint pts[2], bool operand) { @@ -1078,25 +1260,26 @@ public: fBounds.set(pts, 2); } - const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { +#if 0 + const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const { const SkPoint& pt = xyAtT(tIndex); if (active) { - #if DEBUG_PATH_CONSTRUCTION - SkDebugf("path.moveTo(%1.9g, %1.9g);\n", pt.fX, pt.fY); - #endif - path.moveTo(pt.fX, pt.fY); + path.deferredMove(pt); } return pt; } +#endif // add 2 to edge or out of range values to get T extremes void addOtherT(int index, double otherT, int otherIndex) { Span& span = fTs[index]; + #if PIN_ADD_T if (precisely_less_than_zero(otherT)) { otherT = 0; } else if (precisely_greater_than_one(otherT)) { otherT = 1; } + #endif span.fOtherT = otherT; span.fOtherIndex = otherIndex; } @@ -1118,12 +1301,14 @@ public: // binary search? int insertedAt = -1; size_t tCount = fTs.count(); + #if PIN_ADD_T // FIXME: only do this pinning here (e.g. this is done also in quad/line intersect) if (precisely_less_than_zero(newT)) { newT = 0; } else if (precisely_greater_than_one(newT)) { newT = 1; } + #endif for (size_t index = 0; index < tCount; ++index) { // OPTIMIZATION: if there are three or more identical Ts, then // the fourth and following could be further insertion-sorted so @@ -1149,11 +1334,32 @@ public: span->fWindSum = SK_MinS32; span->fWindValue = 1; span->fWindValueOpp = 0; + span->fTiny = false; if ((span->fDone = newT == 1)) { ++fDoneSpans; } span->fUnsortableStart = false; span->fUnsortableEnd = false; + if (span - fTs.begin() > 0 && !span[-1].fDone + && !precisely_negative(newT - span[-1].fT) + // && approximately_negative(newT - span[-1].fT) + && xyAtT(&span[-1]) == xyAtT(span)) { + span[-1].fTiny = true; + span[-1].fDone = true; + span[-1].fUnsortableStart = approximately_negative(newT - span[-1].fT) + && approximately_greater_than_one(newT); + ++fDoneSpans; + } + if (fTs.end() - span > 1 && !span->fDone + && !precisely_negative(span[1].fT - newT) + // && approximately_negative(span[1].fT - newT) + && xyAtT(&span[1]) == xyAtT(span)) { + span->fTiny = true; + span->fDone = true; + span->fUnsortableEnd = approximately_negative(span[1].fT - newT) + && approximately_less_than_zero(newT); + ++fDoneSpans; + } return insertedAt; } @@ -1657,8 +1863,10 @@ public: bool decrementSpan(Span* span) { SkASSERT(span->fWindValue > 0); if (--(span->fWindValue) == 0) { - span->fDone = true; - ++fDoneSpans; + if (!span->fDone) { + span->fDone = true; + ++fDoneSpans; + } return true; } return false; @@ -1668,12 +1876,13 @@ public: SkASSERT(fDoneSpans <= fTs.count()); return fDoneSpans == fTs.count(); } + + bool done(int min) const { + return fTs[min].fDone; + } bool done(const Angle& angle) const { - int start = angle.start(); - int end = angle.end(); - const Span& mSpan = fTs[SkMin32(start, end)]; - return mSpan.fDone; + return done(SkMin32(angle.start(), angle.end())); } Segment* findNextOp(SkTDArray<Span*>& chase, bool active, @@ -1779,6 +1988,8 @@ public: } const Angle* nextAngle = sorted[nextIndex]; nextSegment = nextAngle->segment(); + bool nextDone = nextSegment->done(*nextAngle); + bool nextTiny = nextSegment->tiny(*nextAngle); angleIsOp = nextSegment->operand(); int sumWinding = angleIsOp ? bSumWinding : aSumWinding; int maxWinding = sumWinding; @@ -1815,7 +2026,7 @@ public: } if (!foundAngle || foundDone) { foundAngle = nextAngle; - foundDone = nextSegment->done(*nextAngle); + foundDone = nextDone && !nextTiny; foundFlipped = altFlipped; foundMax = maxWinding; } @@ -1829,7 +2040,7 @@ public: } #endif foundAngle = nextAngle; - foundDone2 = nextSegment->done(*nextAngle); + foundDone2 = nextDone && !nextTiny; foundFlipped = altFlipped; foundSum = sumWinding; } @@ -2011,6 +2222,8 @@ public: lastNonZeroSum = sumWinding; } nextSegment = nextAngle->segment(); + bool nextDone = nextSegment->done(*nextAngle); + bool nextTiny = nextSegment->tiny(*nextAngle); sumWinding -= nextSegment->spanSign(nextAngle); altFlipped ^= lastNonZeroSum * sumWinding < 0; // flip if different signs #if 0 && DEBUG_WINDING @@ -2031,12 +2244,13 @@ public: } if (!foundAngle || foundDone) { foundAngle = nextAngle; - foundDone = nextSegment->done(*nextAngle); + foundDone = nextDone && !nextTiny; foundFlipped = altFlipped; foundMax = maxWinding; } continue; } + if (!maxWinding && (!foundAngle || foundDone2)) { #if DEBUG_WINDING if (foundAngle && foundDone2) { @@ -2044,7 +2258,7 @@ public: } #endif foundAngle = nextAngle; - foundDone2 = nextSegment->done(*nextAngle); + foundDone2 = nextDone && !nextTiny; foundFlipped = altFlipped; foundSum = sumWinding; } @@ -2362,9 +2576,13 @@ public: int count = fTs.count(); // see if either end is not done since we want smaller Y of the pair bool lastDone = true; + bool lastUnsortable = false; for (int index = 0; index < count; ++index) { const Span& span = fTs[index]; - if (!span.fDone || !lastDone) { + if (span.fUnsortableStart | lastUnsortable) { + goto next; + } + if (!span.fDone | !lastDone) { const SkPoint& intercept = xyAtT(&span); if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY && topPt.fX > intercept.fX)) { @@ -2374,7 +2592,9 @@ public: lastT = index; } } + next: lastDone = span.fDone; + lastUnsortable = span.fUnsortableEnd; } // sort the edges to find the leftmost int step = 1; @@ -2391,24 +2611,19 @@ public: addTwoAngles(end, firstT, angles); buildAngles(firstT, angles); SkTDArray<Angle*> sorted; - (void) SortAngles(angles, sorted); + bool sortable = SortAngles(angles, sorted); #if DEBUG_SORT sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0); #endif + if (!sortable) { + return NULL; + } // skip edges that have already been processed firstT = -1; Segment* leftSegment; do { const Angle* angle = sorted[++firstT]; - if (angle->unsortable()) { - // FIXME: if all angles are unsortable, find next topmost - if (firstT >= angles.count() - 1) { - #if SORTABLE_CONTOURS - SkASSERT(0); - #endif - return NULL; - } - } + SkASSERT(!angle->unsortable()); leftSegment = angle->segment(); tIndex = angle->end(); endIndex = angle->start(); @@ -2594,7 +2809,7 @@ public: } while (++index < fTs.count() && approximately_negative(fTs[index].fT - referenceT)); #endif } - + void markOneDone(const char* funName, int tIndex, int winding) { Span* span = markOneWinding(funName, tIndex, winding); if (!span) { @@ -2620,6 +2835,9 @@ public: return &span; } + // note that just because a span has one end that is unsortable, that's + // not enough to mark it done. The other end may be sortable, allowing the + // span to be added. void markUnsortable(int start, int end) { Span* span = &fTs[start]; if (start < end) { @@ -2628,7 +2846,7 @@ public: --span; span->fUnsortableEnd = true; } - if (span->fDone) { + if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) { return; } span->fDone = true; @@ -2678,7 +2896,7 @@ public: if (nextDoorWind != SK_MaxS32) { Span& newSpan = fTs[tIndex]; newSpan.fWindValue = nextDoorWind; - if (!nextDoorWind) { + if (!nextDoorWind && !newSpan.fDone) { newSpan.fDone = true; ++fDoneSpans; } @@ -2759,24 +2977,36 @@ public: fTs.reset(); } + // This marks all spans unsortable so that this info is available for early + // exclusion in find top and others. This could be optimized to only mark + // adjacent spans that unsortable. However, this makes it difficult to later + // determine starting points for edge detection in find top and the like. static bool SortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { + bool sortable = true; int angleCount = angles.count(); int angleIndex; angleList.setReserve(angleCount); for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - *angleList.append() = &angles[angleIndex]; - } - QSort<Angle>(angleList.begin(), angleList.end() - 1); - bool result = true; - for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { Angle& angle = angles[angleIndex]; - if (angle.unsortable()) { - // so that it is available for early exclusion in findTop and others + *angleList.append() = ∠ + sortable &= !angle.unsortable(); + } + if (sortable) { + QSort<Angle>(angleList.begin(), angleList.end() - 1); + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { + if (angles[angleIndex].unsortable()) { + sortable = false; + break; + } + } + } + if (!sortable) { + for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { + Angle& angle = angles[angleIndex]; angle.segment()->markUnsortable(angle.start(), angle.end()); - result = false; } } - return result; + return sortable; } // OPTIMIZATION: mark as debugging only if used solely by tests @@ -2803,6 +3033,13 @@ public: return fTs[tIndex].fT; } + bool tiny(const Angle& angle) const { + int start = angle.start(); + int end = angle.end(); + const Span& mSpan = fTs[SkMin32(start, end)]; + return mSpan.fTiny; + } + static void TrackOutside(SkTDArray<double>& outsideTs, double end, double start) { int outCount = outsideTs.count(); @@ -3078,9 +3315,9 @@ public: } else { SkDebugf("%d", mSpan.fWindSum); } - SkDebugf(" winding: %d->%d (max=%d) done=%d\n", lastSum, windSum, + SkDebugf(" winding: %d->%d (max=%d) done=%d tiny=%d\n", lastSum, windSum, useInnerWinding(lastSum, windSum) ? windSum : lastSum, - mSpan.fDone); + mSpan.fDone, mSpan.fTiny); #if false && DEBUG_ANGLE angle.debugShow(segment.xyAtT(&sSpan)); #endif @@ -3274,6 +3511,11 @@ public: } return false; } + + const SkPoint& end() const { + const Segment& segment = fSegments.back(); + return segment.pts()[segment.verb()]; + } void findTooCloseToCall() { int segmentCount = fSegments.count(); @@ -3380,6 +3622,35 @@ public: } #endif + const SkPoint& start() const { + return fSegments.front().pts()[0]; + } + + void toPath(PathWrapper& path) const { + int segmentCount = fSegments.count(); + const SkPoint& pt = fSegments.front().pts()[0]; + path.deferredMove(pt); + for (int test = 0; test < segmentCount; ++test) { + fSegments[test].addCurveTo(0, 1, path, true); + } + path.close(); + } + + void toPartialBackward(PathWrapper& path) const { + int segmentCount = fSegments.count(); + for (int test = segmentCount - 1; test >= 0; --test) { + fSegments[test].addCurveTo(1, 0, path, true); + } + } + + void toPartialForward(PathWrapper& path) const { + int segmentCount = fSegments.count(); + for (int test = 0; test < segmentCount; ++test) { + fSegments[test].addCurveTo(0, 1, path, true); + } + } + +#if 0 // FIXME: obsolete, remove // OPTIMIZATION: feel pretty uneasy about this. It seems like once again // we need to sort and walk edges in y, but that on the surface opens the // same can of worms as before. But then, this is a rough sort based on @@ -3419,25 +3690,39 @@ public: bestY = bestTop; return bestSegment; } +#endif #if !SORTABLE_CONTOURS - Segment* topSortableSegment(SkScalar& bestY) { + Segment* topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY) { int segmentCount = fSortedSegments.count(); SkASSERT(segmentCount > 0); Segment* bestSegment = NULL; - while (fFirstSorted < segmentCount) { - Segment* testSegment = fSortedSegments[fFirstSorted]; + int sortedIndex = fFirstSorted; + for ( ; sortedIndex < segmentCount; ++sortedIndex) { + Segment* testSegment = fSortedSegments[sortedIndex]; if (testSegment->done()) { - fFirstSorted++; + if (sortedIndex == fFirstSorted) { + ++fFirstSorted; + } + continue; + } + SkPoint testXY; + testSegment->activeLeftTop(testXY); + if (testXY.fY < topLeft.fY) { + continue; + } + if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { + continue; + } + if (bestXY.fY < testXY.fY) { + continue; + } + if (bestXY.fY == testXY.fY && bestXY.fX < testXY.fX) { continue; } bestSegment = testSegment; - break; - } - if (!bestSegment) { - return NULL; + bestXY = testXY; } - bestY = bestSegment->activeTop(); return bestSegment; } #endif @@ -3539,13 +3824,24 @@ private: class EdgeBuilder { public: +EdgeBuilder(const PathWrapper& path, SkTArray<Contour>& contours) + : fPath(path.nativePath()) + , fContours(contours) +{ + init(); +} + EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) : fPath(&path) , fContours(contours) - , fCurrentContour(NULL) - , fOperand(false) { - fXorMask = (path.getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; + init(); +} + +void init() { + fCurrentContour = NULL; + fOperand = false; + fXorMask = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; #if DEBUG_DUMP gContourID = 0; gSegmentID = 0; @@ -3555,7 +3851,7 @@ EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) void addOperand(const SkPath& path) { fPath = &path; - fXorMask = (path.getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; + fXorMask = (fPath->getFillType() & 1) ? kEvenOdd_Mask : kWinding_Mask; preFetch(); } @@ -4509,34 +4805,30 @@ static bool windingIsActive(int winding, int spanWinding) { #if !SORTABLE_CONTOURS static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index, - int& endIndex) { + int& endIndex, SkPoint& topLeft) { Segment* result; do { + SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; int contourCount = contourList.count(); - int cIndex = 0; - Segment* topStart; - SkScalar bestY = SK_ScalarMax; - Contour* contour; - do { - contour = contourList[cIndex]; - topStart = contour->topSortableSegment(bestY); - } while (!topStart && ++cIndex < contourCount); - if (!topStart) { - return NULL; - } - while (++cIndex < contourCount) { - contour = contourList[cIndex]; - if (bestY < contour->bounds().fTop) { + Segment* topStart = NULL; + for (int cIndex = 0; cIndex < contourCount; ++cIndex) { + Contour* contour = contourList[cIndex]; + const Bounds& bounds = contour->bounds(); + if (bounds.fBottom < topLeft.fY) { continue; } - SkScalar testY = SK_ScalarMax; - Segment* test = contour->topSortableSegment(testY); - if (!test || bestY <= testY) { + if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) { continue; } - topStart = test; - bestY = testY; + Segment* test = contour->topSortableSegment(topLeft, bestXY); + if (test) { + topStart = test; + } + } + if (!topStart) { + return NULL; } + topLeft = bestXY; result = topStart->findTop(index, endIndex); } while (!result); return result; @@ -4553,9 +4845,11 @@ static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index, // since we start with leftmost top edge, we'll traverse through a // smaller angle counterclockwise to get to the next edge. // returns true if all edges were processed -static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { +static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) { bool firstContour = true; bool unsortable = false; + bool closable = true; + SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin}; do { #if SORTABLE_CONTOURS // old way Segment* topStart = findTopContour(contourList); @@ -4568,7 +4862,7 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { Segment* current = topStart->findTop(index, endIndex); #else // new way: iterate while top is unsortable int index, endIndex; - Segment* current = findSortableTop(contourList, index, endIndex); + Segment* current = findSortableTop(contourList, index, endIndex, topLeft); if (!current) { break; } @@ -4604,7 +4898,6 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); #endif } - SkPoint lastPt; int winding = contourWinding; int spanWinding = current->spanSign(index, endIndex); // FIXME: needs work. While it works in limited situations, it does @@ -4621,7 +4914,6 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { __FUNCTION__, active ? "true" : "false", winding, spanWinding); #endif - const SkPoint* firstPt = NULL; do { SkASSERT(unsortable || !current->done()); int nextStart = index; @@ -4629,24 +4921,30 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { Segment* next = current->findNextWinding(chaseArray, active, nextStart, nextEnd, winding, spanWinding, unsortable); if (!next) { - if (active && firstPt && current->verb() != SkPath::kLine_Verb && *firstPt != lastPt) { - lastPt = current->addCurveTo(index, endIndex, simple, true); - SkASSERT(*firstPt == lastPt); + if (active && simple.hasMove() + && current->verb() != SkPath::kLine_Verb + && !simple.isClosed()) { + current->addCurveTo(index, endIndex, simple, true); + SkASSERT(simple.isClosed()); } break; } - if (!firstPt) { - firstPt = ¤t->addMoveTo(index, simple, active); - } - lastPt = current->addCurveTo(index, endIndex, simple, active); + current->addCurveTo(index, endIndex, simple, active); current = next; index = nextStart; endIndex = nextEnd; - } while (*firstPt != lastPt && (active || !current->done())); - if (firstPt && active) { - #if DEBUG_PATH_CONSTRUCTION - SkDebugf("path.close();\n"); - #endif + } while (!simple.isClosed() + && ((active && !unsortable) || !current->done())); + if (active) { + if (!simple.isClosed()) { + SkASSERT(unsortable); + int min = SkMin32(index, endIndex); + if (!current->done(min)) { + current->addCurveTo(index, endIndex, simple, true); + current->markDone(SkMin32(index, endIndex), spanWinding); + } + closable = false; + } simple.close(); } current = findChase(chaseArray, index, endIndex, contourWinding); @@ -4674,41 +4972,36 @@ static bool bridgeWinding(SkTDArray<Contour*>& contourList, SkPath& simple) { active = windingIsActive(winding, spanWinding); } while (true); } while (true); - return !unsortable; + return closable; } // returns true if all edges were processed -static bool bridgeXor(SkTDArray<Contour*>& contourList, SkPath& simple) { +static bool bridgeXor(SkTDArray<Contour*>& contourList, PathWrapper& simple) { Segment* current; int start, end; bool unsortable = false; while ((current = findUndone(contourList, start, end))) { - const SkPoint* firstPt = NULL; - SkPoint lastPt; do { SkASSERT(unsortable || !current->done()); int nextStart = start; int nextEnd = end; Segment* next = current->findNextXor(nextStart, nextEnd, unsortable); if (!next) { - if (firstPt && current->verb() != SkPath::kLine_Verb && *firstPt != lastPt) { - lastPt = current->addCurveTo(start, end, simple, true); - SkASSERT(*firstPt == lastPt); + if (simple.hasMove() + && current->verb() != SkPath::kLine_Verb + && !simple.isClosed()) { + current->addCurveTo(start, end, simple, true); + SkASSERT(simple.isClosed()); } break; } - if (!firstPt) { - firstPt = ¤t->addMoveTo(start, simple, true); - } - lastPt = current->addCurveTo(start, end, simple, true); + current->addCurveTo(start, end, simple, true); current = next; start = nextStart; end = nextEnd; - } while (*firstPt != lastPt); - if (firstPt) { - #if DEBUG_PATH_CONSTRUCTION - SkDebugf("%s close\n", __FUNCTION__); - #endif + } while (!simple.isClosed()); + // FIXME: add unsortable test + if (simple.hasMove()) { simple.close(); } #if DEBUG_ACTIVE_SPANS @@ -4748,15 +5041,161 @@ static void makeContourList(SkTArray<Contour>& contours, QSort<Contour>(list.begin(), list.end() - 1); } -static void assemble(SkPath& simple) { - // TODO: find the non-closed paths and connect them together - SkASSERT(0); +static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { + return approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY); +} + + /* + check start and end of each contour + if not the same, record them + match them up + connect closest + reassemble contour pieces into new path + */ +static void assemble(const PathWrapper& path, PathWrapper& simple) { +#if DEBUG_PATH_CONSTRUCTION + SkDebugf("%s\n", __FUNCTION__); +#endif + SkTArray<Contour> contours; + EdgeBuilder builder(path, contours); + builder.finish(); + int count = contours.count(); + int oIndex; + SkTDArray<int> runs; // indices of partial contours + for (oIndex = 0; oIndex < count; ++oIndex) { + const Contour& eContour = contours[oIndex]; + const SkPoint& eStart = eContour.start(); + const SkPoint& eEnd = eContour.end(); + if (approximatelyEqual(eStart, eEnd)) { + eContour.toPath(simple); + continue; + } + *runs.append() = oIndex; + } + count = runs.count(); + SkTDArray<int> sLink, eLink; + sLink.setCount(count); + eLink.setCount(count); + int rIndex; + for (rIndex = 0; rIndex < count; ++rIndex) { + sLink[rIndex] = eLink[rIndex] = INT_MAX; + } + for (rIndex = 0; rIndex < count - 1; ++rIndex) { + oIndex = runs[rIndex]; + const Contour& oContour = contours[oIndex]; + const SkPoint& oStart = oContour.start(); + const SkPoint& oEnd = oContour.end(); + for (int inner = rIndex + 1; inner < count; ++inner) { + int iIndex = runs[inner]; + const Contour& iContour = contours[iIndex]; + const SkPoint& iStart = iContour.start(); + const SkPoint& iEnd = iContour.end(); + if (approximatelyEqual(oStart, iStart)) { + SkASSERT(sLink[rIndex] == INT_MAX); + sLink[rIndex] = ~iIndex; + SkASSERT(sLink[iIndex] == INT_MAX); + sLink[iIndex] = ~rIndex; + } else if (approximatelyEqual(oStart, iEnd)) { + SkASSERT(sLink[rIndex] == INT_MAX); + sLink[rIndex] = iIndex; + SkASSERT(eLink[iIndex] == INT_MAX); + eLink[iIndex] = rIndex; + } + if (approximatelyEqual(oEnd, iStart)) { + SkASSERT(eLink[rIndex] == INT_MAX); + eLink[rIndex] = iIndex; + SkASSERT(sLink[iIndex] == INT_MAX); + sLink[iIndex] = rIndex; + } else if (approximatelyEqual(oEnd, iEnd)) { + SkASSERT(eLink[rIndex] == INT_MAX); + eLink[rIndex] = ~iIndex; + SkASSERT(eLink[iIndex] == INT_MAX); + eLink[iIndex] = ~rIndex; + } + } + } + rIndex = 0; + bool forward = true; + bool first = true; + const SkPoint* startPtr; + int sIndex = sLink[rIndex]; + if (sIndex < 0) { + SkASSERT(sLink[~sIndex] != INT_MAX); + sLink[~sIndex] = INT_MAX; + } else { + SkASSERT(eLink[sIndex] != INT_MAX); + eLink[sIndex] = INT_MAX; + } + SkASSERT(sLink[rIndex] != INT_MAX); + sLink[rIndex] = INT_MAX; + do { + do { + oIndex = runs[rIndex]; + const Contour& contour = contours[oIndex]; + if (first) { + startPtr = &contour.start(); + first = false; + simple.deferredMove(startPtr[0]); + } + const SkPoint* endPtr; + if (forward) { + contour.toPartialForward(simple); + endPtr = &contour.end(); + } else { + contour.toPartialBackward(simple); + endPtr = &contour.start(); + } + if (approximatelyEqual(*startPtr, *endPtr)) { + simple.close(); + first = forward = true; + break; + } + int newRIndex; + if (forward) { + newRIndex = eLink[rIndex]; + SkASSERT(newRIndex != INT_MAX); + SkASSERT(eLink[rIndex] != INT_MAX); + eLink[rIndex] = INT_MAX; + if (newRIndex >= 0) { + SkASSERT(sLink[newRIndex] == rIndex); + sLink[newRIndex] = INT_MAX; + } else { + SkASSERT(eLink[~newRIndex] == ~rIndex); + eLink[~newRIndex] = INT_MAX; + } + } else { + newRIndex = sLink[rIndex]; + SkASSERT(newRIndex != INT_MAX); + SkASSERT(sLink[rIndex] != INT_MAX); + sLink[rIndex] = INT_MAX; + if (newRIndex >= 0) { + SkASSERT(eLink[newRIndex] == rIndex); + eLink[newRIndex] = INT_MAX; + } else { + SkASSERT(sLink[~newRIndex] == ~rIndex); + sLink[~newRIndex] = INT_MAX; + } + } + rIndex = newRIndex; + if (rIndex < 0) { + forward ^= 1; + rIndex = ~rIndex; + } + } while (true); + for (rIndex = 0; rIndex < count; ++rIndex) { + if (sLink[rIndex] != INT_MAX) { + break; + } + } + } while (rIndex < count); + SkASSERT(first); } -void simplifyx(const SkPath& path, SkPath& simple) { +void simplifyx(const SkPath& path, SkPath& result) { // returns 1 for evenodd, -1 for winding, regardless of inverse-ness - simple.reset(); - simple.setFillType(SkPath::kEvenOdd_FillType); + result.reset(); + result.setFillType(SkPath::kEvenOdd_FillType); + PathWrapper simple(result); // turn path into list of segments SkTArray<Contour> contours; @@ -4790,7 +5229,11 @@ void simplifyx(const SkPath& path, SkPath& simple) { ? !bridgeWinding(contourList, simple) : !bridgeXor(contourList, simple)) { // if some edges could not be resolved, assemble remaining fragments - assemble(simple); + SkPath temp; + temp.setFillType(SkPath::kEvenOdd_FillType); + PathWrapper assembled(temp); + assemble(simple, assembled); + result = *assembled.nativePath(); } } diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp index 11b083f947..0c30b2ec88 100644 --- a/experimental/Intersection/SimplifyFindTop_Test.cpp +++ b/experimental/Intersection/SimplifyFindTop_Test.cpp @@ -32,7 +32,9 @@ static const SimplifyFindTopTest::Segment* testCommon( const SimplifyFindTopTest::Segment* topSegment = topStart->findTop(index, end); #else - const SimplifyFindTopTest::Segment* topSegment = findSortableTop(contourList, index, end); + SkPoint bestXY = {SK_ScalarMin, SK_ScalarMin}; + const SimplifyFindTopTest::Segment* topSegment = + findSortableTop(contourList, index, end, bestXY); #endif return topSegment; } diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp index 667b59635e..e2f64fc45f 100644 --- a/experimental/Intersection/SimplifyNew_Test.cpp +++ b/experimental/Intersection/SimplifyNew_Test.cpp @@ -2841,12 +2841,106 @@ static void testQuadratic51() { testSimplifyx(path); } -static void (*firstTest)() = 0; +static void testQuadratic53() { + SkPath path; + path.moveTo(303.12088f, 141.299606f); + path.lineTo(330.463562f, 217.659027f); + path.lineTo(303.12088f, 141.299606f); + path.close(); + path.moveTo(371.919067f, 205.854996f); + path.lineTo(326.236786f, 205.854996f); + path.quadTo(329.104431f, 231.663818f, 351.512085f, 231.663818f); + path.lineTo(371.919067f, 205.854996f); + path.close(); + testSimplifyx(path); +} +static void testQuadratic55() { + SkPath path; +path.moveTo(303.12088f, 141.299606f); +path.lineTo(330.463562f, 217.659027f); +path.lineTo(358.606506f, 141.299606f); +path.lineTo(303.12088f, 141.299606f); +path.close(); +path.moveTo(326.236786f, 205.854996f); +path.quadTo(329.104431f, 231.663818f, 351.512085f, 231.663818f); +path.lineTo(326.236786f, 205.854996f); +path.close(); + testSimplifyx(path); +} + +static void testQuadratic56() { + SkPath path; +path.moveTo(366.608826f, 151.196014f); +path.quadTo(378.803101f, 136.674606f, 398.164948f, 136.674606f); +path.lineTo(354.009216f, 208.816208f); +path.lineTo(393.291473f, 102.232819f); +path.lineTo(359.978058f, 136.581512f); +path.quadTo(378.315979f, 136.581512f, 388.322723f, 149.613556f); +path.lineTo(364.390686f, 157.898193f); +path.quadTo(375.281769f, 136.674606f, 396.039917f, 136.674606f); +path.lineTo(350, 120); +path.lineTo(366.608826f, 151.196014f); +path.close(); + testSimplifyx(path); +} + +static void testLine80() { + SkPath path; +path.moveTo(4, 0); +path.lineTo(3, 7); +path.lineTo(7, 5); +path.lineTo(2, 2); +path.close(); +path.moveTo(0, 6); +path.lineTo(6, 12); +path.lineTo(8, 3); +path.close(); + testSimplifyx(path); +} + +static void testQuadratic58() { + SkPath path; +path.moveTo(283.714233f, 240); +path.lineTo(283.714233f, 141.299606f); +path.lineTo(303.12088f, 141.299606f); +path.lineTo(330.463562f, 217.659027f); +path.lineTo(358.606506f, 141.299606f); +path.lineTo(362.874634f, 159.705902f); +path.lineTo(335.665344f, 233.397751f); +path.lineTo(322.12738f, 233.397751f); +path.lineTo(295.718353f, 159.505829f); +path.lineTo(295.718353f, 240); +path.lineTo(283.714233f, 240); +path.close(); +path.moveTo(322.935669f, 231.030273f); +path.quadTo(312.832214f, 220.393295f, 312.832214f, 203.454178f); +path.quadTo(312.832214f, 186.981888f, 321.73526f, 176.444946f); +path.quadTo(330.638306f, 165.90802f, 344.509705f, 165.90802f); +path.quadTo(357.647522f, 165.90802f, 364.81665f, 175.244537f); +path.lineTo(371.919067f, 205.854996f); +path.lineTo(326.236786f, 205.854996f); +path.quadTo(329.104431f, 231.663818f, 351.512085f, 231.663818f); +path.lineTo(322.935669f, 231.030273f); +path.close(); +path.moveTo(326.837006f, 195.984955f); +path.lineTo(358.78125f, 195.984955f); +path.quadTo(358.78125f, 175.778046f, 343.709442f, 175.778046f); +path.quadTo(328.570923f, 175.778046f, 326.837006f, 195.984955f); +path.close(); + testSimplifyx(path); +} + +static void (*firstTest)() = testQuadratic58; static struct { void (*fun)(); const char* str; } tests[] = { + TEST(testQuadratic58), + TEST(testLine80), + TEST(testQuadratic56), + TEST(testQuadratic55), + TEST(testQuadratic53), TEST(testQuadratic51), TEST(testQuadratic38), TEST(testQuadratic37), @@ -3127,7 +3221,7 @@ static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]); static bool skipAll = false; static bool runSubTests = false; -static bool runReverse = false; +static bool runReverse = true; void SimplifyNew_Test() { if (skipAll) { diff --git a/experimental/Intersection/as.htm b/experimental/Intersection/as.htm new file mode 100644 index 0000000000..a6d2be9e26 --- /dev/null +++ b/experimental/Intersection/as.htm @@ -0,0 +1,488 @@ +<html> +<head> +<div style="height:0"> + +<div id="quad56"> +debugShowActiveSpans id=1 (366.608826,151.196014 378.803101,136.674606 398.164948,136.674606) t=0.490456543 (380.294495,140.44487) other=7 otherT=0.578520747 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=2 (398.164948,136.674606 354.009216,208.816208) t=0 (398.164948,136.674606) other=1 otherT=1 otherIndex=4 windSum=? windValue=1 +debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0 (354.009216,208.816208) other=2 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0.508945199 (374.00174,154.571106) other=6 otherT=0.598402499 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=3 (354.009216,208.816208 393.291473,102.232819) t=0.634079491 (378.917297,141.233871) other=7 otherT=0.536512741 otherIndex=1 windSum=-1 windValue=1 +debugShowActiveSpans id=5 (359.978058,136.581512 378.315979,136.581512 388.322723,149.613556) t=0.597488996 (378.917297,141.233856) other=7 otherT=0.536512973 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=6 (388.322723,149.613556 364.390686,157.898193) t=0 (388.322723,149.613556) other=5 otherT=1 otherIndex=4 windSum=? windValue=1 +debugShowActiveSpans id=6 (388.322723,149.613556 364.390686,157.898193) t=0.598402499 (374.00174,154.571106) other=3 otherT=0.508945199 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0 (364.390686,157.898193) other=6 otherT=1 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0.536512741 (378.917297,141.233871) other=3 otherT=0.634079491 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=7 (364.390686,157.898193 375.281769,136.674606 396.039917,136.674606) t=0.536512973 (378.917297,141.233856) other=5 otherT=0.597488996 otherIndex=3 windSum=-1 windValue=1 +</div> + +<div id="quad57c"> +debugShowActiveSpans id=1 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=13 otherT=0.999999913 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=1 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=13 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=2 otherT=0.154585135 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=14 (326.236786,205.854996 329.104431,231.663818 351.512085,231.663818) t=0.962138429 (349.843323,231.626816) other=15 otherT=0.0583966647 otherIndex=1 windSum=1 windValue=1 +debugShowActiveSpans id=15 (351.512085,231.663818 322.935669,231.030273) t=0 (351.512085,231.663818) other=14 otherT=1 otherIndex=3 windSum=1 windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1 +</div> + +<div id="quad57b"> +debugShowActiveSpans id=1 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=13 otherT=0.999999913 otherIndex=3 windSum=1 windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=1 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=13 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=2 otherT=0.154585135 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1 +</div> + +<div id="quad57a"> +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=13 otherT=0.812241055 otherIndex=2 windSum=-1 windValue=1 +debugShowActiveSpans id=2 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=16 otherT=0.363593784 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=4 (362.874634,159.705902 335.665344,233.397751) t=0.379109438 (352.559326,187.643173) other=17 otherT=0.412818074 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=18 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=2 otherT=0.283842806 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=16 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=4 otherT=0.492307539 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=-0 (358.78125,195.984955) other=16 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.412818074 (352.559326,187.643173) other=4 otherT=0.379109438 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=17 (358.78125,195.984955 343.709442,175.778046) t=0.902761903 (345.174988,177.74292) other=2 otherT=0.522739691 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=18 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=17 otherT=1 otherIndex=3 windSum=? windValue=1 +</div> + +<div id="quad58b"> +debugShowActiveSpans id=3 (303.12088,141.299606 330.463562,217.659027) t=0.845414865 (326.236786,205.854996) other=16 otherT=0.999999913 otherIndex=3 windSum=1 windValue=1 +debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=-0 (330.463562,217.659027) other=3 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=16 otherT=0.812241055 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=19 otherT=0.363593784 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=6 (362.874634,159.705902 335.665344,233.397751) t=0.287405665 (355.054535,180.885361) other=20 otherT=0.497256785 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=16 (371.919067,205.854996 326.236786,205.854996) t=0.812241055 (334.814056,205.854996) other=4 otherT=0.154585135 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=21 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=4 otherT=0.283842806 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=6 otherT=0.492307539 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0 (358.78125,195.984955) other=19 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.497256785 (355.054535,180.885361) other=6 otherT=0.287405665 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.925970638 (345.858368,175.888794) other=4 otherT=0.547021444 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=21 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=20 otherT=1 otherIndex=3 windSum=? windValue=1 +</div> + +<div id="quad58a"> +debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.154585135 (334.814056,205.854996) other=16 otherT=0.812241055 otherIndex=2 windSum=-1 windValue=1 +debugShowActiveSpans id=4 (330.463562,217.659027 358.606506,141.299606) t=0.283842806 (338.451721,195.984955) other=19 otherT=0.363593784 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=6 (362.874634,159.705902 335.665344,233.397751) t=0.287405665 (355.054535,180.885361) other=20 otherT=0.497256785 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0 (326.837006,195.984955) other=21 otherT=1 otherIndex=1 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.363593784 (338.451721,195.984955) other=4 otherT=0.283842806 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=19 (326.837006,195.984955 358.78125,195.984955) t=0.708806554 (349.479309,195.984955) other=6 otherT=0.492307539 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0 (358.78125,195.984955) other=19 otherT=1 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.497256785 (355.054535,180.885361) other=6 otherT=0.287405665 otherIndex=2 windSum=? windValue=1 +debugShowActiveSpans id=20 (358.78125,195.984955 358.78125,175.778046 343.709442,175.778046) t=0.925970638 (345.858368,175.888794) other=4 otherT=0.547021444 otherIndex=3 windSum=? windValue=1 +debugShowActiveSpans id=21 (343.709442,175.778046 328.570923,175.778046 326.837006,195.984955) t=0 (343.709442,175.778046) other=20 otherT=1 otherIndex=3 windSum=? windValue=1 +</div> + +</div> + +<script type="text/javascript"> + +var testDivs = [ + quad58b, + quad58a, + quad57c, + quad57b, + quad57a, + quad56, +]; + +var decimal_places = 3; // make this 3 to show more precision + +var tests = []; +var testTitles = []; +var testIndex = 0; +var ctx; + +var xmin; +var ymin; +var scale; +var mouseX, mouseY; +var srcLeft, srcTop; +var srcWidth, srcHeight; +var screenWidth, screenHeight; +var drawnPts; + +var ptLabels = true; +var digit_mode = false; +var index_mode = true; +var index_bits = -1; +var debug_xy = false; +var info_mode = false; +var intersect_mode = false; +var sequence = -1; + +var SPAN_ID = 1; +var SPAN_X1 = 2; +var SPAN_Y1 = 3; +var SPAN_X2 = 4; +var SPAN_Y2 = 5; +var SPAN_L_T = 6; +var SPAN_L_TX = 7; +var SPAN_L_TY = 8; +var SPAN_L_OTHER = 9; +var SPAN_L_OTHERT = 10; +var SPAN_L_OTHERI = 11; +var SPAN_L_SUM = 12; +var SPAN_L_VAL = 13; + +var SPAN_X3 = 6; +var SPAN_Y3 = 7; +var SPAN_Q_T = 8; +var SPAN_Q_TX = 9; +var SPAN_Q_TY = 10; +var SPAN_Q_OTHER = 11; +var SPAN_Q_OTHERT = 12; +var SPAN_Q_OTHERI = 13; +var SPAN_Q_SUM = 14; +var SPAN_Q_VAL = 15; + +var Q_LENGTH = 18; + +function strs_to_nums(strs) { + var result = []; + for (var idx in strs) { + var str = strs[idx]; + var num = parseFloat(str); + if (isNaN(num)) { + result.push(str); + } else { + result.push(num); + } + } + return result; +} + +function parse_debugShowActiveSpans(test, title) { + var re_quad = / id=(\d+) \((\d+\.?\d*),(\d+\.?\d*) (\d+\.?\d*),(\d+\.?\d*) (\d+\.?\d*),(\d+\.?\d*)\) t=(\d+\.?\d*) \((\d+\.?\d*),(\d+\.?\d*)\) other=(\d+) otherT=(\d+\.?\d*) otherIndex=(\d+) windSum=(\?|-?\d+) windValue=(\d+)/; + var re_line = / id=(\d+) \((\d+\.?\d*),(\d+\.?\d*) (\d+\.?\d*),(\d+\.?\d*)\) t=(\d+\.?\d*) \((\d+\.?\d*),(\d+\.?\d*)\) other=(\d+) otherT=(\d+\.?\d*) otherIndex=(\d+) windSum=(\?|-?\d+) windValue=(\d+)/; + + var strs = test.split("debugShowActiveSpans"); + if (strs.length == 1) + return; + var spans = []; + for (var s in strs) { + var str = strs[s]; + if (str == "\n") { + continue; + } + if (re_line.test(str)) { + var lineStrs = re_line.exec(str); + var line = strs_to_nums(lineStrs); + spans.push(line); + } else if (re_quad.test(str)) { + var quadStrs = re_quad.exec(str); + var quad = strs_to_nums(quadStrs); + spans.push(quad); + } + } + if (spans.length >= 1) { + tests.push(spans); + testTitles.push(title); + } +} + +function init(test) { + var canvas = document.getElementById('canvas'); + if (!canvas.getContext) return; + screenWidth = canvas.width = window.innerWidth - 20; + screenHeight = canvas.height = window.innerHeight - 20; + ctx = canvas.getContext('2d'); + xmin = Infinity; + var xmax = -Infinity; + ymin = Infinity; + var ymax = -Infinity; + for (var scans in test) { + var scan = test[scans]; + var last = scan.length >= Q_LENGTH ? SPAN_X3 : SPAN_X2; + for (var idx = SPAN_X1; idx <= last; idx += 2) { + xmin = Math.min(xmin, scan[idx]); + xmax = Math.max(xmax, scan[idx]); + ymin = Math.min(ymin, scan[idx + 1]); + ymax = Math.max(ymax, scan[idx + 1]); + } + } + srcWidth = xmax - xmin; + srcHeight = ymax - ymin; + var hscale = ctx.canvas.width / srcWidth; + var vscale = ctx.canvas.height / srcHeight; + var minScale = Math.min(hscale, vscale); + scale = minScale; + srcLeft = xmin; + srcTop = ymin; +} + +function drawPoint(px, py) { + for (var pts = 0; pts < drawnPts.length; pts += 2) { + var x = drawnPts[pts]; + var y = drawnPts[pts + 1]; + if (px == x && py == y) { + return; + } + } + drawnPts.push(px); + drawnPts.push(py); + var label = px.toFixed(decimal_places) + ", " + py.toFixed(decimal_places); + var _px = (px - srcLeft)* scale; + var _py = (py - srcTop) * scale; + ctx.beginPath(); + ctx.arc(_px, _py, 3, 0, Math.PI*2, true); + ctx.closePath(); + ctx.fill(); + ctx.fillText(label, _px + 5, _py); +} + +function draw(test, title) { + ctx.fillStyle = "rgba(0,0,0, 0.1)"; + ctx.font = "normal 50px Arial"; + ctx.fillText(title, 50, 50); + ctx.font = "normal 10px Arial"; + ctx.lineWidth = "1.001"; "0.999"; + var id = -1; + var firstIdx; + var lastIdx; + var index_tst = -1; + drawnPts = []; + for (var scansStr in test) { + var scans = parseInt(scansStr); + var scan = test[scans]; + var isQuad = scan.length >= Q_LENGTH; + if (id != scan[SPAN_ID]) { + id = scan[SPAN_ID]; + firstIdx = lastIdx = scans; + ++index_tst; + var nextIdx = lastIdx + 1; + while (nextIdx < test.length && test[nextIdx][SPAN_ID] == id) { + lastIdx = nextIdx++; + } + } + var seq = sequence % test.length; + var selected = sequence >= 0 ? seq == scans + : (index_bits & (1 << index_tst)) != 0 && scans == firstIdx; + var skippable = (sequence >= 0 && seq >= firstIdx && seq <= lastIdx) + || scans != firstIdx; + if (skippable && !selected) { + continue; + } + ctx.strokeStyle = selected ? "red" : "rgba(0,0,0, 0.2)"; + ctx.beginPath(); + ctx.moveTo((scan[SPAN_X1] - srcLeft)* scale, + (scan[SPAN_Y1] - srcTop) * scale); + if (isQuad) { + ctx.quadraticCurveTo((scan[SPAN_X2] - srcLeft) * scale, + (scan[SPAN_Y2] - srcTop) * scale, + (scan[SPAN_X3] - srcLeft) * scale, + (scan[SPAN_Y3] - srcTop) * scale); + } else { + ctx.lineTo((scan[SPAN_X2] - srcLeft)* scale, + (scan[SPAN_Y2] - srcTop) * scale); + } + ctx.stroke(); + if (debug_xy && selected) { + var debugText = ""; + for (var idx = SPAN_X1; idx <= (isQuad ? SPAN_X3 : SPAN_X2); idx += 2) { + var screenX = (scan[idx] - srcLeft) * scale; + var screenY = (scan[idx + 1] - srcTop) * scale; + debugText += screenX.toFixed(decimal_places) + ", "; + debugText += screenY.toFixed(decimal_places) + " "; + } + ctx.fillStyle="blue"; + ctx.fillText(debugText, 50, scans * 50 + 100); + } + if (ptLabels && selected) { + ctx.fillStyle="blue"; + drawPoint(scan[SPAN_X1], scan[SPAN_Y1]); + drawPoint(scan[SPAN_X2], scan[SPAN_Y2]); + if (scan.length >= Q_LENGTH) { + drawPoint(scan[SPAN_X3], scan[SPAN_Y3]); + } + } + if (info_mode && selected) { + var infoText = "id=" + scan[SPAN_ID]; + ctx.fillStyle="green"; + ctx.fillText(infoText, 10, scans * 50 + 100); + } + if (intersect_mode && selected) { + ctx.fillStyle="rgba(50,100,200, 1.0)"; + if (isQuad) { + drawPoint(scan[SPAN_Q_TX], scan[SPAN_Q_TY]); + } else { + drawPoint(scan[SPAN_L_TX], scan[SPAN_L_TY]); + } + } + } +} + +function drawTop() { + init(tests[testIndex]); + redraw(); +} + +function redraw() { + ctx.beginPath(); + ctx.rect(0, 0, ctx.canvas.width, ctx.canvas.height); + ctx.fillStyle="white"; + ctx.fill(); + draw(tests[testIndex], testTitles[testIndex]); +} + +function doKeyPress(evt) { + var char = String.fromCharCode(evt.charCode); + switch (char) { + case '0': + case '1': + case '2': + case '3': + case '4': + case '5': + case '6': + case '7': + case '8': + case '9': + if (digit_mode) { + decimal_places = char - '0'; + } else if (index_mode) { + index_bits ^= 1 << (char - '0'); + } + redraw(); + break; + case 'd': + digit_mode = true; + index_mode = false; + break; + case 'f': + info_mode ^= true; + redraw(); + break; + case 'i': + digit_mode = false; + if (sequence >= 0) { + sequence = -1; + index_mode = false; + } else { + index_mode ^= true; + } + if (index_mode) { + index_bits = 0; + } else { + index_bits = -1; + } + redraw(); + break; + case 'N': + testIndex += 9; + case 'n': + if (++testIndex >= tests.length) + testIndex = 0; + drawTop(); + break; + case 'P': + testIndex -= 9; + case 'p': + if (--testIndex < 0) + testIndex = tests.length - 1; + drawTop(); + break; + case 's': + sequence++; + drawTop(); + break; + case 't': + intersect_mode ^= true; + redraw(); + break; + case 'x': + ptLabels ^= true; + redraw(); + break; + case 'y': + debug_xy ^= true; + redraw(); + break; + case '-': + scale /= 2; + calcLeftTop(); + redraw(); + break; + case '=': + case '+': + scale *= 2; + calcLeftTop(); + redraw(); + break; + } +} + +function calcXY() { + var e = window.event; + var tgt = e.target || e.srcElement; + var left = tgt.offsetLeft; + var top = tgt.offsetTop; + var unit = scale; + mouseX = (e.clientX - left) / scale + srcLeft; + mouseY = (e.clientY - top) / scale + srcTop; +} + +function calcLeftTop() { + srcLeft = mouseX - screenWidth / 2 / scale; + srcTop = mouseY - screenHeight / 2 / scale; +} + +function handleMouseClick() { + calcXY(); + calcLeftTop(); + redraw(); +} + +function handleMouseOver() { + calcXY(); + var num = mouseX.toFixed(decimal_places) + ", " + mouseY.toFixed(decimal_places); + ctx.beginPath(); + ctx.rect(300,100,200,10); + ctx.fillStyle="white"; + ctx.fill(); + ctx.fillStyle="black"; + ctx.fillText(num, 300, 108); +} + +function start() { + for (i = 0; i < testDivs.length; ++i) { + var title = testDivs[i].id.toString(); + var str = testDivs[i].firstChild.data; + parse_debugShowActiveSpans(str, title); + } + drawTop(); + window.addEventListener('keypress', doKeyPress, true); + window.onresize = function() { + drawTop(); + } +} + +</script> +</head> + +<body onLoad="start();"> +<canvas id="canvas" width="750" height="500" + onmousemove="handleMouseOver()" + onclick="handleMouseClick()" + ></canvas > +</body> +</html> diff --git a/experimental/Intersection/bc.htm b/experimental/Intersection/bc.htm index 15601def03..fc9191a694 100644 --- a/experimental/Intersection/bc.htm +++ b/experimental/Intersection/bc.htm @@ -58,7 +58,7 @@ bezier_clip q1=(0.475846194,0.304363878 0.53317904,0.507883959 0.454423387,0.847 bezier_clip q1=(0.493290691,0.311274036 0.486581381,0.343588381 0.473162762,0.379257381) q2=(0.475846194,0.304363878 0.53317904,0.507883959 0.454423387,0.847492538) minT=0.0828748517 maxT=0.150086861 </div> -<div id="quad21g"> +<div id="quad21g"> (gdb) p smaller $1 = {{ x = 0.48441440743366754, @@ -129,12 +129,13 @@ $4 = {{fX = 406.232788, fY = 121.260353}, {fX = 409.441956, fY = 121.260353}, {f <script type="text/javascript"> var testDivs = [ + quad56, quad39, quad38, quad37, quad36, quad21g, - quad21a, + quad21a, quad21b, quad21c, quad21d, diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm index 7973755cdd..63581bc5e5 100644 --- a/experimental/Intersection/op.htm +++ b/experimental/Intersection/op.htm @@ -2473,11 +2473,341 @@ path.lineTo(383.340973,136.608322); path.close(); </div> +<div id="testQuadratic52sa"> +path.moveTo(331.585693, 138.050415); +path.quadTo(345.867188,121.147957, 368.11853,121.147957); +path.quadTo(378.797424,121.147957, 387.017914,124.993469); +path.quadTo(391.577667,123.030998, 396.645874,122.098694); +path.quadTo(401.232697,121.254936, 406.235992,121.254936); +path.close(); +</div> + +<div id="testQuadratic52sb"> +path.moveTo(383.340973, 136.608322); +path.lineTo(369.863983,145.645813); +path.quadTo(372.378204,140.746292, 375.350006,136.830978); +path.lineTo(372.197113,136.918823); +path.lineTo(369.970581,137.94342); +path.quadTo(370.390961,137.442825, 370.818756,136.95723); +path.lineTo(331.585693,138.050415); +path.quadTo(345.867188,121.147957, 368.11853,121.147957); +path.quadTo(378.797424,121.147957, 387.017914,124.993469); +path.quadTo(391.577667,123.030998, 396.645874,122.098694); +path.quadTo(401.232697,121.254936, 406.235992,121.254936); +path.close(); +</div> + +<div id="testQuadratic52sc"> +path.moveTo(383.340973, 136.608322); +path.lineTo(391.380798,136.384293); +path.lineTo(400.693176,136.124817); +path.quadTo(397.721985,132.255341, 394.111664,129.385605); +path.lineTo(406.236359,121.254936); +path.quadTo(406.236176,121.254936, 406.235992,121.254936); +path.lineTo(406.235992,121.254936); +path.quadTo(401.232697,121.254936, 396.645874,122.098694); +path.quadTo(391.577667,123.030998, 387.017914,124.993469); +path.quadTo(378.797424,121.147957, 368.11853,121.147957); +path.quadTo(345.867188,121.147957, 331.585693,138.050415); +path.lineTo(370.818756,136.95723); +path.quadTo(370.390961,137.442825, 369.970581,137.94342); +path.lineTo(372.197113,136.918823); +path.lineTo(375.350006,136.830978); +path.quadTo(372.378204,140.746292, 369.863983,145.645813); +path.lineTo(383.340973,136.608322); +path.close(); +</div> + +<div id="testQuadratic53o"> +path.moveTo(303.12088, 141.299606); +path.lineTo(330.463562, 217.659027); +path.lineTo(303.12088, 141.299606); +path.close(); +path.moveTo(371.919067, 205.854996); +path.lineTo(326.236786, 205.854996); +path.quadTo(329.104431, 231.663818, 351.512085, 231.663818); +path.lineTo(371.919067, 205.854996); +path.close(); +</div> + +<div id="testQuadratic53s"> +path.moveTo(326.236786,205.854996); +path.lineTo(326.236786,205.854996); +path.close(); +path.moveTo(371.919067,205.854996); +path.lineTo(326.236786,205.854996); +</div> + +<div id="testQuadratic54"> +path.moveTo(303.12088, 141.299606); +path.lineTo(330.463562, 217.659027); +path.lineTo(358.606506, 141.299606); +path.lineTo(303.12088, 141.299606); +path.close(); +path.moveTo(371.919067, 205.854996); +path.lineTo(326.236786, 205.854996); +path.quadTo(329.104431, 231.663818, 351.512085, 231.663818); +path.lineTo(371.919067, 205.854996); +path.close(); +</div> + +<div id="testQuadratic55o"> +path.moveTo(303.12088, 141.299606); +path.lineTo(330.463562, 217.659027); +path.lineTo(358.606506, 141.299606); +path.lineTo(303.12088, 141.299606); +path.close(); +path.moveTo(326.236786, 205.854996); +path.quadTo(329.104431, 231.663818, 351.512085, 231.663818); +path.lineTo(326.236786, 205.854996); +path.close(); +</div> + +<div id="testQuadratic55s"> +path.moveTo(326.236786,205.854996); +path.lineTo(303.12088,141.299606); +path.lineTo(358.606506,141.299606); +path.lineTo(332.468719,212.218475); +path.lineTo(351.512085,231.663818); +path.quadTo(329.104431,231.663818, 326.236786,205.854996); +path.close(); +</div> + +<div id="testQuadratic56o"> +path.moveTo(366.608826, 151.196014); +path.quadTo(378.803101, 136.674606, 398.164948, 136.674606); +path.lineTo(354.009216, 208.816208); +path.lineTo(393.291473, 102.232819); +path.lineTo(359.978058, 136.581512); +path.quadTo(378.315979, 136.581512, 388.322723, 149.613556); +path.lineTo(364.390686, 157.898193); +path.quadTo(375.281769, 136.674606, 396.039917, 136.674606); +path.lineTo(350, 120); +path.lineTo(366.608826, 151.196014); +path.close(); +</div> + +<div id="testQuadratic56s"> +path.moveTo(369.285553,126.984779); +path.lineTo(393.291473,102.232819); +path.lineTo(382.416199,131.740402); +path.lineTo(396.039917,136.674606); +path.quadTo(387.290802,136.674606, 380.294495,140.44487); +path.quadTo(379.623352,140.760971, 378.965302,141.103577); +path.lineTo(378.917297,141.233856); +path.quadTo(378.86972,141.206131, 378.822021,141.178574); +path.quadTo(372.011871,144.761871, 366.608826,151.196014); +path.lineTo(350,120); +path.lineTo(369.285553,126.984779); +path.close(); +path.moveTo(378.917297,141.233871); +path.lineTo(378.917297,141.233856); +path.quadTo(378.86972,141.206131, 378.822021,141.178574); +path.quadTo(372.011871,144.761871, 366.608826,151.196014); +</div> + +<div id="testQuadratic57o"> +path.moveTo(303.12088, 141.299606); +path.lineTo(330.463562, 217.659027); +path.lineTo(358.606506, 141.299606); +path.lineTo(362.874634, 159.705902); +path.lineTo(335.665344, 233.397751); +path.lineTo(322.12738, 233.397751); +path.lineTo(295.718353, 159.505829); +path.lineTo(295.718353, 240); +path.lineTo(303.12088, 141.299606); +path.close(); +path.moveTo(322.935669, 231.030273); +path.quadTo(312.832214, 220.393295, 312.832214, 203.454178); +path.quadTo(312.832214, 186.981888, 321.73526, 176.444946); +path.quadTo(330.638306, 165.90802, 344.509705, 165.90802); +path.lineTo(371.919067, 205.854996); +path.lineTo(326.236786, 205.854996); +path.quadTo(329.104431, 231.663818, 351.512085, 231.663818); +path.lineTo(322.935669, 231.030273); +path.close(); +path.moveTo(326.837006, 195.984955); +path.lineTo(358.78125, 195.984955); +path.lineTo(343.709442, 175.778046); +path.quadTo(328.570923, 175.778046, 326.837006, 195.984955); +path.close(); +</div> + +<div id="testQuadratic57s"> +path.moveTo(300.708282,173.46756); +path.lineTo(303.12088,141.299606); +path.lineTo(317.770294,182.210785); +path.quadTo(319.462738,179.134506, 321.73526,176.444946); +path.quadTo(330.638306,165.90802, 344.509705,165.90802); +path.lineTo(347.780151,170.674438); +path.lineTo(358.606506,141.299606); +path.lineTo(362.874634,159.705902); +path.lineTo(354.960693,181.139511); +path.lineTo(371.919067,205.854996); +path.lineTo(345.834961,205.854996); +path.lineTo(337.609253,228.13298); +path.quadTo(342.649323,231.302383, 349.843323,231.626816); +path.lineTo(336.429047,231.329422); +path.lineTo(335.665344,233.397751); +path.lineTo(322.12738,233.397751); +path.lineTo(320.050781,227.587433); +path.quadTo(313.982483,219.336182, 313.015503,207.902908); +path.lineTo(300.708282,173.46756); +path.close(); +path.moveTo(300.708282,173.46756); +path.lineTo(295.718353,240); +path.lineTo(295.718353,159.505829); +path.lineTo(300.708282,173.46756); +path.close(); +path.moveTo(349.843323,231.626816); +path.lineTo(351.512085,231.663818); +path.quadTo(350.663696,231.663818, 349.843323,231.626816); +path.close(); +path.moveTo(326.236786,205.854996); +path.lineTo(330.463562,217.659027); +path.lineTo(334.814056,205.854996); +path.lineTo(326.236786,205.854996); +path.close(); +path.moveTo(334.814056,205.854996); +path.lineTo(338.451721,195.984955); +path.lineTo(349.479309,195.984955); +path.lineTo(352.559326,187.643173); +path.lineTo(358.78125,195.984955); +</div> + +<div id="testQuadratic58o"> +path.moveTo(283.714233, 240); +path.lineTo(283.714233, 141.299606); +path.lineTo(303.12088, 141.299606); +path.lineTo(330.463562, 217.659027); +path.lineTo(358.606506, 141.299606); +path.lineTo(362.874634, 159.705902); +path.lineTo(335.665344, 233.397751); +path.lineTo(322.12738, 233.397751); +path.lineTo(295.718353, 159.505829); +path.lineTo(295.718353, 240); +path.lineTo(283.714233, 240); +path.close(); +path.moveTo(322.935669, 231.030273); +path.quadTo(312.832214, 220.393295, 312.832214, 203.454178); +path.quadTo(312.832214, 186.981888, 321.73526, 176.444946); +path.quadTo(330.638306, 165.90802, 344.509705, 165.90802); +path.quadTo(357.647522, 165.90802, 364.81665, 175.244537); +path.lineTo(371.919067, 205.854996); +path.lineTo(326.236786, 205.854996); +path.quadTo(329.104431, 231.663818, 351.512085, 231.663818); +path.lineTo(322.935669, 231.030273); +path.close(); +path.moveTo(326.837006, 195.984955); +path.lineTo(358.78125, 195.984955); +path.quadTo(358.78125, 175.778046, 343.709442, 175.778046); +path.quadTo(328.570923, 175.778046, 326.837006, 195.984955); +path.close(); +</div> + +<div id="testQuadratic58s"> +path.moveTo(283.714233,240); +path.lineTo(283.714233,141.299606); +path.lineTo(303.12088,141.299606); +path.lineTo(317.770294,182.210785); +path.quadTo(319.462738,179.134506, 321.73526,176.444946); +path.quadTo(330.638306,165.90802, 344.509705,165.90802); +path.quadTo(347.07132,165.90802, 349.406036,166.26297); +path.lineTo(358.606506,141.299606); +path.lineTo(362.874634,159.705902); +path.lineTo(359.116211,169.884979); +path.quadTo(362.326477,172.001541, 364.81665,175.244537); +path.lineTo(371.919067,205.854996); +path.lineTo(345.834961,205.854996); +path.lineTo(337.609253,228.13298); +path.quadTo(342.649323,231.302383, 349.843323,231.626816); +path.lineTo(336.429047,231.329422); +path.lineTo(335.665344,233.397751); +path.lineTo(322.12738,233.397751); +path.lineTo(320.050781,227.587433); +path.quadTo(313.982483,219.336182, 313.015503,207.902908); +path.lineTo(295.718353,159.505829); +path.lineTo(295.718353,240); +path.lineTo(283.714233,240); +path.close(); +path.moveTo(349.843323,231.626816); +path.lineTo(351.512085,231.663818); +path.quadTo(350.663696,231.663818, 349.843323,231.626816); +path.close(); +path.moveTo(326.236786,205.854996); +path.lineTo(330.463562,217.659027); +path.lineTo(334.814056,205.854996); +path.lineTo(326.236786,205.854996); +path.close(); +path.moveTo(334.814056,205.854996); +path.lineTo(338.451721,195.984955); +path.lineTo(349.479309,195.984955); +path.lineTo(355.054535,180.885361); +path.quadTo(358.78125,185.936935, 358.78125,195.984955); +</div> + +<div id="testQuadratic58a"> +path.moveTo(283.714233,240); +path.lineTo(283.714233,141.299606); +path.lineTo(303.12088,141.299606); +path.lineTo(317.770294,182.210785); +path.quadTo(319.462738,179.134506, 321.73526,176.444946); +path.quadTo(330.638306,165.90802, 344.509705,165.90802); +path.quadTo(347.07132,165.90802, 349.406036,166.26297); +path.lineTo(358.606506,141.299606); +path.lineTo(362.874634,159.705902); +path.lineTo(359.116211,169.884979); +path.quadTo(362.326477,172.001541, 364.81665,175.244537); +path.lineTo(371.919067,205.854996); +path.lineTo(345.834961,205.854996); +path.lineTo(337.609253,228.13298); +path.quadTo(342.649323,231.302383, 349.843323,231.626816); +path.lineTo(336.429047,231.329422); +path.lineTo(335.665344,233.397751); +path.lineTo(322.12738,233.397751); +path.lineTo(320.050781,227.587433); +path.quadTo(313.982483,219.336182, 313.015503,207.902908); +path.lineTo(295.718353,159.505829); +path.lineTo(295.718353,240); +path.lineTo(283.714233,240); +path.close(); +path.moveTo(349.843323,231.626816); +path.lineTo(351.512085,231.663818); +path.quadTo(350.663696,231.663818, 349.843323,231.626816); +path.close(); +path.moveTo(349.479309,195.984955); +path.lineTo(358.78125,195.984955); +path.quadTo(358.78125,185.936935, 355.054535,180.885361); +path.lineTo(349.479309,195.984955); +path.close(); +path.moveTo(345.858368,175.888794); +path.lineTo(338.451721,195.984955); +path.lineTo(326.837006,195.984955); +path.quadTo(328.570923,175.778046, 343.709442,175.778046); +path.quadTo(344.825195,175.778046, 345.858368,175.888794); +path.close(); +</div> + </div> <script type="text/javascript"> var testDivs = [ + testQuadratic58o, + testQuadratic58a, + testQuadratic58s, + testQuadratic57o, + testQuadratic57s, + testQuadratic56o, + testQuadratic56s, + testQuadratic55o, + testQuadratic55s, + testQuadratic54, + testQuadratic53o, + testQuadratic53s, + testQuadratic52sa, + testQuadratic52sb, + testQuadratic52sc, testQuadratic52o, testQuadratic52s, testQuadratic51, |