aboutsummaryrefslogtreecommitdiffhomepage
path: root/experimental
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-10-26 21:03:50 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-10-26 21:03:50 +0000
commitf839c0359c308fd06895d9f73fc12c4f3869e399 (patch)
tree0c5821437bb8d2eefc6a2e7f9c476b1b865f783f /experimental
parent0c5f3762e863411798b1d6c55157d24c69d5bc25 (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.cpp55
-rw-r--r--experimental/Intersection/EdgeDemoApp.mm2
-rw-r--r--experimental/Intersection/MiniSimplify_Test.cpp8
-rw-r--r--experimental/Intersection/ShapeOps.cpp32
-rw-r--r--experimental/Intersection/Simplify.cpp751
-rw-r--r--experimental/Intersection/SimplifyFindTop_Test.cpp4
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp98
-rw-r--r--experimental/Intersection/as.htm488
-rw-r--r--experimental/Intersection/bc.htm5
-rw-r--r--experimental/Intersection/op.htm330
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 = &current->addMoveTo(index, simple, active);
- }
- lastPt = current->addCurveTo(index, endIndex, simple, active);
+ // if (!firstPt) {
+ // firstPt = &current->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() = &angle;
+ 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 = &current->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 = &current->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,