Now, path ops natively intersect conics, quads, and cubics in any combination. There are still a class of cubic tests that fail and a handful of undiagnosed failures from skps and fuzz tests, but things are much better overall.
Extended tests (150M+) run to completion in release in about 6 minutes; the standard test suite exceeds 100K and finishes in a few seconds on desktops.
TBR=reed
BUG=skia:3588
Review URL: https://codereview.chromium.org/1037953004
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index b507eb7..8bdb70b 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -71,6 +71,67 @@
SkDebugf("\n");
}
+static void debugShowConicLineIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CONIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
+ __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), LINE_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowConicQuadIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CONIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
+ __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), QUAD_DEBUG_DATA(wn.pts()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
+static void debugShowConicIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CONIC_DEBUG_STR " " CONIC_DEBUG_STR "\n",
+ __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()),
+ CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt,
const SkIntersectionHelper& wn, const SkIntersections& i) {
SkASSERT(i.used() == pts);
@@ -111,6 +172,26 @@
SkDebugf("\n");
}
+static void debugShowCubicConicIntersection(int pts, const SkIntersectionHelper& wt,
+ const SkIntersectionHelper& wn, const SkIntersections& i) {
+ SkASSERT(i.used() == pts);
+ if (!pts) {
+ SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CONIC_DEBUG_STR "\n",
+ __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
+ return;
+ }
+ SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
+ i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
+ }
+ SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight()));
+ for (int n = 1; n < pts; ++n) {
+ SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
+ }
+ SkDebugf("\n");
+}
+
static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
const SkIntersectionHelper& wn, const SkIntersections& i) {
SkASSERT(i.used() == pts);
@@ -144,6 +225,18 @@
const SkIntersectionHelper& , const SkIntersections& ) {
}
+static void debugShowConicLineIntersection(int , const SkIntersectionHelper& ,
+ const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowConicQuadIntersection(int , const SkIntersectionHelper& ,
+ const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
+static void debugShowConicIntersection(int , const SkIntersectionHelper& ,
+ const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
const SkIntersectionHelper& , const SkIntersections& ) {
}
@@ -152,6 +245,10 @@
const SkIntersectionHelper& , const SkIntersections& ) {
}
+static void debugShowCubicConicIntersection(int , const SkIntersectionHelper& ,
+ const SkIntersectionHelper& , const SkIntersections& ) {
+}
+
static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
const SkIntersectionHelper& , const SkIntersections& ) {
}
@@ -185,30 +282,35 @@
int pts = 0;
SkIntersections ts;
bool swap = false;
+ SkDQuad quad1, quad2;
+ SkDConic conic1, conic2;
+ SkDCubic cubic1, cubic2;
switch (wt.segmentType()) {
case SkIntersectionHelper::kHorizontalLine_Segment:
swap = true;
switch (wn.segmentType()) {
case SkIntersectionHelper::kHorizontalLine_Segment:
case SkIntersectionHelper::kVerticalLine_Segment:
- case SkIntersectionHelper::kLine_Segment: {
+ case SkIntersectionHelper::kLine_Segment:
pts = ts.lineHorizontal(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped());
debugShowLineIntersection(pts, wn, wt, ts);
break;
- }
- case SkIntersectionHelper::kQuad_Segment: {
+ case SkIntersectionHelper::kQuad_Segment:
pts = ts.quadHorizontal(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped());
debugShowQuadLineIntersection(pts, wn, wt, ts);
break;
- }
- case SkIntersectionHelper::kCubic_Segment: {
+ case SkIntersectionHelper::kConic_Segment:
+ pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(),
+ wt.right(), wt.y(), wt.xFlipped());
+ debugShowConicLineIntersection(pts, wn, wt, ts);
+ break;
+ case SkIntersectionHelper::kCubic_Segment:
pts = ts.cubicHorizontal(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped());
debugShowCubicLineIntersection(pts, wn, wt, ts);
break;
- }
default:
SkASSERT(0);
}
@@ -230,6 +332,12 @@
debugShowQuadLineIntersection(pts, wn, wt, ts);
break;
}
+ case SkIntersectionHelper::kConic_Segment: {
+ pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(),
+ wt.bottom(), wt.x(), wt.yFlipped());
+ debugShowConicLineIntersection(pts, wn, wt, ts);
+ break;
+ }
case SkIntersectionHelper::kCubic_Segment: {
pts = ts.cubicVertical(wn.pts(), wt.top(),
wt.bottom(), wt.x(), wt.yFlipped());
@@ -252,23 +360,25 @@
wn.bottom(), wn.x(), wn.yFlipped());
debugShowLineIntersection(pts, wt, wn, ts);
break;
- case SkIntersectionHelper::kLine_Segment: {
+ case SkIntersectionHelper::kLine_Segment:
pts = ts.lineLine(wt.pts(), wn.pts());
debugShowLineIntersection(pts, wt, wn, ts);
break;
- }
- case SkIntersectionHelper::kQuad_Segment: {
+ case SkIntersectionHelper::kQuad_Segment:
swap = true;
pts = ts.quadLine(wn.pts(), wt.pts());
debugShowQuadLineIntersection(pts, wn, wt, ts);
break;
- }
- case SkIntersectionHelper::kCubic_Segment: {
+ case SkIntersectionHelper::kConic_Segment:
+ swap = true;
+ pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts());
+ debugShowConicLineIntersection(pts, wn, wt, ts);
+ break;
+ case SkIntersectionHelper::kCubic_Segment:
swap = true;
pts = ts.cubicLine(wn.pts(), wt.pts());
- debugShowCubicLineIntersection(pts, wn, wt, ts);
+ debugShowCubicLineIntersection(pts, wn, wt, ts);
break;
- }
default:
SkASSERT(0);
}
@@ -285,28 +395,25 @@
wn.bottom(), wn.x(), wn.yFlipped());
debugShowQuadLineIntersection(pts, wt, wn, ts);
break;
- case SkIntersectionHelper::kLine_Segment: {
+ case SkIntersectionHelper::kLine_Segment:
pts = ts.quadLine(wt.pts(), wn.pts());
debugShowQuadLineIntersection(pts, wt, wn, ts);
break;
- }
case SkIntersectionHelper::kQuad_Segment: {
- SkDQuad quad1;
- quad1.set(wt.pts());
- SkDQuad quad2;
- quad2.set(wn.pts());
- pts = ts.intersect(quad1, quad2);
+ pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
debugShowQuadIntersection(pts, wt, wn, ts);
break;
}
+ case SkIntersectionHelper::kConic_Segment: {
+ swap = true;
+ pts = ts.intersect(conic2.set(wn.pts(), wn.weight()),
+ quad1.set(wt.pts()));
+ debugShowConicQuadIntersection(pts, wn, wt, ts);
+ break;
+ }
case SkIntersectionHelper::kCubic_Segment: {
swap = true;
- SkDQuad quad1;
- quad1.set(wt.pts());
- SkDCubic cubic1 = quad1.toCubic();
- SkDCubic cubic2;
- cubic2.set(wn.pts());
- pts = ts.intersect(cubic2, cubic1);
+ pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
debugShowCubicQuadIntersection(pts, wn, wt, ts);
break;
}
@@ -314,6 +421,43 @@
SkASSERT(0);
}
break;
+ case SkIntersectionHelper::kConic_Segment:
+ switch (wn.segmentType()) {
+ case SkIntersectionHelper::kHorizontalLine_Segment:
+ pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(),
+ wn.right(), wn.y(), wn.xFlipped());
+ debugShowConicLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kVerticalLine_Segment:
+ pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(),
+ wn.bottom(), wn.x(), wn.yFlipped());
+ debugShowConicLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kLine_Segment:
+ pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts());
+ debugShowConicLineIntersection(pts, wt, wn, ts);
+ break;
+ case SkIntersectionHelper::kQuad_Segment: {
+ pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
+ quad2.set(wn.pts()));
+ debugShowConicQuadIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kConic_Segment: {
+ pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
+ conic2.set(wn.pts(), wn.weight()));
+ debugShowConicIntersection(pts, wt, wn, ts);
+ break;
+ }
+ case SkIntersectionHelper::kCubic_Segment: {
+ swap = true;
+ pts = ts.intersect(cubic2.set(wn.pts()),
+ conic1.set(wt.pts(), wt.weight()));
+ debugShowCubicConicIntersection(pts, wn, wt, ts);
+ break;
+ }
+ }
+ break;
case SkIntersectionHelper::kCubic_Segment:
switch (wn.segmentType()) {
case SkIntersectionHelper::kHorizontalLine_Segment:
@@ -326,27 +470,23 @@
wn.bottom(), wn.x(), wn.yFlipped());
debugShowCubicLineIntersection(pts, wt, wn, ts);
break;
- case SkIntersectionHelper::kLine_Segment: {
+ case SkIntersectionHelper::kLine_Segment:
pts = ts.cubicLine(wt.pts(), wn.pts());
debugShowCubicLineIntersection(pts, wt, wn, ts);
break;
- }
case SkIntersectionHelper::kQuad_Segment: {
- SkDCubic cubic1;
- cubic1.set(wt.pts());
- SkDQuad quad2;
- quad2.set(wn.pts());
- SkDCubic cubic2 = quad2.toCubic();
- pts = ts.intersect(cubic1, cubic2);
+ pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
debugShowCubicQuadIntersection(pts, wt, wn, ts);
break;
}
+ case SkIntersectionHelper::kConic_Segment: {
+ pts = ts.intersect(cubic1.set(wt.pts()),
+ conic2.set(wn.pts(), wn.weight()));
+ debugShowCubicConicIntersection(pts, wt, wn, ts);
+ break;
+ }
case SkIntersectionHelper::kCubic_Segment: {
- SkDCubic cubic1;
- cubic1.set(wt.pts());
- SkDCubic cubic2;
- cubic2.set(wn.pts());
- pts = ts.intersect(cubic1, cubic2);
+ pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
debugShowCubicIntersection(pts, wt, wn, ts);
break;
}
diff --git a/src/pathops/SkConicLineIntersection.cpp b/src/pathops/SkConicLineIntersection.cpp
new file mode 100644
index 0000000..aa1b12d
--- /dev/null
+++ b/src/pathops/SkConicLineIntersection.cpp
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkIntersections.h"
+#include "SkPathOpsConic.h"
+#include "SkPathOpsLine.h"
+
+class LineConicIntersections {
+public:
+ LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i)
+ : fConic(c)
+ , fLine(l)
+ , fIntersections(i)
+ , fAllowNear(true) {
+ i->setMax(3); // allow short partial coincidence plus discrete intersection
+ }
+
+ void allowNear(bool allow) {
+ fAllowNear = allow;
+ }
+
+ int intersectRay(double roots[2]) {
+ return 0;
+ }
+};
+
+int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) {
+ LineConicIntersections c(conic, line, this);
+ fUsed = c.intersectRay(fT[0]);
+ for (int index = 0; index < fUsed; ++index) {
+ fPt[index] = conic.ptAtT(fT[0][index]);
+ }
+ return fUsed;
+}
diff --git a/src/pathops/SkDConicLineIntersection.cpp b/src/pathops/SkDConicLineIntersection.cpp
new file mode 100644
index 0000000..674068d
--- /dev/null
+++ b/src/pathops/SkDConicLineIntersection.cpp
@@ -0,0 +1,337 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkIntersections.h"
+#include "SkPathOpsConic.h"
+#include "SkPathOpsLine.h"
+
+class LineConicIntersections {
+public:
+ enum PinTPoint {
+ kPointUninitialized,
+ kPointInitialized
+ };
+
+ LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i)
+ : fConic(c)
+ , fLine(l)
+ , fIntersections(i)
+ , fAllowNear(true) {
+ i->setMax(3); // allow short partial coincidence plus discrete intersection
+ }
+
+ void allowNear(bool allow) {
+ fAllowNear = allow;
+ }
+
+ void checkCoincident() {
+ int last = fIntersections->used() - 1;
+ for (int index = 0; index < last; ) {
+ double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2;
+ SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
+ double t = fLine.nearPoint(conicMidPt, NULL);
+ if (t < 0) {
+ ++index;
+ continue;
+ }
+ if (fIntersections->isCoincident(index)) {
+ fIntersections->removeOne(index);
+ --last;
+ } else if (fIntersections->isCoincident(index + 1)) {
+ fIntersections->removeOne(index + 1);
+ --last;
+ } else {
+ fIntersections->setCoincident(index++);
+ }
+ fIntersections->setCoincident(index);
+ }
+ }
+
+#ifdef SK_DEBUG
+ static bool close_to(double a, double b, const double c[3]) {
+ double max = SkTMax(-SkTMin(SkTMin(c[0], c[1]), c[2]), SkTMax(SkTMax(c[0], c[1]), c[2]));
+ return approximately_zero_when_compared_to(a - b, max);
+ }
+#endif
+
+ int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
+ this->addExactHorizontalEndPoints(left, right, axisIntercept);
+ if (fAllowNear) {
+ this->addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
+ double roots[2];
+ double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY };
+ int count = this->validT(conicVals, axisIntercept, roots);
+ for (int index = 0; index < count; ++index) {
+ double conicT = roots[index];
+ SkDPoint pt = fConic.ptAtT(conicT);
+ SkASSERT(close_to(pt.fY, axisIntercept, conicVals));
+ double lineT = (pt.fX - left) / (right - left);
+ if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
+ && this->uniqueAnswer(conicT, pt)) {
+ fIntersections->insert(conicT, lineT, pt);
+ }
+ }
+ if (flipped) {
+ fIntersections->flip();
+ }
+ this->checkCoincident();
+ return fIntersections->used();
+ }
+
+ int intersect() {
+ this->addExactEndPoints();
+ if (fAllowNear) {
+ this->addNearEndPoints();
+ }
+ double rootVals[2];
+ int roots = this->intersectRay(rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double conicT = rootVals[index];
+ double lineT = this->findLineT(conicT);
+ SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT));
+ SkDEBUGCODE(SkDPoint linePt = fLine.ptAtT(lineT));
+ SkASSERT(conicPt.approximatelyEqual(linePt));
+ SkDPoint pt;
+ if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized)
+ && this->uniqueAnswer(conicT, pt)) {
+ fIntersections->insert(conicT, lineT, pt);
+ }
+ }
+ this->checkCoincident();
+ return fIntersections->used();
+ }
+
+ int intersectRay(double roots[2]) {
+ double adj = fLine[1].fX - fLine[0].fX;
+ double opp = fLine[1].fY - fLine[0].fY;
+ double r[3];
+ for (int n = 0; n < 3; ++n) {
+ r[n] = (fConic[n].fY - fLine[0].fY) * adj - (fConic[n].fX - fLine[0].fX) * opp;
+ }
+ return this->validT(r, 0, roots);
+ }
+
+ int validT(double r[3], double axisIntercept, double roots[2]) {
+ double A = r[2];
+ double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept;
+ double C = r[0];
+ A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept)
+ B -= C; // B = b*w - w * xCept + xCept - a
+ C -= axisIntercept;
+ return SkDQuad::RootsValidT(A, 2 * B, C, roots);
+ }
+
+ int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
+ this->addExactVerticalEndPoints(top, bottom, axisIntercept);
+ if (fAllowNear) {
+ this->addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
+ double roots[2];
+ double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX };
+ int count = this->validT(conicVals, axisIntercept, roots);
+ for (int index = 0; index < count; ++index) {
+ double conicT = roots[index];
+ SkDPoint pt = fConic.ptAtT(conicT);
+ SkASSERT(close_to(pt.fX, axisIntercept, conicVals));
+ double lineT = (pt.fY - top) / (bottom - top);
+ if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized)
+ && this->uniqueAnswer(conicT, pt)) {
+ fIntersections->insert(conicT, lineT, pt);
+ }
+ }
+ if (flipped) {
+ fIntersections->flip();
+ }
+ this->checkCoincident();
+ return fIntersections->used();
+ }
+
+protected:
+// OPTIMIZE: Functions of the form add .. points are indentical to the conic routines.
+ // add endpoints first to get zero and one t values exactly
+ void addExactEndPoints() {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double lineT = fLine.exactPoint(fConic[cIndex]);
+ if (lineT < 0) {
+ continue;
+ }
+ double conicT = (double) (cIndex >> 1);
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ }
+
+ void addNearEndPoints() {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double conicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(conicT)) {
+ continue;
+ }
+ double lineT = fLine.nearPoint(fConic[cIndex], NULL);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ // FIXME: see if line end is nearly on conic
+ }
+
+ void addExactHorizontalEndPoints(double left, double right, double y) {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
+ }
+ double conicT = (double) (cIndex >> 1);
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ }
+
+ void addNearHorizontalEndPoints(double left, double right, double y) {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double conicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(conicT)) {
+ continue;
+ }
+ double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ // FIXME: see if line end is nearly on conic
+ }
+
+ void addExactVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ double conicT = (double) (cIndex >> 1);
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ }
+
+ void addNearVerticalEndPoints(double top, double bottom, double x) {
+ for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) {
+ double conicT = (double) (cIndex >> 1);
+ if (fIntersections->hasT(conicT)) {
+ continue;
+ }
+ double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x);
+ if (lineT < 0) {
+ continue;
+ }
+ fIntersections->insert(conicT, lineT, fConic[cIndex]);
+ }
+ // FIXME: see if line end is nearly on conic
+ }
+
+ double findLineT(double t) {
+ SkDPoint xy = fConic.ptAtT(t);
+ double dx = fLine[1].fX - fLine[0].fX;
+ double dy = fLine[1].fY - fLine[0].fY;
+ if (fabs(dx) > fabs(dy)) {
+ return (xy.fX - fLine[0].fX) / dx;
+ }
+ return (xy.fY - fLine[0].fY) / dy;
+ }
+
+ bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) {
+ if (!approximately_one_or_less_double(*lineT)) {
+ return false;
+ }
+ if (!approximately_zero_or_more_double(*lineT)) {
+ return false;
+ }
+ double qT = *conicT = SkPinT(*conicT);
+ double lT = *lineT = SkPinT(*lineT);
+ if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) {
+ *pt = fLine.ptAtT(lT);
+ } else if (ptSet == kPointUninitialized) {
+ *pt = fConic.ptAtT(qT);
+ }
+ SkPoint gridPt = pt->asSkPoint();
+ if (SkDPoint::ApproximatelyEqual(gridPt, fLine[0].asSkPoint())) {
+ *pt = fLine[0];
+ *lineT = 0;
+ } else if (SkDPoint::ApproximatelyEqual(gridPt, fLine[1].asSkPoint())) {
+ *pt = fLine[1];
+ *lineT = 1;
+ }
+ if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) {
+ return false;
+ }
+ if (gridPt == fConic[0].asSkPoint()) {
+ *pt = fConic[0];
+ *conicT = 0;
+ } else if (gridPt == fConic[2].asSkPoint()) {
+ *pt = fConic[2];
+ *conicT = 1;
+ }
+ return true;
+ }
+
+ bool uniqueAnswer(double conicT, const SkDPoint& pt) {
+ for (int inner = 0; inner < fIntersections->used(); ++inner) {
+ if (fIntersections->pt(inner) != pt) {
+ continue;
+ }
+ double existingConicT = (*fIntersections)[0][inner];
+ if (conicT == existingConicT) {
+ return false;
+ }
+ // check if midway on conic is also same point. If so, discard this
+ double conicMidT = (existingConicT + conicT) / 2;
+ SkDPoint conicMidPt = fConic.ptAtT(conicMidT);
+ if (conicMidPt.approximatelyEqual(pt)) {
+ return false;
+ }
+ }
+#if ONE_OFF_DEBUG
+ SkDPoint qPt = fConic.ptAtT(conicT);
+ SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY,
+ qPt.fX, qPt.fY);
+#endif
+ return true;
+ }
+
+private:
+ const SkDConic& fConic;
+ const SkDLine& fLine;
+ SkIntersections* fIntersections;
+ bool fAllowNear;
+};
+
+int SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y,
+ bool flipped) {
+ SkDLine line = {{{ left, y }, { right, y }}};
+ LineConicIntersections c(conic, line, this);
+ return c.horizontalIntersect(y, left, right, flipped);
+}
+
+int SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x,
+ bool flipped) {
+ SkDLine line = {{{ x, top }, { x, bottom }}};
+ LineConicIntersections c(conic, line, this);
+ return c.verticalIntersect(x, top, bottom, flipped);
+}
+
+int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) {
+ LineConicIntersections c(conic, line, this);
+ c.allowNear(fAllowNear);
+ return c.intersect();
+}
+
+int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) {
+ LineConicIntersections c(conic, line, this);
+ fUsed = c.intersectRay(fT[0]);
+ for (int index = 0; index < fUsed; ++index) {
+ fPt[index] = conic.ptAtT(fT[0][index]);
+ }
+ return fUsed;
+}
diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h
index c633fd0..79de034 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -19,6 +19,7 @@
kVerticalLine_Segment = 0,
kLine_Segment = SkPath::kLine_Verb,
kQuad_Segment = SkPath::kQuad_Verb,
+ kConic_Segment = SkPath::kConic_Verb,
kCubic_Segment = SkPath::kCubic_Verb,
};
@@ -82,6 +83,10 @@
return bounds().fTop;
}
+ SkScalar weight() const {
+ return fSegment->weight();
+ }
+
SkScalar x() const {
return bounds().fLeft;
}
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index 007efa7..a1f8598 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -47,10 +47,12 @@
return count;
}
-int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar, SkScalar, SkScalar, bool) = {
+int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar,
+ SkScalar, SkScalar, SkScalar, bool) = {
NULL,
&SkIntersections::verticalLine,
&SkIntersections::verticalQuad,
+ &SkIntersections::verticalConic,
&SkIntersections::verticalCubic
};
@@ -193,23 +195,30 @@
fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
}
-int SkIntersections::verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom,
- SkScalar x, bool flipped) {
+int SkIntersections::verticalConic(const SkPoint a[3], SkScalar weight,
+ SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
+ SkDConic conic;
+ conic.set(a, weight);
+ return vertical(conic, top, bottom, x, flipped);
+}
+
+int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar weight,
+ SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
+ SkDCubic cubic;
+ cubic.set(a);
+ return vertical(cubic, top, bottom, x, flipped);
+}
+
+int SkIntersections::verticalLine(const SkPoint a[2], SkScalar weight,
+ SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
SkDLine line;
line.set(a);
return vertical(line, top, bottom, x, flipped);
}
-int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom,
- SkScalar x, bool flipped) {
+int SkIntersections::verticalQuad(const SkPoint a[3], SkScalar weight,
+ SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
SkDQuad quad;
quad.set(a);
return vertical(quad, top, bottom, x, flipped);
}
-
-int SkIntersections::verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom,
- SkScalar x, bool flipped) {
- SkDCubic cubic;
- cubic.set(a);
- return vertical(cubic, top, bottom, x, flipped);
-}
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 15bac19..57fb49b 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -7,6 +7,7 @@
#ifndef SkIntersections_DEFINE
#define SkIntersections_DEFINE
+#include "SkPathOpsConic.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsLine.h"
#include "SkPathOpsPoint.h"
@@ -49,6 +50,31 @@
fIsCoincident[1] &= ~bit;
}
+ int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right,
+ SkScalar y, bool flipped) {
+ SkDConic conic;
+ conic.set(a, weight);
+ fMax = 2;
+ return horizontal(conic, left, right, y, flipped);
+ }
+
+ int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped) {
+ SkDConic conic;
+ conic.set(a, weight);
+ fMax = 2;
+ return vertical(conic, top, bottom, x, flipped);
+ }
+
+ int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) {
+ SkDConic conic;
+ conic.set(a, weight);
+ SkDLine line;
+ line.set(b);
+ fMax = 3; // 2; permit small coincident segment + non-coincident intersection
+ return intersect(conic, line);
+ }
+
int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
bool flipped) {
SkDCubic cubic;
@@ -206,6 +232,7 @@
int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
int horizontal(const SkDCubic&, double y, double tRange[3]);
+ int horizontal(const SkDConic&, double left, double right, double y, bool flipped);
int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
// FIXME : does not respect swap
@@ -216,10 +243,16 @@
int intersect(const SkDLine&, const SkDLine&);
int intersect(const SkDQuad&, const SkDLine&);
int intersect(const SkDQuad&, const SkDQuad&);
+ int intersect(const SkDConic&, const SkDLine&);
+ int intersect(const SkDConic&, const SkDQuad&);
+ int intersect(const SkDConic&, const SkDConic&);
int intersect(const SkDCubic&, const SkDLine&);
+ int intersect(const SkDCubic&, const SkDQuad&);
+ int intersect(const SkDCubic&, const SkDConic&);
int intersect(const SkDCubic&, const SkDCubic&);
int intersectRay(const SkDLine&, const SkDLine&);
int intersectRay(const SkDQuad&, const SkDLine&);
+ int intersectRay(const SkDConic&, const SkDLine&);
int intersectRay(const SkDCubic&, const SkDLine&);
void merge(const SkIntersections& , int , const SkIntersections& , int );
int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
@@ -228,10 +261,16 @@
void setCoincident(int index);
int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
+ int vertical(const SkDConic&, double top, double bottom, double x, bool flipped);
int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
- int verticalCubic(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
- int verticalLine(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
- int verticalQuad(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
+ int verticalConic(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped);
+ int verticalCubic(const SkPoint a[4], SkScalar weight, SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped);
+ int verticalLine(const SkPoint a[2], SkScalar weight, SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped);
+ int verticalQuad(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped);
int depth() const {
#ifdef SK_DEBUG
@@ -264,7 +303,7 @@
#endif
};
-extern int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar top, SkScalar bottom,
- SkScalar x, bool flipped);
+extern int (SkIntersections::* const CurveVertical[])(const SkPoint[], SkScalar weight,
+ SkScalar top, SkScalar bottom, SkScalar x, bool flipped);
#endif
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index c13a51a..52a98d0 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -189,7 +189,7 @@
SkPath::Verb testVerb = test->segment()->verb();
int iMax = SkPathOpsVerbToPoints(testVerb);
// SkASSERT(origin == test.fCurveHalf[0]);
- const SkDCubic& testCurve = test->fCurvePart;
+ const SkDCurve& testCurve = test->fCurvePart;
for (int index = 1; index <= iMax; ++index) {
float xy1 = (float) (line.fX * (testCurve[index].fY - origin.fY));
float xy2 = (float) (line.fY * (testCurve[index].fX - origin.fX));
@@ -292,11 +292,14 @@
// compute the perpendicular to the endpoints and see where it intersects the opposite curve
// if the intersections within the t range, do a cross check on those
bool inside;
- if (this->endToSide(rh, &inside)) {
- return inside;
- }
- if (rh->endToSide(this, &inside)) {
- return !inside;
+ if (!fCurvePart[SkPathOpsVerbToPoints(this->segment()->verb())].approximatelyEqual(
+ rh->fCurvePart[SkPathOpsVerbToPoints(rh->segment()->verb())])) {
+ if (this->endToSide(rh, &inside)) {
+ return inside;
+ }
+ if (rh->endToSide(this, &inside)) {
+ return !inside;
+ }
}
if (this->midToSide(rh, &inside)) {
return inside;
@@ -445,14 +448,14 @@
double smallTs[2] = {-1, -1};
bool limited[2] = {false, false};
for (int index = 0; index < 2; ++index) {
- int cPts = index ? rPts : lPts;
+ SkPath::Verb cVerb = index ? rVerb : lVerb;
// if the curve is a line, then the line and the ray intersect only at their crossing
- if (cPts == 1) { // line
+ if (cVerb == SkPath::kLine_Verb) {
continue;
}
const SkOpSegment& segment = index ? *rh->segment() : *this->segment();
SkIntersections i;
- (*CurveIntersectRay[cPts])(segment.pts(), rays[index], &i);
+ (*CurveIntersectRay[cVerb])(segment.pts(), segment.weight(), rays[index], &i);
double tStart = index ? rh->fStart->t() : this->fStart->t();
double tEnd = index ? rh->fComputedEnd->t() : this->fComputedEnd->t();
bool testAscends = tStart < (index ? rh->fComputedEnd->t() : this->fComputedEnd->t());
@@ -509,7 +512,7 @@
double minX, minY, maxX, maxY;
minX = minY = SK_ScalarInfinity;
maxX = maxY = -SK_ScalarInfinity;
- const SkDCubic& curve = index ? rh->fCurvePart : this->fCurvePart;
+ const SkDCurve& curve = index ? rh->fCurvePart : this->fCurvePart;
int ptCount = index ? rPts : lPts;
for (int idx2 = 0; idx2 <= ptCount; ++idx2) {
minX = SkTMin(minX, curve[idx2].fX);
@@ -527,7 +530,7 @@
}
}
if (useIntersect) {
- const SkDCubic& curve = sIndex ? rh->fCurvePart : this->fCurvePart;
+ const SkDCurve& curve = sIndex ? rh->fCurvePart : this->fCurvePart;
const SkOpSegment& segment = sIndex ? *rh->segment() : *this->segment();
double tStart = sIndex ? rh->fStart->t() : fStart->t();
SkDVector mid = segment.dPtAtT(tStart + (sCeptT - tStart) / 2) - curve[0];
@@ -544,18 +547,17 @@
bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const {
const SkOpSegment* segment = this->segment();
SkPath::Verb verb = segment->verb();
- int pts = SkPathOpsVerbToPoints(verb);
SkDLine rayEnd;
rayEnd[0].set(this->fEnd->pt());
rayEnd[1] = rayEnd[0];
- SkDVector slopeAtEnd = (*CurveDSlopeAtT[pts])(segment->pts(), this->fEnd->t());
+ SkDVector slopeAtEnd = (*CurveDSlopeAtT[verb])(segment->pts(), segment->weight(),
+ this->fEnd->t());
rayEnd[1].fX += slopeAtEnd.fY;
rayEnd[1].fY -= slopeAtEnd.fX;
SkIntersections iEnd;
const SkOpSegment* oppSegment = rh->segment();
SkPath::Verb oppVerb = oppSegment->verb();
- int oppPts = SkPathOpsVerbToPoints(oppVerb);
- (*CurveIntersectRay[oppPts])(oppSegment->pts(), rayEnd, &iEnd);
+ (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayEnd, &iEnd);
double endDist;
int closestEnd = iEnd.closestTo(rh->fStart->t(), rh->fEnd->t(), rayEnd[0], &endDist);
if (closestEnd < 0) {
@@ -570,7 +572,8 @@
double minX, minY, maxX, maxY;
minX = minY = SK_ScalarInfinity;
maxX = maxY = -SK_ScalarInfinity;
- const SkDCubic& curve = rh->fCurvePart;
+ const SkDCurve& curve = rh->fCurvePart;
+ int oppPts = SkPathOpsVerbToPoints(oppVerb);
for (int idx2 = 0; idx2 <= oppPts; ++idx2) {
minX = SkTMin(minX, curve[idx2].fX);
minY = SkTMin(minY, curve[idx2].fY);
@@ -814,11 +817,14 @@
}
// OPTIMIZATION: can this be done better in after when angles are sorted?
-void SkOpAngle::markStops() {
+bool SkOpAngle::markStops() {
SkOpAngle* angle = this;
int lastEnd = SkTMax(fSectorStart, fSectorEnd);
do {
angle = angle->fNext;
+ if (!angle) {
+ return false;
+ }
int angleStart = SkTMin(angle->fSectorStart, angle->fSectorEnd);
// angles that are smaller by one aren't necessary better, since the larger may be a line
// and the smaller may be a curve that curls to the other side of the line.
@@ -827,6 +833,7 @@
}
lastEnd = SkTMax(angle->fSectorStart, angle->fSectorEnd);
} while (angle != this);
+ return true;
}
bool SkOpAngle::merge(SkOpAngle* angle) {
@@ -857,7 +864,6 @@
bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const {
const SkOpSegment* segment = this->segment();
SkPath::Verb verb = segment->verb();
- int pts = SkPathOpsVerbToPoints(verb);
const SkPoint& startPt = this->fStart->pt();
const SkPoint& endPt = this->fEnd->pt();
SkDPoint dStartPt;
@@ -868,16 +874,15 @@
rayMid[1].fX = rayMid[0].fX + (endPt.fY - startPt.fY);
rayMid[1].fY = rayMid[0].fY - (endPt.fX - startPt.fX);
SkIntersections iMid;
- (*CurveIntersectRay[pts])(segment->pts(), rayMid, &iMid);
+ (*CurveIntersectRay[verb])(segment->pts(), segment->weight(), rayMid, &iMid);
int iOutside = iMid.mostOutside(this->fStart->t(), this->fEnd->t(), dStartPt);
if (iOutside < 0) {
return false;
}
const SkOpSegment* oppSegment = rh->segment();
SkPath::Verb oppVerb = oppSegment->verb();
- int oppPts = SkPathOpsVerbToPoints(oppVerb);
SkIntersections oppMid;
- (*CurveIntersectRay[oppPts])(oppSegment->pts(), rayMid, &oppMid);
+ (*CurveIntersectRay[oppVerb])(oppSegment->pts(), oppSegment->weight(), rayMid, &oppMid);
int oppOutside = oppMid.mostOutside(rh->fStart->t(), rh->fEnd->t(), dStartPt);
if (oppOutside < 0) {
return false;
@@ -966,7 +971,7 @@
fStop = false;
setSpans();
setSector();
- PATH_OPS_DEBUG_CODE(fID = start->globalState()->nextAngleID());
+ SkDEBUGCODE(fID = start ? start->globalState()->nextAngleID() : -1);
}
void SkOpAngle::setCurveHullSweep() {
@@ -1015,10 +1020,16 @@
void SkOpAngle::setSpans() {
fUnorderable = false;
fLastMarked = NULL;
+ if (!fStart) {
+ fUnorderable = true;
+ return;
+ }
const SkOpSegment* segment = fStart->segment();
const SkPoint* pts = segment->pts();
+ SkDEBUGCODE(fCurvePart.fVerb = SkPath::kCubic_Verb);
SkDEBUGCODE(fCurvePart[2].fX = fCurvePart[2].fY = fCurvePart[3].fX = fCurvePart[3].fY
= SK_ScalarNaN);
+ SkDEBUGCODE(fCurvePart.fVerb = segment->verb());
segment->subDivide(fStart, fEnd, &fCurvePart);
setCurveHullSweep();
const SkPath::Verb verb = segment->verb();
@@ -1041,15 +1052,15 @@
fSide = 0;
fIsCurve = false;
} return;
- case SkPath::kQuad_Verb: {
+ case SkPath::kQuad_Verb:
+ case SkPath::kConic_Verb: {
SkLineParameters tangentPart;
- SkDQuad& quad2 = *SkTCast<SkDQuad*>(&fCurvePart);
- (void) tangentPart.quadEndPoints(quad2);
+ (void) tangentPart.quadEndPoints(fCurvePart.fQuad);
fSide = -tangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
} break;
case SkPath::kCubic_Verb: {
SkLineParameters tangentPart;
- (void) tangentPart.cubicPart(fCurvePart);
+ (void) tangentPart.cubicPart(fCurvePart.fCubic);
fSide = -tangentPart.pointDistance(fCurvePart[3]);
double testTs[4];
// OPTIMIZATION: keep inflections precomputed with cubic segment?
@@ -1080,9 +1091,9 @@
testT = (testT + testTs[testIndex + 1]) / 2;
}
// OPTIMIZE: could avoid call for t == startT, endT
- SkDPoint pt = dcubic_xy_at_t(pts, testT);
+ SkDPoint pt = dcubic_xy_at_t(pts, segment->weight(), testT);
SkLineParameters tangentPart;
- tangentPart.cubicEndPoints(fCurvePart);
+ tangentPart.cubicEndPoints(fCurvePart.fCubic);
double testSide = tangentPart.pointDistance(pt);
if (fabs(bestSide) < fabs(testSide)) {
bestSide = testSide;
@@ -1096,6 +1107,10 @@
}
void SkOpAngle::setSector() {
+ if (!fStart) {
+ fUnorderable = true;
+ return;
+ }
const SkOpSegment* segment = fStart->segment();
SkPath::Verb verb = segment->verb();
fSectorStart = this->findSector(verb, fSweep[0].fX, fSweep[0].fY);
@@ -1176,5 +1191,5 @@
double tDist = tweep[0].length() * m;
bool useS = fabs(sDist) < fabs(tDist);
double mFactor = fabs(useS ? this->distEndRatio(sDist) : rh->distEndRatio(tDist));
- return mFactor < 5000; // empirically found limit
+ return mFactor < 2400; // empirically found limit
}
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index 84b3701..9947b43 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -8,6 +8,7 @@
#define SkOpAngle_DEFINED
#include "SkLineParameters.h"
+#include "SkPathOpsCurve.h"
#if DEBUG_ANGLE
#include "SkString.h"
#endif
@@ -38,7 +39,7 @@
SkOpContour* debugContour(int id);
int debugID() const {
- return PATH_OPS_DEBUG_RELEASE(fID, -1);
+ return SkDEBUGRELEASE(fID, -1);
}
#if DEBUG_SORT
@@ -75,7 +76,7 @@
SkOpSpanBase* lastMarked() const;
bool loopContains(const SkOpAngle* ) const;
int loopCount() const;
- void markStops();
+ bool markStops();
bool merge(SkOpAngle* );
double midT() const;
bool midToSide(const SkOpAngle* rh, bool* inside) const;
@@ -102,7 +103,7 @@
void setCurveHullSweep();
void setID(int id) {
- PATH_OPS_DEBUG_CODE(fID = id);
+ SkDEBUGCODE(fID = id);
}
void setLastMarked(SkOpSpanBase* marked) {
@@ -124,7 +125,7 @@
return fUnorderable;
}
- SkDCubic fCurvePart; // the curve from start to end
+ SkDCurve fCurvePart; // the curve from start to end
double fSide;
SkLineParameters fTangentHalf; // used only to sort a pair of lines or line-like sections
SkOpAngle* fNext;
@@ -143,7 +144,7 @@
bool fComputeSector;
bool fComputedSector;
bool fCheckCoincidence;
- PATH_OPS_DEBUG_CODE(int fID);
+ SkDEBUGCODE(int fID);
};
diff --git a/src/pathops/SkOpBuilder.cpp b/src/pathops/SkOpBuilder.cpp
index 1c21a59..2f19b33 100644
--- a/src/pathops/SkOpBuilder.cpp
+++ b/src/pathops/SkOpBuilder.cpp
@@ -27,6 +27,7 @@
paths with union ops could be locally resolved and still improve over doing the
ops one at a time. */
bool SkOpBuilder::resolve(SkPath* result) {
+ SkPath original = *result;
int count = fOps.count();
bool allUnion = true;
SkPath::Direction firstDir;
@@ -67,6 +68,7 @@
for (int index = 1; index < count; ++index) {
if (!Op(*result, fPathRefs[index], fOps[index], result)) {
reset();
+ *result = original;
return false;
}
}
@@ -77,10 +79,15 @@
for (int index = 0; index < count; ++index) {
if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
reset();
+ *result = original;
return false;
}
sum.addPath(fPathRefs[index]);
}
reset();
- return Simplify(sum, result);
+ bool success = Simplify(sum, result);
+ if (!success) {
+ *result = original;
+ }
+ return success;
}
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 45eee0a..4251d9f 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -22,7 +22,7 @@
this->fHead = coinRec;
}
-static void tRange(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
+static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
double denom = overE->fT - overS->fT;
double start = 0 < denom ? tStart : tEnd;
@@ -38,8 +38,8 @@
SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
double coinTs, coinTe, oppTs, oppTe;
- tRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
- tRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+ t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+ t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
SkOpSegment* coinSeg = coinPtTStart->segment();
SkOpSegment* oppSeg = oppPtTStart->segment();
SkASSERT(coinSeg != oppSeg);
@@ -103,7 +103,7 @@
double overS, overE;
if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
- if (!addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+ if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
@@ -111,7 +111,7 @@
}
} else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
- if (!addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+ if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
@@ -119,7 +119,7 @@
}
} else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
- if (!addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+ if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
@@ -127,7 +127,7 @@
}
} else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
- if (!addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+ if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
@@ -140,7 +140,6 @@
return true;
}
-
bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
SkOpPtT* oppPtTEnd, bool flipped) {
SkCoincidentSpans* coin = fHead;
@@ -183,16 +182,21 @@
oStart = oNext->upCast();
} while (true);
}
- bool isXor = segment->isXor();
- bool oppXor = oSegment->isXor();
do {
int windValue = start->windValue();
- int oWindValue = oStart->windValue();
int oppValue = start->oppValue();
+ int oWindValue = oStart->windValue();
int oOppValue = oStart->oppValue();
// winding values are added or subtracted depending on direction and wind type
// same or opposite values are summed depending on the operand value
- if (windValue >= oWindValue) {
+ int windDiff = operandSwap ? oOppValue : oWindValue;
+ int oWindDiff = operandSwap ? oppValue : windValue;
+ if (!flipped) {
+ windDiff = -windDiff;
+ oWindDiff = -oWindDiff;
+ }
+ if (windValue && (windValue > windDiff || (windValue == windDiff
+ && oWindValue <= oWindDiff))) {
if (operandSwap) {
SkTSwap(oWindValue, oOppValue);
}
@@ -203,10 +207,10 @@
windValue += oWindValue;
oppValue += oOppValue;
}
- if (isXor) {
+ if (segment->isXor()) {
windValue &= 1;
}
- if (oppXor) {
+ if (segment->oppXor()) {
oppValue &= 1;
}
oWindValue = oOppValue = 0;
@@ -221,12 +225,12 @@
oWindValue += windValue;
oOppValue += oppValue;
}
- if (isXor) {
- oOppValue &= 1;
- }
- if (oppXor) {
+ if (oSegment->isXor()) {
oWindValue &= 1;
}
+ if (oSegment->oppXor()) {
+ oOppValue &= 1;
+ }
windValue = oppValue = 0;
}
start->setWindValue(windValue);
@@ -245,11 +249,9 @@
break;
}
start = next->upCast();
- if (!oNext) {
- return false;
- }
- if (!oNext->upCastable()) {
- return false;
+ // if the opposite ran out too soon, just reuse the last span
+ if (!oNext || !oNext->upCastable()) {
+ oNext = oStart;
}
oStart = oNext->upCast();
} while (true);
diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h
index b79b88b..84bc832 100644
--- a/src/pathops/SkOpCoincidence.h
+++ b/src/pathops/SkOpCoincidence.h
@@ -32,6 +32,7 @@
void add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator);
bool addMissing(SkChunkAlloc* allocator);
+ void addMissing(SkCoincidentSpans* check, SkChunkAlloc* allocator);
bool apply();
bool contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
SkOpPtT* oppPtTEnd, bool flipped);
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index d17b189..ab1a37b 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -22,6 +22,9 @@
memcpy(ptStorage, pts, sizeof(SkPoint) * 3);
appendSegment(allocator).addQuad(ptStorage, this);
} break;
+ case SkPath::kConic_Verb: {
+ SkASSERT(0); // the original curve is a cubic, which will never reduce to a conic
+ } break;
case SkPath::kCubic_Verb: {
SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 4);
memcpy(ptStorage, pts, sizeof(SkPoint) * 4);
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 495b643..184ee92 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -32,6 +32,10 @@
: fBounds.fTop < rh.fBounds.fTop;
}
+ void addConic(SkPoint pts[3], SkScalar weight, SkChunkAlloc* allocator) {
+ appendSegment(allocator).addConic(pts, weight, this);
+ }
+
void addCubic(SkPoint pts[4], SkChunkAlloc* allocator) {
appendSegment(allocator).addCubic(pts, this);
}
@@ -98,11 +102,11 @@
}
int debugID() const {
- return PATH_OPS_DEBUG_RELEASE(fID, -1);
+ return SkDEBUGRELEASE(fID, -1);
}
int debugIndent() const {
- return PATH_OPS_DEBUG_RELEASE(fIndent, 0);
+ return SkDEBUGRELEASE(fIndent, 0);
}
#if DEBUG_ACTIVE_SPANS
@@ -115,23 +119,23 @@
#endif
const SkOpAngle* debugAngle(int id) const {
- return PATH_OPS_DEBUG_RELEASE(globalState()->debugAngle(id), NULL);
+ return SkDEBUGRELEASE(globalState()->debugAngle(id), NULL);
}
SkOpContour* debugContour(int id) {
- return PATH_OPS_DEBUG_RELEASE(globalState()->debugContour(id), NULL);
+ return SkDEBUGRELEASE(globalState()->debugContour(id), NULL);
}
const SkOpPtT* debugPtT(int id) const {
- return PATH_OPS_DEBUG_RELEASE(globalState()->debugPtT(id), NULL);
+ return SkDEBUGRELEASE(globalState()->debugPtT(id), NULL);
}
const SkOpSegment* debugSegment(int id) const {
- return PATH_OPS_DEBUG_RELEASE(globalState()->debugSegment(id), NULL);
+ return SkDEBUGRELEASE(globalState()->debugSegment(id), NULL);
}
const SkOpSpanBase* debugSpan(int id) const {
- return PATH_OPS_DEBUG_RELEASE(globalState()->debugSpan(id), NULL);
+ return SkDEBUGRELEASE(globalState()->debugSpan(id), NULL);
}
SkOpGlobalState* globalState() const {
@@ -181,13 +185,14 @@
}
void indentDump() {
- PATH_OPS_DEBUG_CODE(fIndent += 2);
+ SkDEBUGCODE(fIndent += 2);
}
void init(SkOpGlobalState* globalState, bool operand, bool isXor) {
fState = globalState;
fOperand = operand;
fXor = isXor;
+ SkDEBUGCODE(fID = globalState->nextContourID());
}
bool isXor() const {
@@ -236,7 +241,7 @@
}
void outdentDump() {
- PATH_OPS_DEBUG_CODE(fIndent -= 2);
+ SkDEBUGCODE(fIndent -= 2);
}
void remove(SkOpContour* contour) {
@@ -262,7 +267,7 @@
fDone = false;
SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin));
SkDEBUGCODE(fFirstSorted = -1);
- PATH_OPS_DEBUG_CODE(fIndent = 0);
+ SkDEBUGCODE(fIndent = 0);
}
void setBounds() {
@@ -349,8 +354,8 @@
bool fOperand; // true for the second argument to a binary operator
bool fXor; // set if original path had even-odd fill
bool fOppXor; // set if opposite path had even-odd fill
- PATH_OPS_DEBUG_CODE(int fID);
- PATH_OPS_DEBUG_CODE(int fIndent);
+ SkDEBUGCODE(int fID);
+ SkDEBUGCODE(int fIndent);
};
#endif
diff --git a/src/pathops/SkOpCubicHull.cpp b/src/pathops/SkOpCubicHull.cpp
index 11eaa1f..f3e0a7f 100644
--- a/src/pathops/SkOpCubicHull.cpp
+++ b/src/pathops/SkOpCubicHull.cpp
@@ -14,6 +14,18 @@
return false;
}
rotPath = cubic;
+ if (dy) {
+ rotPath[index].fY = cubic[zero].fY;
+ int mask = other_two(index, zero);
+ int side1 = index ^ mask;
+ int side2 = zero ^ mask;
+ if (approximately_equal(cubic[side1].fY, cubic[zero].fY)) {
+ rotPath[side1].fY = cubic[zero].fY;
+ }
+ if (approximately_equal(cubic[side2].fY, cubic[zero].fY)) {
+ rotPath[side2].fY = cubic[zero].fY;
+ }
+ }
return true;
}
for (int index = 0; index < 4; ++index) {
@@ -81,8 +93,19 @@
order[2] = 2;
return 3;
}
- SkASSERT(fPts[2] == fPts[0] || fPts[2] == fPts[3]);
- order[2] = 1;
+ if (fPts[2] == fPts[0] || fPts[2] == fPts[3]) {
+ order[2] = 1;
+ return 3;
+ }
+ // one of the control points may be very nearly but not exactly equal --
+ double dist1_0 = fPts[1].distanceSquared(fPts[0]);
+ double dist1_3 = fPts[1].distanceSquared(fPts[3]);
+ double dist2_0 = fPts[2].distanceSquared(fPts[0]);
+ double dist2_3 = fPts[2].distanceSquared(fPts[3]);
+ double smallest1distSq = SkTMin(dist1_0, dist1_3);
+ double smallest2distSq = SkTMin(dist2_0, dist2_3);
+ SkASSERT(approximately_zero(SkTMin(smallest1distSq, smallest2distSq)));
+ order[2] = smallest1distSq < smallest2distSq ? 2 : 1;
return 3;
}
midX = index;
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index e3dc139..24ca9b1 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -73,8 +73,6 @@
fUnparseable = true;
return 0;
}
- SkAutoConicToQuads quadder;
- const SkScalar quadderTol = SK_Scalar1 / 16;
SkPath::RawIter iter(*fPath);
SkPoint curveStart;
SkPoint curve[4];
@@ -114,18 +112,16 @@
continue; // skip degenerate points
}
break;
- case SkPath::kConic_Verb: {
- const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
- quadderTol);
- const int nQuads = quadder.countQuads();
- for (int i = 0; i < nQuads; ++i) {
- *fPathVerbs.append() = SkPath::kQuad_Verb;
- }
- fPathPts.append(nQuads * 2, &quadPts[1]);
- curve[0] = pts[2];
- lastCurve = true;
+ case SkPath::kConic_Verb:
+ force_small_to_zero(&pts[1]);
+ force_small_to_zero(&pts[2]);
+ curve[1] = pts[1];
+ curve[2] = pts[2];
+ verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts);
+ if (verb == SkPath::kMove_Verb) {
+ continue; // skip degenerate points
}
- continue;
+ break;
case SkPath::kCubic_Verb:
force_small_to_zero(&pts[1]);
force_small_to_zero(&pts[2]);
@@ -148,6 +144,9 @@
*fPathVerbs.append() = verb;
int ptCount = SkPathOpsVerbToPoints(verb);
fPathPts.append(ptCount, &pts[1]);
+ if (verb == SkPath::kConic_Verb) {
+ *fWeights.append() = iter.conicWeight();
+ }
curve[0] = pts[ptCount];
lastCurve = true;
} while (verb != SkPath::kDone_Verb);
@@ -167,6 +166,7 @@
uint8_t* verbPtr = fPathVerbs.begin();
uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
SkPoint* pointsPtr = fPathPts.begin() - 1;
+ SkScalar* weightPtr = fWeights.begin();
SkPath::Verb verb;
while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
if (verbPtr == endOfFirstHalf) {
@@ -195,6 +195,9 @@
case SkPath::kQuad_Verb:
fCurrentContour->addQuad(pointsPtr, fAllocator);
break;
+ case SkPath::kConic_Verb:
+ fCurrentContour->addConic(pointsPtr, *weightPtr++, fAllocator);
+ break;
case SkPath::kCubic_Verb: {
// split self-intersecting cubics in two before proceeding
// if the cubic is convex, it doesn't self intersect.
@@ -202,6 +205,9 @@
if (SkDCubic::ComplexBreak(pointsPtr, &loopT)) {
SkPoint cubicPair[7];
SkChopCubicAt(pointsPtr, cubicPair, loopT);
+ if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cubicPair) * 2)) {
+ return false;
+ }
SkPoint cStorage[2][4];
SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]);
SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]);
diff --git a/src/pathops/SkOpEdgeBuilder.h b/src/pathops/SkOpEdgeBuilder.h
index 3ecc915..f81f727 100644
--- a/src/pathops/SkOpEdgeBuilder.h
+++ b/src/pathops/SkOpEdgeBuilder.h
@@ -62,6 +62,7 @@
SkOpGlobalState* fGlobalState;
const SkPath* fPath;
SkTDArray<SkPoint> fPathPts;
+ SkTDArray<SkScalar> fWeights;
SkTDArray<uint8_t> fPathVerbs;
SkOpContour* fCurrentContour;
SkOpContour* fContoursHead;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index c6ccf93..161eb33 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -122,8 +122,7 @@
}
}
if (fVerb != SkPath::kLine_Verb && !lastDone) {
- SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT,
- span->t());
+ SkPoint curveTop = (*CurveTop[fVerb])(fPts, fWeight, lastT, span->t());
if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
&& topPt.fX > curveTop.fX)) {
topPt = curveTop;
@@ -202,14 +201,17 @@
void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
SkPathWriter* path, bool active) const {
- SkPoint edge[4];
+ SkOpCurve edge;
const SkPoint* ePtr;
+ SkScalar eWeight;
if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) {
ePtr = fPts;
+ eWeight = fWeight;
} else {
// OPTIMIZE? if not active, skip remainder and return xyAtT(end)
- subDivide(start, end, edge);
- ePtr = edge;
+ subDivide(start, end, &edge);
+ ePtr = edge.fPts;
+ eWeight = edge.fWeight;
}
if (active) {
bool reverse = ePtr == fPts && start != &fHead;
@@ -222,6 +224,9 @@
case SkPath::kQuad_Verb:
path->quadTo(ePtr[1], ePtr[0]);
break;
+ case SkPath::kConic_Verb:
+ path->conicTo(ePtr[1], ePtr[0], eWeight);
+ break;
case SkPath::kCubic_Verb:
path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
break;
@@ -237,6 +242,9 @@
case SkPath::kQuad_Verb:
path->quadTo(ePtr[1], ePtr[2]);
break;
+ case SkPath::kConic_Verb:
+ path->conicTo(ePtr[1], ePtr[2], eWeight);
+ break;
case SkPath::kCubic_Verb:
path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
break;
@@ -294,6 +302,9 @@
break;
}
}
+ if (!oStartSpan) {
+ return NULL;
+ }
SkOpAngle* oAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
oAngle->set(oStartSpan, oEndSpan);
oStartSpan->setToAngle(oAngle);
@@ -309,6 +320,9 @@
} else {
otherAngle = addSingletonAngleDown(&other, &angle, allocator);
}
+ if (!otherAngle) {
+ return NULL;
+ }
angle->insert(otherAngle);
return angle;
}
@@ -476,7 +490,7 @@
// from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
bool SkOpSegment::clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const {
SkASSERT(fVerb != SkPath::kLine_Verb);
- SkPoint edge[4];
+ SkOpCurve edge;
if (fVerb == SkPath::kCubic_Verb) {
double startT = start->t();
double endT = end->t();
@@ -489,22 +503,20 @@
double inflectionT = inflectionTs[index];
if (between(startT, inflectionT, endT)) {
if (flip) {
- if (inflectionT != endT) {
- startT = inflectionT;
+ if (!roughly_equal(inflectionT, endT)) {
+ startT = inflectionT;
}
} else {
- if (inflectionT != startT) {
+ if (!roughly_equal(inflectionT, startT)) {
endT = inflectionT;
}
}
}
}
SkDCubic part = cubic.subDivide(startT, endT);
- for (int index = 0; index < 4; ++index) {
- edge[index] = part[index].asSkPoint();
- }
+ edge.set(part);
} else {
- subDivide(start, end, edge);
+ subDivide(start, end, &edge);
}
bool sumSet = false;
int points = SkPathOpsVerbToPoints(fVerb);
@@ -516,11 +528,11 @@
}
if (fVerb == SkPath::kCubic_Verb) {
SkDCubic cubic;
- cubic.set(edge);
+ cubic.set(edge.fPts);
*swap = sum > 0 && !cubic.monotonicInY();
} else {
SkDQuad quad;
- quad.set(edge);
+ quad.set(edge.fPts);
*swap = sum > 0 && !quad.monotonicInY();
}
return sum <= 0;
@@ -682,8 +694,7 @@
// OPTIMIZE: use specialty function that intersects ray with curve,
// returning t values only for curve (we don't care about t on ray)
intersections.allowNear(false);
- int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
- (fPts, top, bottom, basePt.fX, false);
+ int pts = (intersections.*CurveVertical[fVerb])(fPts, fWeight, top, bottom, basePt.fX, false);
if (pts == 0 || (current && pts == 1)) {
return NULL;
}
@@ -707,7 +718,7 @@
|| approximately_greater_than_one(foundT)) {
continue;
}
- SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
+ SkScalar testY = (*CurvePointAtT[fVerb])(fPts, fWeight, foundT).fY;
if (approximately_negative(testY - *bestY)
|| approximately_negative(basePt.fY - testY)) {
continue;
@@ -717,7 +728,7 @@
return NULL; // if the intersection is edge on, wait for another one
}
if (fVerb > SkPath::kLine_Verb) {
- SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
+ SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, foundT).fX;
if (approximately_zero(dx)) {
*vertical = true;
return NULL; // hit vertical, wait for another one
@@ -767,8 +778,7 @@
testPerp[1].fY -= slope.fX;
SkIntersections i;
SkOpSegment* oppSegment = oppAngle->segment();
- int oppPtCount = SkPathOpsVerbToPoints(oppSegment->verb());
- (*CurveIntersectRay[oppPtCount])(oppSegment->pts(), testPerp, &i);
+ (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
double closestDistSq = SK_ScalarInfinity;
for (int index = 0; index < i.used(); ++index) {
if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
@@ -1092,7 +1102,12 @@
if (!markAngle) {
markAngle = addSingletonAngles(step, allocator);
}
- markAngle->markStops();
+ if (!markAngle) {
+ return NULL;
+ }
+ if (!markAngle->markStops()) {
+ return NULL;
+ }
const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle
: markAngle->findFirst();
if (!baseAngle) {
@@ -1161,6 +1176,7 @@
SkTSwap(*startPtr, *endPtr);
}
}
+ // FIXME: clockwise isn't reliable -- try computing swap from tangent ?
}
return leftSegment;
}
@@ -1169,10 +1185,11 @@
return contour()->globalState();
}
-void SkOpSegment::init(SkPoint pts[], SkOpContour* contour, SkPath::Verb verb) {
+void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
fContour = contour;
fNext = NULL;
fPts = pts;
+ fWeight = weight;
fVerb = verb;
fCount = 0;
fDoneCount = 0;
@@ -1182,7 +1199,7 @@
SkOpSpanBase* oneSpan = &fTail;
zeroSpan->setNext(oneSpan);
oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
- PATH_OPS_DEBUG_CODE(fID = globalState()->nextSegmentID());
+ SkDEBUGCODE(fID = globalState()->nextSegmentID());
}
void SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end,
@@ -1215,7 +1232,7 @@
int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx) {
SkASSERT(this == start->segment());
SkASSERT(hitDx || !winding);
- SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
+ SkScalar dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX;
// SkASSERT(dx);
int windVal = start->starter(end)->windValue();
#if DEBUG_WINDING_AT_T
@@ -1249,12 +1266,10 @@
bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
SkDPoint cPt = this->dPtAtT(t);
- int pts = SkPathOpsVerbToPoints(this->verb());
- SkDVector dxdy = (*CurveDSlopeAtT[pts])(this->pts(), t);
+ SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
SkIntersections i;
- int oppPts = SkPathOpsVerbToPoints(opp->verb());
- (*CurveIntersectRay[oppPts])(opp->pts(), perp, &i);
+ (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
int used = i.used();
for (int index = 0; index < used; ++index) {
if (cPt.roughlyEqual(i.pt(index))) {
@@ -1453,6 +1468,10 @@
SkDQuad dst = SkDQuad::SubDivide(fPts, start->t(), end->t());
return dst.monotonicInY();
}
+ if (fVerb == SkPath::kConic_Verb) {
+ SkDConic dst = SkDConic::SubDivide(fPts, fWeight, start->t(), end->t());
+ return dst.monotonicInY();
+ }
SkASSERT(fVerb == SkPath::kCubic_Verb);
SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t());
return dst.monotonicInY();
@@ -1615,18 +1634,16 @@
&& !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
coincident = false;
SkIntersections i;
- int ptCount = SkPathOpsVerbToPoints(this->verb());
- SkVector dxdy = (*CurveSlopeAtT[ptCount])(pts(), midT);
+ SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
SkDLine ray = {{{midPt.fX, midPt.fY},
{midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
- int oppPtCount = SkPathOpsVerbToPoints(opp->verb());
- (*CurveIntersectRay[oppPtCount])(opp->pts(), ray, &i);
+ (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
// measure distance and see if it's small enough to denote coincidence
for (int index = 0; index < i.used(); ++index) {
SkDPoint oppPt = i.pt(index);
if (oppPt.approximatelyEqual(midPt)) {
- SkVector oppDxdy = (*CurveSlopeAtT[oppPtCount])(opp->pts(),
- i[index][0]);
+ SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
+ opp->weight(), i[index][0]);
oppDxdy.normalize();
dxdy.normalize();
SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
@@ -1829,13 +1846,15 @@
// return true if midpoints were computed
bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
- SkPoint edge[4]) const {
+ SkOpCurve* edge) const {
SkASSERT(start != end);
const SkOpPtT& startPtT = *start->ptT();
const SkOpPtT& endPtT = *end->ptT();
- edge[0] = startPtT.fPt;
+ SkDEBUGCODE(edge->fVerb = fVerb);
+ edge->fPts[0] = startPtT.fPt;
int points = SkPathOpsVerbToPoints(fVerb);
- edge[points] = endPtT.fPt;
+ edge->fPts[points] = endPtT.fPt;
+ edge->fWeight = 1;
if (fVerb == SkPath::kLine_Verb) {
return false;
}
@@ -1844,40 +1863,50 @@
if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
// don't compute midpoints if we already have them
if (fVerb == SkPath::kQuad_Verb) {
- edge[1] = fPts[1];
+ edge->fPts[1] = fPts[1];
+ return false;
+ }
+ if (fVerb == SkPath::kConic_Verb) {
+ edge->fPts[1] = fPts[1];
+ edge->fWeight = fWeight;
return false;
}
SkASSERT(fVerb == SkPath::kCubic_Verb);
if (start < end) {
- edge[1] = fPts[1];
- edge[2] = fPts[2];
+ edge->fPts[1] = fPts[1];
+ edge->fPts[2] = fPts[2];
return false;
}
- edge[1] = fPts[2];
- edge[2] = fPts[1];
+ edge->fPts[1] = fPts[2];
+ edge->fPts[2] = fPts[1];
return false;
}
- const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
+ const SkDPoint sub[2] = {{ edge->fPts[0].fX, edge->fPts[0].fY},
+ {edge->fPts[points].fX, edge->fPts[points].fY }};
if (fVerb == SkPath::kQuad_Verb) {
- edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
+ edge->fPts[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
+ } else if (fVerb == SkPath::kConic_Verb) {
+ edge->fPts[1] = SkDConic::SubDivide(fPts, fWeight, sub[0], sub[1],
+ startT, endT, &edge->fWeight).asSkPoint();
} else {
SkASSERT(fVerb == SkPath::kCubic_Verb);
SkDPoint ctrl[2];
SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
- edge[1] = ctrl[0].asSkPoint();
- edge[2] = ctrl[1].asSkPoint();
+ edge->fPts[1] = ctrl[0].asSkPoint();
+ edge->fPts[2] = ctrl[1].asSkPoint();
}
return true;
}
bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
- SkDCubic* result) const {
+ SkDCurve* edge) const {
SkASSERT(start != end);
const SkOpPtT& startPtT = *start->ptT();
const SkOpPtT& endPtT = *end->ptT();
- (*result)[0].set(startPtT.fPt);
+ SkDEBUGCODE(edge->fVerb = fVerb);
+ edge->fCubic[0].set(startPtT.fPt);
int points = SkPathOpsVerbToPoints(fVerb);
- (*result)[points].set(endPtT.fPt);
+ edge->fCubic[points].set(endPtT.fPt);
if (fVerb == SkPath::kLine_Verb) {
return false;
}
@@ -1886,33 +1915,41 @@
if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
// don't compute midpoints if we already have them
if (fVerb == SkPath::kQuad_Verb) {
- (*result)[1].set(fPts[1]);
+ edge->fLine[1].set(fPts[1]);
+ return false;
+ }
+ if (fVerb == SkPath::kConic_Verb) {
+ edge->fConic[1].set(fPts[1]);
+ edge->fConic.fWeight = fWeight;
return false;
}
SkASSERT(fVerb == SkPath::kCubic_Verb);
if (startT == 0) {
- (*result)[1].set(fPts[1]);
- (*result)[2].set(fPts[2]);
+ edge->fCubic[1].set(fPts[1]);
+ edge->fCubic[2].set(fPts[2]);
return false;
}
- (*result)[1].set(fPts[2]);
- (*result)[2].set(fPts[1]);
+ edge->fCubic[1].set(fPts[2]);
+ edge->fCubic[2].set(fPts[1]);
return false;
}
if (fVerb == SkPath::kQuad_Verb) {
- (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
+ edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
+ } else if (fVerb == SkPath::kConic_Verb) {
+ edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
+ startT, endT, &edge->fConic.fWeight);
} else {
SkASSERT(fVerb == SkPath::kCubic_Verb);
- SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
+ SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
}
return true;
}
void SkOpSegment::subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end,
SkPathOpsBounds* bounds) const {
- SkPoint edge[4];
- subDivide(start, end, edge);
- (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
+ SkOpCurve edge;
+ subDivide(start, end, &edge);
+ (bounds->*SetCurveBounds[fVerb])(edge.fPts, edge.fWeight);
}
void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) {
@@ -2001,7 +2038,7 @@
debugID(), crossOpp, tHit, span->t(), winding, windVal);
#endif
// see if a + change in T results in a +/- change in X (compute x'(T))
- *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
+ *dx = (*CurveSlopeAtT[fVerb])(fPts, fWeight, tHit).fX;
if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
*dx = fPts[2].fX - fPts[1].fX - *dx;
}
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index c1c6e69..65ed95c 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -13,6 +13,7 @@
#include "SkPathOpsBounds.h"
#include "SkPathOpsCurve.h"
+struct SkDCurve;
class SkOpCoincidence;
class SkOpContour;
class SkPathWriter;
@@ -44,9 +45,14 @@
bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end);
bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding);
+ void addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) {
+ init(pts, weight, parent, SkPath::kConic_Verb);
+ fBounds.setConicBounds(pts, weight);
+ }
+
void addCubic(SkPoint pts[4], SkOpContour* parent) {
- init(pts, parent, SkPath::kCubic_Verb);
- fBounds.setCubicBounds(pts);
+ init(pts, 1, parent, SkPath::kCubic_Verb);
+ fBounds.setCubicBounds(pts, 1);
}
void addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path,
@@ -60,7 +66,7 @@
}
void addLine(SkPoint pts[2], SkOpContour* parent) {
- init(pts, parent, SkPath::kLine_Verb);
+ init(pts, 1, parent, SkPath::kLine_Verb);
fBounds.set(pts, 2);
}
@@ -77,8 +83,8 @@
}
void addQuad(SkPoint pts[3], SkOpContour* parent) {
- init(pts, parent, SkPath::kQuad_Verb);
- fBounds.setQuadBounds(pts);
+ init(pts, 1, parent, SkPath::kQuad_Verb);
+ fBounds.setQuadBounds(pts, 1);
}
SkOpPtT* addT(double t, AllowAlias , SkChunkAlloc* );
@@ -120,7 +126,7 @@
SkOpContour* debugContour(int id);
int debugID() const {
- return PATH_OPS_DEBUG_RELEASE(fID, -1);
+ return SkDEBUGRELEASE(fID, -1);
}
#if DEBUG_SWAP_TOP
@@ -155,11 +161,11 @@
}
SkDPoint dPtAtT(double mid) const {
- return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
+ return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid);
}
SkDVector dSlopeAtT(double mid) const {
- return (*CurveDSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
+ return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid);
}
void dump() const;
@@ -186,7 +192,7 @@
return &fHead;
}
- void init(SkPoint pts[], SkOpContour* parent, SkPath::Verb verb);
+ void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb);
void initWinding(SkOpSpanBase* start, SkOpSpanBase* end,
SkOpAngle::IncludeType angleIncludeType);
bool initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHit, int winding,
@@ -220,7 +226,7 @@
}
bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const {
- return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start->t(), end->t());
+ return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t());
}
bool isXor() const;
@@ -266,7 +272,7 @@
}
SkPoint ptAtT(double mid) const {
- return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
+ return (*CurvePointAtT[fVerb])(fPts, fWeight, mid);
}
const SkPoint* pts() const {
@@ -329,8 +335,8 @@
return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle();
}
- bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPoint edge[4]) const;
- bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCubic* result) const;
+ bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const;
+ bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkOpCurve* result) const;
void subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end,
SkPathOpsBounds* bounds) const;
@@ -360,6 +366,10 @@
return fVerb;
}
+ SkScalar weight() const {
+ return fWeight;
+ }
+
int windingAtT(double tHit, const SkOpSpan* span, bool crossOpp, SkScalar* dx) const;
int windSum(const SkOpAngle* angle) const;
@@ -375,11 +385,12 @@
const SkOpSegment* fPrev;
SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked
SkPathOpsBounds fBounds; // tight bounds
+ SkScalar fWeight;
int fCount; // number of spans (one for a non-intersecting segment)
int fDoneCount; // number of processed spans (zero initially)
SkPath::Verb fVerb;
bool fVisited; // used by missing coincidence check
- PATH_OPS_DEBUG_CODE(int fID);
+ SkDEBUGCODE(int fID);
};
#endif
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index 37d5120..32d2376 100755
--- a/src/pathops/SkOpSpan.cpp
+++ b/src/pathops/SkOpSpan.cpp
@@ -28,7 +28,7 @@
fNext = this;
fDuplicatePt = duplicate;
fDeleted = false;
- PATH_OPS_DEBUG_CODE(fID = span->globalState()->nextPtTID());
+ SkDEBUGCODE(fID = span->globalState()->nextPtTID());
}
bool SkOpPtT::onEnd() const {
@@ -89,13 +89,15 @@
// find the starting or ending span with an existing loop of angles
// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
// FIXME? assert that only one other span has a valid windValue or oppValue
-void SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) {
+bool SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) {
SkOpAngle* angle;
if (checkFrom) {
- SkASSERT(this->final());
+ if (!this->final()) {
+ return false;
+ }
if (this->fromAngle()) {
SkASSERT(this->fromAngle()->loopCount() == 2);
- return;
+ return true;
}
angle = this->segment()->addEndSpan(allocator);
} else {
@@ -105,7 +107,7 @@
SkASSERT(span->toAngle()->loopCount() == 2);
SkASSERT(!span->fromAngle());
span->setFromAngle(span->toAngle()->next());
- return;
+ return true;
}
angle = this->segment()->addStartSpan(allocator);
}
@@ -140,6 +142,7 @@
SkASSERT(oAngle == oSpanBase->fromAngle());
}
angle->insert(oAngle);
+ return true;
}
void SkOpSpanBase::align() {
@@ -274,8 +277,8 @@
fPrev = prev;
fAligned = true;
fChased = false;
- PATH_OPS_DEBUG_CODE(fCount = 1);
- PATH_OPS_DEBUG_CODE(fID = globalState()->nextSpanID());
+ SkDEBUGCODE(fCount = 1);
+ SkDEBUGCODE(fID = globalState()->nextSpanID());
}
// this pair of spans share a common t value or point; merge them and eliminate duplicates
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 9e5939a..bf03f4d 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -50,7 +50,7 @@
SkOpContour* contour() const;
int debugID() const {
- return PATH_OPS_DEBUG_RELEASE(fID, -1);
+ return SkDEBUGRELEASE(fID, -1);
}
const SkOpAngle* debugAngle(int id) const;
@@ -119,12 +119,12 @@
SkOpPtT* fNext; // intersection on opposite curve or alias on this curve
bool fDeleted; // set if removed from span list
bool fDuplicatePt; // set if identical pt is somewhere in the next loop
- PATH_OPS_DEBUG_CODE(int fID);
+ SkDEBUGCODE(int fID);
};
class SkOpSpanBase {
public:
- void addSimpleAngle(bool checkFrom , SkChunkAlloc* );
+ bool addSimpleAngle(bool checkFrom , SkChunkAlloc* );
void align();
bool aligned() const {
@@ -164,11 +164,11 @@
SkOpContour* contour() const;
int debugBumpCount() {
- return PATH_OPS_DEBUG_RELEASE(++fCount, -1);
+ return SkDEBUGRELEASE(++fCount, -1);
}
int debugID() const {
- return PATH_OPS_DEBUG_RELEASE(fID, -1);
+ return SkDEBUGRELEASE(fID, -1);
}
const SkOpAngle* debugAngle(int id) const;
@@ -318,8 +318,8 @@
SkOpSpan* fPrev; // previous intersection point
bool fAligned;
bool fChased; // set after span has been added to chase array
- PATH_OPS_DEBUG_CODE(int fCount); // number of pt/t pairs added
- PATH_OPS_DEBUG_CODE(int fID);
+ SkDEBUGCODE(int fCount); // number of pt/t pairs added
+ SkDEBUGCODE(int fID);
};
class SkOpSpan : public SkOpSpanBase {
diff --git a/src/pathops/SkPathOpsBounds.cpp b/src/pathops/SkPathOpsBounds.cpp
index e5b26ee..ea13e2e 100644
--- a/src/pathops/SkPathOpsBounds.cpp
+++ b/src/pathops/SkPathOpsBounds.cpp
@@ -5,11 +5,21 @@
* found in the LICENSE file.
*/
#include "SkPathOpsBounds.h"
+#include "SkPathOpsConic.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
-void SkPathOpsBounds::setCubicBounds(const SkPoint a[4]) {
+void SkPathOpsBounds::setConicBounds(const SkPoint a[3], SkScalar weight) {
+ SkDConic conic;
+ conic.set(a, weight);
+ SkDRect dRect;
+ dRect.setBounds(conic);
+ set(SkDoubleToScalar(dRect.fLeft), SkDoubleToScalar(dRect.fTop),
+ SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
+}
+
+void SkPathOpsBounds::setCubicBounds(const SkPoint a[4], SkScalar ) {
SkDCubic cubic;
cubic.set(a);
SkDRect dRect;
@@ -18,12 +28,12 @@
SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
}
-void SkPathOpsBounds::setLineBounds(const SkPoint a[2]) {
+void SkPathOpsBounds::setLineBounds(const SkPoint a[2], SkScalar ) {
setPointBounds(a[0]);
add(a[1]);
}
-void SkPathOpsBounds::setQuadBounds(const SkPoint a[3]) {
+void SkPathOpsBounds::setQuadBounds(const SkPoint a[3], SkScalar ) {
SkDQuad quad;
quad.set(a);
SkDRect dRect;
@@ -32,9 +42,10 @@
SkDoubleToScalar(dRect.fRight), SkDoubleToScalar(dRect.fBottom));
}
-void (SkPathOpsBounds::* const SetCurveBounds[])(const SkPoint[]) = {
+void (SkPathOpsBounds::* const SetCurveBounds[])(const SkPoint[], SkScalar weight) = {
NULL,
&SkPathOpsBounds::setLineBounds,
&SkPathOpsBounds::setQuadBounds,
+ &SkPathOpsBounds::setConicBounds,
&SkPathOpsBounds::setCubicBounds
};
diff --git a/src/pathops/SkPathOpsBounds.h b/src/pathops/SkPathOpsBounds.h
index cabc639..b65d3be 100644
--- a/src/pathops/SkPathOpsBounds.h
+++ b/src/pathops/SkPathOpsBounds.h
@@ -55,9 +55,10 @@
|| (fLeft == fRight && fTop == fBottom);
}
- void setCubicBounds(const SkPoint a[4]);
- void setLineBounds(const SkPoint a[2]);
- void setQuadBounds(const SkPoint a[3]);
+ void setConicBounds(const SkPoint a[3], SkScalar weight);
+ void setCubicBounds(const SkPoint a[4], SkScalar );
+ void setLineBounds(const SkPoint a[2], SkScalar );
+ void setQuadBounds(const SkPoint a[3], SkScalar );
void setPointBounds(const SkPoint& pt) {
fLeft = fRight = pt.fX;
@@ -67,6 +68,6 @@
typedef SkRect INHERITED;
};
-extern void (SkPathOpsBounds::* const SetCurveBounds[])(const SkPoint[]);
+extern void (SkPathOpsBounds::* const SetCurveBounds[])(const SkPoint[], SkScalar weight);
#endif
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 1dc171c..a16e811 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -323,7 +323,10 @@
do {
bool checkFrom = oSpan->t() < iSpan->t();
if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) {
- iSpan->addSimpleAngle(checkFrom, allocator);
+ if (!iSpan->addSimpleAngle(checkFrom, allocator)) {
+ *unsortable = true;
+ return NULL;
+ }
}
sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType);
SkTSwap(iSpan, oSpan);
@@ -442,7 +445,7 @@
void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
SkOpContour contour;
- SkOpGlobalState globalState(NULL PATH_OPS_DEBUG_PARAMS(&contour));
+ SkOpGlobalState globalState(NULL SkDEBUGPARAMS(&contour));
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("%s\n", __FUNCTION__);
#endif
diff --git a/src/pathops/SkPathOpsConic.cpp b/src/pathops/SkPathOpsConic.cpp
new file mode 100644
index 0000000..1b544e4
--- /dev/null
+++ b/src/pathops/SkPathOpsConic.cpp
@@ -0,0 +1,132 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkIntersections.h"
+#include "SkLineParameters.h"
+#include "SkPathOpsConic.h"
+#include "SkPathOpsCubic.h"
+#include "SkPathOpsQuad.h"
+
+// cribbed from the float version in SkGeometry.cpp
+static void conic_deriv_coeff(const double src[],
+ SkScalar w,
+ double coeff[3]) {
+ const double P20 = src[4] - src[0];
+ const double P10 = src[2] - src[0];
+ const double wP10 = w * P10;
+ coeff[0] = w * P20 - P20;
+ coeff[1] = P20 - 2 * wP10;
+ coeff[2] = wP10;
+}
+
+static double conic_eval_tan(const double coord[], SkScalar w, double t) {
+ double coeff[3];
+ conic_deriv_coeff(coord, w, coeff);
+ return t * (t * coeff[0] + coeff[1]) + coeff[2];
+}
+
+int SkDConic::FindExtrema(const double src[], SkScalar w, double t[1]) {
+ double coeff[3];
+ conic_deriv_coeff(src, w, coeff);
+
+ double tValues[2];
+ int roots = SkDQuad::RootsValidT(coeff[0], coeff[1], coeff[2], tValues);
+ SkASSERT(0 == roots || 1 == roots);
+
+ if (1 == roots) {
+ t[0] = tValues[0];
+ return 1;
+ }
+ return 0;
+}
+
+SkDVector SkDConic::dxdyAtT(double t) const {
+ SkDVector result = {
+ conic_eval_tan(&fPts[0].fX, fWeight, t),
+ conic_eval_tan(&fPts[0].fY, fWeight, t)
+ };
+ return result;
+}
+
+static double conic_eval_numerator(const double src[], SkScalar w, double t) {
+ SkASSERT(src);
+ SkASSERT(t >= 0 && t <= 1);
+ double src2w = src[2] * w;
+ double C = src[0];
+ double A = src[4] - 2 * src2w + C;
+ double B = 2 * (src2w - C);
+ return (A * t + B) * t + C;
+}
+
+
+static double conic_eval_denominator(SkScalar w, double t) {
+ double B = 2 * (w - 1);
+ double C = 1;
+ double A = -B;
+ return (A * t + B) * t + C;
+}
+
+bool SkDConic::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
+ return cubic.hullIntersects(*this, isLinear);
+}
+
+SkDPoint SkDConic::ptAtT(double t) const {
+ double denominator = conic_eval_denominator(fWeight, t);
+ SkDPoint result = {
+ conic_eval_numerator(&fPts[0].fX, fWeight, t) / denominator,
+ conic_eval_numerator(&fPts[0].fY, fWeight, t) / denominator
+ };
+ return result;
+}
+
+SkDPoint SkDConic::top(double startT, double endT) const {
+ SkDConic sub = subDivide(startT, endT);
+ SkDPoint topPt = sub[0];
+ if (topPt.fY > sub[2].fY || (topPt.fY == sub[2].fY && topPt.fX > sub[2].fX)) {
+ topPt = sub[2];
+ }
+ if (!between(sub[0].fY, sub[1].fY, sub[2].fY)) {
+ double extremeT;
+ if (FindExtrema(&sub[0].fY, sub.fWeight, &extremeT)) {
+ extremeT = startT + (endT - startT) * extremeT;
+ SkDPoint test = ptAtT(extremeT);
+ if (topPt.fY > test.fY || (topPt.fY == test.fY && topPt.fX > test.fX)) {
+ topPt = test;
+ }
+ }
+ }
+ return topPt;
+}
+
+/* see quad subdivide for rationale */
+SkDConic SkDConic::subDivide(double t1, double t2) const {
+ double ax = conic_eval_numerator(&fPts[0].fX, fWeight, t1);
+ double ay = conic_eval_numerator(&fPts[0].fY, fWeight, t1);
+ double az = conic_eval_denominator(fWeight, t1);
+ double midT = (t1 + t2) / 2;
+ double dx = conic_eval_numerator(&fPts[0].fX, fWeight, midT);
+ double dy = conic_eval_numerator(&fPts[0].fY, fWeight, midT);
+ double dz = conic_eval_denominator(fWeight, midT);
+ double cx = conic_eval_numerator(&fPts[0].fX, fWeight, t2);
+ double cy = conic_eval_numerator(&fPts[0].fY, fWeight, t2);
+ double cz = conic_eval_denominator(fWeight, t2);
+ double bx = 2 * dx - (ax + cx) / 2;
+ double by = 2 * dy - (ay + cy) / 2;
+ double bz = 2 * dz - (az + cz) / 2;
+ double dt = t2 - t1;
+ double dt_1 = 1 - dt;
+ SkScalar w = SkDoubleToScalar((1 + dt * (fWeight - 1))
+ / sqrt(dt * dt + 2 * dt * dt_1 * fWeight + dt_1 * dt_1));
+ SkDConic dst = {{{{ax / az, ay / az}, {bx / bz, by / bz}, {cx / cz, cy / cz}}}, w };
+ return dst;
+}
+
+SkDPoint SkDConic::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2,
+ SkScalar* weight) const {
+ SkDConic chopped = this->subDivide(t1, t2);
+ *weight = chopped.fWeight;
+ return chopped[1];
+}
diff --git a/src/pathops/SkPathOpsConic.h b/src/pathops/SkPathOpsConic.h
new file mode 100644
index 0000000..dce7032
--- /dev/null
+++ b/src/pathops/SkPathOpsConic.h
@@ -0,0 +1,121 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkPathOpsConic_DEFINED
+#define SkPathOpsConic_DEFINED
+
+#include "SkPathOpsPoint.h"
+#include "SkPathOpsQuad.h"
+
+struct SkDConic {
+ static const int kPointCount = 3;
+ static const int kPointLast = kPointCount - 1;
+ static const int kMaxIntersections = 4;
+
+ SkDQuad fPts;
+ SkScalar fWeight;
+
+ bool collapsed() const {
+ return fPts.collapsed();
+ }
+
+ bool controlsInside() const {
+ return fPts.controlsInside();
+ }
+
+ void debugInit() {
+ fPts.debugInit();
+ }
+
+ SkDConic flip() const {
+ SkDConic result = {{{fPts[2], fPts[1], fPts[0]}}, fWeight};
+ return result;
+ }
+
+ static bool IsCubic() { return false; }
+
+ const SkDConic& set(const SkPoint pts[kPointCount], SkScalar weight) {
+ fPts.set(pts);
+ fWeight = weight;
+ return *this;
+ }
+
+ const SkDPoint& operator[](int n) const { return fPts[n]; }
+ SkDPoint& operator[](int n) { return fPts[n]; }
+
+ static int AddValidTs(double s[], int realRoots, double* t) {
+ return SkDQuad::AddValidTs(s, realRoots, t);
+ }
+
+ void align(int endIndex, SkDPoint* dstPt) const {
+ fPts.align(endIndex, dstPt);
+ }
+
+ SkDVector dxdyAtT(double t) const;
+ static int FindExtrema(const double src[], SkScalar weight, double tValue[1]);
+
+ bool hullIntersects(const SkDQuad& quad, bool* isLinear) const {
+ return fPts.hullIntersects(quad, isLinear);
+ }
+
+ bool hullIntersects(const SkDConic& conic, bool* isLinear) const {
+ return fPts.hullIntersects(conic.fPts, isLinear);
+ }
+
+ bool hullIntersects(const SkDCubic& cubic, bool* isLinear) const;
+
+ bool isLinear(int startIndex, int endIndex) const {
+ return fPts.isLinear(startIndex, endIndex);
+ }
+
+ bool monotonicInY() const {
+ return fPts.monotonicInY();
+ }
+
+ void otherPts(int oddMan, const SkDPoint* endPt[2]) const {
+ fPts.otherPts(oddMan, endPt);
+ }
+
+ SkDPoint ptAtT(double t) const;
+
+ static int RootsReal(double A, double B, double C, double t[2]) {
+ return SkDQuad::RootsReal(A, B, C, t);
+ }
+
+ static int RootsValidT(const double A, const double B, const double C, double s[2]) {
+ return SkDQuad::RootsValidT(A, B, C, s);
+ }
+
+ SkDConic subDivide(double t1, double t2) const;
+
+ static SkDConic SubDivide(const SkPoint a[kPointCount], SkScalar weight, double t1, double t2) {
+ SkDConic conic;
+ conic.set(a, weight);
+ return conic.subDivide(t1, t2);
+ }
+
+ SkDPoint subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2,
+ SkScalar* weight) const;
+
+ static SkDPoint SubDivide(const SkPoint pts[kPointCount], SkScalar weight,
+ const SkDPoint& a, const SkDPoint& c,
+ double t1, double t2, SkScalar* newWeight) {
+ SkDConic conic;
+ conic.set(pts, weight);
+ return conic.subDivide(a, c, t1, t2, newWeight);
+ }
+
+ SkDPoint top(double startT, double endT) const;
+
+ // utilities callable by the user from the debugger when the implementation code is linked in
+ void dump() const;
+ void dumpID(int id) const;
+ void dumpInner() const;
+};
+
+
+#endif
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index d4a5898..a44d29b 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -6,6 +6,7 @@
*/
#include "SkGeometry.h"
#include "SkLineParameters.h"
+#include "SkPathOpsConic.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
@@ -105,7 +106,7 @@
/* if returning true, check contains true if cubic's hull collapsed, making the cubic linear
if returning false, check contains true if the the cubic pair have only the end point in common
*/
-bool SkDCubic::hullIntersects(const SkDCubic& c2, bool* isLinear) const {
+bool SkDCubic::hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const {
bool linear = true;
char hullOrder[4];
int hullCount = convexHull(hullOrder);
@@ -137,8 +138,8 @@
}
linear = false;
bool foundOutlier = false;
- for (int n = 0; n < kPointCount; ++n) {
- double test = (c2[n].fY - origY) * adj - (c2[n].fX - origX) * opp;
+ for (int n = 0; n < ptCount; ++n) {
+ double test = (pts[n].fY - origY) * adj - (pts[n].fX - origX) * opp;
if (test * sign > 0 && !precisely_zero(test)) {
foundOutlier = true;
break;
@@ -154,6 +155,19 @@
return true;
}
+bool SkDCubic::hullIntersects(const SkDCubic& c2, bool* isLinear) const {
+ return hullIntersects(c2.fPts, c2.kPointCount, isLinear);
+}
+
+bool SkDCubic::hullIntersects(const SkDQuad& quad, bool* isLinear) const {
+ return hullIntersects(quad.fPts, quad.kPointCount, isLinear);
+}
+
+bool SkDCubic::hullIntersects(const SkDConic& conic, bool* isLinear) const {
+
+ return hullIntersects(conic.fPts, isLinear);
+}
+
bool SkDCubic::isLinear(int startIndex, int endIndex) const {
SkLineParameters lineParameters;
lineParameters.cubicEndPoints(*this, startIndex, endIndex);
@@ -191,7 +205,7 @@
*t = (smaller + larger) / 2;
return *t > 0 && *t < 1;
}
- } else if (cubicType == kSerpentine_SkCubicType) {
+ } else if (kSerpentine_SkCubicType == cubicType || kCusp_SkCubicType == cubicType) {
SkDCubic cubic;
cubic.set(pointsPtr);
double inflectionTs[2];
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 9932e1d..1263ac8 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -54,6 +54,11 @@
static void Coefficients(const double* cubic, double* A, double* B, double* C, double* D);
static bool ComplexBreak(const SkPoint pts[4], SkScalar* t);
int convexHull(char order[kPointCount]) const;
+
+ void debugInit() {
+ sk_bzero(fPts, sizeof(fPts));
+ }
+
void dump() const; // callable from the debugger when the implementation code is linked in
void dumpID(int id) const;
void dumpInner() const;
@@ -70,6 +75,9 @@
int findMaxCurvature(double tValues[]) const;
bool hullIntersects(const SkDCubic& c2, bool* isLinear) const;
+ bool hullIntersects(const SkDConic& c, bool* isLinear) const;
+ bool hullIntersects(const SkDQuad& c2, bool* isLinear) const;
+ bool hullIntersects(const SkDPoint* pts, int ptCount, bool* isLinear) const;
bool isLinear(int startIndex, int endIndex) const;
bool monotonicInY() const;
void otherPts(int index, const SkDPoint* o1Pts[kPointCount - 1]) const;
@@ -80,11 +88,12 @@
int searchRoots(double extremes[6], int extrema, double axisIntercept,
SearchAxis xAxis, double* validRoots) const;
- void set(const SkPoint pts[kPointCount]) {
+ const SkDCubic& set(const SkPoint pts[kPointCount]) {
fPts[0] = pts[0];
fPts[1] = pts[1];
fPts[2] = pts[2];
fPts[3] = pts[3];
+ return *this;
}
SkDCubic subDivide(double t1, double t2) const;
diff --git a/src/pathops/SkPathOpsCurve.h b/src/pathops/SkPathOpsCurve.h
index a7d3e81..5a2eeec 100644
--- a/src/pathops/SkPathOpsCurve.h
+++ b/src/pathops/SkPathOpsCurve.h
@@ -12,130 +12,214 @@
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
-static SkDPoint dline_xy_at_t(const SkPoint a[2], double t) {
+#ifndef SK_RELEASE
+#include "SkPath.h"
+#endif
+
+struct SkOpCurve {
+ SkPoint fPts[4];
+ SkScalar fWeight;
+ SkDEBUGCODE(SkPath::Verb fVerb);
+
+ const SkPoint& operator[](int n) const {
+ SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
+ return fPts[n];
+ }
+
+ void set(const SkDCubic& cubic) {
+ for (int index = 0; index < SkDCubic::kPointCount; ++index) {
+ fPts[index] = cubic[index].asSkPoint();
+ }
+ SkDEBUGCODE(fWeight = 1);
+ SkDEBUGCODE(fVerb = SkPath::kCubic_Verb);
+ }
+};
+
+struct SkDCurve {
+ union {
+ SkDLine fLine;
+ SkDQuad fQuad;
+ SkDConic fConic;
+ SkDCubic fCubic;
+ };
+ SkDEBUGCODE(SkPath::Verb fVerb);
+
+ const SkDPoint& operator[](int n) const {
+ SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
+ return fCubic[n];
+ }
+
+ SkDPoint& operator[](int n) {
+ SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
+ return fCubic[n];
+ }
+
+ void dumpID(int ) const;
+};
+
+static SkDPoint dline_xy_at_t(const SkPoint a[2], SkScalar , double t) {
SkDLine line;
line.set(a);
return line.ptAtT(t);
}
-static SkDPoint dquad_xy_at_t(const SkPoint a[3], double t) {
+static SkDPoint dquad_xy_at_t(const SkPoint a[3], SkScalar , double t) {
SkDQuad quad;
quad.set(a);
return quad.ptAtT(t);
}
-static SkDPoint dcubic_xy_at_t(const SkPoint a[4], double t) {
+static SkDPoint dconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ SkDConic conic;
+ conic.set(a, weight);
+ return conic.ptAtT(t);
+}
+
+static SkDPoint dcubic_xy_at_t(const SkPoint a[4], SkScalar , double t) {
SkDCubic cubic;
cubic.set(a);
return cubic.ptAtT(t);
}
-static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], double ) = {
+static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], SkScalar , double ) = {
NULL,
dline_xy_at_t,
dquad_xy_at_t,
+ dconic_xy_at_t,
dcubic_xy_at_t
};
-static SkPoint fline_xy_at_t(const SkPoint a[2], double t) {
- return dline_xy_at_t(a, t).asSkPoint();
+static SkPoint fline_xy_at_t(const SkPoint a[2], SkScalar weight, double t) {
+ return dline_xy_at_t(a, weight, t).asSkPoint();
}
-static SkPoint fquad_xy_at_t(const SkPoint a[3], double t) {
- return dquad_xy_at_t(a, t).asSkPoint();
+static SkPoint fquad_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ return dquad_xy_at_t(a, weight, t).asSkPoint();
}
-static SkPoint fcubic_xy_at_t(const SkPoint a[4], double t) {
- return dcubic_xy_at_t(a, t).asSkPoint();
+static SkPoint fconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ return dconic_xy_at_t(a, weight, t).asSkPoint();
}
-static SkPoint (* const CurvePointAtT[])(const SkPoint[], double ) = {
+static SkPoint fcubic_xy_at_t(const SkPoint a[4], SkScalar weight, double t) {
+ return dcubic_xy_at_t(a, weight, t).asSkPoint();
+}
+
+static SkPoint (* const CurvePointAtT[])(const SkPoint[], SkScalar , double ) = {
NULL,
fline_xy_at_t,
fquad_xy_at_t,
+ fconic_xy_at_t,
fcubic_xy_at_t
};
-static SkDVector dline_dxdy_at_t(const SkPoint a[2], double ) {
+static SkDVector dline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
SkDLine line;
line.set(a);
return line[1] - line[0];
}
-static SkDVector dquad_dxdy_at_t(const SkPoint a[3], double t) {
+static SkDVector dquad_dxdy_at_t(const SkPoint a[3], SkScalar , double t) {
SkDQuad quad;
quad.set(a);
return quad.dxdyAtT(t);
}
-static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], double t) {
+static SkDVector dconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ SkDConic conic;
+ conic.set(a, weight);
+ return conic.dxdyAtT(t);
+}
+
+static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], SkScalar , double t) {
SkDCubic cubic;
cubic.set(a);
return cubic.dxdyAtT(t);
}
-static SkDVector (* const CurveDSlopeAtT[])(const SkPoint[], double ) = {
+static SkDVector (* const CurveDSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
NULL,
dline_dxdy_at_t,
dquad_dxdy_at_t,
+ dconic_dxdy_at_t,
dcubic_dxdy_at_t
};
-static SkVector fline_dxdy_at_t(const SkPoint a[2], double ) {
+static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
return a[1] - a[0];
}
-static SkVector fquad_dxdy_at_t(const SkPoint a[3], double t) {
- return dquad_dxdy_at_t(a, t).asSkVector();
+static SkVector fquad_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ return dquad_dxdy_at_t(a, weight, t).asSkVector();
}
-static SkVector fcubic_dxdy_at_t(const SkPoint a[4], double t) {
- return dcubic_dxdy_at_t(a, t).asSkVector();
+static SkVector fconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
+ return dconic_dxdy_at_t(a, weight, t).asSkVector();
}
-static SkVector (* const CurveSlopeAtT[])(const SkPoint[], double ) = {
+static SkVector fcubic_dxdy_at_t(const SkPoint a[4], SkScalar weight, double t) {
+ return dcubic_dxdy_at_t(a, weight, t).asSkVector();
+}
+
+static SkVector (* const CurveSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
NULL,
fline_dxdy_at_t,
fquad_dxdy_at_t,
+ fconic_dxdy_at_t,
fcubic_dxdy_at_t
};
-static SkPoint quad_top(const SkPoint a[3], double startT, double endT) {
+static SkPoint quad_top(const SkPoint a[3], SkScalar , double startT, double endT) {
SkDQuad quad;
quad.set(a);
SkDPoint topPt = quad.top(startT, endT);
return topPt.asSkPoint();
}
-static SkPoint cubic_top(const SkPoint a[4], double startT, double endT) {
+static SkPoint conic_top(const SkPoint a[3], SkScalar weight, double startT, double endT) {
+ SkDConic conic;
+ conic.set(a, weight);
+ SkDPoint topPt = conic.top(startT, endT);
+ return topPt.asSkPoint();
+}
+
+static SkPoint cubic_top(const SkPoint a[4], SkScalar , double startT, double endT) {
SkDCubic cubic;
cubic.set(a);
SkDPoint topPt = cubic.top(startT, endT);
return topPt.asSkPoint();
}
-static SkPoint (* const CurveTop[])(const SkPoint[], double , double ) = {
+static SkPoint (* const CurveTop[])(const SkPoint[], SkScalar , double , double ) = {
NULL,
NULL,
quad_top,
+ conic_top,
cubic_top
};
-static bool line_is_vertical(const SkPoint a[2], double startT, double endT) {
+static bool line_is_vertical(const SkPoint a[2], SkScalar , double startT, double endT) {
SkDLine line;
line.set(a);
SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) };
return AlmostEqualUlps(dst[0].fX, dst[1].fX);
}
-static bool quad_is_vertical(const SkPoint a[3], double startT, double endT) {
+static bool quad_is_vertical(const SkPoint a[3], SkScalar , double startT, double endT) {
SkDQuad quad;
quad.set(a);
SkDQuad dst = quad.subDivide(startT, endT);
return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
}
-static bool cubic_is_vertical(const SkPoint a[4], double startT, double endT) {
+static bool conic_is_vertical(const SkPoint a[3], SkScalar weight, double startT, double endT) {
+ SkDConic conic;
+ conic.set(a, weight);
+ SkDConic dst = conic.subDivide(startT, endT);
+ return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
+}
+
+static bool cubic_is_vertical(const SkPoint a[4], SkScalar , double startT, double endT) {
SkDCubic cubic;
cubic.set(a);
SkDCubic dst = cubic.subDivide(startT, endT);
@@ -143,35 +227,48 @@
&& AlmostEqualUlps(dst[2].fX, dst[3].fX);
}
-static bool (* const CurveIsVertical[])(const SkPoint[], double , double) = {
+static bool (* const CurveIsVertical[])(const SkPoint[], SkScalar , double , double) = {
NULL,
line_is_vertical,
quad_is_vertical,
+ conic_is_vertical,
cubic_is_vertical
};
-static void line_intersect_ray(const SkPoint a[2], const SkDLine& ray, SkIntersections* i) {
+static void line_intersect_ray(const SkPoint a[2], SkScalar , const SkDLine& ray,
+ SkIntersections* i) {
SkDLine line;
line.set(a);
i->intersectRay(line, ray);
}
-static void quad_intersect_ray(const SkPoint a[3], const SkDLine& ray, SkIntersections* i) {
+static void quad_intersect_ray(const SkPoint a[3], SkScalar , const SkDLine& ray,
+ SkIntersections* i) {
SkDQuad quad;
quad.set(a);
i->intersectRay(quad, ray);
}
-static void cubic_intersect_ray(const SkPoint a[4], const SkDLine& ray, SkIntersections* i) {
+static void conic_intersect_ray(const SkPoint a[3], SkScalar weight, const SkDLine& ray,
+ SkIntersections* i) {
+ SkDConic conic;
+ conic.set(a, weight);
+ i->intersectRay(conic, ray);
+}
+
+static void cubic_intersect_ray(const SkPoint a[4], SkScalar , const SkDLine& ray,
+ SkIntersections* i) {
SkDCubic cubic;
cubic.set(a);
i->intersectRay(cubic, ray);
}
-static void (* const CurveIntersectRay[])(const SkPoint[] , const SkDLine& , SkIntersections* ) = {
+static void (* const CurveIntersectRay[])(const SkPoint[] , SkScalar , const SkDLine& ,
+ SkIntersections* ) = {
NULL,
line_intersect_ray,
quad_intersect_ray,
+ conic_intersect_ray,
cubic_intersect_ray
};
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 0331f34..61bca42 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -7,9 +7,8 @@
#include "SkPathOpsDebug.h"
#include "SkPath.h"
-#if DEBUG_ANGLE
#include "SkString.h"
-#endif
+#include "SkThread.h"
#if DEBUG_VALIDATE
extern bool FLAGS_runFail;
@@ -101,10 +100,36 @@
}
#endif
-#if !DEBUG_SHOW_TEST_NAME // enable when building without extended test
-void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) {
+static void show_function_header(const char* functionName) {
+ SkDebugf("\nstatic void %s(skiatest::Reporter* reporter, const char* filename) {\n", functionName);
+ if (strcmp("skphealth_com76", functionName) == 0) {
+ SkDebugf("found it\n");
+ }
}
-#endif
+
+static const char* gOpStrs[] = {
+ "kDifference_SkPathOp",
+ "kIntersect_SkPathOp",
+ "kUnion_SkPathOp",
+ "kXor_PathOp",
+ "kReverseDifference_SkPathOp",
+};
+
+static void show_op(SkPathOp op, const char* pathOne, const char* pathTwo) {
+ SkDebugf(" testPathOp(reporter, %s, %s, %s, filename);\n", pathOne, pathTwo, gOpStrs[op]);
+ SkDebugf("}\n");
+}
+
+SK_DECLARE_STATIC_MUTEX(gTestMutex);
+
+void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
+ const char* testName) {
+ SkAutoMutexAcquire ac(gTestMutex);
+ show_function_header(testName);
+ ShowOnePath(a, "path", true);
+ ShowOnePath(b, "pathB", true);
+ show_op(shapeOp, "path", "pathB");
+}
#include "SkOpAngle.h"
#include "SkOpSegment.h"
@@ -134,7 +159,7 @@
}
void SkOpSegment::debugReset() {
- this->init(this->fPts, this->contour(), this->verb());
+ this->init(this->fPts, this->fWeight, this->contour(), this->verb());
}
#if DEBUG_ACTIVE_SPANS
@@ -150,16 +175,19 @@
if (span->done()) {
continue;
}
- if (lastId == fID && lastT == span->t()) {
+ if (lastId == this->debugID() && lastT == span->t()) {
continue;
}
- lastId = fID;
+ lastId = this->debugID();
lastT = span->t();
- SkDebugf("%s id=%d", __FUNCTION__, fID);
+ SkDebugf("%s id=%d", __FUNCTION__, this->debugID());
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
}
+ if (SkPath::kConic_Verb == fVerb) {
+ SkDebugf(" %1.9gf", fWeight);
+ }
const SkOpPtT* ptT = span->ptT();
SkDebugf(") t=%1.9g (%1.9g,%1.9g)", ptT->fT, ptT->fPt.fX, ptT->fPt.fY);
SkDebugf(" tEnd=%1.9g", span->next()->t());
@@ -178,7 +206,7 @@
#if DEBUG_MARK_DONE
void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding) {
const SkPoint& pt = span->ptT()->fPt;
- SkDebugf("%s id=%d", fun, fID);
+ SkDebugf("%s id=%d", fun, this->debugID());
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
@@ -202,7 +230,7 @@
void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding,
int oppWinding) {
const SkPoint& pt = span->ptT()->fPt;
- SkDebugf("%s id=%d", fun, fID);
+ SkDebugf("%s id=%d", fun, this->debugID());
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
@@ -249,6 +277,11 @@
result.printf(QUAD_DEBUG_STR " id=%d", QUAD_DEBUG_DATA(fCurvePart),
this->segment()->debugID());
break;
+ case SkPath::kConic_Verb:
+ result.printf(CONIC_DEBUG_STR " id=%d",
+ CONIC_DEBUG_DATA(fCurvePart, fCurvePart.fConic.fWeight),
+ this->segment()->debugID());
+ break;
case SkPath::kCubic_Verb:
result.printf(CUBIC_DEBUG_STR " id=%d", CUBIC_DEBUG_DATA(fCurvePart),
this->segment()->debugID());
@@ -471,3 +504,107 @@
SkASSERT(debugLoopLimit(false) == 0);
#endif
}
+
+static void output_scalar(SkScalar num) {
+ if (num == (int) num) {
+ SkDebugf("%d", (int) num);
+ } else {
+ SkString str;
+ str.printf("%1.9g", num);
+ int width = (int) str.size();
+ const char* cStr = str.c_str();
+ while (cStr[width - 1] == '0') {
+ --width;
+ }
+ str.resize(width);
+ SkDebugf("%sf", str.c_str());
+ }
+}
+
+static void output_points(const SkPoint* pts, int count) {
+ for (int index = 0; index < count; ++index) {
+ output_scalar(pts[index].fX);
+ SkDebugf(", ");
+ output_scalar(pts[index].fY);
+ if (index + 1 < count) {
+ SkDebugf(", ");
+ }
+ }
+}
+
+static void showPathContours(SkPath::RawIter& iter, const char* pathName) {
+ uint8_t verb;
+ SkPoint pts[4];
+ while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ SkDebugf(" %s.moveTo(", pathName);
+ output_points(&pts[0], 1);
+ SkDebugf(");\n");
+ continue;
+ case SkPath::kLine_Verb:
+ SkDebugf(" %s.lineTo(", pathName);
+ output_points(&pts[1], 1);
+ SkDebugf(");\n");
+ break;
+ case SkPath::kQuad_Verb:
+ SkDebugf(" %s.quadTo(", pathName);
+ output_points(&pts[1], 2);
+ SkDebugf(");\n");
+ break;
+ case SkPath::kConic_Verb:
+ SkDebugf(" %s.conicTo(", pathName);
+ output_points(&pts[1], 2);
+ SkDebugf(", %1.9gf);\n", iter.conicWeight());
+ break;
+ case SkPath::kCubic_Verb:
+ SkDebugf(" %s.cubicTo(", pathName);
+ output_points(&pts[1], 3);
+ SkDebugf(");\n");
+ break;
+ case SkPath::kClose_Verb:
+ SkDebugf(" %s.close();\n", pathName);
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ }
+}
+
+static const char* gFillTypeStr[] = {
+ "kWinding_FillType",
+ "kEvenOdd_FillType",
+ "kInverseWinding_FillType",
+ "kInverseEvenOdd_FillType"
+};
+
+void SkPathOpsDebug::ShowOnePath(const SkPath& path, const char* name, bool includeDeclaration) {
+ SkPath::RawIter iter(path);
+#define SUPPORT_RECT_CONTOUR_DETECTION 0
+#if SUPPORT_RECT_CONTOUR_DETECTION
+ int rectCount = path.isRectContours() ? path.rectContours(NULL, NULL) : 0;
+ if (rectCount > 0) {
+ SkTDArray<SkRect> rects;
+ SkTDArray<SkPath::Direction> directions;
+ rects.setCount(rectCount);
+ directions.setCount(rectCount);
+ path.rectContours(rects.begin(), directions.begin());
+ for (int contour = 0; contour < rectCount; ++contour) {
+ const SkRect& rect = rects[contour];
+ SkDebugf("path.addRect(%1.9g, %1.9g, %1.9g, %1.9g, %s);\n", rect.fLeft, rect.fTop,
+ rect.fRight, rect.fBottom, directions[contour] == SkPath::kCCW_Direction
+ ? "SkPath::kCCW_Direction" : "SkPath::kCW_Direction");
+ }
+ return;
+ }
+#endif
+ SkPath::FillType fillType = path.getFillType();
+ SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
+ if (includeDeclaration) {
+ SkDebugf(" SkPath %s;\n", name);
+ }
+ SkDebugf(" %s.setFillType(SkPath::%s);\n", name, gFillTypeStr[fillType]);
+ iter.setPath(path);
+ showPathContours(iter, name);
+}
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 72a9ea5..78fc57a 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -84,13 +84,13 @@
#endif
#ifdef SK_RELEASE
- #define PATH_OPS_DEBUG_RELEASE(a, b) b
- #define PATH_OPS_DEBUG_CODE(...)
- #define PATH_OPS_DEBUG_PARAMS(...)
+ #define SkDEBUGRELEASE(a, b) b
+ #define SkDEBUGPARAMS(...)
+ #define SkDEBUGCODE_(...)
#else
- #define PATH_OPS_DEBUG_RELEASE(a, b) a
- #define PATH_OPS_DEBUG_CODE(...) __VA_ARGS__
- #define PATH_OPS_DEBUG_PARAMS(...) , __VA_ARGS__
+ #define SkDEBUGRELEASE(a, b) a
+ #define SkDEBUGPARAMS(...) , __VA_ARGS__
+ #define SkDEBUGCODE_(...) __VA_ARGS__ // temporary until SkDEBUGCODE is fixed
#endif
#if DEBUG_T_SECT == 0
@@ -107,14 +107,16 @@
extern int gDumpTSectNum;
#endif
-#define CUBIC_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
-#define QUAD_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
-#define LINE_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
+#define CUBIC_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
+#define CONIC_DEBUG_STR "{{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}, %1.9g}"
+#define QUAD_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
+#define LINE_DEBUG_STR "{{{%1.9g,%1.9g}, {%1.9g,%1.9g}}}"
#define PT_DEBUG_STR "{{%1.9g,%1.9g}}"
#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
#define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
+#define CONIC_DEBUG_DATA(c, w) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, w
#define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
#define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY
#define PT_DEBUG_DATA(i, n) i.pt(n).asSkPoint().fX, i.pt(n).asSkPoint().fY
@@ -204,35 +206,7 @@
static void DumpContoursSpans(const SkTDArray<class SkOpContour* >* contours);
};
-// shorthand for calling from debugger
-template<typename TCurve> class SkTSect;
-template<typename TCurve> class SkTSpan;
-
struct SkDQuad;
-struct SkDCubic;
-
-const SkTSpan<SkDCubic>* DebugSpan(const SkTSect<SkDCubic>* , int id);
-const SkTSpan<SkDQuad>* DebugSpan(const SkTSect<SkDQuad>* , int id);
-const SkTSpan<SkDCubic>* DebugT(const SkTSect<SkDCubic>* , double t);
-const SkTSpan<SkDQuad>* DebugT(const SkTSect<SkDQuad>* , double t);
-
-const SkTSpan<SkDCubic>* DebugSpan(const SkTSpan<SkDCubic>* , int id);
-const SkTSpan<SkDQuad>* DebugSpan(const SkTSpan<SkDQuad>* , int id);
-const SkTSpan<SkDCubic>* DebugT(const SkTSpan<SkDCubic>* , double t);
-const SkTSpan<SkDQuad>* DebugT(const SkTSpan<SkDQuad>* , double t);
-
-void Dump(const SkTSect<SkDCubic>* );
-void Dump(const SkTSect<SkDQuad>* );
-void Dump(const SkTSpan<SkDCubic>* , const SkTSect<SkDCubic>* = NULL);
-void Dump(const SkTSpan<SkDQuad>* , const SkTSect<SkDQuad>* = NULL);
-void DumpBoth(SkTSect<SkDCubic>* sect1, SkTSect<SkDCubic>* sect2);
-void DumpBoth(SkTSect<SkDQuad>* sect1, SkTSect<SkDQuad>* sect2);
-void DumpCoin(SkTSect<SkDCubic>* sect1);
-void DumpCoin(SkTSect<SkDQuad>* sect1);
-void DumpCoinCurves(SkTSect<SkDCubic>* sect1);
-void DumpCoinCurves(SkTSect<SkDQuad>* sect1);
-void DumpCurves(const SkTSpan<SkDCubic>* );
-void DumpCurves(const SkTSpan<SkDQuad>* );
// generates tools/path_sorter.htm and path_visualizer.htm compatible data
void DumpQ(const SkDQuad& quad1, const SkDQuad& quad2, int testNo);
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index bb25162..ce55861 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -34,6 +34,8 @@
SkDPoint ptAtT(double t) const;
void dump() const;
+ void dumpID(int ) const;
+ void dumpInner() const;
};
#endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 25ddb7d..f7580ae 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -264,7 +264,7 @@
SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune
SkOpContour contour;
SkOpCoincidence coincidence;
- SkOpGlobalState globalState(&coincidence PATH_OPS_DEBUG_PARAMS(&contour));
+ SkOpGlobalState globalState(&coincidence SkDEBUGPARAMS(&contour));
#if DEBUGGING_PATHOPS_FROM_HOST
dump_op(one, two, op);
#endif
@@ -302,18 +302,20 @@
contour.dumpSegments(op);
#endif
- result->reset();
- result->setFillType(fillType);
const int xorOpMask = builder.xorMask();
SkTDArray<SkOpContour* > contourList;
MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask,
xorOpMask == kEvenOdd_PathOpsMask);
SkOpContour** currentPtr = contourList.begin();
if (!currentPtr) {
+ result->reset();
+ result->setFillType(fillType);
return true;
}
if ((*currentPtr)->count() == 0) {
SkASSERT((*currentPtr)->next() == NULL);
+ result->reset();
+ result->setFillType(fillType);
return true;
}
SkOpContour** listEnd = contourList.end();
@@ -334,6 +336,8 @@
return false;
}
// construct closed contours
+ result->reset();
+ result->setFillType(fillType);
SkPathWriter wrapper(*result);
bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator);
{ // if some edges could not be resolved, assemble remaining fragments
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 2d07427..35ad80e 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -193,6 +193,20 @@
return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
}
+ static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) {
+ if (!RoughlyEqualUlps(a.fX, b.fX) || !RoughlyEqualUlps(a.fY, b.fY)) {
+ return false;
+ }
+ SkDPoint dA, dB;
+ dA.set(a);
+ dB.set(b);
+ double dist = dA.distance(dB); // OPTIMIZATION: can we compare against distSq instead ?
+ float tiniest = SkTMin(SkTMin(SkTMin(a.fX, b.fX), a.fY), b.fY);
+ float largest = SkTMax(SkTMax(SkTMax(a.fX, b.fX), a.fY), b.fY);
+ largest = SkTMax(largest, -tiniest);
+ return RoughlyEqualUlps((double) largest, largest + dist); // is dist within ULPS tolerance?
+ }
+
// utilities callable by the user from the debugger when the implementation code is linked in
void dump() const;
static void Dump(const SkPoint& pt);
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 4913c9f..054509b 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -47,6 +47,14 @@
return true;
}
+bool SkDQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const {
+ return conic.hullIntersects(*this, isLinear);
+}
+
+bool SkDQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const {
+ return cubic.hullIntersects(*this, isLinear);
+}
+
/* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan)
oddMan opp x=oddMan^opp x=x-oddMan m=x>>2 x&~m
0 1 1 1 0 1
@@ -198,6 +206,13 @@
return approximately_zero_when_compared_to(distance, largest);
}
+SkDConic SkDQuad::toConic() const {
+ SkDConic conic;
+ memcpy(conic.fPts.fPts, fPts, sizeof(fPts));
+ conic.fWeight = 1;
+ return conic;
+}
+
SkDCubic SkDQuad::toCubic() const {
SkDCubic cubic;
cubic[0] = fPts[0];
@@ -236,6 +251,17 @@
return result;
}
+static double interp_quad_coords(const double* src, double t) {
+ double ab = SkDInterp(src[0], src[2], t);
+ double bc = SkDInterp(src[2], src[4], t);
+ double abc = SkDInterp(ab, bc, t);
+ return abc;
+}
+
+bool SkDQuad::monotonicInY() const {
+ return between(fPts[0].fY, fPts[1].fY, fPts[2].fY);
+}
+
/*
Given a quadratic q, t1, and t2, find a small quadratic segment.
@@ -259,17 +285,7 @@
B = D*2 - A/2 - C/2
*/
-static double interp_quad_coords(const double* src, double t) {
- double ab = SkDInterp(src[0], src[2], t);
- double bc = SkDInterp(src[2], src[4], t);
- double abc = SkDInterp(ab, bc, t);
- return abc;
-}
-
-bool SkDQuad::monotonicInY() const {
- return between(fPts[0].fY, fPts[1].fY, fPts[2].fY);
-}
-
+// OPTIMIZE : special case either or both of t1 = 0, t2 = 1
SkDQuad SkDQuad::subDivide(double t1, double t2) const {
SkDQuad dst;
double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1);
@@ -278,8 +294,8 @@
double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2);
double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2);
double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2);
- /* bx = */ dst[1].fX = 2*dx - (ax + cx)/2;
- /* by = */ dst[1].fY = 2*dy - (ay + cy)/2;
+ /* bx = */ dst[1].fX = 2 * dx - (ax + cx) / 2;
+ /* by = */ dst[1].fY = 2 * dy - (ay + cy) / 2;
return dst;
}
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index 81638cf..847c69c 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -34,6 +34,10 @@
return v02.dot(v01) > 0 && v02.dot(v12) > 0;
}
+ void debugInit() {
+ sk_bzero(fPts, sizeof(fPts));
+ }
+
SkDQuad flip() const {
SkDQuad result = {{fPts[2], fPts[1], fPts[0]}};
return result;
@@ -41,10 +45,11 @@
static bool IsCubic() { return false; }
- void set(const SkPoint pts[kPointCount]) {
+ const SkDQuad& set(const SkPoint pts[kPointCount]) {
fPts[0] = pts[0];
fPts[1] = pts[1];
fPts[2] = pts[2];
+ return *this;
}
const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < kPointCount); return fPts[n]; }
@@ -56,6 +61,8 @@
SkDVector dxdyAtT(double t) const;
static int FindExtrema(double a, double b, double c, double tValue[1]);
bool hullIntersects(const SkDQuad& , bool* isLinear) const;
+ bool hullIntersects(const SkDConic& , bool* isLinear) const;
+ bool hullIntersects(const SkDCubic& , bool* isLinear) const;
bool isLinear(int startIndex, int endIndex) const;
bool monotonicInY() const;
double nearestT(const SkDPoint&) const;
@@ -77,6 +84,7 @@
quad.set(pts);
return quad.subDivide(a, c, t1, t2);
}
+ SkDConic toConic() const;
SkDCubic toCubic() const;
SkDPoint top(double startT, double endT) const;
diff --git a/src/pathops/SkPathOpsRect.cpp b/src/pathops/SkPathOpsRect.cpp
index 5dd3d8d..540db16 100644
--- a/src/pathops/SkPathOpsRect.cpp
+++ b/src/pathops/SkPathOpsRect.cpp
@@ -4,6 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
+#include "SkPathOpsConic.h"
#include "SkPathOpsCubic.h"
#include "SkPathOpsLine.h"
#include "SkPathOpsQuad.h"
@@ -25,6 +26,22 @@
}
}
+void SkDRect::setBounds(const SkDConic& conic) {
+ set(conic[0]);
+ add(conic[2]);
+ double tValues[2];
+ int roots = 0;
+ if (!between(conic[0].fX, conic[1].fX, conic[2].fX)) {
+ roots = SkDConic::FindExtrema(&conic[0].fX, conic.fWeight, tValues);
+ }
+ if (!between(conic[0].fY, conic[1].fY, conic[2].fY)) {
+ roots += SkDConic::FindExtrema(&conic[0].fY, conic.fWeight, &tValues[roots]);
+ }
+ for (int x = 0; x < roots; ++x) {
+ add(conic.ptAtT(tValues[x]));
+ }
+}
+
static bool is_bounded_by_end_points(double a, double b, double c, double d) {
return between(a, b, d) && between(a, c, d);
}
diff --git a/src/pathops/SkPathOpsRect.h b/src/pathops/SkPathOpsRect.h
index 2b37a5f..f783d96 100644
--- a/src/pathops/SkPathOpsRect.h
+++ b/src/pathops/SkPathOpsRect.h
@@ -48,6 +48,7 @@
return fBottom - fTop;
}
+ void setBounds(const SkDConic&);
void setBounds(const SkDCubic&);
void setBounds(const SkDQuad&);
};
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 5c8a7fd..8d525fa 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -191,7 +191,7 @@
// turn path into list of segments
SkOpCoincidence coincidence;
SkOpContour contour;
- SkOpGlobalState globalState(&coincidence PATH_OPS_DEBUG_PARAMS(&contour));
+ SkOpGlobalState globalState(&coincidence SkDEBUGPARAMS(&contour));
#if DEBUG_SORT || DEBUG_SWAP_TOP
SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
@@ -202,16 +202,18 @@
#if !FORCE_RELEASE
contour.dumpSegments((SkPathOp) -1);
#endif
- result->reset();
- result->setFillType(fillType);
SkTDArray<SkOpContour* > contourList;
MakeContourList(&contour, contourList, false, false);
SkOpContour** currentPtr = contourList.begin();
if (!currentPtr) {
+ result->reset();
+ result->setFillType(fillType);
return true;
}
if ((*currentPtr)->count() == 0) {
SkASSERT((*currentPtr)->next() == NULL);
+ result->reset();
+ result->setFillType(fillType);
return true;
}
SkOpContour** listEnd2 = contourList.end();
@@ -231,6 +233,8 @@
return false;
}
// construct closed contours
+ result->reset();
+ result->setFillType(fillType);
SkPathWriter wrapper(*result);
if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &wrapper, &allocator)
: !bridgeXor(contourList, &wrapper, &allocator))
diff --git a/src/pathops/SkPathOpsTCubicSect.cpp b/src/pathops/SkPathOpsTCubicSect.cpp
deleted file mode 100644
index 10a84a3..0000000
--- a/src/pathops/SkPathOpsTCubicSect.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-/*
- * Copyright 2014 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "SkPathOpsTSect.h"
-
-int SkIntersections::intersect(const SkDCubic& cubic1, const SkDCubic& cubic2) {
- SkTSect<SkDCubic> sect1(cubic1 PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDCubic> sect2(cubic2 PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDCubic>::BinarySearch(§1, §2, this);
- return used();
-}
diff --git a/src/pathops/SkPathOpsTQuadSect.cpp b/src/pathops/SkPathOpsTQuadSect.cpp
deleted file mode 100644
index 06b5f2f..0000000
--- a/src/pathops/SkPathOpsTQuadSect.cpp
+++ /dev/null
@@ -1,15 +0,0 @@
-/*
- * Copyright 2014 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#include "SkPathOpsTSect.h"
-
-int SkIntersections::intersect(const SkDQuad& quad1, const SkDQuad& quad2) {
- SkTSect<SkDQuad> sect1(quad1 PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect<SkDQuad> sect2(quad2 PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect<SkDQuad>::BinarySearch(§1, §2, this);
- return used();
-}
diff --git a/src/pathops/SkPathOpsTSect.cpp b/src/pathops/SkPathOpsTSect.cpp
new file mode 100644
index 0000000..1549e6b
--- /dev/null
+++ b/src/pathops/SkPathOpsTSect.cpp
@@ -0,0 +1,50 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkPathOpsTSect.h"
+
+int SkIntersections::intersect(const SkDQuad& quad1, const SkDQuad& quad2) {
+ SkTSect<SkDQuad, SkDQuad> sect1(quad1 PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDQuad, SkDQuad> sect2(quad2 PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDQuad, SkDQuad>::BinarySearch(§1, §2, this);
+ return used();
+}
+
+int SkIntersections::intersect(const SkDConic& conic, const SkDQuad& quad) {
+ SkTSect<SkDConic, SkDQuad> sect1(conic PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDQuad, SkDConic> sect2(quad PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDConic, SkDQuad>::BinarySearch(§1, §2, this);
+ return used();
+}
+
+int SkIntersections::intersect(const SkDConic& conic1, const SkDConic& conic2) {
+ SkTSect<SkDConic, SkDConic> sect1(conic1 PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDConic, SkDConic> sect2(conic2 PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDConic, SkDConic>::BinarySearch(§1, §2, this);
+ return used();
+}
+
+int SkIntersections::intersect(const SkDCubic& cubic, const SkDQuad& quad) {
+ SkTSect<SkDCubic, SkDQuad> sect1(cubic PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDQuad, SkDCubic> sect2(quad PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDCubic, SkDQuad>::BinarySearch(§1, §2, this);
+ return used();
+}
+
+int SkIntersections::intersect(const SkDCubic& cubic, const SkDConic& conic) {
+ SkTSect<SkDCubic, SkDConic> sect1(cubic PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDConic, SkDCubic> sect2(conic PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDCubic, SkDConic>::BinarySearch(§1, §2, this);
+ return used();
+}
+
+int SkIntersections::intersect(const SkDCubic& cubic1, const SkDCubic& cubic2) {
+ SkTSect<SkDCubic, SkDCubic> sect1(cubic1 PATH_OPS_DEBUG_T_SECT_PARAMS(1));
+ SkTSect<SkDCubic, SkDCubic> sect2(cubic2 PATH_OPS_DEBUG_T_SECT_PARAMS(2));
+ SkTSect<SkDCubic, SkDCubic>::BinarySearch(§1, §2, this);
+ return used();
+}
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 9d63433..ffd6995 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -8,16 +8,15 @@
#include "SkChunkAlloc.h"
#include "SkPathOpsBounds.h"
#include "SkPathOpsRect.h"
-#include "SkPathOpsQuad.h"
#include "SkIntersections.h"
#include "SkTSort.h"
-/* TCurve is either SkDQuadratic or SkDCubic */
-template<typename TCurve>
+/* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */
+template<typename TCurve, typename OppCurve>
class SkTCoincident {
public:
SkTCoincident() {
- clear();
+ this->clear();
}
void clear() {
@@ -25,12 +24,19 @@
fCoincident = false;
}
+ void debugInit() {
+ this->clear();
+ fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
+ }
+
+ void dump() const;
+
bool isCoincident() const {
return fCoincident;
}
void init() {
- clear();
+ this->clear();
SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN);
}
@@ -49,7 +55,7 @@
return fPerpT;
}
- void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const TCurve& );
+ void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& );
private:
SkDPoint fPerpPt;
@@ -57,40 +63,51 @@
bool fCoincident;
};
-template<typename TCurve> class SkTSect;
-template<typename TCurve> class SkTSpan;
+template<typename TCurve, typename OppCurve> class SkTSect;
+template<typename TCurve, typename OppCurve> class SkTSpan;
-template<typename TCurve>
+template<typename TCurve, typename OppCurve>
struct SkTSpanBounded {
- SkTSpan<TCurve>* fBounded;
+ SkTSpan<TCurve, OppCurve>* fBounded;
SkTSpanBounded* fNext;
};
/* Curve is either TCurve or SkDCubic */
-template<typename TCurve>
+template<typename TCurve, typename OppCurve>
class SkTSpan {
public:
- void addBounded(SkTSpan* , SkChunkAlloc* );
+ void addBounded(SkTSpan<OppCurve, TCurve>* , SkChunkAlloc* );
double closestBoundedT(const SkDPoint& pt) const;
bool contains(double t) const;
- const SkTSect<TCurve>* debugOpp() const;
+ void debugInit() {
+ TCurve dummy;
+ dummy.debugInit();
+ init(dummy);
+ initBounds(dummy);
+ fCoinStart.debugInit();
+ fCoinEnd.debugInit();
+ }
+
+ const SkTSect<OppCurve, TCurve>* debugOpp() const;
const SkTSpan* debugSpan(int ) const;
const SkTSpan* debugT(double t) const;
#ifdef SK_DEBUG
bool debugIsBefore(const SkTSpan* span) const;
#endif
void dump() const;
- void dumpBounds(int id) const;
+ void dumpBounded(int id) const;
+ void dumpBounds() const;
+ void dumpCoin() const;
double endT() const {
return fEndT;
}
- SkTSpan* findOppSpan(const SkTSpan* opp) const;
+ SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const;
- SkTSpan* findOppT(double t) const {
- SkTSpan* result = oppT(t);
+ SkTSpan<OppCurve, TCurve>* findOppT(double t) const {
+ SkTSpan<OppCurve, TCurve>* result = oppT(t);
SkASSERT(result);
return result;
}
@@ -99,7 +116,7 @@
return SkToBool(oppT(t));
}
- int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart);
+ int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart);
void init(const TCurve& );
void initBounds(const TCurve& );
@@ -107,7 +124,7 @@
return fBounded != NULL;
}
- bool linearsIntersect(SkTSpan* span);
+ bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span);
double linearT(const SkDPoint& ) const;
void markCoincident() {
@@ -119,14 +136,15 @@
return fNext;
}
- bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart, bool* ptsInCommon);
+ bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start,
+ bool* oppStart, bool* ptsInCommon);
const TCurve& part() const {
return fPart;
}
bool removeAllBounded();
- bool removeBounded(const SkTSpan* opp);
+ bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp);
void reset() {
fBounded = NULL;
@@ -156,9 +174,9 @@
void dumpID() const;
- int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart);
- int linearIntersects(const TCurve& ) const;
- SkTSpan* oppT(double t) const;
+ int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart);
+ int linearIntersects(const OppCurve& ) const;
+ SkTSpan<OppCurve, TCurve>* oppT(double t) const;
void validate() const;
void validateBounded() const;
@@ -166,9 +184,9 @@
void validatePerpPt(double t, const SkDPoint& ) const;
TCurve fPart;
- SkTCoincident<TCurve> fCoinStart;
- SkTCoincident<TCurve> fCoinEnd;
- SkTSpanBounded<TCurve>* fBounded;
+ SkTCoincident<TCurve, OppCurve> fCoinStart;
+ SkTCoincident<TCurve, OppCurve> fCoinEnd;
+ SkTSpanBounded<OppCurve, TCurve>* fBounded;
SkTSpan* fPrev;
SkTSpan* fNext;
SkDRect fBounds;
@@ -180,29 +198,33 @@
bool fIsLinear;
bool fIsLine;
bool fDeleted;
- PATH_OPS_DEBUG_CODE(SkTSect<TCurve>* fDebugSect);
+ SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect);
PATH_OPS_DEBUG_T_SECT_CODE(int fID);
- friend class SkTSect<TCurve>;
+ friend class SkTSect<TCurve, OppCurve>;
+ friend class SkTSect<OppCurve, TCurve>;
+ friend class SkTSpan<OppCurve, TCurve>;
};
-template<typename TCurve>
+template<typename TCurve, typename OppCurve>
class SkTSect {
public:
SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
- static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections);
+ static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2,
+ SkIntersections* intersections);
// for testing only
- bool debugHasBounded(const SkTSpan<TCurve>* ) const;
+ bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const;
- const SkTSect* debugOpp() const {
- return PATH_OPS_DEBUG_RELEASE(fOppSect, NULL);
+ const SkTSect<OppCurve, TCurve>* debugOpp() const {
+ return SkDEBUGRELEASE(fOppSect, NULL);
}
- const SkTSpan<TCurve>* debugSpan(int id) const;
- const SkTSpan<TCurve>* debugT(double t) const;
+ const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const;
+ const SkTSpan<TCurve, OppCurve>* debugT(double t) const;
void dump() const;
- void dumpBoth(SkTSect* ) const;
- void dumpBounds(int id) const;
+ void dumpBoth(SkTSect<OppCurve, TCurve>* ) const;
+ void dumpBounded(int id) const;
+ void dumpBounds() const;
void dumpCoin() const;
void dumpCoinCurves() const;
void dumpCurves() const;
@@ -215,82 +237,92 @@
kOneS2Set = 8
};
- SkTSpan<TCurve>* addFollowing(SkTSpan<TCurve>* prior);
- void addForPerp(SkTSpan<TCurve>* span, double t);
- SkTSpan<TCurve>* addOne();
+ SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior);
+ void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t);
+ SkTSpan<TCurve, OppCurve>* addOne();
- SkTSpan<TCurve>* addSplitAt(SkTSpan<TCurve>* span, double t) {
- SkTSpan<TCurve>* result = this->addOne();
+ SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) {
+ SkTSpan<TCurve, OppCurve>* result = this->addOne();
result->splitAt(span, t, &fHeap);
result->initBounds(fCurve);
span->initBounds(fCurve);
return result;
}
- bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t, double* oppT);
- SkTSpan<TCurve>* boundsMax() const;
- void coincidentCheck(SkTSect* sect2);
+ bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t,
+ double* oppT);
+ SkTSpan<TCurve, OppCurve>* boundsMax() const;
+ void coincidentCheck(SkTSect<OppCurve, TCurve>* sect2);
bool coincidentHasT(double t);
- void computePerpendiculars(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
- int countConsecutiveSpans(SkTSpan<TCurve>* first, SkTSpan<TCurve>** last) const;
+ int collapsed() const;
+ void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>* last);
+ int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>** last) const;
int debugID() const {
return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
}
void deleteEmptySpans();
- void dumpCommon(const SkTSpan<TCurve>* ) const;
- void dumpCommonCurves(const SkTSpan<TCurve>* ) const;
- static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* );
- SkTSpan<TCurve>* extractCoincident(SkTSect* sect2, SkTSpan<TCurve>* first,
- SkTSpan<TCurve>* last);
- SkTSpan<TCurve>* findCoincidentRun(SkTSpan<TCurve>* first, SkTSpan<TCurve>** lastPtr,
- const SkTSect* sect2);
- int intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
- SkTSpan<TCurve>* oppSpan, int* oppResult) const;
- int linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* opp,
- const SkTSpan<TCurve>* oppSpan, SkIntersections* ) const;
- void markSpanGone(SkTSpan<TCurve>* span);
- bool matchedDirection(double t, const SkTSect* sect2, double t2) const;
- void matchedDirCheck(double t, const SkTSect* sect2, double t2,
+ void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const;
+ void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const;
+ static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2,
+ SkIntersections* );
+ SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect2,
+ SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>* last);
+ SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>** lastPtr);
+ int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
+ SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult);
+ int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp,
+ SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* );
+ void markSpanGone(SkTSpan<TCurve, OppCurve>* span);
+ bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const;
+ void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2,
bool* calcMatched, bool* oppMatched) const;
- void mergeCoincidence(SkTSect* sect2);
- SkTSpan<TCurve>* prev(SkTSpan<TCurve>* ) const;
- void removeByPerpendicular(SkTSect* opp);
+ void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2);
+ SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const;
+ void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp);
void recoverCollapsed();
- void removeCoincident(SkTSpan<TCurve>* span, bool isBetween);
- void removeAllBut(const SkTSpan<TCurve>* keep, SkTSpan<TCurve>* span, SkTSect* opp);
- void removeSpan(SkTSpan<TCurve>* span);
- void removeSpanRange(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
- void removeSpans(SkTSpan<TCurve>* span, SkTSect* opp);
- SkTSpan<TCurve>* spanAtT(double t, SkTSpan<TCurve>** priorSpan);
- SkTSpan<TCurve>* tail();
- void trim(SkTSpan<TCurve>* span, SkTSect* opp);
- void unlinkSpan(SkTSpan<TCurve>* span);
- bool updateBounded(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last, SkTSpan<TCurve>* oppFirst);
+ void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween);
+ void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span,
+ SkTSect<OppCurve, TCurve>* opp);
+ void removeSpan(SkTSpan<TCurve, OppCurve>* span);
+ void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last);
+ void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
+ SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan);
+ SkTSpan<TCurve, OppCurve>* tail();
+ void trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp);
+ void unlinkSpan(SkTSpan<TCurve, OppCurve>* span);
+ bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last,
+ SkTSpan<OppCurve, TCurve>* oppFirst);
void validate() const;
void validateBounded() const;
const TCurve& fCurve;
SkChunkAlloc fHeap;
- SkTSpan<TCurve>* fHead;
- SkTSpan<TCurve>* fCoincident;
- SkTSpan<TCurve>* fDeleted;
+ SkTSpan<TCurve, OppCurve>* fHead;
+ SkTSpan<TCurve, OppCurve>* fCoincident;
+ SkTSpan<TCurve, OppCurve>* fDeleted;
int fActiveCount;
- PATH_OPS_DEBUG_CODE(SkTSect* fOppSect);
+ SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* fOppSect);
PATH_OPS_DEBUG_T_SECT_CODE(int fID);
PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
#if DEBUG_T_SECT
int fDebugAllocatedCount;
#endif
- friend class SkTSpan<TCurve>; // only used by debug id
+ friend class SkTSpan<TCurve, OppCurve>;
+ friend class SkTSpan<OppCurve, TCurve>;
+ friend class SkTSect<OppCurve, TCurve>;
};
#define COINCIDENT_SPAN_COUNT 9
-template<typename TCurve>
-void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t,
- const SkDPoint& cPt, const TCurve& c2) {
+template<typename TCurve, typename OppCurve>
+void SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t,
+ const SkDPoint& cPt, const OppCurve& c2) {
SkDVector dxdy = c1.dxdyAtT(t);
SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
SkIntersections i;
@@ -312,8 +344,9 @@
}
}
#if DEBUG_T_SECT
- SkDebugf("%s cPt=(%1.9g,%1.9g) %s fPerpPt=(%1.9g,%1.9g)\n", __FUNCTION__, cPt.fX, cPt.fY,
- cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpPt.fX, fPerpPt.fY);
+ SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
+ t, cPt.fX, cPt.fY,
+ cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
#endif
fCoincident = cPt.approximatelyEqual(fPerpPt);
#if DEBUG_T_SECT
@@ -323,20 +356,21 @@
#endif
}
-template<typename TCurve>
-void SkTSpan<TCurve>::addBounded(SkTSpan* span, SkChunkAlloc* heap) {
- SkTSpanBounded<TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow(
- sizeof(SkTSpanBounded<TCurve>)), SkTSpanBounded<TCurve>);
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkChunkAlloc* heap) {
+ SkTSpanBounded<OppCurve, TCurve>* bounded = SkNEW_PLACEMENT(heap->allocThrow(
+ sizeof(SkTSpanBounded<OppCurve, TCurve>)), (SkTSpanBounded<OppCurve, TCurve>));
bounded->fBounded = span;
bounded->fNext = fBounded;
fBounded = bounded;
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::addFollowing(SkTSpan<TCurve>* prior) {
- SkTSpan<TCurve>* result = this->addOne();
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing(
+ SkTSpan<TCurve, OppCurve>* prior) {
+ SkTSpan<TCurve, OppCurve>* result = this->addOne();
result->fStartT = prior ? prior->fEndT : 0;
- SkTSpan<TCurve>* next = prior ? prior->fNext : fHead;
+ SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead;
result->fEndT = next ? next->fStartT : 1;
result->fPrev = prior;
result->fNext = next;
@@ -352,11 +386,11 @@
return result;
}
-template<typename TCurve>
-void SkTSect<TCurve>::addForPerp(SkTSpan<TCurve>* span, double t) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) {
if (!span->hasOppT(t)) {
- SkTSpan<TCurve>* priorSpan;
- SkTSpan<TCurve>* opp = this->spanAtT(t, &priorSpan);
+ SkTSpan<TCurve, OppCurve>* priorSpan;
+ SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan);
if (!opp) {
opp = this->addFollowing(priorSpan);
#if DEBUG_PERP
@@ -373,22 +407,24 @@
span->addBounded(opp, &fHeap);
}
this->validate();
+#if DEBUG_T_SECT
span->validatePerpT(t);
+#endif
}
-template<typename TCurve>
-double SkTSpan<TCurve>::closestBoundedT(const SkDPoint& pt) const {
+template<typename TCurve, typename OppCurve>
+double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const {
double result = -1;
double closest = FLT_MAX;
- const SkTSpanBounded<TCurve>* testBounded = fBounded;
+ const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
- const SkTSpan* test = testBounded->fBounded;
+ const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
double startDist = test->fPart[0].distanceSquared(pt);
if (closest > startDist) {
closest = startDist;
result = test->fStartT;
}
- double endDist = test->fPart[TCurve::kPointLast].distanceSquared(pt);
+ double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt);
if (closest > endDist) {
closest = endDist;
result = test->fEndT;
@@ -400,8 +436,8 @@
}
#ifdef SK_DEBUG
-template<typename TCurve>
-bool SkTSpan<TCurve>::debugIsBefore(const SkTSpan* span) const {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const {
const SkTSpan* work = this;
do {
if (span == work) {
@@ -412,8 +448,8 @@
}
#endif
-template<typename TCurve>
-bool SkTSpan<TCurve>::contains(double t) const {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::contains(double t) const {
const SkTSpan* work = this;
do {
if (between(work->fStartT, t, work->fEndT)) {
@@ -423,16 +459,17 @@
return false;
}
-template<typename TCurve>
-const SkTSect<TCurve>* SkTSpan<TCurve>::debugOpp() const {
- return PATH_OPS_DEBUG_RELEASE(fDebugSect->debugOpp(), NULL);
+template<typename TCurve, typename OppCurve>
+const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const {
+ return SkDEBUGRELEASE(fDebugSect->debugOpp(), NULL);
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSpan<TCurve>::findOppSpan(const SkTSpan* opp) const {
- SkTSpanBounded<TCurve>* bounded = fBounded;
+template<typename TCurve, typename OppCurve>
+SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan(
+ const SkTSpan<OppCurve, TCurve>* opp) const {
+ SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
- SkTSpan* test = bounded->fBounded;
+ SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (opp == test) {
return test;
}
@@ -445,8 +482,9 @@
// 1 if hulls intersect
// 2 if hulls only share a common endpoint
// -1 if linear and further checking is required
-template<typename TCurve>
-int SkTSpan<TCurve>::hullCheck(const SkTSpan* opp, bool* start, bool* oppStart) {
+template<typename TCurve, typename OppCurve>
+int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp,
+ bool* start, bool* oppStart) {
if (fIsLinear) {
return -1;
}
@@ -472,8 +510,9 @@
// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
// use line intersection to guess a better split than 0.5
// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
-template<typename TCurve>
-int SkTSpan<TCurve>::hullsIntersect(SkTSpan* opp, bool* start, bool* oppStart) {
+template<typename TCurve, typename OppCurve>
+int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp,
+ bool* start, bool* oppStart) {
if (!fBounds.intersects(opp->fBounds)) {
return 0;
}
@@ -488,8 +527,8 @@
return -1;
}
-template<typename TCurve>
-void SkTSpan<TCurve>::init(const TCurve& c) {
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) {
fPrev = fNext = NULL;
fStartT = 0;
fEndT = 1;
@@ -497,8 +536,8 @@
resetBounds(c);
}
-template<typename TCurve>
-void SkTSpan<TCurve>::initBounds(const TCurve& c) {
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) {
fPart = c.subDivide(fStartT, fEndT);
fBounds.setBounds(fPart);
fCoinStart.init();
@@ -514,8 +553,8 @@
#endif
}
-template<typename TCurve>
-bool SkTSpan<TCurve>::linearsIntersect(SkTSpan* span) {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) {
int result = this->linearIntersects(span->fPart);
if (result <= 1) {
return SkToBool(result);
@@ -526,16 +565,16 @@
return SkToBool(result);
}
-template<typename TCurve>
-double SkTSpan<TCurve>::linearT(const SkDPoint& pt) const {
+template<typename TCurve, typename OppCurve>
+double SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const {
SkDVector len = fPart[TCurve::kPointLast] - fPart[0];
return fabs(len.fX) > fabs(len.fY)
? (pt.fX - fPart[0].fX) / len.fX
: (pt.fY - fPart[0].fY) / len.fY;
}
-template<typename TCurve>
-int SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const {
+template<typename TCurve, typename OppCurve>
+int SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const {
// looks like q1 is near-linear
int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes
if (!fPart.controlsInside()) {
@@ -559,7 +598,7 @@
double opp = fPart[end].fY - origY;
double maxPart = SkTMax(fabs(adj), fabs(opp));
double sign = 0; // initialization to shut up warning in release build
- for (int n = 0; n < TCurve::kPointCount; ++n) {
+ for (int n = 0; n < OppCurve::kPointCount; ++n) {
double dx = q2[n].fY - origY;
double dy = q2[n].fX - origX;
double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
@@ -581,33 +620,33 @@
return 0;
}
-template<typename TCurve>
-bool SkTSpan<TCurve>::onlyEndPointsInCommon(const SkTSpan* opp, bool* start, bool* oppStart,
- bool* ptsInCommon) {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp,
+ bool* start, bool* oppStart, bool* ptsInCommon) {
if (opp->fPart[0] == fPart[0]) {
*start = *oppStart = true;
} else if (opp->fPart[0] == fPart[TCurve::kPointLast]) {
*start = false;
*oppStart = true;
- } else if (opp->fPart[TCurve::kPointLast] == fPart[0]) {
+ } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) {
*start = true;
*oppStart = false;
- } else if (opp->fPart[TCurve::kPointLast] == fPart[TCurve::kPointLast]) {
+ } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) {
*start = *oppStart = false;
} else {
*ptsInCommon = false;
return false;
}
*ptsInCommon = true;
- const SkDPoint* o1Pts[TCurve::kPointCount - 1], * o2Pts[TCurve::kPointCount - 1];
+ const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1];
int baseIndex = *start ? 0 : TCurve::kPointLast;
- fPart.otherPts(baseIndex, o1Pts);
- opp->fPart.otherPts(*oppStart ? 0 : TCurve::kPointLast, o2Pts);
+ fPart.otherPts(baseIndex, otherPts);
+ opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts);
const SkDPoint& base = fPart[baseIndex];
- for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(o1Pts); ++o1) {
- SkDVector v1 = *o1Pts[o1] - base;
- for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(o2Pts); ++o2) {
- SkDVector v2 = *o2Pts[o2] - base;
+ for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) {
+ SkDVector v1 = *otherPts[o1] - base;
+ for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) {
+ SkDVector v2 = *oppOtherPts[o2] - base;
if (v2.dot(v1) >= 0) {
return false;
}
@@ -616,11 +655,11 @@
return true;
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSpan<TCurve>::oppT(double t) const {
- SkTSpanBounded<TCurve>* bounded = fBounded;
+template<typename TCurve, typename OppCurve>
+SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const {
+ SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
- SkTSpan* test = bounded->fBounded;
+ SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (between(test->fStartT, t, test->fEndT)) {
return test;
}
@@ -629,26 +668,26 @@
return NULL;
}
-template<typename TCurve>
-bool SkTSpan<TCurve>::removeAllBounded() {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::removeAllBounded() {
bool deleteSpan = false;
- SkTSpanBounded<TCurve>* bounded = fBounded;
+ SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
- SkTSpan* opp = bounded->fBounded;
+ SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded;
deleteSpan |= opp->removeBounded(this);
bounded = bounded->fNext;
}
return deleteSpan;
}
-template<typename TCurve>
-bool SkTSpan<TCurve>::removeBounded(const SkTSpan* opp) {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) {
if (fHasPerp) {
bool foundStart = false;
bool foundEnd = false;
- SkTSpanBounded<TCurve>* bounded = fBounded;
+ SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
while (bounded) {
- SkTSpan* test = bounded->fBounded;
+ SkTSpan<OppCurve, TCurve>* test = bounded->fBounded;
if (opp != test) {
foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
@@ -661,10 +700,10 @@
fCoinEnd.init();
}
}
- SkTSpanBounded<TCurve>* bounded = fBounded;
- SkTSpanBounded<TCurve>* prev = NULL;
+ SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded;
+ SkTSpanBounded<OppCurve, TCurve>* prev = NULL;
while (bounded) {
- SkTSpanBounded<TCurve>* boundedNext = bounded->fNext;
+ SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext;
if (opp == bounded->fBounded) {
if (prev) {
prev->fNext = boundedNext;
@@ -681,8 +720,8 @@
return false;
}
-template<typename TCurve>
-bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) {
+template<typename TCurve, typename OppCurve>
+bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkChunkAlloc* heap) {
fStartT = t;
fEndT = work->fEndT;
if (fStartT == fEndT) {
@@ -703,7 +742,7 @@
if (fNext) {
fNext->fPrev = this;
}
- SkTSpanBounded<TCurve>* bounded = work->fBounded;
+ SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded;
fBounded = NULL;
while (bounded) {
this->addBounded(bounded->fBounded, heap);
@@ -717,8 +756,8 @@
return true;
}
-template<typename TCurve>
-void SkTSpan<TCurve>::validate() const {
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::validate() const {
#if DEBUG_T_SECT
SkASSERT(fNext == NULL || fNext != fPrev);
SkASSERT(fNext == NULL || this == fNext->fPrev);
@@ -743,12 +782,12 @@
#endif
}
-template<typename TCurve>
-void SkTSpan<TCurve>::validateBounded() const {
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::validateBounded() const {
#if DEBUG_VALIDATE
- const SkTSpanBounded<TCurve>* testBounded = fBounded;
+ const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
- const SkTSpan* overlap = testBounded->fBounded;
+ SkDEBUGCODE_(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded);
SkASSERT(!overlap->fDeleted);
SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
SkASSERT(overlap->findOppSpan(this));
@@ -757,33 +796,29 @@
#endif
}
-template<typename TCurve>
-void SkTSpan<TCurve>::validatePerpT(double oppT) const {
-#if DEBUG_VALIDATE
- const SkTSpanBounded<TCurve>* testBounded = fBounded;
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const {
+ const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded;
while (testBounded) {
- const SkTSpan* overlap = testBounded->fBounded;
+ const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded;
if (between(overlap->fStartT, oppT, overlap->fEndT)) {
return;
}
testBounded = testBounded->fNext;
}
SkASSERT(0);
-#endif
}
-template<typename TCurve>
-void SkTSpan<TCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
-#if DEBUG_T_SECT
- PATH_OPS_DEBUG_CODE(SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt));
-#endif
+template<typename TCurve, typename OppCurve>
+void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const {
+ SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
}
-template<typename TCurve>
-SkTSect<TCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
+template<typename TCurve, typename OppCurve>
+SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
: fCurve(c)
- , fHeap(sizeof(SkTSpan<TCurve>) * 4)
+ , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4)
, fCoincident(NULL)
, fDeleted(NULL)
, fActiveCount(0)
@@ -795,15 +830,16 @@
fHead->init(c);
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::addOne() {
- SkTSpan<TCurve>* result;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() {
+ SkTSpan<TCurve, OppCurve>* result;
if (fDeleted) {
result = fDeleted;
result->reset();
fDeleted = result->fNext;
} else {
- result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve>)), SkTSpan<TCurve>);
+ result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)),
+ (SkTSpan<TCurve, OppCurve>));
result->fBounded = NULL;
#if DEBUG_T_SECT
++fDebugAllocatedCount;
@@ -813,21 +849,21 @@
result->fDeleted = false;
++fActiveCount;
PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
- PATH_OPS_DEBUG_CODE(result->fDebugSect = this);
+ SkDEBUGCODE(result->fDebugSect = this);
return result;
}
-template<typename TCurve>
-bool SkTSect<TCurve>::binarySearchCoin(SkTSect* sect2, double tStart, double tStep,
- double* resultT, double* oppT) {
- SkTSpan<TCurve> work;
+template<typename TCurve, typename OppCurve>
+bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart,
+ double tStep, double* resultT, double* oppT) {
+ SkTSpan<TCurve, OppCurve> work;
double result = work.fStartT = work.fEndT = tStart;
- PATH_OPS_DEBUG_CODE(work.fDebugSect = this);
+ SkDEBUGCODE(work.fDebugSect = this);
SkDPoint last = fCurve.ptAtT(tStart);
SkDPoint oppPt;
bool flip = false;
SkDEBUGCODE(bool down = tStep < 0);
- const TCurve& opp = sect2->fCurve;
+ const OppCurve& opp = sect2->fCurve;
do {
tStep *= 0.5;
work.fStartT += tStep;
@@ -867,7 +903,7 @@
}
if (oppPt.approximatelyEqual(opp[0])) {
*oppT = 0;
- } else if (oppPt.approximatelyEqual(opp[TCurve::kPointLast])) {
+ } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) {
*oppT = 1;
}
*resultT = result;
@@ -877,25 +913,26 @@
// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
// so that each quad sect has a pointer to the largest, and can update it as spans
// are split
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::boundsMax() const {
- SkTSpan<TCurve>* test = fHead;
- SkTSpan<TCurve>* largest = fHead;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const {
+ SkTSpan<TCurve, OppCurve>* test = fHead;
+ SkTSpan<TCurve, OppCurve>* largest = fHead;
bool lCollapsed = largest->fCollapsed;
while ((test = test->fNext)) {
bool tCollapsed = test->fCollapsed;
if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
largest->fBoundsMax < test->fBoundsMax)) {
largest = test;
+ lCollapsed = test->fCollapsed;
}
}
return largest;
}
-template<typename TCurve>
-void SkTSect<TCurve>::coincidentCheck(SkTSect* sect2) {
- SkTSpan<TCurve>* first = fHead;
- SkTSpan<TCurve>* last, * next;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) {
+ SkTSpan<TCurve, OppCurve>* first = fHead;
+ SkTSpan<TCurve, OppCurve>* last, * next;
do {
int consecutive = this->countConsecutiveSpans(first, &last);
next = last->fNext;
@@ -908,16 +945,16 @@
this->validate();
sect2->validate();
// check to see if a range of points are on the curve
- SkTSpan<TCurve>* coinStart = first;
+ SkTSpan<TCurve, OppCurve>* coinStart = first;
do {
coinStart = this->extractCoincident(sect2, coinStart, last);
} while (coinStart && !last->fDeleted);
} while ((first = next));
}
-template<typename TCurve>
-bool SkTSect<TCurve>::coincidentHasT(double t) {
- SkTSpan<TCurve>* test = fCoincident;
+template<typename TCurve, typename OppCurve>
+bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) {
+ SkTSpan<TCurve, OppCurve>* test = fCoincident;
while (test) {
if (between(test->fStartT, t, test->fEndT)) {
return true;
@@ -927,12 +964,25 @@
return false;
}
-template<typename TCurve>
-void SkTSect<TCurve>::computePerpendiculars(SkTSect* sect2, SkTSpan<TCurve>* first,
- SkTSpan<TCurve>* last) {
- const TCurve& opp = sect2->fCurve;
- SkTSpan<TCurve>* work = first;
- SkTSpan<TCurve>* prior = NULL;
+template<typename TCurve, typename OppCurve>
+int SkTSect<TCurve, OppCurve>::collapsed() const {
+ int result = 0;
+ const SkTSpan<TCurve, OppCurve>* test = fHead;
+ while (test) {
+ if (test->fCollapsed) {
+ ++result;
+ }
+ test = test->next();
+ }
+ return result;
+}
+
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2,
+ SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
+ const OppCurve& opp = sect2->fCurve;
+ SkTSpan<TCurve, OppCurve>* work = first;
+ SkTSpan<TCurve, OppCurve>* prior = NULL;
do {
if (!work->fHasPerp && !work->fCollapsed) {
if (prior) {
@@ -968,13 +1018,13 @@
} while (true);
}
-template<typename TCurve>
-int SkTSect<TCurve>::countConsecutiveSpans(SkTSpan<TCurve>* first,
- SkTSpan<TCurve>** lastPtr) const {
+template<typename TCurve, typename OppCurve>
+int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>** lastPtr) const {
int consecutive = 1;
- SkTSpan<TCurve>* last = first;
+ SkTSpan<TCurve, OppCurve>* last = first;
do {
- SkTSpan<TCurve>* next = last->fNext;
+ SkTSpan<TCurve, OppCurve>* next = last->fNext;
if (!next) {
break;
}
@@ -988,9 +1038,9 @@
return consecutive;
}
-template<typename TCurve>
-bool SkTSect<TCurve>::debugHasBounded(const SkTSpan<TCurve>* span) const {
- const SkTSpan<TCurve>* test = fHead;
+template<typename TCurve, typename OppCurve>
+bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const {
+ const SkTSpan<TCurve, OppCurve>* test = fHead;
if (!test) {
return false;
}
@@ -1002,10 +1052,10 @@
return false;
}
-template<typename TCurve>
-void SkTSect<TCurve>::deleteEmptySpans() {
- SkTSpan<TCurve>* test;
- SkTSpan<TCurve>* next = fHead;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::deleteEmptySpans() {
+ SkTSpan<TCurve, OppCurve>* test;
+ SkTSpan<TCurve, OppCurve>* next = fHead;
while ((test = next)) {
next = test->fNext;
if (!test->fBounded) {
@@ -1014,10 +1064,11 @@
}
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::extractCoincident(SkTSect* sect2, SkTSpan<TCurve>* first,
- SkTSpan<TCurve>* last) {
- first = findCoincidentRun(first, &last, sect2);
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::extractCoincident(
+ SkTSect<OppCurve, TCurve>* sect2,
+ SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) {
+ first = findCoincidentRun(first, &last);
if (!first) {
return NULL;
}
@@ -1025,24 +1076,25 @@
double startT = first->fStartT;
double oppStartT SK_INIT_TO_AVOID_WARNING;
double oppEndT SK_INIT_TO_AVOID_WARNING;
- SkTSpan<TCurve>* prev = first->fPrev;
+ SkTSpan<TCurve, OppCurve>* prev = first->fPrev;
SkASSERT(first->fCoinStart.isCoincident());
- SkTSpan<TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
+ SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT());
SkASSERT(last->fCoinEnd.isCoincident());
bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
double coinStart;
SkDEBUGCODE(double coinEnd);
+ SkTSpan<OppCurve, TCurve>* cutFirst;
if (prev && prev->fEndT == startT
&& this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
&oppStartT)
- && prev->fStartT < coinStart && coinStart < startT) {
- oppFirst = prev->findOppT(oppStartT); // find opp start before splitting prev
- SkASSERT(oppFirst);
+ && prev->fStartT < coinStart && coinStart < startT
+ && (cutFirst = prev->oppT(oppStartT))) {
+ oppFirst = cutFirst;
first = this->addSplitAt(prev, coinStart);
first->markCoincident();
prev->fCoinEnd.markCoincident();
if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
- SkTSpan<TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
+ SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
if (oppMatched) {
oppFirst->fCoinEnd.markCoincident();
oppHalf->markCoincident();
@@ -1056,7 +1108,8 @@
SkDEBUGCODE(coinStart = first->fStartT);
SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
}
- SkTSpan<TCurve>* oppLast;
+ // FIXME: incomplete : if we're not at the end, find end of coin
+ SkTSpan<OppCurve, TCurve>* oppLast;
SkASSERT(last->fCoinEnd.isCoincident());
oppLast = last->findOppT(last->fCoinEnd.perpT());
SkDEBUGCODE(coinEnd = last->fEndT);
@@ -1073,8 +1126,8 @@
// reduce coincident runs to single entries
this->validate();
sect2->validate();
- bool deleteThisSpan = this->updateBounded(first, last, oppFirst);
- bool deleteSect2Span = sect2->updateBounded(oppFirst, oppLast, first);
+ bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
+ deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
this->removeSpanRange(first, last);
sect2->removeSpanRange(oppFirst, oppLast);
first->fEndT = last->fEndT;
@@ -1096,10 +1149,8 @@
last = first->fNext;
this->removeCoincident(first, false);
sect2->removeCoincident(oppFirst, true);
- if (deleteThisSpan) {
+ if (deleteEmptySpans) {
this->deleteEmptySpans();
- }
- if (deleteSect2Span) {
sect2->deleteEmptySpans();
}
this->validate();
@@ -1107,17 +1158,19 @@
return last && !last->fDeleted ? last : NULL;
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::findCoincidentRun(SkTSpan<TCurve>* first,
- SkTSpan<TCurve>** lastPtr, const SkTSect* sect2) {
- SkTSpan<TCurve>* work = first;
- SkTSpan<TCurve>* lastCandidate = NULL;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun(
+ SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) {
+ SkTSpan<TCurve, OppCurve>* work = first;
+ SkTSpan<TCurve, OppCurve>* lastCandidate = NULL;
first = NULL;
// find the first fully coincident span
do {
if (work->fCoinStart.isCoincident()) {
+#if DEBUG_T_SECT
work->validatePerpT(work->fCoinStart.perpT());
work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
+#endif
SkASSERT(work->hasOppT(work->fCoinStart.perpT()));
if (!work->fCoinEnd.isCoincident()) {
break;
@@ -1126,6 +1179,9 @@
if (!first) {
first = work;
}
+ } else if (first && work->fCollapsed) {
+ *lastPtr = lastCandidate;
+ return first;
} else {
lastCandidate = NULL;
SkASSERT(!first);
@@ -1142,9 +1198,10 @@
return first;
}
-template<typename TCurve>
-int SkTSect<TCurve>::intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
- SkTSpan<TCurve>* oppSpan, int* oppResult) const {
+template<typename TCurve, typename OppCurve>
+int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span,
+ SkTSect<OppCurve, TCurve>* opp,
+ SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) {
bool spanStart, oppStart;
int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
if (hullResult >= 0) {
@@ -1194,21 +1251,22 @@
// while the intersection points are sufficiently far apart:
// construct the tangent lines from the intersections
// find the point where the tangent line intersects the opposite curve
-template<typename TCurve>
-int SkTSect<TCurve>::linesIntersect(const SkTSpan<TCurve>* span, const SkTSect* opp,
- const SkTSpan<TCurve>* oppSpan, SkIntersections* i) const {
+template<typename TCurve, typename OppCurve>
+int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span,
+ SkTSect<OppCurve, TCurve>* opp,
+ SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) {
SkIntersections thisRayI, oppRayI;
SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }};
- SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[TCurve::kPointLast] }};
+ SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }};
int loopCount = 0;
double bestDistSq = DBL_MAX;
+ if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
+ return 0;
+ }
+ if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
+ return 0;
+ }
do {
- if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
- return 0;
- }
- if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
- return 0;
- }
// pick the closest pair of points
double closest = DBL_MAX;
int closeIndex SK_INIT_TO_AVOID_WARNING;
@@ -1230,7 +1288,7 @@
}
}
if (closest == DBL_MAX) {
- return 0;
+ break;
}
const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
const SkDPoint& iPt = oppRayI.pt(closeIndex);
@@ -1242,20 +1300,88 @@
}
double distSq = oppIPt.distanceSquared(iPt);
if (bestDistSq < distSq || ++loopCount > 5) {
- break;
+ return 0;
}
bestDistSq = distSq;
- thisLine[0] = fCurve.ptAtT(oppRayI[0][closeIndex]);
- thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppRayI[0][closeIndex]);
- oppLine[0] = opp->fCurve.ptAtT(thisRayI[0][oppCloseIndex]);
- oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(thisRayI[0][oppCloseIndex]);
+ double oppStart = oppRayI[0][closeIndex];
+ thisLine[0] = fCurve.ptAtT(oppStart);
+ thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
+ if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
+ break;
+ }
+ double start = thisRayI[0][oppCloseIndex];
+ oppLine[0] = opp->fCurve.ptAtT(start);
+ oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
+ if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
+ break;
+ }
} while (true);
- return false;
+ // convergence may fail if the curves are nearly coincident
+ SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE;
+ oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve);
+ oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve);
+ double tStart = oCoinS.perpT();
+ double tEnd = oCoinE.perpT();
+ bool swap = tStart > tEnd;
+ if (swap) {
+ SkTSwap(tStart, tEnd);
+ }
+ tStart = SkTMax(tStart, span->fStartT);
+ tEnd = SkTMin(tEnd, span->fEndT);
+ if (tStart > tEnd) {
+ return 0;
+ }
+ SkDVector perpS, perpE;
+ if (tStart == span->fStartT) {
+ SkTCoincident<TCurve, OppCurve> coinS;
+ coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve);
+ perpS = span->fPart[0] - coinS.perpPt();
+ } else if (swap) {
+ perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
+ } else {
+ perpS = oCoinS.perpPt() - oppSpan->fPart[0];
+ }
+ if (tEnd == span->fEndT) {
+ SkTCoincident<TCurve, OppCurve> coinE;
+ coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve);
+ perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt();
+ } else if (swap) {
+ perpE = oCoinS.perpPt() - oppSpan->fPart[0];
+ } else {
+ perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast];
+ }
+ if (perpS.dot(perpE) >= 0) {
+ return 0;
+ }
+ SkTCoincident<TCurve, OppCurve> coinW;
+ double workT = tStart;
+ double tStep = tEnd - tStart;
+ SkDPoint workPt;
+ do {
+ tStep *= 0.5;
+ if (precisely_zero(tStep)) {
+ return 0;
+ }
+ workT += tStep;
+ workPt = fCurve.ptAtT(workT);
+ coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
+ SkDVector perpW = workPt - coinW.perpPt();
+ if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
+ tStep = -tStep;
+ }
+ } while (!workPt.approximatelyEqual(coinW.perpPt()));
+ double oppTTest = coinW.perpT();
+ if (!opp->fHead->contains(oppTTest)) {
+ return 0;
+ }
+ i->setMax(1);
+ i->insert(workT, oppTTest, workPt);
+ return 1;
}
-template<typename TCurve>
-void SkTSect<TCurve>::markSpanGone(SkTSpan<TCurve>* span) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) {
--fActiveCount;
span->fNext = fDeleted;
fDeleted = span;
@@ -1263,16 +1389,17 @@
span->fDeleted = true;
}
-template<typename TCurve>
-bool SkTSect<TCurve>::matchedDirection(double t, const SkTSect* sect2, double t2) const {
+template<typename TCurve, typename OppCurve>
+bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2,
+ double t2) const {
SkDVector dxdy = this->fCurve.dxdyAtT(t);
SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
return dxdy.dot(dxdy2) >= 0;
}
-template<typename TCurve>
-void SkTSect<TCurve>::matchedDirCheck(double t, const SkTSect* sect2, double t2,
- bool* calcMatched, bool* oppMatched) const {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2,
+ double t2, bool* calcMatched, bool* oppMatched) const {
if (*calcMatched) {
SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
} else {
@@ -1281,13 +1408,13 @@
}
}
-template<typename TCurve>
-void SkTSect<TCurve>::mergeCoincidence(SkTSect* sect2) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) {
double smallLimit = 0;
do {
// find the smallest unprocessed span
- SkTSpan<TCurve>* smaller = NULL;
- SkTSpan<TCurve>* test = fCoincident;
+ SkTSpan<TCurve, OppCurve>* smaller = NULL;
+ SkTSpan<TCurve, OppCurve>* test = fCoincident;
do {
if (test->fStartT < smallLimit) {
continue;
@@ -1302,9 +1429,9 @@
}
smallLimit = smaller->fEndT;
// find next larger span
- SkTSpan<TCurve>* prior = NULL;
- SkTSpan<TCurve>* larger = NULL;
- SkTSpan<TCurve>* largerPrior = NULL;
+ SkTSpan<TCurve, OppCurve>* prior = NULL;
+ SkTSpan<TCurve, OppCurve>* larger = NULL;
+ SkTSpan<TCurve, OppCurve>* largerPrior = NULL;
test = fCoincident;
do {
if (test->fStartT < smaller->fEndT) {
@@ -1323,7 +1450,7 @@
// check middle t value to see if it is coincident as well
double midT = (smaller->fEndT + larger->fStartT) / 2;
SkDPoint midPt = fCurve.ptAtT(midT);
- SkTCoincident<TCurve> coin;
+ SkTCoincident<TCurve, OppCurve> coin;
coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
if (coin.isCoincident()) {
smaller->fEndT = larger->fEndT;
@@ -1337,10 +1464,11 @@
} while (true);
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::prev(SkTSpan<TCurve>* span) const {
- SkTSpan<TCurve>* result = NULL;
- SkTSpan<TCurve>* test = fHead;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev(
+ SkTSpan<TCurve, OppCurve>* span) const {
+ SkTSpan<TCurve, OppCurve>* result = NULL;
+ SkTSpan<TCurve, OppCurve>* test = fHead;
while (span != test) {
result = test;
test = test->fNext;
@@ -1349,13 +1477,13 @@
return result;
}
-template<typename TCurve>
-void SkTSect<TCurve>::recoverCollapsed() {
- SkTSpan<TCurve>* deleted = fDeleted;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::recoverCollapsed() {
+ SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
while (deleted) {
- SkTSpan<TCurve>* delNext = deleted->fNext;
+ SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext;
if (deleted->fCollapsed) {
- SkTSpan<TCurve>** spanPtr = &fHead;
+ SkTSpan<TCurve, OppCurve>** spanPtr = &fHead;
while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
spanPtr = &(*spanPtr)->fNext;
}
@@ -1366,13 +1494,13 @@
}
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeAllBut(const SkTSpan<TCurve>* keep, SkTSpan<TCurve>* span,
- SkTSect* opp) {
- const SkTSpanBounded<TCurve>* testBounded = span->fBounded;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep,
+ SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) {
+ const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
while (testBounded) {
- SkTSpan<TCurve>* bounded = testBounded->fBounded;
- const SkTSpanBounded<TCurve>* next = testBounded->fNext;
+ SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded;
+ const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
// may have been deleted when opp did 'remove all but'
if (bounded != keep && !bounded->fDeleted) {
SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
@@ -1387,10 +1515,10 @@
SkASSERT(keep->findOppSpan(span));
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeByPerpendicular(SkTSect<TCurve>* opp) {
- SkTSpan<TCurve>* test = fHead;
- SkTSpan<TCurve>* next;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) {
+ SkTSpan<TCurve, OppCurve>* test = fHead;
+ SkTSpan<TCurve, OppCurve>* next;
do {
next = test->fNext;
if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
@@ -1409,8 +1537,8 @@
} while ((test = next));
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeCoincident(SkTSpan<TCurve>* span, bool isBetween) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) {
this->unlinkSpan(span);
if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
--fActiveCount;
@@ -1421,21 +1549,22 @@
}
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeSpan(SkTSpan<TCurve>* span) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {
this->unlinkSpan(span);
this->markSpanGone(span);
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeSpanRange(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>* last) {
if (first == last) {
return;
}
- SkTSpan<TCurve>* span = first;
+ SkTSpan<TCurve, OppCurve>* span = first;
SkASSERT(span);
- SkTSpan<TCurve>* final = last->fNext;
- SkTSpan<TCurve>* next = span->fNext;
+ SkTSpan<TCurve, OppCurve>* final = last->fNext;
+ SkTSpan<TCurve, OppCurve>* next = span->fNext;
while ((span = next) && span != final) {
next = span->fNext;
this->markSpanGone(span);
@@ -1446,12 +1575,13 @@
first->fNext = final;
}
-template<typename TCurve>
-void SkTSect<TCurve>::removeSpans(SkTSpan<TCurve>* span, SkTSect<TCurve>* opp) {
- SkTSpanBounded<TCurve>* bounded = span->fBounded;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span,
+ SkTSect<OppCurve, TCurve>* opp) {
+ SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded;
while (bounded) {
- SkTSpan<TCurve>* spanBounded = bounded->fBounded;
- SkTSpanBounded<TCurve>* next = bounded->fNext;
+ SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded;
+ SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext;
if (span->removeBounded(spanBounded)) { // shuffles last into position 0
this->removeSpan(span);
}
@@ -1463,10 +1593,11 @@
}
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::spanAtT(double t, SkTSpan<TCurve>** priorSpan) {
- SkTSpan<TCurve>* test = fHead;
- SkTSpan<TCurve>* prev = NULL;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t,
+ SkTSpan<TCurve, OppCurve>** priorSpan) {
+ SkTSpan<TCurve, OppCurve>* test = fHead;
+ SkTSpan<TCurve, OppCurve>* prev = NULL;
while (test && test->fEndT < t) {
prev = test;
test = test->fNext;
@@ -1475,10 +1606,10 @@
return test && test->fStartT <= t ? test : NULL;
}
-template<typename TCurve>
-SkTSpan<TCurve>* SkTSect<TCurve>::tail() {
- SkTSpan<TCurve>* result = fHead;
- SkTSpan<TCurve>* next = fHead;
+template<typename TCurve, typename OppCurve>
+SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() {
+ SkTSpan<TCurve, OppCurve>* result = fHead;
+ SkTSpan<TCurve, OppCurve>* next = fHead;
while ((next = next->fNext)) {
if (next->fEndT > result->fEndT) {
result = next;
@@ -1489,13 +1620,14 @@
/* Each span has a range of opposite spans it intersects. After the span is split in two,
adjust the range to its new size */
-template<typename TCurve>
-void SkTSect<TCurve>::trim(SkTSpan<TCurve>* span, SkTSect* opp) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span,
+ SkTSect<OppCurve, TCurve>* opp) {
span->initBounds(fCurve);
- const SkTSpanBounded<TCurve>* testBounded = span->fBounded;
+ const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded;
while (testBounded) {
- SkTSpan<TCurve>* test = testBounded->fBounded;
- const SkTSpanBounded<TCurve>* next = testBounded->fNext;
+ SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded;
+ const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext;
int oppSects, sects = this->intersects(span, opp, test, &oppSects);
if (sects >= 1) {
if (oppSects == 2) {
@@ -1519,10 +1651,10 @@
}
}
-template<typename TCurve>
-void SkTSect<TCurve>::unlinkSpan(SkTSpan<TCurve>* span) {
- SkTSpan<TCurve>* prev = span->fPrev;
- SkTSpan<TCurve>* next = span->fNext;
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) {
+ SkTSpan<TCurve, OppCurve>* prev = span->fPrev;
+ SkTSpan<TCurve, OppCurve>* next = span->fNext;
if (prev) {
prev->fNext = next;
if (next) {
@@ -1536,11 +1668,11 @@
}
}
-template<typename TCurve>
-bool SkTSect<TCurve>::updateBounded(SkTSpan<TCurve>* first, SkTSpan<TCurve>* last,
- SkTSpan<TCurve>* oppFirst) {
- SkTSpan<TCurve>* test = first;
- const SkTSpan<TCurve>* final = last->next();
+template<typename TCurve, typename OppCurve>
+bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first,
+ SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) {
+ SkTSpan<TCurve, OppCurve>* test = first;
+ const SkTSpan<TCurve, OppCurve>* final = last->next();
bool deleteSpan = false;
do {
deleteSpan |= test->removeAllBounded();
@@ -1552,12 +1684,12 @@
}
-template<typename TCurve>
-void SkTSect<TCurve>::validate() const {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::validate() const {
#if DEBUG_T_SECT
int count = 0;
if (fHead) {
- const SkTSpan<TCurve>* span = fHead;
+ const SkTSpan<TCurve, OppCurve>* span = fHead;
SkASSERT(!span->fPrev);
SkDEBUGCODE(double last = 0);
do {
@@ -1570,12 +1702,12 @@
SkASSERT(count == fActiveCount);
SkASSERT(fActiveCount <= fDebugAllocatedCount);
int deletedCount = 0;
- const SkTSpan<TCurve>* deleted = fDeleted;
+ const SkTSpan<TCurve, OppCurve>* deleted = fDeleted;
while (deleted) {
++deletedCount;
deleted = deleted->fNext;
}
- const SkTSpan<TCurve>* coincident = fCoincident;
+ const SkTSpan<TCurve, OppCurve>* coincident = fCoincident;
while (coincident) {
++deletedCount;
coincident = coincident->fNext;
@@ -1584,28 +1716,28 @@
#endif
}
-template<typename TCurve>
-void SkTSect<TCurve>::validateBounded() const {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::validateBounded() const {
#if DEBUG_T_SECT
if (!fHead) {
return;
}
- const SkTSpan<TCurve>* span = fHead;
+ const SkTSpan<TCurve, OppCurve>* span = fHead;
do {
span->validateBounded();
} while ((span = span->fNext) != NULL);
#endif
}
-template<typename TCurve>
-int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
- SkIntersections* intersections) {
+template<typename TCurve, typename OppCurve>
+int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1,
+ const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
int zeroOneSet = 0;
if (sect1->fCurve[0] == sect2->fCurve[0]) {
zeroOneSet |= kZeroS1Set | kZeroS2Set;
intersections->insert(0, 0, sect1->fCurve[0]);
}
- if (sect1->fCurve[0] == sect2->fCurve[TCurve::kPointLast]) {
+ if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) {
zeroOneSet |= kZeroS1Set | kOneS2Set;
intersections->insert(0, 1, sect1->fCurve[0]);
}
@@ -1613,7 +1745,7 @@
zeroOneSet |= kOneS1Set | kZeroS2Set;
intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]);
}
- if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[TCurve::kPointLast]) {
+ if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) {
zeroOneSet |= kOneS1Set | kOneS2Set;
intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]);
}
@@ -1624,9 +1756,9 @@
intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
}
if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
- && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) {
+ && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) {
zeroOneSet |= kZeroS1Set | kOneS2Set;
- intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[TCurve::kPointLast]);
+ intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]);
}
// check for one
if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
@@ -1636,15 +1768,15 @@
}
if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
&& sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[
- TCurve::kPointLast])) {
+ OppCurve::kPointLast])) {
zeroOneSet |= kOneS1Set | kOneS2Set;
intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast],
- sect2->fCurve[TCurve::kPointLast]);
+ sect2->fCurve[OppCurve::kPointLast]);
}
return zeroOneSet;
}
-template<typename TCurve>
+template<typename TCurve, typename OppCurve>
struct SkClosestRecord {
bool operator<(const SkClosestRecord& rh) const {
return fClosest < rh.fClosest;
@@ -1656,10 +1788,10 @@
intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
}
- void findEnd(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2,
+ void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2,
int c1Index, int c2Index) {
const TCurve& c1 = span1->part();
- const TCurve& c2 = span2->part();
+ const OppCurve& c2 = span2->part();
if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
return;
}
@@ -1700,7 +1832,8 @@
void reset() {
fClosest = FLT_MAX;
- SkDEBUGCODE(fC1Span = fC2Span = NULL);
+ SkDEBUGCODE(fC1Span = NULL);
+ SkDEBUGCODE(fC2Span = NULL);
SkDEBUGCODE(fC1Index = fC2Index = -1);
}
@@ -1711,8 +1844,8 @@
fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
}
- const SkTSpan<TCurve>* fC1Span;
- const SkTSpan<TCurve>* fC2Span;
+ const SkTSpan<TCurve, OppCurve>* fC1Span;
+ const SkTSpan<OppCurve, TCurve>* fC2Span;
double fC1StartT;
double fC1EndT;
double fC2StartT;
@@ -1722,24 +1855,24 @@
int fC2Index;
};
-template<typename TCurve>
+template<typename TCurve, typename OppCurve>
struct SkClosestSect {
SkClosestSect()
: fUsed(0) {
fClosest.push_back().reset();
}
- bool find(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2) {
- SkClosestRecord<TCurve>* record = &fClosest[fUsed];
+ bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2) {
+ SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed];
record->findEnd(span1, span2, 0, 0);
- record->findEnd(span1, span2, 0, TCurve::kPointLast);
+ record->findEnd(span1, span2, 0, OppCurve::kPointLast);
record->findEnd(span1, span2, TCurve::kPointLast, 0);
- record->findEnd(span1, span2, TCurve::kPointLast, TCurve::kPointLast);
+ record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast);
if (record->fClosest == FLT_MAX) {
return false;
}
for (int index = 0; index < fUsed; ++index) {
- SkClosestRecord<TCurve>* test = &fClosest[index];
+ SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index];
if (test->matesWith(*record)) {
if (test->fClosest > record->fClosest) {
test->merge(*record);
@@ -1755,34 +1888,37 @@
}
void finish(SkIntersections* intersections) const {
- SkSTArray<TCurve::kMaxIntersections * 2, const SkClosestRecord<TCurve>*, true> closestPtrs;
+ SkSTArray<TCurve::kMaxIntersections * 3,
+ const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs;
for (int index = 0; index < fUsed; ++index) {
closestPtrs.push_back(&fClosest[index]);
}
- SkTQSort<const SkClosestRecord<TCurve> >(closestPtrs.begin(), closestPtrs.end() - 1);
+ SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end()
+ - 1);
for (int index = 0; index < fUsed; ++index) {
- const SkClosestRecord<TCurve>* test = closestPtrs[index];
+ const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index];
test->addIntersection(intersections);
}
}
// this is oversized so that an extra records can merge into final one
- SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve>, true> fClosest;
+ SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest;
int fUsed;
};
// returns true if the rect is too small to consider
-template<typename TCurve>
-void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections) {
+template<typename TCurve, typename OppCurve>
+void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1,
+ SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) {
#if DEBUG_T_SECT_DUMP > 1
gDumpTSectNum = 0;
#endif
- PATH_OPS_DEBUG_CODE(sect1->fOppSect = sect2);
- PATH_OPS_DEBUG_CODE(sect2->fOppSect = sect1);
+ SkDEBUGCODE(sect1->fOppSect = sect2);
+ SkDEBUGCODE(sect2->fOppSect = sect1);
intersections->reset();
- intersections->setMax(TCurve::kMaxIntersections * 2); // give extra for slop
- SkTSpan<TCurve>* span1 = sect1->fHead;
- SkTSpan<TCurve>* span2 = sect2->fHead;
+ intersections->setMax(TCurve::kMaxIntersections * 3); // give extra for slop
+ SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead;
+ SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead;
int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
// SkASSERT(between(0, sect, 2));
if (!sect) {
@@ -1796,28 +1932,36 @@
span2->addBounded(span1, §2->fHeap);
do {
// find the largest bounds
- SkTSpan<TCurve>* largest1 = sect1->boundsMax();
+ SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax();
if (!largest1) {
break;
}
- SkTSpan<TCurve>* largest2 = sect2->boundsMax();
- bool split1 = !largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
- || (!largest1->fCollapsed && largest2->fCollapsed)));
+ SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax();
// split it
- SkTSpan<TCurve>* half1 = split1 ? largest1 : largest2;
- SkASSERT(half1);
- if (half1->fCollapsed) {
- break;
+ if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
+ || (!largest1->fCollapsed && largest2->fCollapsed)))) {
+ if (largest1->fCollapsed) {
+ break;
+ }
+ // trim parts that don't intersect the opposite
+ SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne();
+ if (!half1->split(largest1, §1->fHeap)) {
+ break;
+ }
+ sect1->trim(largest1, sect2);
+ sect1->trim(half1, sect2);
+ } else {
+ if (largest2->fCollapsed) {
+ break;
+ }
+ // trim parts that don't intersect the opposite
+ SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne();
+ if (!half2->split(largest2, §2->fHeap)) {
+ break;
+ }
+ sect2->trim(largest2, sect1);
+ sect2->trim(half2, sect1);
}
- SkTSect* splitSect = split1 ? sect1 : sect2;
- // trim parts that don't intersect the opposite
- SkTSpan<TCurve>* half2 = splitSect->addOne();
- SkTSect* unsplitSect = split1 ? sect2 : sect1;
- if (!half2->split(half1, &splitSect->fHeap)) {
- break;
- }
- splitSect->trim(half1, unsplitSect);
- splitSect->trim(half2, unsplitSect);
sect1->validate();
sect2->validate();
// if there are 9 or more continuous spans on both sects, suspect coincidence
@@ -1834,6 +1978,9 @@
sect1->removeByPerpendicular(sect2);
sect1->validate();
sect2->validate();
+ if (sect1->collapsed() > TCurve::kMaxIntersections) {
+ break;
+ }
}
#if DEBUG_T_SECT_DUMP
sect1->dumpBoth(sect2);
@@ -1842,7 +1989,7 @@
break;
}
} while (true);
- SkTSpan<TCurve>* coincident = sect1->fCoincident;
+ SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident;
if (coincident) {
// if there is more than one coincident span, check loosely to see if they should be joined
if (coincident->fNext) {
@@ -1862,15 +2009,15 @@
}
} while ((coincident = coincident->fNext));
}
+ int zeroOneSet = EndsEqual(sect1, sect2, intersections);
if (!sect1->fHead || !sect2->fHead) {
return;
}
- int zeroOneSet = EndsEqual(sect1, sect2, intersections);
sect1->recoverCollapsed();
sect2->recoverCollapsed();
- SkTSpan<TCurve>* result1 = sect1->fHead;
+ SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead;
// check heads and tails for zero and ones and insert them if we haven't already done so
- const SkTSpan<TCurve>* head1 = result1;
+ const SkTSpan<TCurve, OppCurve>* head1 = result1;
if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
const SkDPoint& start1 = sect1->fCurve[0];
if (head1->isBounded()) {
@@ -1880,7 +2027,7 @@
}
}
}
- const SkTSpan<TCurve>* head2 = sect2->fHead;
+ const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead;
if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
const SkDPoint& start2 = sect2->fCurve[0];
if (head2->isBounded()) {
@@ -1890,7 +2037,7 @@
}
}
}
- const SkTSpan<TCurve>* tail1 = sect1->tail();
+ const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail();
if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast];
if (tail1->isBounded()) {
@@ -1900,9 +2047,9 @@
}
}
}
- const SkTSpan<TCurve>* tail2 = sect2->tail();
+ const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail();
if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
- const SkDPoint& end2 = sect2->fCurve[TCurve::kPointLast];
+ const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast];
if (tail2->isBounded()) {
double t = tail2->closestBoundedT(end2);
if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
@@ -1910,7 +2057,7 @@
}
}
}
- SkClosestSect<TCurve> closest;
+ SkClosestSect<TCurve, OppCurve> closest;
do {
while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) {
result1 = result1->fNext;
@@ -1918,7 +2065,7 @@
if (!result1) {
break;
}
- SkTSpan<TCurve>* result2 = sect2->fHead;
+ SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead;
bool found = false;
while (result2) {
found |= closest.find(result1, result2);
@@ -1936,7 +2083,7 @@
double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
SkDPoint midPt = sect1->fCurve.ptAtT(midT);
// intersect perpendicular with opposite curve
- SkTCoincident<TCurve> perp;
+ SkTCoincident<TCurve, OppCurve> perp;
perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
if (!perp.isCoincident()) {
++index;
diff --git a/src/pathops/SkPathOpsTightBounds.cpp b/src/pathops/SkPathOpsTightBounds.cpp
index 2f09f41..01c1673 100644
--- a/src/pathops/SkPathOpsTightBounds.cpp
+++ b/src/pathops/SkPathOpsTightBounds.cpp
@@ -10,7 +10,7 @@
bool TightBounds(const SkPath& path, SkRect* result) {
SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune
SkOpContour contour;
- SkOpGlobalState globalState( NULL PATH_OPS_DEBUG_PARAMS(&contour));
+ SkOpGlobalState globalState( NULL SkDEBUGPARAMS(&contour));
// turn path into list of segments
SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
if (!builder.finish(&allocator)) {
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 0248e71..15a1b4b 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -27,19 +27,19 @@
class SkOpGlobalState {
public:
- SkOpGlobalState(SkOpCoincidence* coincidence PATH_OPS_DEBUG_PARAMS(SkOpContour* head))
+ SkOpGlobalState(SkOpCoincidence* coincidence SkDEBUGPARAMS(SkOpContour* head))
: fCoincidence(coincidence)
, fWindingFailed(false)
, fAngleCoincidence(false)
#if DEBUG_VALIDATE
, fPhase(kIntersecting)
#endif
- PATH_OPS_DEBUG_PARAMS(fHead(head))
- PATH_OPS_DEBUG_PARAMS(fAngleID(0))
- PATH_OPS_DEBUG_PARAMS(fContourID(0))
- PATH_OPS_DEBUG_PARAMS(fPtTID(0))
- PATH_OPS_DEBUG_PARAMS(fSegmentID(0))
- PATH_OPS_DEBUG_PARAMS(fSpanID(0)) {
+ SkDEBUGPARAMS(fHead(head))
+ SkDEBUGPARAMS(fAngleID(0))
+ SkDEBUGPARAMS(fContourID(0))
+ SkDEBUGPARAMS(fPtTID(0))
+ SkDEBUGPARAMS(fSegmentID(0))
+ SkDEBUGPARAMS(fSpanID(0)) {
}
#if DEBUG_VALIDATE
@@ -438,6 +438,7 @@
struct SkDVector;
struct SkDLine;
struct SkDQuad;
+struct SkDConic;
struct SkDCubic;
struct SkDRect;
@@ -456,11 +457,12 @@
}
inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
- int points = (int) verb - ((int) verb >> 2);
+ int points = (int) verb - (((int) verb + 1) >> 2);
#ifdef SK_DEBUG
switch (verb) {
case SkPath::kLine_Verb: SkASSERT(1 == points); break;
case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
+ case SkPath::kConic_Verb: SkASSERT(2 == points); break;
case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
default: SkDEBUGFAIL("should not get here");
}
diff --git a/src/pathops/SkPathWriter.cpp b/src/pathops/SkPathWriter.cpp
index 46ec7b9..bd8c721 100644
--- a/src/pathops/SkPathWriter.cpp
+++ b/src/pathops/SkPathWriter.cpp
@@ -35,6 +35,24 @@
init();
}
+void SkPathWriter::conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight) {
+ lineTo();
+ if (fEmpty && AlmostEqualUlps(fDefer[0], pt1) && AlmostEqualUlps(pt1, pt2)) {
+ deferredLine(pt2);
+ return;
+ }
+ moveTo();
+ fDefer[1] = pt2;
+ nudge();
+ fDefer[0] = fDefer[1];
+#if DEBUG_PATH_CONSTRUCTION
+ SkDebugf("path.conicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g);\n",
+ pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY, weight);
+#endif
+ fPathPtr->conicTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY, weight);
+ fEmpty = false;
+}
+
void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
lineTo();
if (fEmpty && AlmostEqualUlps(fDefer[0], pt1) && AlmostEqualUlps(pt1, pt2)
diff --git a/src/pathops/SkPathWriter.h b/src/pathops/SkPathWriter.h
index f32074d..820ddc5 100644
--- a/src/pathops/SkPathWriter.h
+++ b/src/pathops/SkPathWriter.h
@@ -13,6 +13,7 @@
public:
SkPathWriter(SkPath& path);
void close();
+ void conicTo(const SkPoint& pt1, const SkPoint& pt2, SkScalar weight);
void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3);
void deferredLine(const SkPoint& pt);
void deferredMove(const SkPoint& pt);
diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp
index c19cd3d..9c19bc5 100644
--- a/src/pathops/SkReduceOrder.cpp
+++ b/src/pathops/SkReduceOrder.cpp
@@ -271,6 +271,14 @@
return SkPathOpsPointsToVerb(order - 1);
}
+SkPath::Verb SkReduceOrder::Conic(const SkPoint a[3], SkScalar weight, SkPoint* reducePts) {
+ SkPath::Verb verb = SkReduceOrder::Quad(a, reducePts);
+ if (verb > SkPath::kLine_Verb && weight == 1) {
+ return SkPath::kQuad_Verb;
+ }
+ return verb == SkPath::kQuad_Verb ? SkPath::kConic_Verb : verb;
+}
+
SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkPoint* reducePts) {
if (SkDPoint::ApproximatelyEqual(a[0], a[1]) && SkDPoint::ApproximatelyEqual(a[0], a[2])
&& SkDPoint::ApproximatelyEqual(a[0], a[3])) {
diff --git a/src/pathops/SkReduceOrder.h b/src/pathops/SkReduceOrder.h
index 397b58d..e9e4090 100644
--- a/src/pathops/SkReduceOrder.h
+++ b/src/pathops/SkReduceOrder.h
@@ -21,6 +21,7 @@
int reduce(const SkDLine& line);
int reduce(const SkDQuad& quad);
+ static SkPath::Verb Conic(const SkPoint pts[3], SkScalar weight, SkPoint* reducePts);
static SkPath::Verb Cubic(const SkPoint pts[4], SkPoint* reducePts);
static SkPath::Verb Quad(const SkPoint pts[3], SkPoint* reducePts);