checkpoint for shape ops
at minimum, the unit tests in SimplyNew_Test pass
git-svn-id: http://skia.googlecode.com/svn/trunk@5860 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index c87beb0..6c2ac53 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -82,6 +82,7 @@
if (approximately_zero(x - y)) {
return true;
}
+ // FIXME: since no other function uses ULPS, this one shouldn't either
return AlmostEqualUlps((float) x, (float) y, UlpsEpsilon);
}
diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp
index 33aae21..14ede5b 100644
--- a/experimental/Intersection/EdgeDemo.cpp
+++ b/experimental/Intersection/EdgeDemo.cpp
@@ -4,6 +4,35 @@
#import "SkCanvas.h"
#import "SkPaint.h"
+extern void showPath(const SkPath& path, const char* str);
+
+static bool drawPaths(SkCanvas* canvas, const SkPath& path, bool useOld)
+{
+ SkPath out;
+#define SHOW_PATH 0
+#if SHOW_PATH
+ showPath(path, "original:");
+#endif
+ if (useOld) {
+ simplify(path, true, out);
+ } else {
+ simplifyx(path, out);
+ }
+#if SHOW_PATH
+ showPath(out, "simplified:");
+#endif
+ SkPaint paint;
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ // paint.setStrokeWidth(6);
+ // paint.setColor(0x1F003f7f);
+ // canvas->drawPath(path, paint);
+ paint.setColor(0xFF305F00);
+ paint.setStrokeWidth(1);
+ canvas->drawPath(out, paint);
+ return true;
+}
+
// Three circles bounce inside a rectangle. The circles describe three, four
// or five points which in turn describe a polygon. The polygon points
// bounce inside the circles. The circles rotate and scale over time. The
@@ -26,7 +55,7 @@
pts[c * 8 + p * 2 + 1] = abs(110 - ((step + c * 223 + p * 17) % 230));
}
}
- SkPath path, out;
+ SkPath path;
for (c = 0; c < circles; ++c) {
for (p = 0; p < 4; ++p) {
SkScalar x = pts[c * 8 + p * 2];
@@ -49,23 +78,7 @@
}
path.close();
}
- showPath(path, "original:");
- if (useOld) {
- simplify(path, true, out);
- } else {
- simplifyx(path, out);
- }
- showPath(out, "simplified:");
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setStyle(SkPaint::kStroke_Style);
- paint.setStrokeWidth(3);
- paint.setColor(0x3F007fbF);
- canvas->drawPath(path, paint);
- paint.setColor(0xFF60FF00);
- paint.setStrokeWidth(1);
- canvas->drawPath(out, paint);
- return true;
+ return drawPaths(canvas, path, useOld);
}
static void createStar(SkPath& path, SkScalar innerRadius, SkScalar outerRadius,
@@ -89,7 +102,7 @@
static bool drawStars(SkCanvas* canvas, int step, bool useOld)
{
- SkPath path, out;
+ SkPath path;
const int stars = 25;
int pts[stars];
// static bool initialize = true;
@@ -134,43 +147,171 @@
createStar(path, innerRadius[s] / 4.0f, outerRadius[s] / 4.0f,
angles[s], pts[s], locs[s]);
}
-#define SHOW_PATH 0
-#if SHOW_PATH
- showPath(path, "original:");
-#endif
-#define TEST_SIMPLIFY 01
-#if TEST_SIMPLIFY
- if (useOld) {
- simplify(path, true, out);
+ return drawPaths(canvas, path, useOld);
+}
+
+static void tryRoncoOnce(const SkPath& path, const SkRect& target, bool show) {
+ // capture everything in a desired rectangle
+ SkPath tiny;
+ bool closed = true;
+ SkPath::Iter iter(path, false);
+ SkPoint pts[4];
+ SkPath::Verb verb;
+ int count = 0;
+ SkPoint lastPt;
+ while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ count = 0;
+ break;
+ case SkPath::kLine_Verb:
+ count = 1;
+ break;
+ case SkPath::kQuad_Verb:
+ count = 2;
+ break;
+ case SkPath::kCubic_Verb:
+ count = 3;
+ break;
+ case SkPath::kClose_Verb:
+ if (!closed) {
+ tiny.close();
+ closed = true;
+ }
+ count = 0;
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ }
+ if (!count) {
+ continue;
+ }
+ SkRect bounds;
+ bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
+ for (int i = 1; i <= count; ++i) {
+ bounds.growToInclude(pts[i].fX + 0.1f, pts[i].fY + 0.1f);
+ }
+ if (!SkRect::Intersects(target, bounds)) {
+ continue;
+ }
+ if (closed) {
+ tiny.moveTo(pts[0].fX, pts[0].fY);
+ closed = false;
+ } else if (pts[0] != lastPt) {
+ tiny.lineTo(pts[0].fX, pts[0].fY);
+ }
+ switch (verb) {
+ case SkPath::kLine_Verb:
+ tiny.lineTo(pts[1].fX, pts[1].fY);
+ lastPt = pts[1];
+ break;
+ case SkPath::kQuad_Verb:
+ tiny.quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
+ lastPt = pts[2];
+ break;
+ case SkPath::kCubic_Verb:
+ tiny.cubicTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
+ lastPt = pts[3];
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ }
+ }
+ if (!closed) {
+ tiny.close();
+ }
+ if (show) {
+ showPath(tiny, NULL);
+ SkDebugf("simplified:\n");
+ }
+ SkPath out;
+ simplifyx(tiny, out);
+}
+
+static void tryRonco(const SkPath& path) {
+ const SkRect& overall = path.getBounds();
+ const int divs = 50;
+ SkScalar cellWidth = overall.width() / divs * 2;
+ SkScalar cellHeight = overall.height() / divs * 2;
+ SkRect target;
+ if (true) {
+ int xDiv = 21;
+ int yDiv = 9;
+ 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) {
+ target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs,
+ overall.fTop + (overall.height() - cellHeight) * yDiv / divs,
+ cellWidth, cellHeight);
+ tryRoncoOnce(path, target, false);
+ }
+ }
+ }
+}
+
+static bool drawLetters(SkCanvas* canvas, int step, bool useOld)
+{
+ SkPath path;
+ const int width = 640;
+ const int height = 480;
+ const char testStr[] = "Merge";
+ const int testStrLen = sizeof(testStr) - 1;
+ SkPoint textPos[testStrLen];
+ SkScalar widths[testStrLen];
+ SkPaint paint;
+ paint.setTextSize(40);
+ paint.setAntiAlias(true);
+ paint.getTextWidths(testStr, testStrLen, widths, NULL);
+ SkScalar running = 0;
+ for (int x = 0; x < testStrLen; ++x) {
+ SkScalar width = widths[x];
+ widths[x] = running;
+ running += width;
+ }
+ SkScalar bias = (width - widths[testStrLen - 1]) / 2;
+ for (int x = 0; x < testStrLen; ++x) {
+ textPos[x].fX = bias + widths[x];
+ textPos[x].fY = height / 2;
+ }
+ paint.setTextSize(40 + step / 100.0f);
+#if 0
+ for (int mask = 0; mask < 1 << testStrLen; ++mask) {
+ char maskStr[testStrLen];
+ // mask = 26;
+ for (int letter = 0; letter < testStrLen; ++letter) {
+ maskStr[letter] = mask & (1 << letter) ? testStr[letter] : ' ';
+ }
+ paint.getPosTextPath(maskStr, testStrLen, textPos, &path);
+ showPath(path, NULL);
+ SkDebugf("%d simplified:\n", mask);
+ SkPath out;
simplifyx(path, out);
}
#endif
-#if SHOW_PATH
- showPath(out, "simplified:");
+ paint.getPosTextPath(testStr, testStrLen, textPos, &path);
+#if 1
+ tryRonco(path);
#endif
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setStyle(SkPaint::kStroke_Style);
- paint.setStrokeWidth(6);
- paint.setColor(0x1F003f7f);
- canvas->drawPath(path, paint);
- paint.setColor(0xFF305F00);
- paint.setStrokeWidth(1);
-#if TEST_SIMPLIFY
- canvas->drawPath(out, paint);
+#if 1
+ showPath(path, NULL);
+ SkDebugf("simplified:\n");
#endif
- return true;
+ return drawPaths(canvas, path, false);
}
static bool (*drawDemos[])(SkCanvas* , int , bool ) = {
drawStars,
- drawCircles
+ drawCircles,
+ drawLetters,
};
static size_t drawDemosCount = sizeof(drawDemos) / sizeof(drawDemos[0]);
-static bool (*firstTest)(SkCanvas* , int , bool) = 0;
+static bool (*firstTest)(SkCanvas* , int , bool) = drawLetters;
bool DrawEdgeDemo(SkCanvas* canvas, int step, bool useOld) {
diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm
index 23d8c5a..340ded5 100644
--- a/experimental/Intersection/EdgeDemoApp.mm
+++ b/experimental/Intersection/EdgeDemoApp.mm
@@ -16,7 +16,8 @@
};
protected:
virtual void onDraw(SkCanvas* canvas) {
- static int step = 0; // useNew triggers error at 23275
+ static int step = 15064; // drawLetters first error
+ // drawStars triggers error at 23275
// error is not easy to debug in its current state
static double seconds;
if (step == -1) {
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index 397bfca..e236cca 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -40,6 +40,7 @@
static bool gShowAsciiPaths = true;
static bool gComparePathsAssert = false;
static bool gPathStrAssert = true;
+static bool gUsePhysicalFiles = false;
void showPath(const SkPath& path, const char* str) {
SkDebugf("%s\n", !str ? "original:" : str);
@@ -291,7 +292,7 @@
State4 threadState[maxThreadsAllocated];
static int testNumber;
static const char* testName;
-static bool debugThreads = true;
+static bool debugThreads = false;
State4* State4::queue = NULL;
pthread_mutex_t State4::addQueue = PTHREAD_MUTEX_INITIALIZER;
@@ -421,12 +422,17 @@
}
SkDebugf("%s\n", pathStr);
}
- SkFILEWStream outFile(state.filename);
- if (!outFile.isValid()) {
- SkASSERT(0);
+ if (gUsePhysicalFiles) {
+ SkFILEWStream outFile(state.filename);
+ if (!outFile.isValid()) {
+ SkASSERT(0);
+ return;
+ }
+ outputToStream(state, pathStr, pathFillType, outFile);
return;
}
- outputToStream(state, pathStr, pathFillType, outFile);
+ SkFILEWStream outRam(state.filename);
+ outputToStream(state, pathStr, pathFillType, outRam);
}
static void writeTestName(SkPath::FillType pathFillType, SkWStream& outFile) {
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 36582fe..b3dcb06 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,9 +14,11 @@
void Intersection_Tests() {
int testsRun = 0;
+ SimplifyNew_Test();
+ QuadraticIntersection_Test();
+ SimplifyAngle_Test();
QuarticRoot_Test();
// QuadraticIntersection_Test();
- SimplifyNew_Test();
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
LineQuadraticIntersection_Test();
@@ -25,12 +27,10 @@
SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
Simplify4x4QuadralateralsThreaded_Test(testsRun);
SkDebugf("%s total testsRun=%d\n", __FUNCTION__, testsRun);
- SimplifyAngle_Test();
QuadraticBezierClip_Test();
SimplifyFindNext_Test();
SimplifyFindTop_Test();
QuadraticReduceOrder_Test();
- QuadraticIntersection_Test();
SimplifyAddIntersectingTs_Test();
cubecode_test(1);
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index a09cfcd..c1421e3 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -16,6 +16,7 @@
, fUsed2(0)
, fCoincidentUsed(0)
, fSwap(0)
+ , fFlip(0)
{
// OPTIMIZE: don't need to be initialized in release
bzero(fT, sizeof(fT));
@@ -188,6 +189,7 @@
int fUsed;
int fUsed2;
int fCoincidentUsed;
+ int fFlip;
private:
int fSwap;
};
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index 835b3bf..268d7d3 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -64,7 +64,55 @@
}
}
+static bool onlyEndPtsInCommon(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
+// the idea here is to see at minimum do a quick reject by rotating all points
+// to either side of the line formed by connecting the endpoints
+// if the opposite curves points are on the line or on the other side, the
+// curves at most intersect at the endpoints
+ for (int oddMan = 0; oddMan < 3; ++oddMan) {
+ const _Point* endPt[2];
+ for (int opp = 1; opp < 3; ++opp) {
+ int end = oddMan ^ opp;
+ if (end == 3) {
+ end = opp;
+ }
+ endPt[opp - 1] = &q1[end];
+ }
+ double origX = endPt[0]->x;
+ double origY = endPt[0]->y;
+ double adj = endPt[1]->x - origX;
+ double opp = endPt[1]->y - origY;
+ double sign = (q1[oddMan].y - origY) * adj - (q1[oddMan].x - origX) * opp;
+ assert(!approximately_zero(sign));
+ for (int n = 0; n < 3; ++n) {
+ double test = (q2[n].y - origY) * adj - (q2[n].x - origX) * opp;
+ if (test * sign > 0) {
+ goto tryNextHalfPlane;
+ }
+ }
+ for (int i1 = 0; i1 < 3; i1 += 2) {
+ for (int i2 = 0; i2 < 3; i2 += 2) {
+ if (q1[i1] == q2[i2]) {
+ i.insertOne(i1 >> 1, 0);
+ i.insertOne(i2 >> 1, 1);
+ }
+ }
+ }
+ assert(i.fUsed < 3);
+ return true;
+tryNextHalfPlane:
+ ;
+ }
+ return false;
+}
+
bool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
+ // if the quads share an end point, check to see if they overlap
+
+ if (onlyEndPtsInCommon(q1, q2, i)) {
+ assert(i.insertBalanced());
+ return i.intersected();
+ }
QuadImplicitForm i1(q1);
QuadImplicitForm i2(q2);
if (i1.implicit_match(i2)) {
@@ -100,7 +148,9 @@
addValidRoots(roots2, rootCount, 1, i);
_Point pts[4];
bool matches[4];
+ int flipCheck[4];
int index, ndex2;
+ int flipIndex = 0;
for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
xy_at_t(q2, i.fT[1][ndex2], pts[ndex2].x, pts[ndex2].y);
matches[ndex2] = false;
@@ -110,6 +160,8 @@
xy_at_t(q1, i.fT[0][index], xy.x, xy.y);
for (ndex2 = 0; ndex2 < i.fUsed2; ++ndex2) {
if (approximately_equal(pts[ndex2].x, xy.x) && approximately_equal(pts[ndex2].y, xy.y)) {
+ assert(flipIndex < 4);
+ flipCheck[flipIndex++] = ndex2;
matches[ndex2] = true;
goto next;
}
@@ -131,6 +183,7 @@
}
++ndex2;
}
+ i.fFlip = i.fUsed >= 2 && flipCheck[0] > flipCheck[1];
assert(i.insertBalanced());
return i.intersected();
}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 08736cc..e077bd5 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -59,6 +59,10 @@
}
static const Quadratic testSet[] = {
+ {{400.121704, 149.468719}, {391.949493, 161.037186}, {391.949493, 181.202423}},
+ {{391.946747, 181.839218}, {391.946747, 155.62442}, {406.115479, 138.855438}},
+ {{360.048828125, 229.2578125}, {360.048828125, 224.4140625}, {362.607421875, 221.3671875}},
+ {{362.607421875, 221.3671875}, {365.166015625, 218.3203125}, {369.228515625, 218.3203125}},
{{8, 8}, {10, 10}, {8, -10}},
{{8, 8}, {12, 12}, {14, 4}},
{{8, 8}, {9, 9}, {10, 8}}
@@ -71,12 +75,13 @@
for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
const Quadratic& quad1 = testSet[outer];
const Quadratic& quad2 = testSet[inner];
+ double tt1, tt2;
+ #if 0 // enable to test bezier clip style intersection
Intersections intersections;
intersect(quad1, quad2, intersections);
if (!intersections.intersected()) {
SkDebugf("%s no intersection!\n", __FUNCTION__);
}
- double tt1, tt2;
for (int pt = 0; pt < intersections.used(); ++pt) {
tt1 = intersections.fT[0][pt];
double tx1, ty1;
@@ -97,8 +102,10 @@
SkDebugf("%s [%d][%d] t1=%1.9g (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
outer, inner, tt1, tx1, tx2, tt2);
}
+ #endif
Intersections intersections2;
intersect2(quad1, quad2, intersections2);
+ #if 0
SkASSERT(intersections.used() == intersections2.used());
for (int pt = 0; pt < intersections2.used(); ++pt) {
tt1 = intersections2.fT[0][pt];
@@ -106,6 +113,28 @@
tt2 = intersections2.fT[1][pt];
SkASSERT(approximately_equal(intersections.fT[1][pt], tt2));
}
+ #endif
+ for (int pt = 0; pt < intersections2.used(); ++pt) {
+ tt1 = intersections2.fT[0][pt];
+ double tx1, ty1;
+ xy_at_t(quad1, tt1, tx1, ty1);
+ int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt;
+ tt2 = intersections2.fT[1][pt2];
+ double tx2, ty2;
+ xy_at_t(quad2, tt2, tx2, ty2);
+ if (!approximately_equal(tx1, tx2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
+ SkASSERT(0);
+ }
+ if (!approximately_equal(ty1, ty2)) {
+ SkDebugf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
+ SkASSERT(0);
+ }
+ SkDebugf("%s [%d][%d] t1=%1.9g (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
+ outer, inner, tt1, tx1, tx2, tt2);
+ }
}
}
}
@@ -148,7 +177,7 @@
}
void QuadraticIntersection_Test() {
- coincidentTest();
oneOffTest();
+ coincidentTest();
standardTestCases();
}
diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp
index 839c3b9..b2e73cb 100644
--- a/experimental/Intersection/QuarticRoot.cpp
+++ b/experimental/Intersection/QuarticRoot.cpp
@@ -120,7 +120,7 @@
if (approximately_zero(A)) { // we're just a quadratic
return quadraticRootsX(B, C, D, s);
}
- if (approximately_zero(D)) {
+ if (approximately_zero(D)) { // 0 is one root
int num = quadraticRootsX(A, B, C, s);
for (int i = 0; i < num; ++i) {
if (approximately_zero(s[i])) {
@@ -130,6 +130,16 @@
s[num++] = 0;
return num;
}
+ if (approximately_zero(A + B + C + D)) { // 1 is one root
+ int num = quadraticRootsX(A, A + B, -D, s);
+ for (int i = 0; i < num; ++i) {
+ if (approximately_equal(s[i], 1)) {
+ return num;
+ }
+ }
+ s[num++] = 1;
+ return num;
+ }
double a, b, c;
{
double invA = 1 / A;
@@ -197,7 +207,7 @@
}
int num;
int i;
- if (approximately_zero(E)) {
+ if (approximately_zero(E)) { // 0 is one root
num = cubicRootsX(A, B, C, D, s);
for (i = 0; i < num; ++i) {
if (approximately_zero(s[i])) {
@@ -207,6 +217,16 @@
s[num++] = 0;
return num;
}
+ if (approximately_zero(A + B + C + D + E)) { // 1 is one root
+ num = cubicRootsX(A, A + B, -(D + E), -E, s); // note that -C==A+B+D+E
+ for (i = 0; i < num; ++i) {
+ if (approximately_equal(s[i], 1)) {
+ return num;
+ }
+ }
+ s[num++] = 1;
+ return num;
+ }
double u, v;
/* normal form: x^4 + Ax^3 + Bx^2 + Cx + D = 0 */
const double invA = 1 / A;
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 2a65ad1..2ce83d6 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -25,17 +25,9 @@
int gDebugMaxWindValue = SK_MaxS32;
#endif
-#define HIGH_DEF_ANGLES 1
-
-#if HIGH_DEF_ANGLES
-typedef double AngleValue;
-#else
-typedef SkScalar AngleValue;
-#endif
-
#define DEBUG_UNUSED 0 // set to expose unused functions
-#if 1 // set to 1 for multiple thread -- no debugging
+#if 0 // set to 1 for multiple thread -- no debugging
const bool gRunTestsInOneThread = false;
@@ -45,9 +37,8 @@
#define DEBUG_ANGLE 0
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
-#define DEBUG_DUMP 0
#define DEBUG_MARK_DONE 0
-#define DEBUG_PATH_CONSTRUCTION 0
+#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SORT 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 0
@@ -57,12 +48,11 @@
const bool gRunTestsInOneThread = true;
#define DEBUG_ACTIVE_SPANS 1
-#define DEBUG_ADD_INTERSECTING_TS 0
-#define DEBUG_ADD_T_PAIR 0
+#define DEBUG_ADD_INTERSECTING_TS 1
+#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
-#define DEBUG_DUMP 1
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SORT 1
@@ -71,10 +61,7 @@
#endif
-#if (DEBUG_ACTIVE_SPANS || DEBUG_CONCIDENT || DEBUG_SORT) && !DEBUG_DUMP
-#undef DEBUG_DUMP
-#define DEBUG_DUMP 1
-#endif
+#define DEBUG_DUMP (DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | DEBUG_PATH_CONSTRUCTION)
#if DEBUG_DUMP
static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
@@ -198,6 +185,11 @@
out->fY = SkDoubleToScalar(y);
}
+static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {
+ MAKE_CONST_QUAD(quad, a);
+ xy_at_t(quad, t, out->x, out->y);
+}
+
static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
MAKE_CONST_CUBIC(cubic, a);
double x, y;
@@ -460,15 +452,35 @@
CubicLeftMost
};
+#if 0 // currently unused
static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
MAKE_CONST_LINE(bLine, b);
return intersectRay(aQuad, bLine, intersections);
}
+#endif
+
+static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine,
+ Intersections& intersections) {
+ MAKE_CONST_QUAD(aQuad, a);
+ return intersectRay(aQuad, bLine, intersections);
+}
class Segment;
+struct Span {
+ Segment* fOther;
+ mutable SkPoint fPt; // lazily computed as needed
+ double fT;
+ double fOtherT; // value at fOther[fOtherIndex].fT
+ int fOtherIndex; // can't be used during intersection
+ int fWindSum; // accumulated from contours surrounding this one
+ int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
+ int fWindValueOpp; // opposite value, if any (for binary ops with coincidence)
+ bool fDone; // if set, this span to next higher T has been processed
+};
+
// sorting angles
// given angles of {dx dy ddx ddy dddx dddy} sort them
class Angle {
@@ -490,7 +502,7 @@
the shorter tangent. If the tangents are equal, choose the better second
tangent angle
- maybe I set up LineParameters lazily
+ maybe I could set up LineParameters lazily
*/
bool operator<(const Angle& rh) const {
double y = dy();
@@ -503,9 +515,9 @@
if (y == 0 && ry == 0 && x * rx < 0) {
return x < rx;
}
- AngleValue x_ry = x * ry;
- AngleValue rx_y = rx * y;
- AngleValue cmp = x_ry - rx_y;
+ double x_ry = x * ry;
+ double rx_y = rx * y;
+ double cmp = x_ry - rx_y;
if (!approximately_zero(cmp)) {
return cmp < 0;
}
@@ -513,55 +525,23 @@
&& !approximately_zero_squared(cmp)) {
return cmp < 0;
}
+ // see if either curve can be lengthened and try the tangent compare again
+ if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
+ && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
+ Angle longer = *this;
+ Angle rhLonger = rh;
+ if (longer.lengthen() | rhLonger.lengthen()) {
+ return longer < rhLonger;
+ }
+ }
// at this point, the initial tangent line is coincident
- #if !HIGH_DEF_ANGLES // old way
- AngleValue dy = approximately_pin(fDy + fDDy);
- AngleValue rdy = approximately_pin(rh.fDy + rh.fDDy);
- if (dy * rdy < 0) {
- return dy < 0;
- }
- AngleValue dx = approximately_pin(fDx + fDDx);
- AngleValue rdx = approximately_pin(rh.fDx + rh.fDDx);
- if (dy == 0 && rdy == 0 && dx * rdx < 0) {
- return dx < rdx;
- }
- cmp = dx * rdy - rdx * dy;
- if (!approximately_zero(cmp)) {
- return cmp < 0;
- }
- dy = approximately_pin(dy + fDDDy);
- rdy = approximately_pin(rdy + rh.fDDDy);
- if (dy * rdy < 0) {
- return dy < 0;
- }
- dx = approximately_pin(dx + fDDDx);
- rdx = approximately_pin(rdx + rh.fDDDx);
- if (dy == 0 && rdy == 0 && dx * rdx < 0) {
- return dx < rdx;
- }
- return dx * rdy < rdx * dy;
- #else // new way
if (fSide * rh.fSide <= 0) {
// FIXME: running demo will trigger this assertion
// (don't know if commenting out will trigger further assertion or not)
// commenting it out allows demo to run in release, though
- SkASSERT(fSide != rh.fSide);
+ // SkASSERT(fSide != rh.fSide);
return fSide < rh.fSide;
}
- #if 0 // the following code is a bust. In particular, tangent length doesn't provide a sort
- if (y != ry) {
- return (fabs(y) < fabs(ry)) ^ (fSide > 0);
- }
- if (x != rx) {
- return (fabs(x) < fabs(rx)) ^ (fSide > 0);
- }
- // sort by second tangent angle
- cmp = fD2x * rh.fD2y - rh.fD2x * fD2y;
- if (!approximately_zero(cmp)) {
- return cmp < 0;
- }
- SkASSERT(0); // add code for cubic case
- #else
SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
// FIXME: until I can think of something better, project a ray from the
@@ -570,7 +550,7 @@
// FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
double len = fTangent1.normalSquared();
double rlen = rh.fTangent1.normalSquared();
- SkPoint ray[2];
+ _Line ray;
Intersections i, ri;
int roots, rroots;
bool flip = false;
@@ -578,30 +558,23 @@
const Quadratic& q = (len < rlen) ^ flip ? fQ : rh.fQ;
double midX = (q[0].x + q[2].x) / 2;
double midY = (q[0].y + q[2].y) / 2;
- // FIXME: Ugh! this feels like a huge hack, not sure what else to do
- while (approximately_equal(q[1].x, midX) && approximately_equal(q[1].y, midY)) {
- SkASSERT(midX - q[1].x || midY - q[1].y);
- midX += midX - q[1].x;
- midY += midY - q[1].y;
- }
- ray[0].fX = SkDoubleToScalar(q[1].x);
- ray[0].fY = SkDoubleToScalar(q[1].y);
- ray[1].fX = SkDoubleToScalar(midX);
- ray[1].fY = SkDoubleToScalar(midY);
+ ray[0] = q[1];
+ ray[1].x = midX;
+ ray[1].y = midY;
SkASSERT(ray[0] != ray[1]);
roots = QuadRayIntersect(fPts, ray, i);
rroots = QuadRayIntersect(rh.fPts, ray, ri);
} while ((roots == 0 || rroots == 0) && (flip ^= true));
SkASSERT(roots > 0);
SkASSERT(rroots > 0);
- SkPoint loc;
- SkScalar best = SK_ScalarInfinity;
- SkScalar dx, dy, dist;
+ _Point loc;
+ double best = SK_ScalarInfinity;
+ double dx, dy, dist;
int index;
for (index = 0; index < roots; ++index) {
QuadXYAtT(fPts, i.fT[0][index], &loc);
- dx = loc.fX - ray[0].fX;
- dy = loc.fY - ray[0].fY;
+ dx = loc.x - ray[0].x;
+ dy = loc.y - ray[0].y;
dist = dx * dx + dy * dy;
if (best > dist) {
best = dist;
@@ -609,32 +582,22 @@
}
for (index = 0; index < rroots; ++index) {
QuadXYAtT(rh.fPts, ri.fT[0][index], &loc);
- dx = loc.fX - ray[0].fX;
- dy = loc.fY - ray[0].fY;
+ dx = loc.x - ray[0].x;
+ dy = loc.y - ray[0].y;
dist = dx * dx + dy * dy;
if (best > dist) {
return fSide < 0;
}
}
return fSide > 0;
- #endif
- #endif
}
double dx() const {
-#if HIGH_DEF_ANGLES
return fTangent1.dx();
-#else
- return fDx;
-#endif
}
double dy() const {
-#if HIGH_DEF_ANGLES
return fTangent1.dy();
-#else
- return fDy;
-#endif
}
int end() const {
@@ -642,122 +605,57 @@
}
bool isHorizontal() const {
-#if HIGH_DEF_ANGLES
return dy() == 0 && fVerb == SkPath::kLine_Verb;
-#else
- return fDy == 0 && fDDy == 0 && fDDDy == 0;
-#endif
}
- // high precision version
-#if HIGH_DEF_ANGLES
+ bool lengthen() {
+ int newEnd = fEnd;
+ if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
+ fEnd = newEnd;
+ setSpans();
+ return true;
+ }
+ return false;
+ }
+
void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
- int start, int end, double startT, double endT) {
+ int start, int end, const SkTDArray<Span>& spans) {
fSegment = segment;
fStart = start;
fEnd = end;
fPts = orig;
fVerb = verb;
- switch (verb) {
+ fSpans = &spans;
+ setSpans();
+ }
+
+ void setSpans() {
+ double startT = (*fSpans)[fStart].fT;
+ double endT = (*fSpans)[fEnd].fT;
+ switch (fVerb) {
case SkPath::kLine_Verb:
_Line l;
- LineSubDivideHD(orig, startT, endT, l);
+ LineSubDivideHD(fPts, startT, endT, l);
// OPTIMIZATION: for pure line compares, we never need fTangent1.c
fTangent1.lineEndPoints(l);
fSide = 0;
break;
case SkPath::kQuad_Verb:
- QuadSubDivideHD(orig, startT, endT, fQ);
+ QuadSubDivideHD(fPts, startT, endT, fQ);
fTangent1.quadEndPoints(fQ, 0, 1);
fSide = -fTangent1.pointDistance(fQ[2]); // not normalized -- compare sign only
break;
case SkPath::kCubic_Verb:
Cubic c;
- CubicSubDivideHD(orig, startT, endT, c);
+ CubicSubDivideHD(fPts, startT, endT, c);
fTangent1.cubicEndPoints(c, 0, 1);
fSide = -fTangent1.pointDistance(c[2]); // not normalized -- compare sign only
break;
default:
SkASSERT(0);
}
- // OPTIMIZATION: don't need these, access fTangent1 directly
}
-#else
- // since all angles share a point, this needs to know which point
- // is the common origin, i.e., whether the center is at pts[0] or pts[verb]
- // practically, this should only be called by addAngle
- void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment,
- int start, int end) {
- SkASSERT(start != end);
- fSegment = segment;
- fStart = start;
- fEnd = end;
- fDx = approximately_pin(pts[1].fX - pts[0].fX); // b - a
- fDy = approximately_pin(pts[1].fY - pts[0].fY);
- if (verb == SkPath::kLine_Verb) {
- fDDx = fDDy = fDDDx = fDDDy = 0;
- return;
- }
- fDDx = approximately_pin(pts[2].fX - pts[1].fX - fDx); // a - 2b + c
- fDDy = approximately_pin(pts[2].fY - pts[1].fY - fDy);
- if (verb == SkPath::kQuad_Verb) {
- fDDDx = fDDDy = 0;
- return;
- }
- fDDDx = approximately_pin(pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX);
- fDDDy = approximately_pin(pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY);
- }
-
- // noncoincident quads/cubics may have the same initial angle
- // as lines, so must sort by derivatives as well
- // if flatness turns out to be a reasonable way to sort, use the below:
- void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
- int start, int end) {
- fSegment = segment;
- fStart = start;
- fEnd = end;
- fDx = pts[1].fX - pts[0].fX; // b - a
- fDy = pts[1].fY - pts[0].fY;
- if (verb == SkPath::kLine_Verb) {
- fDDx = fDDy = fDDDx = fDDDy = 0;
- return;
- }
- if (verb == SkPath::kQuad_Verb) {
- int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx);
- int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy);
- int larger = std::max(abs(uplsX), abs(uplsY));
- int shift = 0;
- double flatT;
- SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point)
- LineParameters implicitLine;
- MAKE_CONST_LINE(tangent, pts);
- implicitLine.lineEndPoints(tangent);
- implicitLine.normalize();
- while (larger > UlpsEpsilon * 1024) {
- larger >>= 2;
- ++shift;
- flatT = 0.5 / (1 << shift);
- QuadXYAtT(pts, flatT, &ddPt);
- _Point _pt = {ddPt.fX, ddPt.fY};
- double distance = implicitLine.pointDistance(_pt);
- if (approximately_zero(distance)) {
- SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance);
- break;
- }
- }
- flatT = 0.5 / (1 << shift);
- QuadXYAtT(pts, flatT, &ddPt);
- fDDx = ddPt.fX - pts[0].fX;
- fDDy = ddPt.fY - pts[0].fY;
- SkASSERT(fDDx != 0 || fDDy != 0);
- fDDDx = fDDDy = 0;
- return;
- }
- SkASSERT(0); // FIXME: add cubic case
- }
-#endif
-
Segment* segment() const {
return const_cast<Segment*>(fSegment);
}
@@ -771,56 +669,30 @@
}
#if DEBUG_ANGLE
+ const SkPoint* pts() const {
+ return fPts;
+ }
+
+ const SkTDArray<Span>* spans() const {
+ return fSpans;
+ }
+
+ SkPath::Verb verb() const {
+ return fVerb;
+ }
+
void debugShow(const SkPoint& a) const {
-#if HIGH_DEF_ANGLES
- SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n",
- dx(), dy(), fSide);
-#else
- SkDebugf(" d=(%1.9g,%1.9g) dd=(%1.9g,%1.9g) ddd=(%1.9g,%1.9g)\n",
- fDx, fDy, fDDx, fDDy, fDDDx, fDDDy);
- AngleValue ax = (AngleValue) a.fX;
- AngleValue ay = (AngleValue) a.fY;
- AngleValue bx, by, cx, cy, dx, dy;
- bx = ax + fDx; // add b - a
- by = ay + fDy;
- cx = ax + 2 * fDx + fDDx; // add a + 2(b - a) to a - 2b + c
- cy = ay + 2 * fDy + fDDy;
- if (fDDDx == 0 && fDDDy == 0) {
- if (fDDx == 0 && fDDy == 0) {
- SkDebugf(
-" {SkPath::kLine_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g} }},\n",
- ax, ay, bx, by);
- } else {
- SkDebugf(
-" {SkPath::kQuad_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
- ax, ay, bx, by, cx, cy);
- }
- } else {
- dx = fDDDx - ax - 3 * (cx - bx);
- dy = fDDDy - ay - 3 * (cy - by);
- SkDebugf(
-" {SkPath::kCubic_Verb, {{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
- ax, ay, bx, by, cx, cy, dx, dy);
- }
-#endif
+ SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
}
#endif
private:
-#if HIGH_DEF_ANGLES
const SkPoint* fPts;
Quadratic fQ;
SkPath::Verb fVerb;
double fSide;
LineParameters fTangent1;
-#else
- AngleValue fDx;
- AngleValue fDy;
- AngleValue fDDx;
- AngleValue fDDy;
- AngleValue fDDDx;
- AngleValue fDDDy;
-#endif
+ const SkTDArray<Span>* fSpans;
const Segment* fSegment;
int fStart;
int fEnd;
@@ -900,18 +772,6 @@
return result;
}
-struct Span {
- Segment* fOther;
- mutable SkPoint fPt; // lazily computed as needed
- double fT;
- double fOtherT; // value at fOther[fOtherIndex].fT
- int fOtherIndex; // can't be used during intersection
- int fWindSum; // accumulated from contours surrounding this one
- int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
- int fWindValueOpp; // opposite value, if any (for binary ops with coincidence)
- bool fDone; // if set, this span to next higher T has been processed
-};
-
static const bool opLookup[][2][2] = {
// ==0 !=0
// b a b a
@@ -1010,13 +870,17 @@
void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
SkASSERT(start != end);
Angle* angle = angles.append();
-#if HIGH_DEF_ANGLES==0 // old way
- SkPoint edge[4];
- (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
- angle->set(edge, fVerb, this, start, end);
-#else // new way : compute temp edge in higher precision
- angle->set(fPts, fVerb, this, start, end, fTs[start].fT, fTs[end].fT);
+#if DEBUG_ANGLE
+ if (angles.count() > 1) {
+ SkPoint angle0Pt, newPt;
+ (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
+ (*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
+ (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
+ SkASSERT(approximately_equal(angle0Pt.fX, newPt.fX));
+ SkASSERT(approximately_equal(angle0Pt.fY, newPt.fY));
+ }
#endif
+ angle->set(fPts, fVerb, this, start, end, fTs);
}
void addCancelOutsides(double tStart, double oStart, Segment& other,
@@ -1140,15 +1004,15 @@
(*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
if (active) {
#if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
+ 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);
+ 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(", %1.9g,%1.9g", edge[3].fX, edge[3].fY);
}
- SkDebugf("\n");
+ SkDebugf(");\n");
#endif
switch (fVerb) {
case SkPath::kLine_Verb:
@@ -1177,7 +1041,7 @@
const SkPoint& pt = xyAtT(tIndex);
if (active) {
#if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
+ SkDebugf("path.moveTo(%1.9g, %1.9g);\n", pt.fX, pt.fY);
#endif
path.moveTo(pt.fX, pt.fY);
}
@@ -1440,7 +1304,8 @@
if (!approximately_negative(span.fT - t)) {
break;
}
- if (approximately_negative(span.fT - t) && span.fOther == &other && span.fOtherT == otherT) {
+ if (approximately_negative(span.fT - t) && span.fOther == &other
+ && approximately_equal(span.fOtherT, otherT)) {
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
@@ -1518,6 +1383,61 @@
return false;
}
+ // FIXME may not need this at all
+ // FIXME once I figure out the logic, merge this and too close to call
+ // NOTE not sure if tiny triangles can ever form at the edge, so until we
+ // see one, only worry about triangles that happen away from 0 and 1
+ void collapseTriangles(bool isXor) {
+ if (fTs.count() < 3) { // require t=0, x, 1 at minimum
+ return;
+ }
+ int lastIndex = 1;
+ double lastT;
+ while (approximately_less_than_zero((lastT = fTs[lastIndex].fT))) {
+ ++lastIndex;
+ }
+ if (approximately_greater_than_one(lastT)) {
+ return;
+ }
+ int matchIndex = lastIndex;
+ do {
+ Span& match = fTs[++matchIndex];
+ double matchT = match.fT;
+ if (approximately_greater_than_one(matchT)) {
+ return;
+ }
+ if (matchT == lastT) {
+ goto nextSpan;
+ }
+ if (approximately_negative(matchT - lastT)) {
+ Span& last = fTs[lastIndex];
+ Segment* lOther = last.fOther;
+ double lT = last.fOtherT;
+ if (approximately_less_than_zero(lT) || approximately_greater_than_one(lT)) {
+ goto nextSpan;
+ }
+ Segment* mOther = match.fOther;
+ double mT = match.fOtherT;
+ if (approximately_less_than_zero(mT) || approximately_greater_than_one(mT)) {
+ goto nextSpan;
+ }
+ // add new point to connect adjacent spurs
+ int count = lOther->fTs.count();
+ for (int index = 0; index < count; ++index) {
+ Span& span = lOther->fTs[index];
+ if (span.fOther == mOther && approximately_zero(span.fOtherT - mT)) {
+ goto nextSpan;
+ }
+ }
+ mOther->addTPair(mT, *lOther, lT, false);
+ // FIXME ? this could go on to detect that spans on mOther, lOther are now coincident
+ }
+ nextSpan:
+ lastIndex = matchIndex;
+ lastT = matchT;
+ } while (true);
+ }
+
int computeSum(int startIndex, int endIndex) {
SkTDArray<Angle> angles;
addTwoAngles(startIndex, endIndex, angles);
@@ -2638,6 +2558,23 @@
}
return -1;
}
+
+ // FIXME
+ // this returns at any difference in T, vs. a preset minimum. It may be
+ // that all callers to nextSpan should use this instead.
+ int nextExactSpan(int from, int step) const {
+ const Span& fromSpan = fTs[from];
+ int count = fTs.count();
+ int to = from;
+ while (step > 0 ? ++to < count : --to >= 0) {
+ const Span& span = fTs[to];
+ if (span.fT == fromSpan.fT) {
+ continue;
+ }
+ return to;
+ }
+ return -1;
+ }
bool operand() const {
return fOperand;
@@ -2865,6 +2802,40 @@
SkDebugf(" windValue=%d\n", fTs[i].fWindValue);
}
}
+
+ // This isn't useful yet -- but leaving it in for now in case i think of something
+ // to use it for
+ void validateActiveSpans() const {
+ if (done()) {
+ return;
+ }
+ int tCount = fTs.count();
+ for (int index = 0; index < tCount; ++index) {
+ if (fTs[index].fDone) {
+ continue;
+ }
+ // count number of connections which are not done
+ int first = index;
+ double baseT = fTs[index].fT;
+ while (first > 0 && approximately_equal(fTs[first - 1].fT, baseT)) {
+ --first;
+ }
+ int last = index;
+ while (last < tCount - 1 && approximately_equal(fTs[last + 1].fT, baseT)) {
+ ++last;
+ }
+ int connections = 0;
+ connections += first > 0 && !fTs[first - 1].fDone;
+ for (int test = first; test <= last; ++test) {
+ connections += !fTs[test].fDone;
+ const Segment* other = fTs[test].fOther;
+ int oIndex = fTs[test].fOtherIndex;
+ connections += !other->fTs[oIndex].fDone;
+ connections += oIndex > 0 && !other->fTs[oIndex - 1].fDone;
+ }
+ // SkASSERT(!(connections & 1));
+ }
+ }
#endif
#if DEBUG_MARK_DONE
@@ -2917,7 +2888,7 @@
segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue,
lastSum, windSum, useInnerWinding(lastSum, windSum)
? windSum : lastSum, mSpan.fDone);
-#if DEBUG_ANGLE
+#if false && DEBUG_ANGLE
angle.debugShow(segment.xyAtT(&sSpan));
#endif
++index;
@@ -3045,6 +3016,13 @@
return fBounds;
}
+ void collapseTriangles() {
+ int segmentCount = fSegments.count();
+ for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
+ fSegments[sIndex].collapseTriangles(fXor);
+ }
+ }
+
void complete() {
setBounds();
fContainsIntercepts = false;
@@ -3290,6 +3268,12 @@
fSegments[index].debugShowActiveSpans();
}
}
+
+ void validateActiveSpans() {
+ for (int index = 0; index < fSegments.count(); ++index) {
+ fSegments[index].validateActiveSpans();
+ }
+ }
#endif
protected:
@@ -3854,13 +3838,20 @@
}
}
+ int pt2 = 0;
+ int pt2inc = 1;
+ if (ts.fFlip) {
+ pt2 = pts - 1;
+ pt2inc = -1;
+ }
for (int pt = 0; pt < pts; ++pt) {
SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
int testTAt = wt.addT(ts.fT[swap][pt], wn);
int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
- wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt);
- wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt);
+ wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
+ wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
+ pt2 += pt2inc;
}
} while (wn.advance());
} while (wt.advance());
@@ -3879,6 +3870,13 @@
Contour* contour = contourList[cIndex];
contour->findTooCloseToCall();
}
+#if 0
+ // OPTIMIZATION: this check could be folded in with findTooClose -- maybe
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ Contour* contour = contourList[cIndex];
+ contour->collapseTriangles();
+ }
+#endif
}
// project a ray from the top of the contour up and see if it hits anything
@@ -4183,9 +4181,13 @@
#if DEBUG_ACTIVE_SPANS
static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) {
- for (int index = 0; index < contourList.count(); ++ index) {
+ int index;
+ for (index = 0; index < contourList.count(); ++ index) {
contourList[index]->debugShowActiveSpans();
}
+ for (index = 0; index < contourList.count(); ++ index) {
+ contourList[index]->validateActiveSpans();
+ }
}
#endif
@@ -4286,7 +4288,7 @@
} while (*firstPt != lastPt && (active || !current->done()));
if (firstPt && active) {
#if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s close\n", __FUNCTION__);
+ SkDebugf("path.close();\n");
#endif
simple.close();
}
@@ -4349,6 +4351,9 @@
#endif
simple.close();
}
+ #if DEBUG_ACTIVE_SPANS
+ debugShowActiveSpans(contourList);
+ #endif
}
}
diff --git a/experimental/Intersection/SimplifyAngle_Test.cpp b/experimental/Intersection/SimplifyAngle_Test.cpp
index 4bf22fd..9b25851 100644
--- a/experimental/Intersection/SimplifyAngle_Test.cpp
+++ b/experimental/Intersection/SimplifyAngle_Test.cpp
@@ -93,27 +93,12 @@
int index = 0;
do {
int next = index + 1;
- #if HIGH_DEF_ANGLES==0
- if (testFlat) {
- lesser.setFlat(segPtr[index].pts, segPtr[index].verb, 0, index, next);
- } else {
- lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next);
- }
- #else
- lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next, 0, 1);
- #endif
+ SkTDArray<SimplifyAngleTest::Span> dummy;
+ lesser.set(segPtr[index].pts, segPtr[index].verb, NULL, index, next, dummy);
if (segPtr[next].verb == SkPath::kMove_Verb) {
break;
}
- #if HIGH_DEF_ANGLES==0
- if (testFlat) {
- greater.setFlat(segPtr[next].pts, segPtr[next].verb, 0, index, next);
- } else {
- greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next);
- }
- #else
- greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next, 0, 1);
- #endif
+ greater.set(segPtr[next].pts, segPtr[next].verb, NULL, index, next, dummy);
bool result = lesser < greater;
SkASSERT(result);
index = next;
@@ -129,15 +114,8 @@
size_t x;
for (x = 0; x < lineCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
- #if HIGH_DEF_ANGLES==0
- if (testFlat) {
- angle->setFlat(lines[x], SkPath::kLine_Verb, 0, x, x + 1);
- } else {
- angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1);
- }
- #else
- angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, 0, 1);
- #endif
+ SkTDArray<SimplifyAngleTest::Span> dummy;
+ angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, dummy);
double arcTan = atan2(lines[x][0].fX - lines[x][1].fX,
lines[x][0].fY - lines[x][1].fY);
arcTans.push(arcTan);
@@ -184,15 +162,8 @@
size_t x;
for (x = 0; x < quadCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
- #if HIGH_DEF_ANGLES==0
- if (testFlat) {
- angle->setFlat(quads[x], SkPath::kQuad_Verb, 0, x, x + 1);
- } else {
- angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1);
- }
- #else
- angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, 0, 1);
- #endif
+ SkTDArray<SimplifyAngleTest::Span> dummy;
+ angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, dummy);
}
for (x = 0; x < quadCount; ++x) {
angleList.push(&angles[x]);
@@ -214,15 +185,8 @@
SkTDArray<SimplifyAngleTest::Angle* > angleList;
for (size_t x = 0; x < cubicCount; ++x) {
SimplifyAngleTest::Angle* angle = angles.append();
- #if HIGH_DEF_ANGLES==0
- if (testFlat) {
- angle->setFlat(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1);
- } else {
- angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1);
- }
- #else
- angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, 0, 1);
- #endif
+ SkTDArray<SimplifyAngleTest::Span> dummy;
+ angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, dummy);
angleList.push(angle);
}
QSort<SimplifyAngleTest::Angle>(angleList.begin(), angleList.end() - 1);
@@ -235,7 +199,68 @@
}
}
+struct segmentWithT {
+ SkPath::Verb verb;
+ SkPoint pts[4];
+ double ts[2];
+};
+
+
+static const segmentWithT oneOffTest1[] = {
+ {SkPath::kQuad_Verb, {{391.653534f, 183.286819f}, {391.653534f, 157.724487f}, {405.469604f, 141.372879f}},
+ {0.62346946335026932, 0.62344389027237135}},
+ {SkPath::kQuad_Verb, {{399.365234f, 171.695801f}, {399.365234f, 140.337967f}, {375.976227f, 140.337967f}},
+ {0.31638302676995866, 0.31637992418411398}},
+ {SkPath::kMove_Verb }
+};
+
+static const segmentWithT oneOffTest2[] = {
+ {SkPath::kQuad_Verb, {{399.070374f, 151.722f}, {391.101532f, 163.002533f}, {391.101532f, 182.665863f}},
+ {0.13793711854916513, 0.13790171160614006}},
+ {SkPath::kQuad_Verb, {{391.653534f, 183.286819f}, {391.653534f, 157.724487f}, {405.469604f, 141.372879f}},
+ {0.62344389027237135, 0.62346946335026932}},
+ {SkPath::kMove_Verb }
+};
+
+static const segmentWithT oneOffTest3[] = {
+ {SkPath::kQuad_Verb, {{399.365234f, 171.695801f}, {399.365234f, 140.337967f}, {375.976227f, 140.337967f}},
+ {0.31637992418411398, 0.31638302676995866, }},
+ {SkPath::kQuad_Verb, {{399.070374f, 151.722f}, {391.101532f, 163.002533f}, {391.101532f, 182.665863f}},
+ {0.13790171160614006, 0.13793711854916513}},
+ {SkPath::kMove_Verb }
+};
+
+static const segmentWithT* oneOffTests[] = {
+ oneOffTest1,
+ oneOffTest2,
+ oneOffTest3,
+};
+
+static const size_t oneOffTestCount = sizeof(oneOffTests) / sizeof(oneOffTests[0]);
+
+static void oneOffTest(bool testFlat) {
+ for (size_t testIndex = 0; testIndex < oneOffTestCount; ++testIndex) {
+ const segmentWithT* segPtr = oneOffTests[testIndex];
+ SimplifyAngleTest::Angle lesser, greater;
+ int index = 0;
+ do {
+ int next = index + 1;
+ SkTDArray<SimplifyAngleTest::Span> dummy; // FIXME
+ lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next, dummy); // FIXME: segPtr[index].ts[0], segPtr[index].ts[1]);
+ if (segPtr[next].verb == SkPath::kMove_Verb) {
+ break;
+ }
+ greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next, dummy); // FIXME: segPtr[next].ts[0], segPtr[next].ts[1]);
+ bool result = lesser < greater;
+ SkASSERT(result);
+ index = next;
+ } while (true);
+ }
+ SkDebugf("%s finished\n", __FUNCTION__);
+}
+
static void (*tests[])(bool) = {
+ oneOffTest,
testSegments,
testLines,
testQuads,
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index d317aba..d2f8b2c 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2828,7 +2828,7 @@
testSimplifyx(path);
}
-static void (*firstTest)() = testQuadratic38;
+static void (*firstTest)() = testLine73x;
static struct {
void (*fun)();
diff --git a/experimental/Intersection/bc.htm b/experimental/Intersection/bc.htm
index 95a8d75..e0784bd 100644
--- a/experimental/Intersection/bc.htm
+++ b/experimental/Intersection/bc.htm
@@ -109,11 +109,18 @@
(gdb)
</div>
+<div id="quad37">
+ {{x = 360.048828125, y = 229.2578125}, {x = 360.048828125, y = 224.4140625}, {x = 362.607421875, y = 221.3671875}}
+ {{x = 362.607421875, y = 221.3671875}, {x = 365.166015625, y = 218.3203125}, {x = 369.228515625, y = 218.3203125}}
+</div>
+
+
</div>
<script type="text/javascript">
var testDivs = [
+ quad37,
quad36,
quad21g,
quad21a,
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index 2063152..fabd0ef 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -1556,11 +1556,555 @@
path.close();
</div>
+<div id="testQuadratic40x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(2, 0);
+ path.quadTo(3, 0, 2, 2);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(3, 1);
+ path.lineTo(0, 2);
+ path.quadTo(0, 2, 1, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic40xa">
+path.moveTo(31, 0);
+path.quadTo(41.3333359, 0, 37.8888893, 13.7777777);
+path.lineTo(31, 0);
+path.close();
+path.moveTo(37.8888893, 13.7777777);
+path.quadTo(37.2993202, 16.1360455, 36.3061028, 18.8979664);
+path.lineTo(0, 31);
+path.lineTo(15.5, 31);
+path.lineTo(35.5182915, 20.9908543);
+path.quadTo(33.7454262, 25.5091457, 31, 31);
+path.lineTo(46.5, 31);
+path.lineTo(40.2999992, 18.6000004);
+path.lineTo(46.5, 15.5);
+path.lineTo(39.8571434, 17.7142868);
+path.lineTo(37.8888893, 13.7777777);
+path.close();
+path.moveTo(36.3061028, 18.8979664);
+path.quadTo(35.9396667, 19.9169388, 35.5182915, 20.9908543);
+path.lineTo(40.2999992, 18.6000004);
+path.lineTo(39.8571434, 17.7142868);
+path.lineTo(36.3061028, 18.8979664);
+</div>
+
+<div id="testQuadratic40xb">
+path.moveTo(31, 0);
+path.quadTo(46.5, 0, 31, 31);
+path.lineTo(46.5, 31);
+path.lineTo(31, 0);
+path.close();
+path.moveTo(46.5, 15.5);
+path.lineTo(0, 31);
+path.quadTo(0, 31, 15.5, 31);
+path.lineTo(46.5, 15.5);
+path.close();
+</div>
+
+<div id="testQuadratic41o">
+path.moveTo(419.33905, 236.377808);
+path.quadTo(398.847778, 242.58728, 384.255524, 242.58728);
+path.quadTo(359.417633, 242.58728, 343.738708, 226.080429);
+path.quadTo(328.059784, 209.573578, 328.059784, 183.286819);
+path.quadTo(328.059784, 157.724487, 341.875854, 141.372879);
+path.quadTo(355.691956, 125.021263, 377.218109, 125.021263);
+path.quadTo(397.605896, 125.021263, 408.731201, 139.51004);
+path.quadTo(419.856506, 153.99881, 419.856506, 180.699539);
+path.lineTo(419.752991, 187.012497);
+path.lineTo(348.861511, 187.012497);
+path.quadTo(353.311646, 227.063599, 388.084686, 227.063599);
+path.quadTo(400.814117, 227.063599, 419.33905, 220.233185);
+path.lineTo(419.33905, 236.377808);
+path.close();
+path.moveTo(349.792938, 171.695801);
+path.lineTo(399.365234, 171.695801);
+path.quadTo(399.365234, 140.337967, 375.976227, 140.337967);
+path.quadTo(352.483704, 140.337967, 349.792938, 171.695801);
+path.close();
+path.moveTo(378.682587, 277.360321);
+path.lineTo(381.062897, 259.66333);
+path.quadTo(398.759888, 268.046112, 415.939423, 268.046112);
+path.quadTo(450.402008, 268.046112, 450.402008, 231.513718);
+path.lineTo(450.402008, 213.816727);
+path.quadTo(439.12146, 237.41272, 413.352142, 237.41272);
+path.quadTo(393.171356, 237.41272, 381.269867, 222.716965);
+path.quadTo(369.368378, 208.02121, 369.368378, 183.079834);
+path.quadTo(369.368378, 157.414017, 382.92572, 141.269379);
+path.quadTo(396.483093, 125.124756, 418.009247, 125.124756);
+path.quadTo(436.844666, 125.124756, 450.402008, 140.441467);
+path.lineTo(450.402008, 127.608543);
+path.lineTo(470.89325, 127.608543);
+path.lineTo(470.89325, 209.366608);
+path.quadTo(470.89325, 235.756866, 468.150757, 248.43454);
+path.quadTo(465.408234, 261.112213, 457.853363, 269.184509);
+path.quadTo(444.502991, 283.362823, 416.353394, 283.362823);
+path.quadTo(396.690063, 283.362823, 378.682587, 277.360321);
+path.close();
+path.moveTo(450.402008, 201.087311);
+path.lineTo(450.402008, 154.412781);
+path.quadTo(436.948151, 140.441467, 421.113983, 140.441467);
+path.quadTo(407.039185, 140.441467, 399.070374, 151.722);
+path.quadTo(391.101532, 163.002533, 391.101532, 182.665863);
+path.quadTo(391.101532, 219.612228, 417.07782, 219.612228);
+path.quadTo(434.774841, 219.612228, 450.402008, 201.087311);
+path.close();
+path.moveTo(482.9328, 236.377808);
+path.quadTo(462.441528, 242.58728, 447.849274, 242.58728);
+path.quadTo(423.011383, 242.58728, 407.332458, 226.080429);
+path.quadTo(391.653534, 209.573578, 391.653534, 183.286819);
+path.quadTo(391.653534, 157.724487, 405.469604, 141.372879);
+path.quadTo(419.285706, 125.021263, 440.811859, 125.021263);
+path.quadTo(461.199646, 125.021263, 472.324951, 139.51004);
+path.quadTo(483.450256, 153.99881, 483.450256, 180.699539);
+path.lineTo(483.346741, 187.012497);
+path.lineTo(412.455261, 187.012497);
+path.quadTo(416.905396, 227.063599, 451.678436, 227.063599);
+path.quadTo(464.407867, 227.063599, 482.9328, 220.233185);
+path.lineTo(482.9328, 236.377808);
+path.close();
+path.moveTo(413.386688, 171.695801);
+path.lineTo(462.958984, 171.695801);
+path.quadTo(462.958984, 140.337967, 439.569977, 140.337967);
+path.quadTo(416.077454, 140.337967, 413.386688, 171.695801);
+path.close();
+</div>
+
+<div id="testQuadratic41s">
+path.moveTo(341.875854, 141.372879);
+path.quadTo(355.691956,125.021263, 377.218109,125.021263);
+path.quadTo(388.787811,125.021263, 397.374664,129.687164);
+path.quadTo(406.565979,125.124756, 418.009247,125.124756);
+path.quadTo(423.583374,125.124756, 428.695251,126.466187);
+path.quadTo(434.412903,125.021263, 440.811859,125.021263);
+path.quadTo(449.427277,125.021263, 456.388672,127.608543);
+path.lineTo(470.89325,127.608543);
+path.lineTo(470.89325,137.749908);
+path.quadTo(471.627319,138.601486, 472.324951,139.51004);
+path.quadTo(483.450256,153.99881, 483.450256,180.699539);
+path.lineTo(483.346741,187.012497);
+path.lineTo(470.89325,187.012497);
+path.lineTo(470.89325,209.366608);
+path.quadTo(470.89325,217.414856, 470.638184,224.187729);
+path.quadTo(476.428223,222.631516, 482.9328,220.233185);
+path.lineTo(482.9328,236.377808);
+path.quadTo(475.87207,238.517426, 469.511749,239.919785);
+path.quadTo(468.946777,244.754791, 468.150757,248.43454);
+path.quadTo(465.408234,261.112213, 457.853363,269.184509);
+path.quadTo(444.502991,283.362823, 416.353394,283.362823);
+path.quadTo(396.690063,283.362823, 378.682587,277.360321);
+path.lineTo(381.062897,259.66333);
+path.quadTo(398.759888,268.046112, 415.939423,268.046112);
+path.quadTo(444.719147,268.046112, 449.464905,242.568665);
+path.quadTo(448.648254,242.58728, 447.849274,242.58728);
+path.quadTo(433.084625,242.58728, 421.556366,236.754425);
+path.quadTo(418.89566,237.203537, 416.046783,237.346252);
+path.quadTo(397.661652,242.58728, 384.255524,242.58728);
+path.quadTo(359.417633,242.58728, 343.738708,226.080429);
+path.quadTo(328.059784,209.573578, 328.059784,183.286819);
+path.quadTo(328.059784,157.724487, 341.875854,141.372879);
+path.close();
+path.moveTo(442.014923, 226.179474);
+path.quadTo(445.951935,226.953491, 450.402008,227.049881);
+path.lineTo(450.402008,213.816727);
+path.quadTo(446.904755,221.132065, 442.014923,226.179474);
+path.close();
+path.moveTo(395.347717, 206.501785);
+path.quadTo(392.200165,197.593536, 391.734406,187.012497);
+path.lineTo(391.197113,187.012497);
+path.quadTo(391.738647,198.938644, 395.347717,206.501785);
+path.close();
+path.moveTo(391.808533, 171.695801);
+path.lineTo(392.428436,171.695801);
+path.quadTo(393.693451,162.656265, 397.02359,154.9935);
+path.quadTo(397.023804,154.992996, 397.024048,154.992493);
+path.quadTo(393.175995,143.845093, 383.003235,141.177292);
+path.quadTo(382.964447,141.223267, 382.92572,141.269379);
+</div>
+
+<div id="testQuadratic42o">
+path.moveTo(421.962158, 236.285355);
+path.quadTo(400.947845, 242.65332, 385.983124, 242.65332);
+path.quadTo(360.511261, 242.65332, 344.432129, 225.725143);
+path.quadTo(328.352997, 208.796951, 328.352997, 181.839218);
+path.quadTo(328.352997, 155.62442, 342.521729, 138.855438);
+path.quadTo(356.69046, 122.086449, 378.766083, 122.086449);
+path.quadTo(399.674255, 122.086449, 411.083527, 136.945038);
+path.quadTo(422.492798, 151.803635, 422.492798, 179.185898);
+path.lineTo(422.386688, 185.660004);
+path.lineTo(349.685699, 185.660004);
+path.quadTo(354.24942, 226.733398, 389.910034, 226.733398);
+path.quadTo(402.964386, 226.733398, 421.962158, 219.728638);
+path.lineTo(421.962158, 236.285355);
+path.close();
+path.moveTo(350.6409, 169.952347);
+path.lineTo(401.478516, 169.952347);
+path.quadTo(401.478516, 137.794098, 377.492493, 137.794098);
+path.quadTo(353.40036, 137.794098, 350.6409, 169.952347);
+path.close();
+path.moveTo(379.213562, 278.313934);
+path.lineTo(381.654602, 260.165222);
+path.quadTo(399.803314, 268.761993, 417.421356, 268.761993);
+path.quadTo(452.763611, 268.761993, 452.763611, 231.297104);
+path.lineTo(452.763611, 213.148392);
+path.quadTo(441.195129, 237.34668, 414.768036, 237.34668);
+path.quadTo(394.072144, 237.34668, 381.866882, 222.275818);
+path.quadTo(369.661591, 207.204956, 369.661591, 181.626953);
+path.quadTo(369.661591, 155.306015, 383.565002, 138.749298);
+path.quadTo(397.468384, 122.192581, 419.544037, 122.192581);
+path.quadTo(438.860199, 122.192581, 452.763611, 137.900238);
+path.lineTo(452.763611, 124.739769);
+path.lineTo(473.777893, 124.739769);
+path.lineTo(473.777893, 208.584686);
+path.quadTo(473.777893, 235.64856, 470.965363, 248.649826);
+path.quadTo(468.152863, 261.651093, 460.405151, 269.929443);
+path.quadTo(446.71402, 284.469666, 417.845886, 284.469666);
+path.quadTo(397.680664, 284.469666, 379.213562, 278.313934);
+path.close();
+path.moveTo(452.763611, 200.094055);
+path.lineTo(452.763611, 152.228165);
+path.quadTo(438.966339, 137.900238, 422.727997, 137.900238);
+path.quadTo(408.293945, 137.900238, 400.121704, 149.468719);
+path.quadTo(391.949493, 161.037186, 391.949493, 181.202423);
+path.quadTo(391.949493, 219.091827, 418.588837, 219.091827);
+path.quadTo(436.737549, 219.091827, 452.763611, 200.094055);
+path.close();
+path.moveTo(485.555908, 236.285355);
+path.quadTo(464.541595, 242.65332, 449.576874, 242.65332);
+path.quadTo(424.105011, 242.65332, 408.025879, 225.725143);
+path.quadTo(391.946747, 208.796951, 391.946747, 181.839218);
+path.quadTo(391.946747, 155.62442, 406.115479, 138.855438);
+path.quadTo(420.28421, 122.086449, 442.359833, 122.086449);
+path.quadTo(463.268005, 122.086449, 474.677277, 136.945038);
+path.quadTo(486.086548, 151.803635, 486.086548, 179.185898);
+path.lineTo(485.980438, 185.660004);
+path.lineTo(413.279449, 185.660004);
+path.quadTo(417.84317, 226.733398, 453.503784, 226.733398);
+path.quadTo(466.558136, 226.733398, 485.555908, 219.728638);
+path.lineTo(485.555908, 236.285355);
+path.close();
+path.moveTo(414.23465, 169.952347);
+path.lineTo(465.072266, 169.952347);
+path.quadTo(465.072266, 137.794098, 441.086243, 137.794098);
+path.quadTo(416.99411, 137.794098, 414.23465, 169.952347);
+path.close();
+</div>
+
+<div id="testQuadratic42s">
+path.moveTo(342.521729, 138.855438);
+path.quadTo(356.69046,122.086449, 378.766083,122.086449);
+path.quadTo(390.293488,122.086449, 398.933502,126.603004);
+path.quadTo(408.150299,122.192581, 419.544037,122.192581);
+path.quadTo(425.108429,122.192581, 430.223633,123.496056);
+path.quadTo(435.959412,122.086449, 442.359833,122.086449);
+path.quadTo(451.19516,122.086449, 458.334229,124.739769);
+path.lineTo(473.777893,124.739769);
+path.lineTo(473.777893,135.814713);
+path.quadTo(474.234741,136.368698, 474.677277,136.945038);
+path.quadTo(486.086548,151.803635, 486.086548,179.185898);
+path.lineTo(485.980438,185.660004);
+path.lineTo(473.777893,185.660004);
+path.lineTo(473.777893,208.584686);
+path.quadTo(473.777893,216.745773, 473.522156,223.628113);
+path.quadTo(479.207153,222.069519, 485.555908,219.728638);
+path.lineTo(485.555908,236.285355);
+path.quadTo(478.638306,238.381592, 472.376221,239.787796);
+path.quadTo(471.792389,244.826782, 470.965363,248.649826);
+path.quadTo(468.152863,261.651093, 460.405151,269.929443);
+path.quadTo(446.71402,284.469666, 417.845886,284.469666);
+path.quadTo(397.680664,284.469666, 379.213562,278.313934);
+path.lineTo(381.654602,260.165222);
+path.quadTo(399.803314,268.761993, 417.421356,268.761993);
+path.quadTo(446.944275,268.761993, 451.80542,242.619034);
+path.quadTo(450.674866,242.65332, 449.576874,242.65332);
+path.quadTo(434.524628,242.65332, 422.75238,236.741913);
+path.quadTo(420.864227,237.041901, 418.884674,237.193085);
+path.quadTo(399.840271,242.65332, 385.983124,242.65332);
+path.quadTo(360.511261,242.65332, 344.432129,225.725143);
+path.quadTo(328.352997,208.796951, 328.352997,181.839218);
+path.quadTo(328.352997,155.62442, 342.521729,138.855438);
+path.close();
+path.moveTo(383.823944, 138.443222);
+path.quadTo(380.900299,137.794098, 377.492493,137.794098);
+path.quadTo(353.40036,137.794098, 350.6409,169.952347);
+path.lineTo(370.408203,169.952347);
+path.quadTo(372.883484,151.469254, 383.565002,138.749298);
+path.quadTo(383.694122,138.595551, 383.823944,138.443222);
+path.close();
+path.moveTo(369.740021, 185.660004);
+path.lineTo(349.685699,185.660004);
+path.quadTo(353.983734,224.342361, 385.863525,226.594208);
+path.quadTo(383.762756,224.616837, 381.866882,222.275818);
+path.quadTo(370.639954,208.41301, 369.740021,185.660004);
+path.close();
+path.moveTo(413.279449, 185.660004);
+path.quadTo(415.737305,207.780716, 427.214905,217.987976);
+path.quadTo(440.600586,214.512451, 452.763611,200.094055);
+path.lineTo(452.763611,185.660004);
+</div>
+
+<div id="testQuadratic43o">
+path.moveTo(288.755981, 240);
+path.lineTo(288.755981, 102.232819);
+path.lineTo(315.843994, 102.232819);
+path.lineTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(417.493835, 102.232819);
+path.lineTo(417.493835, 240);
+path.lineTo(399.248962, 240);
+path.lineTo(399.248962, 127.92453);
+path.lineTo(361.269928, 230.784485);
+path.lineTo(342.373474, 230.784485);
+path.lineTo(305.511444, 127.645271);
+path.lineTo(305.511444, 240);
+path.lineTo(288.755981, 240);
+path.close();
+path.moveTo(397.864014, 236.741989);
+path.quadTo(379.433014, 242.327148, 366.307892, 242.327148);
+path.quadTo(343.967255, 242.327148, 329.864746, 227.479935);
+path.quadTo(315.762238, 212.632736, 315.762238, 188.988907);
+path.quadTo(315.762238, 165.996674, 328.189209, 151.289093);
+path.quadTo(340.61618, 136.581512, 359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.quadTo(398.329468, 162.645584, 398.329468, 186.661758);
+path.lineTo(398.236359, 192.339996);
+path.lineTo(334.472504, 192.339996);
+path.quadTo(338.475189, 228.364258, 369.752075, 228.364258);
+path.quadTo(381.20163, 228.364258, 397.864014, 222.220581);
+path.lineTo(397.864014, 236.741989);
+path.close();
+path.moveTo(335.310272, 178.563278);
+path.lineTo(379.898438, 178.563278);
+path.quadTo(379.898438, 150.358246, 358.861023, 150.358246);
+path.quadTo(337.730499, 150.358246, 335.310272, 178.563278);
+path.close();
+path.moveTo(346.052765, 240);
+path.lineTo(346.052765, 138.908661);
+path.lineTo(364.390686, 138.908661);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.quadTo(398.832489, 136.674606, 401.904327, 137.140045);
+path.lineTo(401.904327, 154.267853);
+path.quadTo(397.156952, 152.685394, 393.526611, 152.685394);
+path.quadTo(376.119537, 152.685394, 364.390686, 173.350464);
+path.lineTo(364.390686, 240);
+path.lineTo(346.052765, 240);
+path.close();
+path.moveTo(362.792297, 273.604034);
+path.lineTo(364.933289, 257.68634);
+path.quadTo(380.850983, 265.226288, 396.303253, 265.226288);
+path.quadTo(427.300842, 265.226288, 427.300842, 232.366959);
+path.lineTo(427.300842, 216.449265);
+path.quadTo(417.15448, 237.672852, 393.976105, 237.672852);
+path.quadTo(375.824341, 237.672852, 365.119446, 224.454651);
+path.quadTo(354.414581, 211.23645, 354.414581, 188.802734);
+path.quadTo(354.414581, 165.717422, 366.608826, 151.196014);
+path.quadTo(378.803101, 136.674606, 398.164948, 136.674606);
+path.quadTo(415.106598, 136.674606, 427.300842, 150.451324);
+path.lineTo(427.300842, 138.908661);
+path.lineTo(445.731873, 138.908661);
+path.lineTo(445.731873, 212.446564);
+path.quadTo(445.731873, 236.183472, 443.265106, 247.586502);
+path.quadTo(440.798309, 258.989532, 434.003052, 266.250244);
+path.quadTo(421.994965, 279.002991, 396.675598, 279.002991);
+path.quadTo(378.989258, 279.002991, 362.792297, 273.604034);
+path.close();
+path.moveTo(427.300842, 204.999695);
+path.lineTo(427.300842, 163.017929);
+path.quadTo(415.199677, 150.451324, 400.95755, 150.451324);
+path.quadTo(388.297852, 150.451324, 381.130249, 160.597687);
+path.quadTo(373.962616, 170.744064, 373.962616, 188.430389);
+path.quadTo(373.962616, 221.662079, 397.327179, 221.662079);
+path.quadTo(413.244873, 221.662079, 427.300842, 204.999695);
+path.close();
+path.moveTo(461.457764, 236.741989);
+path.quadTo(443.026764, 242.327148, 429.901642, 242.327148);
+path.quadTo(407.561005, 242.327148, 393.458496, 227.479935);
+path.quadTo(379.355988, 212.632736, 379.355988, 188.988907);
+path.quadTo(379.355988, 165.996674, 391.782959, 151.289093);
+path.quadTo(404.20993, 136.581512, 423.571808, 136.581512);
+path.quadTo(441.909729, 136.581512, 451.916473, 149.613556);
+path.quadTo(461.923218, 162.645584, 461.923218, 186.661758);
+path.lineTo(461.830109, 192.339996);
+path.lineTo(398.066254, 192.339996);
+path.quadTo(402.068939, 228.364258, 433.345825, 228.364258);
+path.quadTo(444.79538, 228.364258, 461.457764, 222.220581);
+path.lineTo(461.457764, 236.741989);
+path.close();
+path.moveTo(398.904022, 178.563278);
+path.lineTo(443.492188, 178.563278);
+path.quadTo(443.492188, 150.358246, 422.454773, 150.358246);
+path.quadTo(401.324249, 150.358246, 398.904022, 178.563278);
+path.close();
+</div>
+
+<div id="testQuadratic43s">
+path.moveTo(288.755981, 240);
+path.lineTo(288.755981,102.232819);
+path.lineTo(315.843994,102.232819);
+path.lineTo(331.979736,147.294876);
+path.quadTo(343.453125,136.581512, 359.978058,136.581512);
+path.quadTo(370.869446,136.581512, 378.822021,141.178574);
+path.quadTo(378.893585,141.140915, 378.965302,141.103577);
+path.lineTo(393.291473,102.232819);
+path.lineTo(417.493835,102.232819);
+path.lineTo(417.493835,136.965759);
+path.quadTo(420.44223,136.581512, 423.571808,136.581512);
+path.quadTo(431.320984,136.581512, 437.582458,138.908661);
+path.lineTo(445.731873,138.908661);
+path.lineTo(445.731873,143.392502);
+path.quadTo(449.143951,146.002823, 451.916473,149.613556);
+path.quadTo(461.923218,162.645584, 461.923218,186.661758);
+path.lineTo(461.830109,192.339996);
+path.lineTo(445.731873,192.339996);
+path.lineTo(445.731873,212.446564);
+path.quadTo(445.731873,220.39856, 445.455017,226.966339);
+path.quadTo(452.7435,225.43367, 461.457764,222.220581);
+path.lineTo(461.457764,236.741989);
+path.quadTo(452.250824,239.531982, 444.367889,240.928268);
+path.quadTo(443.897583,244.662796, 443.265106,247.586502);
+path.quadTo(440.798309,258.989532, 434.003052,266.250244);
+path.quadTo(421.994965,279.002991, 396.675598,279.002991);
+path.quadTo(378.989258,279.002991, 362.792297,273.604034);
+path.lineTo(364.933289,257.68634);
+path.quadTo(380.850983,265.226288, 396.303253,265.226288);
+path.quadTo(422.230743,265.226288, 426.471558,242.237076);
+path.quadTo(419.570892,241.869324, 413.503387,240);
+path.lineTo(399.248962,240);
+path.lineTo(399.248962,237.37915);
+path.quadTo(397.047638,237.633072, 394.711517,237.667465);
+path.quadTo(378.296356,242.327148, 366.307892,242.327148);
+path.quadTo(357.463165,242.327148, 349.909637,240);
+path.lineTo(346.052765,240);
+path.lineTo(346.052765,238.625916);
+path.quadTo(336.926056,234.914124, 329.864746,227.479935);
+path.quadTo(315.762238,212.632736, 315.762238,188.988907);
+path.quadTo(315.762238,176.540054, 319.405273,166.519882);
+path.lineTo(305.511444,127.645271);
+path.lineTo(305.511444,240);
+path.lineTo(288.755981,240);
+path.close();
+path.moveTo(375.464813, 192.339996);
+path.lineTo(374.267029,195.583939);
+path.quadTo(375.987579,214.575378, 387.432068,219.736267);
+path.quadTo(380.122528,208.101486, 379.428741,192.339996);
+path.lineTo(375.464813,192.339996);
+path.close();
+path.moveTo(427.300842, 178.563278);
+path.lineTo(427.300842,163.017929);
+path.quadTo(422.561523,158.096329, 417.493835,155.102234);
+path.lineTo(417.493835,178.563278);
+path.lineTo(427.300842,178.563278);
+path.close();
+path.moveTo(427.300842, 192.339996);
+path.lineTo(417.493835,192.339996);
+path.lineTo(417.493835,214.429169);
+path.quadTo(422.505676,210.684036, 427.300842,204.999695);
+path.lineTo(427.300842,192.339996);
+path.close();
+path.moveTo(420.700134, 226.556015);
+path.quadTo(423.794342,227.54834, 427.300842,227.996094);
+path.lineTo(427.300842,216.449265);
+path.quadTo(424.497772,222.312531, 420.700134,226.556015);
+path.close();
+path.moveTo(368.744965, 228.354782);
+path.quadTo(366.836426,226.574738, 365.119446,224.454651);
+path.quadTo(364.748657,223.996796, 364.390686,223.527878);
+path.lineTo(364.390686,228.077774);
+path.quadTo(366.495239,228.312164, 368.744965,228.354782);
+path.close();
+path.moveTo(399.248962, 199.701065);
+path.lineTo(399.248962,192.339996);
+path.lineTo(398.236359,192.339996);
+path.lineTo(398.066254,192.339996);
+path.quadTo(398.498535,196.230621, 399.248962,199.701065);
+path.close();
+path.moveTo(399.248962, 178.563278);
+path.lineTo(399.248962,175.376892);
+path.quadTo(399.04483,176.922348, 398.904022,178.563278);
+path.lineTo(399.248962,178.563278);
+path.close();
+path.moveTo(399.248962, 136.688828);
+path.lineTo(399.248962,127.92453);
+path.lineTo(396.018158,136.674606);
+path.quadTo(396.029053,136.674606, 396.039917,136.674606);
+path.quadTo(396.513672,136.674606, 396.995453,136.688004);
+path.quadTo(397.576904,136.674606, 398.164948,136.674606);
+path.quadTo(398.709412,136.674606, 399.248962,136.688828);
+path.close();
+path.moveTo(346.052765, 178.563278);
+path.lineTo(346.052765,154.02713);
+path.quadTo(340.97113,157.621338, 338.22525,164.736588);
+path.lineTo(343.1763,178.563278);
+path.lineTo(346.052765,178.563278);
+path.close();
+path.moveTo(364.390686, 150.922379);
+path.lineTo(364.390686,154.048065);
+path.quadTo(365.340851,152.726639, 366.38147,151.468765);
+path.quadTo(365.420258,151.14975, 364.390686,150.922379);
+path.close();
+path.moveTo(367.863586, 152.032623);
+path.quadTo(367.144043,151.721848, 366.38147,151.468765);
+</div>
+
+<div id="testQuadratic44o">
+path.moveTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(399.248962, 127.92453);
+path.lineTo(361.269928, 230.784485);
+path.lineTo(354.009216, 208.816208);
+path.close();
+path.moveTo(328.189209, 151.289093);
+path.quadTo(340.61618, 136.581512, 359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.lineTo(328.189209, 151.289093);
+path.close();
+path.moveTo(346.052765, 138.908661);
+path.lineTo(364.390686, 138.908661);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.lineTo(346.052765, 138.908661);
+path.close();
+</div>
+
+<div id="testQuadratic44s">
+path.moveTo(380.33902, 137.376312);
+path.lineTo(393.291473,102.232819);
+path.lineTo(399.248962,127.92453);
+path.lineTo(396.018158,136.674606);
+path.quadTo(396.029053,136.674606, 396.039917,136.674606);
+path.lineTo(396.017792,136.675598);
+path.lineTo(361.269928,230.784485);
+path.lineTo(354.009216,208.816208);
+path.lineTo(375.699249,149.965286);
+path.lineTo(369.22699,150.14563);
+path.quadTo(373.524384,144.511566, 378.917297,141.233871);
+path.lineTo(380.33902,137.376312);
+path.close();
+path.moveTo(392.55661, 136.830276);
+path.quadTo(385.032623,137.51709, 378.917297,141.233856);
+path.quadTo(378.917297,141.233856, 378.917297,141.233856);
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic44o,
+ testQuadratic44s,
+ testQuadratic43o,
+ testQuadratic43s,
+ testQuadratic42o,
+ testQuadratic42s,
+ testQuadratic41o,
+ testQuadratic41s,
+ testQuadratic40xb,
+ testQuadratic40xa,
+ testQuadratic40x,
testQuadratic39,
testQuadratic39a,
testQuadratic38,
@@ -1729,6 +2273,7 @@
var testTitles = [];
var testIndex = 0;
var hasXor = false;
+var draw_labels = true;
var ctx;
@@ -1939,6 +2484,9 @@
ctx.fillStyle="rgba(192,192,255, 0.3)";
ctx.fill();
+ if (!draw_labels) {
+ return;
+ }
ctx.fillStyle="blue";
for (contours in test) {
var contour = test[contours];
@@ -2025,6 +2573,10 @@
case '+':
drawTop();
break;
+ case 'x':
+ draw_labels ^= true;
+ drawTop();
+ break;
}
}
diff --git a/gyp/shapeops_tool.gyp b/gyp/shapeops_tool.gyp
new file mode 100644
index 0000000..3b1408a
--- /dev/null
+++ b/gyp/shapeops_tool.gyp
@@ -0,0 +1,45 @@
+# GYP file to build unit tests.
+{
+ 'includes': [
+ 'apptype_console.gypi',
+ 'common.gypi',
+ ],
+ 'targets': [
+ {
+ 'target_name': 'addTest',
+ 'type': 'executable',
+ 'include_dirs' : [
+ '../src/core',
+ ],
+ 'sources': [
+ '../experimental/Intersection/AddTestOutput/main.cpp',
+ ],
+ 'dependencies': [
+ 'core.gyp:core',
+ 'effects.gyp:effects',
+ 'experimental.gyp:experimental',
+ 'images.gyp:images',
+ 'ports.gyp:ports',
+ 'pdf.gyp:pdf',
+ 'utils.gyp:utils',
+ ],
+ 'conditions': [
+ [ 'skia_gpu == 1', {
+ 'include_dirs': [
+ '../src/gpu',
+ ],
+ 'dependencies': [
+ 'gpu.gyp:gr',
+ 'gpu.gyp:skgr',
+ ],
+ }],
+ ],
+ },
+ ],
+}
+
+# Local Variables:
+# tab-width:2
+# indent-tabs-mode:nil
+# End:
+# vim: set expandtab tabstop=2 shiftwidth=2: