shape ops work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@3566 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/CubicIntersection.h b/experimental/Intersection/CubicIntersection.h
deleted file mode 100644
index b918400..0000000
--- a/experimental/Intersection/CubicIntersection.h
+++ /dev/null
@@ -1,40 +0,0 @@
-#ifndef CubicIntersection_DEFINE
-#define CubicIntersection_DEFINE
-
-#include "DataTypes.h"
-
-class Intersections;
-
-// unit-testable utilities
-bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT);
-bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT);
-void chop_at(const Cubic& src, CubicPair& dst, double t);
-void chop_at(const Quadratic& src, QuadraticPair& dst, double t);
-int convex_hull(const Cubic& cubic, char order[4]);
-bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]);
-bool implicit_matches(const Cubic& cubic1, const Cubic& cubic2);
-bool implicit_matches(const Quadratic& quad1, const Quadratic& quad2);
-void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst);
-void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst);
-void tangent(const Cubic& cubic, double t, _Point& result);
-void tangent(const Quadratic& cubic, double t, _Point& result);
-
-// utilities used only for unit testing
-bool point_on_parameterized_curve(const Cubic& cubic, const _Point& point);
-bool point_on_parameterized_curve(const Quadratic& quad, const _Point& point);
-
-// main functions
-enum ReduceOrder_Flags {
- kReduceOrder_NoQuadraticsAllowed,
- kReduceOrder_QuadraticsAllowed
-};
-int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags );
-int reduceOrder(const _Line& line, _Line& reduction);
-int reduceOrder(const Quadratic& quad, Quadratic& reduction);
-//bool intersectStart(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
-bool intersectStartT(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
-bool intersectStart(const Cubic& cubic, const _Line& line, Intersections& );
-bool intersectStart(const Quadratic& q1, const Quadratic& q2, Intersections& );
-bool intersectStart(const Quadratic& quad, const _Line& line, Intersections& );
-
-#endif
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
index 88316fa..25c696c 100644
--- a/experimental/Intersection/CurveIntersection.h
+++ b/experimental/Intersection/CurveIntersection.h
@@ -31,6 +31,10 @@
int reduceOrder(const _Line& line, _Line& reduction);
int reduceOrder(const Quadratic& quad, Quadratic& reduction);
int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]);
+int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
+ double tRange[3]);
+int horizontalIntersect(const Quadratic& quad, double left, double right,
+ double y, double tRange[2]);
bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]);
bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& );
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
index 7f0ddff..70fa8e6 100644
--- a/experimental/Intersection/EdgeWalker.cpp
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -16,7 +16,7 @@
#include "ShapeOps.h"
#include "TSearch.h"
-#if 01 // set to 1 for no debugging whatsoever
+#if 0 // set to 1 for no debugging whatsoever
const bool gShowDebugf = false; // FIXME: remove once debugging is complete
#define DEBUG_DUMP 0
@@ -30,6 +30,7 @@
#define DEBUG_OUT_LESS_THAN 0
#define DEBUG_ADJUST_COINCIDENT 0
#define DEBUG_BOTTOM 0
+#define DEBUG_SPLIT 0
#else
const bool gShowDebugf = true; // FIXME: remove once debugging is complete
@@ -44,7 +45,8 @@
#define DEBUG_OUT 01
#define DEBUG_OUT_LESS_THAN 0
#define DEBUG_ADJUST_COINCIDENT 1
-#define DEBUG_BOTTOM 01
+#define DEBUG_BOTTOM 0
+#define DEBUG_SPLIT 1
#endif
@@ -59,7 +61,8 @@
Intersections& intersections) {
const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
- return intersect(aQuad, bLine, intersections);
+ intersect(aQuad, bLine, intersections);
+ return intersections.fUsed;
}
static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3],
@@ -67,15 +70,15 @@
const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
{a[3].fX, a[3].fY}};
const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
- intersections.fUsed = intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
- return intersections.fUsed;
+ return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]);
}
static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
Intersections& intersections) {
const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}};
- return intersect(aQuad, bQuad, intersections);
+ intersect(aQuad, bQuad, intersections);
+ return intersections.fUsed;
}
static int CubicIntersect(const SkPoint a[4], const SkPoint b[4],
@@ -84,7 +87,8 @@
{a[3].fX, a[3].fY}};
const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY},
{b[3].fX, b[3].fY}};
- return intersect(aCubic, bCubic, intersections);
+ intersect(aCubic, bCubic, intersections);
+ return intersections.fUsed;
}
static int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
@@ -93,6 +97,19 @@
return horizontalLineIntersect(aLine, left, right, y, aRange);
}
+static int QuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
+ SkScalar y, double aRange[3]) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ return horizontalIntersect(aQuad, left, right, y, aRange);
+}
+
+static int CubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
+ SkScalar y, double aRange[4]) {
+ const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ return horizontalIntersect(aCubic, left, right, y, aRange);
+}
+
static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
double x, y;
@@ -632,7 +649,25 @@
public:
Intercepts()
: fTopIntercepts(0)
- , fBottomIntercepts(0) {
+ , fBottomIntercepts(0)
+ , fExplicit(false) {
+ }
+
+ Intercepts& operator=(const Intercepts& src) {
+ fTs = src.fTs;
+ fTopIntercepts = src.fTopIntercepts;
+ fBottomIntercepts = src.fBottomIntercepts;
+ }
+
+ // OPTIMIZATION: remove this function if it's never called
+ double t(int tIndex) const {
+ if (tIndex == 0) {
+ return 0;
+ }
+ if (tIndex > fTs.count()) {
+ return 1;
+ }
+ return fTs[tIndex - 1];
}
#if DEBUG_DUMP
@@ -657,16 +692,18 @@
SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className),
className, i, fTs[i], out.fX, out.fY);
}
- SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className),
+ SkDebugf("%*s.fTopIntercepts=%u\n", tab + sizeof(className),
className, fTopIntercepts);
- SkDebugf("%*s.fBottomIntercepts=%d\n", tab + sizeof(className),
+ SkDebugf("%*s.fBottomIntercepts=%u\n", tab + sizeof(className),
className, fBottomIntercepts);
}
#endif
SkTDArray<double> fTs;
- int fTopIntercepts;
- int fBottomIntercepts;
+ unsigned char fTopIntercepts; // 0=init state 1=1 edge >1=multiple edges
+ unsigned char fBottomIntercepts;
+ bool fExplicit; // if set, suppress 0 and 1
+
};
struct HorizontalEdge {
@@ -709,13 +746,16 @@
for (size_t index = 0; index < count; ++index) {
double t = ts[index];
if (t <= 0) {
+ intercepts.fTopIntercepts <<= 1;
fContainsIntercepts |= ++intercepts.fTopIntercepts > 1;
continue;
}
if (t >= 1) {
+ intercepts.fBottomIntercepts <<= 1;
fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1;
continue;
}
+ fIntersected = true;
foundIntercept = true;
size_t tCount = intercepts.fTs.count();
double delta;
@@ -740,6 +780,40 @@
fContainsIntercepts |= foundIntercept;
return insertedAt;
}
+
+ void addPartial(SkTArray<InEdge>& edges, int id, int ptStart, int ptEnd,
+ int verbStart, int verbEnd) {
+ InEdge* edge = edges.push_back_n(1);
+ int verbCount = verbEnd - verbStart;
+ edge->fIntercepts.push_back_n(verbCount);
+ uint8_t* verbs = &fVerbs[verbStart];
+ for (int ceptIdx = 0; ceptIdx < verbCount; ++ceptIdx) {
+ edge->fIntercepts[ceptIdx] = fIntercepts[verbStart + ceptIdx];
+ }
+ edge->fPts.append(ptEnd - ptStart, &fPts[ptStart]);
+ edge->fVerbs.append(verbCount, &fVerbs[verbStart]);
+ edge->setBounds();
+ edge->fID = id + edges.count();
+ edge->fWinding = fWinding;
+ edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
+ }
+
+ void addSplit(SkTArray<InEdge>& edges, int id, SkPoint* pts, uint8_t verb,
+ double* ts, int tCount, bool flipped) {
+ InEdge* edge = edges.push_back_n(1);
+ edge->fIntercepts.push_back_n(1);
+ edge->fIntercepts[0].fTs.append(tCount, ts);
+ edge->fIntercepts[0].fExplicit = true;
+ edge->fPts.append(verb, pts);
+ edge->fVerbs.append(1, &verb);
+ edge->setBounds();
+ edge->fID = id + edges.count();
+ edge->fWinding = fWinding;
+ edge->fContainsIntercepts = fContainsIntercepts; // FIXME: may not be correct -- but do we need to know?
+ if (flipped) {
+ flip();
+ }
+ }
bool cached(const InEdge* edge) {
// FIXME: in the pathological case where there is a ton of edges, binary search?
@@ -758,10 +832,44 @@
}
void complete(signed char winding, int id) {
+ setBounds();
+ fIntercepts.push_back_n(fVerbs.count());
+ if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top
+ flip();
+ }
+ fContainsIntercepts = fIntersected = false;
+ fID = id;
+ }
+
+ void flip() {
+ size_t index;
+ size_t last = fPts.count() - 1;
+ for (index = 0; index < last; ++index, --last) {
+ SkTSwap<SkPoint>(fPts[index], fPts[last]);
+ }
+ last = fVerbs.count() - 1;
+ for (index = 0; index < last; ++index, --last) {
+ SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);
+ }
+ }
+
+ void reset() {
+ fCached.reset();
+ fIntercepts.reset();
+ fPts.reset();
+ fVerbs.reset();
+ fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+ fID = -1;
+ fWinding = 0;
+ fContainsIntercepts = false;
+ fIntersected = false;
+ }
+
+ void setBounds() {
SkPoint* ptPtr = fPts.begin();
SkPoint* ptLast = fPts.end();
if (ptPtr == ptLast) {
- SkDebugf("empty edge\n");
+ SkDebugf("%s empty edge\n", __FUNCTION__);
SkASSERT(0);
// FIXME: delete empty edge?
return;
@@ -772,20 +880,113 @@
fBounds.growToInclude(ptPtr->fX, ptPtr->fY);
++ptPtr;
}
- fIntercepts.push_back_n(fVerbs.count());
- if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top
- size_t index;
- size_t last = fPts.count() - 1;
- for (index = 0; index < last; ++index, --last) {
- SkTSwap<SkPoint>(fPts[index], fPts[last]);
+ }
+
+ void splitInflectionPts(SkTArray<InEdge>& edges, int idStart) {
+ if (!fIntersected) {
+ return;
+ }
+ uint8_t* verbs = fVerbs.begin();
+ SkPoint* pts = fPts.begin();
+ int lastVerb = 0;
+ int lastPt = 0;
+ uint8_t verb;
+ bool edgeSplit = false;
+ for (int ceptIdx = 0; ceptIdx < fIntercepts.count(); ++ceptIdx, pts += verb) {
+ Intercepts& intercepts = fIntercepts[ceptIdx];
+ verb = *verbs++;
+ if (verb <= SkPath::kLine_Verb) {
+ continue;
}
- last = fVerbs.count() - 1;
- for (index = 0; index < last; ++index, --last) {
- SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]);
+ size_t tCount = intercepts.fTs.count();
+ if (!tCount) {
+ continue;
+ }
+ size_t tIndex = -1;
+ SkScalar y = pts[0].fY;
+ int lastSplit = 0;
+ int firstSplit = -1;
+ bool curveSplit = false;
+ while (++tIndex < tCount) {
+ double nextT = intercepts.fTs[tIndex];
+ SkScalar nextY = verb == SkPath::kQuad_Verb
+ ? QuadYAtT(pts, nextT) : CubicYAtT(pts, nextT);
+ if (nextY < y) {
+ edgeSplit = curveSplit = true;
+ if (firstSplit < 0) {
+ firstSplit = tIndex;
+ int nextPt = pts - fPts.begin();
+ int nextVerb = verbs - 1 - fVerbs.begin();
+ if (lastVerb < nextVerb) {
+ addPartial(edges, idStart, lastPt, nextPt,
+ lastVerb, nextVerb);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addPartial 1 edge=%d\n", __FUNCTION__,
+ fID);
+ #endif
+ }
+ lastPt = nextPt;
+ lastVerb = nextVerb;
+ }
+ } else {
+ if (firstSplit >= 0) {
+ if (lastSplit < firstSplit) {
+ addSplit(edges, idStart, pts, verb,
+ &intercepts.fTs[lastSplit],
+ firstSplit - lastSplit, false);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addSplit 1 edge=%d tIndex=%d,%d\n",
+ __FUNCTION__, fID, lastSplit, firstSplit);
+ #endif
+ }
+ addSplit(edges, idStart, pts, verb,
+ &intercepts.fTs[firstSplit],
+ tIndex - firstSplit, true);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addSplit 2 edge=%d tIndex=%d,%d flip\n",
+ __FUNCTION__, fID, firstSplit, tIndex);
+ #endif
+ lastSplit = tIndex;
+ firstSplit = -1;
+ }
+ }
+ y = nextY;
+ }
+ if (curveSplit) {
+ if (firstSplit < 0) {
+ firstSplit = lastSplit;
+ } else {
+ addSplit(edges, idStart, pts, verb,
+ &intercepts.fTs[lastSplit], firstSplit - lastSplit,
+ false);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addSplit 3 edge=%d tIndex=%d,%d\n", __FUNCTION__,
+ fID, lastSplit, firstSplit);
+ #endif
+ }
+ addSplit(edges, idStart, pts, verb,
+ &intercepts.fTs[firstSplit], tIndex - firstSplit,
+ pts[verb].fY < y);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addSplit 4 edge=%d tIndex=%d,%d %s\n", __FUNCTION__,
+ fID, firstSplit, tIndex, pts[verb].fY < y ? "flip" : "");
+ #endif
}
}
- fContainsIntercepts = false;
- fID = id;
+ // collapse remainder -- if there's nothing left, clear it somehow?
+ if (edgeSplit) {
+ int nextVerb = verbs - 1 - fVerbs.begin();
+ if (lastVerb < nextVerb) {
+ int nextPt = pts - fPts.begin();
+ addPartial(edges, idStart, lastPt, nextPt,
+ lastVerb, nextVerb);
+ #if DEBUG_SPLIT
+ SkDebugf("%s addPartial 2 edge=%d\n", __FUNCTION__, fID);
+ #endif
+ }
+ // OPTIMIZATION: reuse the edge instead of marking it empty
+ reset();
+ }
}
#if DEBUG_DUMP
@@ -803,7 +1004,6 @@
for (i = 0; i < fIntercepts.count(); ++i) {
SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className),
className, i);
- // FIXME: take current verb into consideration
fIntercepts[i].dump(pts, (SkPath::Verb) *verbs);
pts += *verbs++;
}
@@ -822,10 +1022,12 @@
fWinding);
SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className),
className, fContainsIntercepts);
+ SkDebugf("%*s.fIntersected=%d\n", tab + sizeof(className),
+ className, fIntersected);
}
#endif
- // temporary data : move this to a separate struct?
+ // FIXME: temporary data : move this to a separate struct?
SkTDArray<const InEdge*> fCached; // list of edges already intercepted
SkTArray<Intercepts> fIntercepts; // one per verb
@@ -836,6 +1038,7 @@
int fID;
signed char fWinding;
bool fContainsIntercepts;
+ bool fIntersected;
};
class InEdgeBuilder {
@@ -849,10 +1052,19 @@
, fID(0)
, fHorizontalEdges(horizontalEdges)
, fIgnoreHorizontal(ignoreHorizontal)
+ , fContainsCurves(false)
{
walk();
}
+bool containsCurves() const {
+ return fContainsCurves;
+}
+
+int nextID() {
+ return ++fID;
+}
+
protected:
void addEdge() {
@@ -864,7 +1076,7 @@
bool complete() {
if (fCurrentEdge && fCurrentEdge->fVerbs.count()) {
- fCurrentEdge->complete(fWinding, ++fID);
+ fCurrentEdge->complete(fWinding, nextID());
fCurrentEdge = NULL;
return true;
}
@@ -913,9 +1125,11 @@
break;
case SkPath::kQuad_Verb:
winding = direction(3);
+ fContainsCurves = true;
break;
case SkPath::kCubic_Verb:
winding = direction(4);
+ fContainsCurves = true;
break;
case SkPath::kClose_Verb:
SkASSERT(fCurrentEdge);
@@ -969,6 +1183,7 @@
int fID;
int8_t fWinding;
bool fIgnoreHorizontal;
+ bool fContainsCurves;
};
struct WorkEdge {
@@ -1134,8 +1349,8 @@
}
bool advanceT() {
- SkASSERT(fTIndex <= fTs->count());
- return ++fTIndex <= fTs->count();
+ SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
+ return ++fTIndex <= fTs->count() - fExplicitTs;
}
bool advance() {
@@ -1153,6 +1368,7 @@
SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts);
} while (fWorkEdge.fPts[0].fY >= y);
initT();
+ SkASSERT(!fExplicitTs);
fTIndex = fTs->count() + 1;
}
@@ -1187,7 +1403,7 @@
// for the fTIndex, don't do it again
// For identical x, this lets us know which edge is first.
// If both edges have T values < 1, check x at next T (fXBelow).
- int add = (fTIndex <= fTs->count()) - 1;
+ int add = (fTIndex <= fTs->count() - fExplicitTs) - 1;
double tAbove = t(fTIndex + add);
(*xyAtTFunc)(fWorkEdge.fPts, tAbove, &fAbove);
double tBelow = t(fTIndex - ~add);
@@ -1195,6 +1411,7 @@
SkASSERT(tAbove != tBelow);
// FIXME: this can loop forever
// need a break if we hit the end
+ // FIXME: in unit test, figure out how explicit Ts work as well
while (fAbove.fY == fBelow.fY) {
if (add < 0 || fTIndex == fTs->count()) {
add -= 1;
@@ -1249,7 +1466,8 @@
const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front();
SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count());
const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex();
- fTs = &interceptPtr->fTs;
+ fTs = &interceptPtr->fTs;
+ fExplicitTs = interceptPtr->fExplicit;
// the above is conceptually the same as
// fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs;
// but templated arrays don't allow returning a pointer to the end() element
@@ -1379,23 +1597,21 @@
#endif
return ulps >= 0 && ulps <= 32;
}
-
+
double nextT() const {
- SkASSERT(fTIndex <= fTs->count());
+ SkASSERT(fTIndex <= fTs->count() - fExplicitTs);
return t(fTIndex + 1);
}
double t() const {
- if (fTIndex == 0) {
- return 0;
- }
- if (fTIndex > fTs->count()) {
- return 1;
- }
- return (*fTs)[fTIndex - 1];
+ return t(fTIndex);
}
double t(int tIndex) const {
+ if (fExplicitTs) {
+ SkASSERT(tIndex < fTs->count());
+ return (*fTs)[tIndex];
+ }
if (tIndex == 0) {
return 0;
}
@@ -1426,6 +1642,7 @@
bool fCloseCall;
bool fDone;
bool fFixBelow;
+ bool fExplicitTs;
};
static void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) {
@@ -1462,24 +1679,39 @@
HorizontalEdge** sorted = horizontal;
horzEdge = *sorted;
do {
- if (wt.verb() == SkPath::kLine_Verb) {
- double wtTs[2];
- int pts = LineIntersect(wt.fPts, horzEdge->fLeft,
- horzEdge->fRight, horzEdge->fY, wtTs);
- if (pts) {
+ double wtTs[4];
+ int pts;
+ uint8_t verb = wt.verb();
+ switch (verb) {
+ case SkPath::kLine_Verb:
+ pts = LineIntersect(wt.fPts, horzEdge->fLeft,
+ horzEdge->fRight, horzEdge->fY, wtTs);
+ break;
+ case SkPath::kQuad_Verb:
+ pts = QuadIntersect(wt.fPts, horzEdge->fLeft,
+ horzEdge->fRight, horzEdge->fY, wtTs);
+ break;
+ case SkPath::kCubic_Verb:
+ pts = CubicIntersect(wt.fPts, horzEdge->fLeft,
+ horzEdge->fRight, horzEdge->fY, wtTs);
+ break;
+ }
+ if (pts) {
#if DEBUG_ADD_BOTTOM_TS
- SkDebugf("%s y=%g wtTs[0]=%g (%g,%g, %g,%g)\n", __FUNCTION__,
- horzEdge->fY, wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY,
- wt.fPts[1].fX, wt.fPts[1].fY);
- if (pts == 2) {
- SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
+ for (int x = 0; x < pts; ++x) {
+ SkDebugf("%s y=%g wtTs[0]=%g (%g,%g", __FUNCTION__,
+ horzEdge->fY, wtTs[x], wt.fPts[0].fX, wt.fPts[0].fY);
+ for (int y = 0; y < verb; ++y) {
+ SkDebugf(" %g,%g", wt.fPts[y + 1].fX, wt.fPts[y + 1].fY));
}
-#endif
- test->add(wtTs, pts, wt.verbIndex());
+ SkDebugf(")\n");
}
- } else {
- // FIXME: add all curve types
- SkASSERT(0);
+ if (pts > verb) {
+ SkASSERT(0); // FIXME ? should this work?
+ SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]);
+ }
+#endif
+ test->add(wtTs, pts, wt.verbIndex());
}
horzEdge = *++sorted;
} while (horzEdge->fY == bottom
@@ -1526,6 +1758,9 @@
InEdge** nextPtr = testPtr;
do {
InEdge* next = *++nextPtr;
+ // FIXME: this compares against the sentinel sometimes
+ // OPTIMIZATION: this may never be needed since this gets called
+ // in two passes now. Verify that double hits are appropriate.
if (test->cached(next)) {
continue;
}
@@ -1695,6 +1930,9 @@
}
} while (wt.advance());
}
+#if DEBUG_BOTTOM
+ SkDebugf("%s bottom=%1.9g\n", __FUNCTION__, bottom);
+#endif
return bottom;
}
@@ -1729,6 +1967,9 @@
}
test = *++testPtr;
}
+#if DEBUG_BOTTOM
+ SkDebugf("%s %d bottom=%1.9g\n", __FUNCTION__, activeEdges ? 2 : 1, bottom);
+#endif
return bottom;
}
@@ -2095,7 +2336,7 @@
aboveBottom &= !activePtr->fCloseCall;
} else {
if (activePtr->fSkip || activePtr->fCloseCall) {
- SkDebugf("== %1.9g\n", clippedPts[0].fY);
+ if (gShowDebugf) SkDebugf("== %1.9g\n", clippedPts[0].fY);
}
}
} while (moreToDo & aboveBottom);
@@ -2103,6 +2344,16 @@
}
}
+static void dumpEdgeList(const SkTDArray<InEdge*>& edgeList,
+ const InEdge& edgeSentinel) {
+#if DEBUG_DUMP
+ InEdge** debugPtr = edgeList.begin();
+ do {
+ (*debugPtr++)->dump();
+ } while (*debugPtr != &edgeSentinel);
+#endif
+}
+
void simplify(const SkPath& path, bool asFill, SkPath& simple) {
// returns 1 for evenodd, -1 for winding, regardless of inverse-ness
int windingMask = (path.getFillType() & 1) ? 1 : -1;
@@ -2149,14 +2400,24 @@
y = bottom;
currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y);
} while (*currentPtr != &edgeSentinel);
-
-#if DEBUG_DUMP
- InEdge** debugPtr = edgeList.begin();
- do {
- (*debugPtr++)->dump();
- } while (*debugPtr != &edgeSentinel);
-#endif
-
+ // if a quadratic or cubic now has an intermediate T value, see if the Ts
+ // on either side cause the Y values to monotonically increase. If not, split
+ // the curve at the new T.
+ if (builder.containsCurves()) {
+ currentPtr = edgeList.begin();
+ SkTArray<InEdge> splits;
+ do {
+ (*currentPtr)->splitInflectionPts(splits, builder.nextID());
+ } while (*++currentPtr != &edgeSentinel);
+ if (splits.count()) {
+ edges.pop_back(); // pop the sentinel
+ for (int index = 0; index < splits.count(); ++index) {
+ edges.push_back(splits[index]);
+ }
+ makeEdgeList(edges, edgeSentinel, edgeList);
+ }
+ }
+ dumpEdgeList(edgeList, edgeSentinel);
// walk the sorted edges from top to bottom, computing accumulated winding
SkTDArray<ActiveEdge> activeEdges;
OutEdgeBuilder outBuilder(asFill);
@@ -2166,21 +2427,12 @@
InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set
SkScalar bottom = findBottom(currentPtr, edgeList.end(),
&activeEdges, y, asFill, lastPtr);
-#if DEBUG_BOTTOM
- SkDebugf("%s findBottom bottom=%1.9g\n", __FUNCTION__, bottom);
-#endif
if (lastPtr > currentPtr) {
bottom = computeInterceptBottom(activeEdges, y, bottom);
-#if DEBUG_BOTTOM
- SkDebugf("%s computeInterceptBottom bottom=%1.9g\n", __FUNCTION__, bottom);
-#endif
SkTDArray<ActiveEdge*> activeEdgeList;
sortHorizontal(activeEdges, activeEdgeList, y);
bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom,
outBuilder);
-#if DEBUG_BOTTOM
- SkDebugf("%s adjustCoincident bottom=%1.9g\n", __FUNCTION__, bottom);
-#endif
stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder);
}
y = bottom;
diff --git a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
index 27ec5be..7054683 100755
--- a/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerPolygon4x4_Test.cpp
@@ -1,14 +1,24 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+#include "SkCanvas.h"
#include <assert.h>
#include <pthread.h>
-
+
struct State {
+ State() {
+ bitmap.setConfig(SkBitmap::kARGB_8888_Config, 150 * 2, 100);
+ bitmap.allocPixels();
+ canvas = new SkCanvas(bitmap);
+ }
+
int a;
int b;
int c;
int d;
pthread_t threadID;
+ SkCanvas* canvas;
+ SkBitmap bitmap;
bool abcIsATriangle;
};
@@ -77,13 +87,13 @@
str += sprintf(str, " path.lineTo(%d, %d);\n", hx, hy);
str += sprintf(str, " path.close();");
}
- if (!testSimplify(path, true, out)) {
+ if (!testSimplify(path, true, out, state.bitmap, state.canvas)) {
SkDebugf("*/\n{ SkPath::kWinding_FillType, %d, %d, %d, %d,"
" %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d,
e, f, g, h);
}
path.setFillType(SkPath::kEvenOdd_FillType);
- if (!testSimplify(path, true, out)) {
+ if (!testSimplify(path, true, out, state.bitmap, state.canvas)) {
SkDebugf("*/\n{ SkPath::kEvenOdd_FillType, %d, %d, %d, %d,"
" %d, %d, %d, %d },\n/*\n", state.a, state.b, state.c, state.d,
e, f, g, h);
@@ -173,9 +183,9 @@
str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy);
str += sprintf(str, " path.close();");
}
- testSimplify(path, true, out);
+ testSimplify(path, true, out, state.bitmap, state.canvas);
path.setFillType(SkPath::kEvenOdd_FillType);
- testSimplify(path, true, out);
+ testSimplify(path, true, out, state.bitmap, state.canvas);
}
}
}
@@ -263,9 +273,9 @@
str += sprintf(str, " path.lineTo(%d, %d);\n", fx, fy);
str += sprintf(str, " path.close();");
}
- testSimplify(path, true, out);
+ testSimplify(path, true, out, state.bitmap, state.canvas);
path.setFillType(SkPath::kEvenOdd_FillType);
- testSimplify(path, true, out);
+ testSimplify(path, true, out, state.bitmap, state.canvas);
}
}
}
diff --git a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp
index 0054cfb..09d6f93 100644
--- a/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp
+++ b/experimental/Intersection/EdgeWalkerPolygons_Mismatches.cpp
@@ -1,5 +1,6 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
// edges that didn't match
struct misMatch {
@@ -1579,6 +1580,7 @@
void TestMismatches();
void TestMismatches() {
+ SkBitmap bitmap;
for (size_t index = 0; index < misMatchCount; ++index) {
const misMatch& miss = misMatches[index];
int ax = miss.a & 0x03;
@@ -1609,6 +1611,6 @@
path.lineTo(gx, gy);
path.lineTo(hx, hy);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
}
diff --git a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
index 7bf6452..f3455ee 100644
--- a/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerPolygons_Test.cpp
@@ -1,5 +1,8 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+
+static SkBitmap bitmap;
static void testSimplifyTriangle() {
SkPath path, out;
@@ -12,7 +15,7 @@
path.lineTo(10,30); // /_|
path.lineTo(20,30);
path.close();
- testSimplify(path, true, out); // expect |\/|
+ testSimplify(path, true, out, bitmap); // expect |\/|
// |__|
}
@@ -26,7 +29,7 @@
path.lineTo(1, 0);
path.lineTo(3, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle4() {
@@ -39,7 +42,7 @@
path.lineTo(1, 0);
path.lineTo(2, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle5() {
@@ -52,7 +55,7 @@
path.lineTo(1, 1);
path.lineTo(2, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle6() {
@@ -67,7 +70,7 @@
path.lineTo(3, 1);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle7() {
@@ -82,7 +85,7 @@
path.lineTo(0, 2);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle8() {
@@ -97,7 +100,7 @@
path.lineTo(1, 3);
path.lineTo(0, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle9() {
@@ -112,7 +115,7 @@
path.lineTo(2, 1);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle10() {
@@ -127,7 +130,7 @@
path.lineTo(0, 1);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle11() {
@@ -142,7 +145,7 @@
path.lineTo(2, 2);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle12() {
@@ -157,7 +160,7 @@
path.lineTo(1, 1);
path.lineTo(2, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle13() {
@@ -172,7 +175,7 @@
path.lineTo(1, 1);
path.lineTo(3, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle14() {
@@ -187,7 +190,7 @@
path.lineTo(0, 1);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle15() {
@@ -201,7 +204,7 @@
path.lineTo(0, 1);
path.lineTo(2, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle16() {
@@ -214,7 +217,7 @@
path.lineTo(0, 1);
path.lineTo(1, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle17() {
@@ -227,7 +230,7 @@
path.lineTo(1, 3);
path.lineTo(0, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle18() {
@@ -240,7 +243,7 @@
path.lineTo(0, 1);
path.lineTo(0, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle19() {
@@ -254,7 +257,7 @@
path.lineTo(1, 1);
path.lineTo(2, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle20() {
@@ -267,7 +270,7 @@
path.lineTo(3, 2);
path.lineTo(0, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle21() {
@@ -280,7 +283,7 @@
path.lineTo(2, 1);
path.lineTo(0, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyDegenerateTriangle1() {
@@ -293,7 +296,7 @@
path.lineTo(0, 0);
path.lineTo(0, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyDegenerateTriangle2() {
@@ -306,7 +309,7 @@
path.lineTo(2, 2);
path.lineTo(3, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyWindingParallelogram() {
@@ -322,7 +325,7 @@
path.lineTo(20,30); // /_/
path.lineTo(30,10);
path.close();
- testSimplify(path, true, out); // expect _
+ testSimplify(path, true, out, bitmap); // expect _
// / \ .
} // /___\ .
@@ -339,7 +342,7 @@
path.lineTo(20,30); // /_/
path.lineTo(30,10);
path.close();
- testSimplify(path, true, out); // expect _
+ testSimplify(path, true, out, bitmap); // expect _
} // \ /
static void testSimplifyTriangle2() {
@@ -353,9 +356,10 @@
path.lineTo(20,10); // \ |
path.lineTo(20,30); // \|
path.close(); // _
- testSimplify(path, true, out); // expect | |
+ testSimplify(path, true, out, bitmap); // expect | |
} // |_|
+#if 0
static void testPathTriangleRendering() {
SkPath one, two;
one.moveTo(0, 0);
@@ -375,10 +379,11 @@
two.reset();
}
}
+#endif
static void simplify(const char* functionName, const SkPath& path,
bool fill, SkPath& out) {
- SkDebugf("%s\n", functionName);
+ if (false) SkDebugf("%s\n", functionName);
simplify(path, fill, out);
}
@@ -525,7 +530,7 @@
path.lineTo(0, 2);
path.lineTo(0, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle23() {
@@ -538,7 +543,7 @@
path.lineTo(0, 1);
path.lineTo(1, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyTriangle24() {
@@ -551,7 +556,7 @@
path.lineTo(1, 0);
path.lineTo(0, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifySkinnyTriangle7() {
@@ -754,7 +759,7 @@
testSimplifyTriangle2,
testSimplifyWindingParallelogram,
testSimplifyXorParallelogram,
- testPathTriangleRendering,
+// testPathTriangleRendering,
};
static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]);
@@ -772,7 +777,7 @@
for ( ; index < simplifyTestsCount; ++index) {
(*simplifyTests[index])();
if (simplifyTests[index] == testSimplifySkinnyTriangle2) {
- SkDebugf("%s last fast skinny test\n", __FUNCTION__);
+ if (false) SkDebugf("%s last fast skinny test\n", __FUNCTION__);
}
firstTestComplete = true;
}
diff --git a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp
index a87b37f..daf5af7 100644
--- a/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerQuadralaterals_Test.cpp
@@ -1,5 +1,8 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+
+static SkBitmap bitmap;
static void testSimplifyQuad1() {
SkPath path, out;
@@ -13,7 +16,7 @@
path.lineTo(1, 3);
path.lineTo(1, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuad2() {
@@ -28,7 +31,7 @@
path.lineTo(1, 1);
path.lineTo(0, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuad3() {
@@ -43,7 +46,7 @@
path.lineTo(2, 1);
path.lineTo(0, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuad4() {
@@ -58,7 +61,7 @@
path.lineTo(3, 1);
path.lineTo(3, 3);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuad5() {
@@ -73,7 +76,7 @@
path.lineTo(2, 1);
path.lineTo(0, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuad6() {
@@ -88,7 +91,7 @@
path.lineTo(1, 1);
path.lineTo(2, 2);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void (*simplifyTests[])() = {
diff --git a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
index ab4e39b..584ecda 100644
--- a/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerQuadratics_Test.cpp
@@ -1,5 +1,8 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+
+static SkBitmap bitmap;
static void testSimplifyQuadratic1() {
SkPath path, out;
@@ -9,7 +12,7 @@
path.moveTo(1, 0);
path.quadTo(0, 0, 0, 1);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuadratic2() {
@@ -20,8 +23,7 @@
path.moveTo(20, 0);
path.quadTo(0, 0, 0, 20);
path.close();
- testSimplify(path, true, out);
- drawAsciiPaths(path, out, true);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyQuadratic3() {
@@ -32,11 +34,23 @@
path.moveTo(0, 20);
path.quadTo(0, 0, 20, 0);
path.close();
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
+}
+
+static void testSimplifyQuadratic4() {
+ SkPath path, out;
+ path.moveTo(0, 20);
+ path.quadTo(20, 0, 40, 20);
+ path.close();
+ path.moveTo(40, 10);
+ path.quadTo(20, 30, 0, 10);
+ path.close();
+ testSimplify(path, true, out, bitmap);
drawAsciiPaths(path, out, true);
}
static void (*simplifyTests[])() = {
+ testSimplifyQuadratic4,
testSimplifyQuadratic3,
testSimplifyQuadratic2,
testSimplifyQuadratic1,
diff --git a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp
index 8dc8627..a5448e3 100644
--- a/experimental/Intersection/EdgeWalkerRectangles_Test.cpp
+++ b/experimental/Intersection/EdgeWalkerRectangles_Test.cpp
@@ -1,5 +1,8 @@
#include "EdgeWalker_Test.h"
#include "Intersection_Tests.h"
+#include "SkBitmap.h"
+
+static SkBitmap bitmap;
static void testSimplifyCoincidentInner() {
SkPath path, out;
@@ -7,7 +10,7 @@
path.addRect(10, 10, 60, 60, SkPath::kCCW_Direction);
path.addRect(20, 20, 50, 50, SkPath::kCW_Direction);
path.addRect(20, 30, 40, 40, SkPath::kCW_Direction);
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
static void testSimplifyCoincidentVertical() {
@@ -304,7 +307,7 @@
SkPath path, out;
path.addRect(rect1, static_cast<SkPath::Direction>(dir));
path.addRect(rect2, static_cast<SkPath::Direction>(dir));
- testSimplify(path, true, out);
+ testSimplify(path, true, out, bitmap);
}
}
}
diff --git a/experimental/Intersection/EdgeWalker_Test.h b/experimental/Intersection/EdgeWalker_Test.h
index ac97436..1f644a7 100644
--- a/experimental/Intersection/EdgeWalker_Test.h
+++ b/experimental/Intersection/EdgeWalker_Test.h
@@ -2,9 +2,13 @@
#include "ShapeOps.h"
-extern bool comparePaths(const SkPath& one, const SkPath& two);
+class SkBitmap;
+class SkCanvas;
+
+//extern int comparePaths(const SkPath& one, const SkPath& two);
extern void comparePathsTiny(const SkPath& one, const SkPath& two);
extern bool drawAsciiPaths(const SkPath& one, const SkPath& two,
bool drawPaths);
extern void showPath(const SkPath& path, const char* str = NULL);
-extern bool testSimplify(const SkPath& path, bool fill, SkPath& out);
+extern bool testSimplify(const SkPath& path, bool fill, SkPath& out,
+ SkBitmap& bitmap, SkCanvas* canvas = 0);
diff --git a/experimental/Intersection/EdgeWalker_TestUtility.cpp b/experimental/Intersection/EdgeWalker_TestUtility.cpp
index 2cd0153..0b2fd06 100644
--- a/experimental/Intersection/EdgeWalker_TestUtility.cpp
+++ b/experimental/Intersection/EdgeWalker_TestUtility.cpp
@@ -5,7 +5,7 @@
#include "SkPaint.h"
static bool gShowPath = false;
-static bool gComparePaths = false;
+static bool gComparePaths = true;
static bool gDrawLastAsciiPaths = true;
static bool gDrawAllAsciiPaths = false;
static bool gShowAsciiPaths = false;
@@ -43,17 +43,27 @@
}
}
-static bool pathsDrawTheSame(const SkPath& one, const SkPath& two) {
+static int pathsDrawTheSame(const SkPath& one, const SkPath& two,
+ SkBitmap& bits, SkCanvas* c) {
+ SkCanvas* canvasPtr = c;
+ if (!c) {
+ canvasPtr = new SkCanvas(bits);
+ }
const SkRect& bounds1 = one.getBounds();
const SkRect& bounds2 = two.getBounds();
SkRect larger = bounds1;
larger.join(bounds2);
- SkBitmap bits;
int bitWidth = SkScalarCeil(larger.width()) + 2;
int bitHeight = SkScalarCeil(larger.height()) + 2;
- bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight);
- bits.allocPixels();
- SkCanvas canvas(bits);
+ if (bits.width() < bitWidth * 2 || bits.height() < bitHeight) {
+ if (bits.width() >= 200) {
+ SkDebugf("%s bitWidth=%d bitHeight=%d\n", __FUNCTION__, bitWidth, bitHeight);
+ }
+ bits.setConfig(SkBitmap::kARGB_8888_Config, bitWidth * 2, bitHeight);
+ bits.allocPixels();
+ canvasPtr->setBitmapDevice(bits);
+ }
+ SkCanvas& canvas = *canvasPtr;
canvas.drawColor(SK_ColorWHITE);
SkPaint paint;
canvas.save();
@@ -64,17 +74,21 @@
canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1);
canvas.drawPath(two, paint);
canvas.restore();
+ int errors = 0;
for (int y = 0; y < bitHeight; ++y) {
uint32_t* addr1 = bits.getAddr32(0, y);
uint32_t* addr2 = bits.getAddr32(bitWidth, y);
for (int x = 0; x < bitWidth; ++x) {
- if (addr1[x] != addr2[x]) {
- return false;
- break;
- }
+ errors += addr1[x] != addr2[x];
}
}
- return true;
+ if (!c) {
+ delete canvasPtr;
+ }
+ return errors;
+}
+
+void bitmapInit(SkBitmap& bits) {
}
bool drawAsciiPaths(const SkPath& one, const SkPath& two,
@@ -130,8 +144,8 @@
return true;
}
-static bool scaledDrawTheSame(const SkPath& one, const SkPath& two,
- int a, int b, bool drawPaths) {
+static int scaledDrawTheSame(const SkPath& one, const SkPath& two,
+ int a, int b, bool drawPaths, SkBitmap& bitmap, SkCanvas* canvas) {
SkMatrix scale;
scale.reset();
float aScale = 1.21f;
@@ -140,8 +154,9 @@
SkPath scaledOne, scaledTwo;
one.transform(scale, &scaledOne);
two.transform(scale, &scaledTwo);
- if (pathsDrawTheSame(scaledOne, scaledTwo)) {
- return true;
+ int errors = pathsDrawTheSame(scaledOne, scaledTwo, bitmap, canvas);
+ if (errors == 0) {
+ return 0;
}
while (!drawAsciiPaths(scaledOne, scaledTwo, drawPaths)) {
scale.reset();
@@ -151,28 +166,36 @@
one.transform(scale, &scaledOne);
two.transform(scale, &scaledTwo);
}
- return false;
+ return errors;
}
-bool comparePaths(const SkPath& one, const SkPath& two) {
- if (pathsDrawTheSame(one, two)) {
- return true;
+static int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap,
+ SkCanvas* canvas) {
+ int errors = pathsDrawTheSame(one, two, bitmap, canvas);
+ if (errors == 0) {
+ return 0;
}
drawAsciiPaths(one, two, gDrawAllAsciiPaths);
for (int x = 9; x <= 33; ++x) {
- if (scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths)) {
- return true;
+ errors = scaledDrawTheSame(one, two, x, x - (x >> 2), gDrawAllAsciiPaths,
+ bitmap, canvas);
+ if (errors == 0) {
+ return 0;
}
}
if (!gDrawAllAsciiPaths) {
- scaledDrawTheSame(one, two, 9, 7, gDrawLastAsciiPaths);
+ errors = scaledDrawTheSame(one, two, 9, 7, false, bitmap, canvas);
+ if (errors > 4) {
+ scaledDrawTheSame(one, two, 9, 7, true, bitmap, canvas);
+ }
}
- if (gComparePathsAssert) {
+ if (errors > 0) SkDebugf("\n%s errors=%d\n", __FUNCTION__, errors);
+ if (errors > 4 && gComparePathsAssert) {
showPath(one);
showPath(two, "simplified:");
SkASSERT(0);
}
- return false;
+ return errors;
}
// doesn't work yet
@@ -206,7 +229,8 @@
}
}
-bool testSimplify(const SkPath& path, bool fill, SkPath& out) {
+bool testSimplify(const SkPath& path, bool fill, SkPath& out, SkBitmap& bitmap,
+ SkCanvas* canvas) {
if (gShowPath) {
showPath(path);
}
@@ -214,5 +238,5 @@
if (!gComparePaths) {
return true;
}
- return comparePaths(path, out);
+ return comparePaths(path, out, bitmap, canvas) == 0;
}
diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp
index 500a91e..8517b7e 100644
--- a/experimental/Intersection/LineCubicIntersection.cpp
+++ b/experimental/Intersection/LineCubicIntersection.cpp
@@ -139,7 +139,25 @@
LineCubicIntersections c(cubic, *((_Line*) 0), tRange);
return c.horizontalIntersect(y);
}
-
+
+int horizontalIntersect(const Cubic& cubic, double left, double right, double y,
+ double tRange[3]) {
+ LineCubicIntersections c(cubic, *((_Line*) 0), tRange);
+ int result = c.horizontalIntersect(y);
+ for (int index = 0; index < result; ) {
+ double x, y;
+ xy_at_t(cubic, tRange[index], x, y);
+ if (x < left || x > right) {
+ if (--result > index) {
+ tRange[index] = tRange[result];
+ }
+ continue;
+ }
+ ++index;
+ }
+ return result;
+}
+
int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]) {
LineCubicIntersections c(cubic, line, cRange);
int roots;
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index 0d6477b..737b767 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -131,6 +131,16 @@
return roots > 0;
}
+int horizontalIntersect(double axisIntercept) {
+ double D = quad[2].y; // f
+ double E = quad[1].y; // e
+ double F = quad[0].y; // d
+ D += F - 2 * E; // D = d - 2*e + f
+ E -= F; // E = -(d - e)
+ F -= axisIntercept;
+ return quadraticRoots(D, E, F, intersections.fT[0]);
+}
+
protected:
double findLineT(double t) {
@@ -156,7 +166,24 @@
bool moreHorizontal;
};
-
+
+int horizontalIntersect(const Quadratic& quad, double left, double right,
+ double y, double tRange[2]) {
+ Intersections i;
+ LineQuadraticIntersections q(quad, *((_Line*) 0), i);
+ int result = q.horizontalIntersect(y);
+ int tCount = 0;
+ for (int index = 0; index < result; ++index) {
+ double x, y;
+ xy_at_t(quad, i.fT[0][index], x, y);
+ if (x < left || x > right) {
+ continue;
+ }
+ tRange[tCount++] = i.fT[0][index];
+ }
+ return tCount;
+}
+
bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
return q.intersect();
diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp
index 634d083..f8c43b5 100644
--- a/experimental/Intersection/QuadraticIntersection.cpp
+++ b/experimental/Intersection/QuadraticIntersection.cpp
@@ -86,16 +86,22 @@
double newMinT1 = interp(minT1, maxT1, minT);
double newMaxT1 = interp(minT1, maxT1, maxT);
split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1;
+#define VERBOSE 0
+#if VERBOSE
printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n", __FUNCTION__, depth,
splits, newMinT1, newMaxT1, minT1, maxT1, split);
+#endif
minT1 = newMinT1;
maxT1 = newMaxT1;
} else {
double newMinT2 = interp(minT2, maxT2, minT);
double newMaxT2 = interp(minT2, maxT2, maxT);
split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
+#define VERBOSE 0
+#if VERBOSE
printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n", __FUNCTION__, depth,
splits, newMinT2, newMaxT2, minT2, maxT2, split);
+#endif
minT2 = newMinT2;
maxT2 = newMaxT2;
}
diff --git a/experimental/Intersection/ShapeOpsDemo-Info.plist b/experimental/Intersection/ShapeOpsDemo-Info.plist
deleted file mode 100644
index 5dd4506..0000000
--- a/experimental/Intersection/ShapeOpsDemo-Info.plist
+++ /dev/null
@@ -1,32 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
-<plist version="1.0">
-<dict>
- <key>CFBundleDevelopmentRegion</key>
- <string>English</string>
- <key>CFBundleExecutable</key>
- <string>${EXECUTABLE_NAME}</string>
- <key>CFBundleIconFile</key>
- <string></string>
- <key>CFBundleIdentifier</key>
- <string>com.googlecode.skia.${PRODUCT_NAME:rfc1034identifier}</string>
- <key>CFBundleInfoDictionaryVersion</key>
- <string>6.0</string>
- <key>CFBundleName</key>
- <string>${PRODUCT_NAME}</string>
- <key>CFBundlePackageType</key>
- <string>APPL</string>
- <key>CFBundleShortVersionString</key>
- <string>1.0</string>
- <key>CFBundleSignature</key>
- <string>????</string>
- <key>CFBundleVersion</key>
- <string>1</string>
- <key>LSMinimumSystemVersion</key>
- <string>${MACOSX_DEPLOYMENT_TARGET}</string>
- <key>NSMainNibFile</key>
- <string>ShapeOpsDemo</string>
- <key>NSPrincipalClass</key>
- <string>NSApplication</string>
-</dict>
-</plist>
diff --git a/experimental/Intersection/ShapeOpsDemo.cpp b/experimental/Intersection/ShapeOpsDemo.cpp
deleted file mode 100644
index a2690ea..0000000
--- a/experimental/Intersection/ShapeOpsDemo.cpp
+++ /dev/null
@@ -1,110 +0,0 @@
-#include "EdgeWalker_Test.h"
-#include "ShapeOps.h"
-#include "SkApplication.h"
-#include "SkCanvas.h"
-#include "SkEvent.h"
-#include "SkGraphics.h"
-#include "SkPaint.h"
-
-SkCanvas* canvas = 0;
-SkBitmap* bitmap;
-
-static bool test15(SkCanvas* canvas) {
- // Three circles bounce inside a rectangle. The circles describe three, four
- // or five points which in turn describe a polygon. The polygon points
- // bounce inside the circles. The circles rotate and scale over time. The
- // polygons are combined into a single path, simplified, and stroked.
- static int step = 0;
- const int circles = 3;
- int scales[circles];
- int angles[circles];
- int locs[circles * 2];
- int pts[circles * 2 * 4];
- int c, p;
- for (c = 0; c < circles; ++c) {
- scales[c] = abs(10 - (step + c * 4) % 21);
- angles[c] = (step + c * 6) % 600;
- locs[c * 2] = abs(130 - (step + c * 9) % 261);
- locs[c * 2 + 1] = abs(170 - (step + c * 11) % 341);
- for (p = 0; p < 4; ++p) {
- pts[c * 8 + p * 2] = abs(90 - ((step + c * 121 + p * 13) % 190));
- pts[c * 8 + p * 2 + 1] = abs(110 - ((step + c * 223 + p * 17) % 230));
- }
- }
- SkPath path, out;
- for (c = 0; c < circles; ++c) {
- for (p = 0; p < 4; ++p) {
- SkScalar x = pts[c * 8 + p * 2];
- SkScalar y = pts[c * 8 + p * 2 + 1];
- x *= 3 + scales[c] / 10.0f;
- y *= 3 + scales[c] / 10.0f;
- SkScalar angle = angles[c] * 3.1415f * 2 / 600;
- SkScalar temp = x * cos(angle) - y * sin(angle);
- y = x * sin(angle) + y * cos(angle);
- x = temp;
- x += locs[c * 2] * 200 / 130.0f;
- y += locs[c * 2 + 1] * 200 / 170.0f;
- x += 50;
- // y += 200;
- if (p == 0) {
- path.moveTo(x, y);
- } else {
- path.lineTo(x, y);
- }
- }
- path.close();
- }
- showPath(path, "original:");
- simplify(path, true, out);
- showPath(out, "simplified:");
- SkPaint paint;
- paint.setAntiAlias(true);
- paint.setStyle(SkPaint::kStroke_Style);
- paint.setStrokeWidth(3);
- paint.setColor(0x3F007fbF);
- canvas->drawPath(path, paint);
- paint.setColor(0xFF60FF00);
- paint.setStrokeWidth(1);
- canvas->drawPath(out, paint);
- ++step;
- return true;
-}
-
-static bool (*tests[])(SkCanvas* ) = {
- test15,
-};
-
-static size_t testsCount = sizeof(tests) / sizeof(tests[0]);
-
-static bool (*firstTest)(SkCanvas*) = test15;
-
-extern "C" void* getPixels(bool* animate);
-extern "C" void unlockPixels();
-
-extern "C" void* getPixels(bool* animate) {
- if (!canvas) {
- canvas = new SkCanvas();
- bitmap = new SkBitmap();
- SkBitmap::Config config = SkBitmap::kARGB_8888_Config;
-
- bitmap->setConfig(config, 1100, 630);
- bitmap->allocPixels();
- bitmap->setIsOpaque(true);
- canvas->setBitmapDevice(*bitmap);
- }
- canvas->drawColor(SK_ColorWHITE);
- size_t index = 0;
- if (index == 0 && firstTest) {
- while (index < testsCount && tests[index] != firstTest) {
- ++index;
- }
- }
- *animate = (tests[index])(canvas);
- bitmap->lockPixels();
- return bitmap->getPixels();
-}
-
-extern "C" void unlockPixels() {
- bitmap->unlockPixels();
-}
-
diff --git a/experimental/Intersection/edge-Info.plist b/experimental/Intersection/edge-Info.plist
deleted file mode 100644
index f696cb2..0000000
--- a/experimental/Intersection/edge-Info.plist
+++ /dev/null
@@ -1,32 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
-<plist version="1.0">
-<dict>
- <key>CFBundleDevelopmentRegion</key>
- <string>English</string>
- <key>CFBundleExecutable</key>
- <string>${EXECUTABLE_NAME}</string>
- <key>CFBundleIconFile</key>
- <string></string>
- <key>CFBundleIdentifier</key>
- <string>com.yourcompany.${PRODUCT_NAME:rfc1034identifier}</string>
- <key>CFBundleInfoDictionaryVersion</key>
- <string>6.0</string>
- <key>CFBundleName</key>
- <string>${PRODUCT_NAME}</string>
- <key>CFBundlePackageType</key>
- <string>APPL</string>
- <key>CFBundleShortVersionString</key>
- <string>1.0</string>
- <key>CFBundleSignature</key>
- <string>????</string>
- <key>CFBundleVersion</key>
- <string>1</string>
- <key>LSMinimumSystemVersion</key>
- <string>${MACOSX_DEPLOYMENT_TARGET}</string>
- <key>NSMainNibFile</key>
- <string>MainMenu</string>
- <key>NSPrincipalClass</key>
- <string>NSApplication</string>
-</dict>
-</plist>
diff --git a/experimental/Intersection/thingsToDo.txt b/experimental/Intersection/thingsToDo.txt
new file mode 100644
index 0000000..a1d8ac0
--- /dev/null
+++ b/experimental/Intersection/thingsToDo.txt
@@ -0,0 +1,20 @@
+add unit test for quadratic horizontal intersection
+add unit test for cubic horizontal intersection with left/right
+add unit test for ActiveEdge::calcLeft (can currently loop forever)
+does ActiveEdge::isCoincidentWith need to support quad, cubic?
+figure out why variation in ActiveEdge::tooCloseToCall isn't better
+why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22?
+add code to promote quad to cubic, or add quad/cubic intersection
+figure out why testSimplifySkinnyTriangle13 fails
+
+for quadratics and cubics, once various T values are added, see if consecutive
+Ts have ys that go up instead of down. If so, the edge needs to be broken.
+
+when splitting curves at inflection pts, should I retain the original curve
+data and note that the first/last T are no longer 0/1 ?
+I need to figure this out before I can proceed
+
+would it make sense to leave the InEdge alone, and add multiple copies of
+ActiveEdge, pointing to the same InEdge, where the copy has only the subset
+of Ts that need to be walked in reverse order?
+
diff --git a/gyp/shapeops_edge.gyp b/gyp/shapeops_edge.gyp
index b5c9d16..92007a0 100644
--- a/gyp/shapeops_edge.gyp
+++ b/gyp/shapeops_edge.gyp
@@ -66,7 +66,6 @@
'../experimental/Intersection/QuadraticUtilities.cpp',
'../experimental/Intersection/RectUtilities.cpp',
'../experimental/Intersection/TestUtilities.cpp',
- '../experimental/Intersection/CubicIntersection.h',
'../experimental/Intersection/CubicIntersection_TestData.h',
'../experimental/Intersection/CubicUtilities.h',
'../experimental/Intersection/CurveIntersection.h',
@@ -87,6 +86,7 @@
'../experimental/Intersection/ShapeOps.h',
'../experimental/Intersection/TestUtilities.h',
'../experimental/Intersection/TSearch.h',
+ '../experimental/Intersection/thingsToDo.txt',
],
'dependencies': [
'core.gyp:core',