shape ops work in progress
M Intersection/DataTypes.cpp
M Intersection/QuadraticIntersection_Test.cpp
M Intersection/EdgeWalker.cpp
M Intersection/LineQuadraticIntersection_Test.cpp
M Intersection/LineIntersection_Test.cpp
M Intersection/LineIntersection.cpp
D Intersection/edge.xcodeproj
M Intersection/SimplifyFindTop_Test.cpp
M Intersection/DataTypes.h
A Intersection/SimplifyRect4x4_Test.cpp
M Intersection/CubicIntersection_Test.cpp
M Intersection/QuadraticUtilities.h
M Intersection/LineCubicIntersection_Test.cpp
A Intersection/CurveUtilities.h
M Intersection/QuadraticBezierClip.cpp
M Intersection/QuadraticBounds.cpp
M Intersection/LineUtilities.h
M Intersection/Intersection_Tests.cpp
M Intersection/Simplify.cpp
M Intersection/EdgeWalker_TestUtility.cpp
M Intersection/QuadraticUtilities.cpp
M Intersection/thingsToDo.txt
M Intersection/LineUtilities.cpp
M Intersection/CubicUtilities.h
M Intersection/SimplifyFindNext_Test.cpp
M Intersection/Intersection_Tests.h
M Intersection/CubicBezierClip.cpp
M Intersection/ActiveEdge_Test.cpp
M Intersection/CubicBounds.cpp
M Intersection/Simplify.h
M Intersection/SimplifyNew_Test.cpp
M Intersection/EdgeWalker_Test.h
M Intersection/CubicUtilities.cpp
M Intersection/op.htm
M Intersection/ConvexHull.cpp
D Intersection/RectUtilities.cpp
M Intersection/SimplifyAddIntersectingTs_Test.cpp
git-svn-id: http://skia.googlecode.com/svn/trunk@4429 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index b57acf3..23a0a3d 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -25,9 +25,12 @@
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_BRIDGE 0
+#define DEBUG_CROSS 0
#define DEBUG_DUMP 0
#define DEBUG_PATH_CONSTRUCTION 0
+#define DEBUG_WINDING 0
#define DEBUG_UNUSED 0 // set to expose unused functions
+#define DEBUG_MARK_DONE 0
#else
@@ -35,9 +38,12 @@
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_BRIDGE 1
+#define DEBUG_CROSS 1
#define DEBUG_DUMP 1
#define DEBUG_PATH_CONSTRUCTION 1
+#define DEBUG_WINDING 0
#define DEBUG_UNUSED 0 // set to expose unused functions
+#define DEBUG_MARK_DONE 01
#endif
@@ -48,6 +54,10 @@
static int gSegmentID;
#endif
+#ifndef DEBUG_TEST
+#define DEBUG_TEST 0
+#endif
+
static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
Intersections& intersections) {
const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
@@ -95,24 +105,12 @@
return horizontalIntersect(aLine, left, right, y, flipped, intersections);
}
-static int VLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
- SkScalar y, bool flipped, Intersections& intersections) {
- const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
- return verticalIntersect(aLine, left, right, y, flipped, intersections);
-}
-
static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
SkScalar y, bool flipped, Intersections& intersections) {
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, flipped, intersections);
}
-static int VQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
- SkScalar y, bool flipped, Intersections& intersections) {
- const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
- return verticalIntersect(aQuad, left, right, y, flipped, intersections);
-}
-
static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
SkScalar y, bool flipped, Intersections& intersections) {
const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
@@ -120,13 +118,33 @@
return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
}
-static int VCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
- SkScalar y, bool flipped, Intersections& intersections) {
+static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped, Intersections& intersections) {
+ const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
+}
+
+static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped, Intersections& intersections) {
+ const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
+}
+
+static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
+ SkScalar x, bool flipped, Intersections& intersections) {
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 verticalIntersect(aCubic, left, right, y, flipped, intersections);
+ return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
}
+static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
+ SkScalar , SkScalar , bool , Intersections& ) = {
+ NULL,
+ VLineIntersect,
+ VQuadIntersect,
+ VCubicIntersect
+};
+
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;
@@ -217,6 +235,32 @@
CubicYAtT
};
+static SkScalar LineDXAtT(const SkPoint a[2], double ) {
+ return a[1].fX - a[0].fX;
+}
+
+static SkScalar QuadDXAtT(const SkPoint a[3], double t) {
+ const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}};
+ double x;
+ dxdy_at_t(quad, t, x, *(double*) 0);
+ return SkDoubleToScalar(x);
+}
+
+static SkScalar CubicDXAtT(const SkPoint a[4], double t) {
+ const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY},
+ {a[3].fX, a[3].fY}};
+ double x;
+ dxdy_at_t(cubic, t, x, *(double*) 0);
+ return SkDoubleToScalar(x);
+}
+
+static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
+ NULL,
+ LineDXAtT,
+ QuadDXAtT,
+ CubicDXAtT
+};
+
static void LineSubDivide(const SkPoint a[2], double startT, double endT,
SkPoint sub[2]) {
const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
@@ -416,6 +460,10 @@
return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy;
}
+ bool cancels(const Angle& rh) const {
+ return fDx * rh.fDx < 0 || fDy * rh.fDy < 0;
+ }
+
int end() const {
return fEnd;
}
@@ -427,7 +475,7 @@
// since all angles share a point, this needs to know which point
// is the common origin, i.e., whether the center is at pts[0] or pts[verb]
// practically, this should only be called by addAngle
- void set(const SkPoint* pts, SkPath::Verb verb, Segment* segment,
+ void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment,
int start, int end) {
SkASSERT(start != end);
fSegment = segment;
@@ -498,18 +546,13 @@
}
Segment* segment() const {
- return fSegment;
+ return const_cast<Segment*>(fSegment);
}
int sign() const {
return SkSign32(fStart - fEnd);
}
- bool slopeEquals(const Angle& rh) const {
- return fDx == rh.fDx && fDy == rh.fDy;
-
- }
-
int start() const {
return fStart;
}
@@ -521,7 +564,7 @@
SkScalar fDDy;
SkScalar fDDDx;
SkScalar fDDDy;
- Segment* fSegment;
+ const Segment* fSegment;
int fStart;
int fEnd;
};
@@ -536,13 +579,32 @@
QSort<Angle>(angleList.begin(), angleList.end() - 1);
}
-// Bounds, unlike Rect, does not consider a vertical line to be empty.
+// Bounds, unlike Rect, does not consider a line to be empty.
struct Bounds : public SkRect {
static bool Intersects(const Bounds& a, const Bounds& b) {
return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
a.fTop <= b.fBottom && b.fTop <= a.fBottom;
}
+ void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
+ if (left < fLeft) {
+ fLeft = left;
+ }
+ if (top < fTop) {
+ fTop = top;
+ }
+ if (right > fRight) {
+ fRight = right;
+ }
+ if (bottom > fBottom) {
+ fBottom = bottom;
+ }
+ }
+
+ void add(const Bounds& toAdd) {
+ add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
+ }
+
bool isEmpty() {
return fLeft > fRight || fTop > fBottom
|| fLeft == fRight && fTop == fBottom
@@ -570,14 +632,13 @@
};
struct Span {
- double fT;
Segment* fOther;
+ mutable SkPoint const* fPt; // lazily computed as needed
+ double fT;
double fOtherT; // value at fOther[fOtherIndex].fT
- mutable SkPoint const * fPt; // lazily computed as needed
int fOtherIndex; // can't be used during intersection
- int fWinding; // accumulated from contours surrounding this one
- // OPTIMIZATION: coincident needs only 2 bits (values are -1, 0, 1)
- int fCoincident; // -1 start of coincidence, 0 no coincidence, 1 end
+ int fWindSum; // accumulated from contours surrounding this one
+ int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
bool fDone; // if set, this span to next higher T has been processed
};
@@ -589,7 +650,26 @@
#endif
}
- void addAngle(SkTDArray<Angle>& angles, int start, int end) {
+ SkScalar activeTop() const {
+ SkASSERT(!done());
+ int count = fTs.count();
+ SkScalar result = SK_ScalarMax;
+ bool lastDone = true;
+ for (int index = 0; index < count; ++index) {
+ bool done = fTs[index].fDone;
+ if (!done || !lastDone) {
+ SkScalar y = yAtT(index);
+ if (result > y) {
+ result = y;
+ }
+ }
+ lastDone = done;
+ }
+ SkASSERT(result < SK_ScalarMax);
+ return result;
+ }
+
+ void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
SkASSERT(start != end);
SkPoint edge[4];
(*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
@@ -603,31 +683,34 @@
}
// FIXME: this needs to defer add for aligned consecutive line segments
- SkPoint addCurveTo(int start, int end, SkPath& path) {
+ SkPoint addCurveTo(int start, int end, SkPath& path, bool active) {
SkPoint edge[4];
+ // OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
(*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
+ if (active) {
#if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
- kLVerbStr[fVerb], edge[1].fX, edge[1].fY);
- if (fVerb > 1) {
- SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY);
- }
- if (fVerb > 2) {
- SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY);
- }
- SkDebugf("\n");
+ SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__,
+ kLVerbStr[fVerb], edge[1].fX, edge[1].fY);
+ if (fVerb > 1) {
+ SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY);
+ }
+ if (fVerb > 2) {
+ SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY);
+ }
+ SkDebugf("\n");
#endif
- switch (fVerb) {
- case SkPath::kLine_Verb:
- path.lineTo(edge[1].fX, edge[1].fY);
- break;
- case SkPath::kQuad_Verb:
- path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY);
- break;
- case SkPath::kCubic_Verb:
- path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY,
- edge[3].fX, edge[3].fY);
- break;
+ switch (fVerb) {
+ case SkPath::kLine_Verb:
+ path.lineTo(edge[1].fX, edge[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY,
+ edge[3].fX, edge[3].fY);
+ break;
+ }
}
return edge[fVerb];
}
@@ -637,12 +720,14 @@
fBounds.set(pts, 2);
}
- const SkPoint& addMoveTo(int tIndex, SkPath& path) {
- const SkPoint& pt = xyAtT(&fTs[tIndex]);
+ const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) {
+ const SkPoint& pt = xyAtT(tIndex);
+ if (active) {
#if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
+ SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY);
#endif
- path.moveTo(pt.fX, pt.fY);
+ path.moveTo(pt.fX, pt.fY);
+ }
return pt;
}
@@ -657,50 +742,233 @@
init(pts, SkPath::kQuad_Verb);
fBounds.setQuadBounds(pts);
}
+
+ // Defer all coincident edge processing until
+ // after normal intersections have been computed
- // edges are sorted by T, then by coincidence
- int addT(double newT, Segment& other, int coincident) {
+// no need to be tricky; insert in normal T order
+// resolve overlapping ts when considering coincidence later
+
+ // add non-coincident intersection. Resulting edges are sorted in T.
+ int addT(double newT, Segment* other) {
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
- Span* span;
size_t tCount = fTs.count();
- for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
+ for (size_t index = 0; index < tCount; ++index) {
// OPTIMIZATION: if there are three or more identical Ts, then
// the fourth and following could be further insertion-sorted so
// that all the edges are clockwise or counterclockwise.
// This could later limit segment tests to the two adjacent
// neighbors, although it doesn't help with determining which
// circular direction to go in.
- if (newT < fTs[idx2].fT || (newT == fTs[idx2].fT &&
- coincident <= fTs[idx2].fCoincident)) {
- insertedAt = idx2;
- span = fTs.insert(idx2);
- goto finish;
+ if (newT < fTs[index].fT) {
+ insertedAt = index;
+ break;
}
}
- insertedAt = tCount;
- span = fTs.append();
-finish:
+ Span* span;
+ if (insertedAt >= 0) {
+ span = fTs.insert(insertedAt);
+ } else {
+ insertedAt = tCount;
+ span = fTs.append();
+ }
span->fT = newT;
- span->fOther = &other;
+ span->fOther = other;
span->fPt = NULL;
- span->fWinding = 0;
- if (span->fDone = newT == 1) {
+ span->fWindSum = SK_MinS32;
+ span->fWindValue = 1;
+ if ((span->fDone = newT == 1)) {
++fDoneSpans;
}
- span->fCoincident = coincident;
- fCoincident |= coincident; // OPTIMIZATION: ever used?
return insertedAt;
}
- void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) {
+ // set spans from start to end to decrement by one
+ // note this walks other backwards
+ // FIMXE: there's probably an edge case that can be constructed where
+ // two span in one segment are separated by float epsilon on one span but
+ // not the other, if one segment is very small. For this
+ // case the counts asserted below may or may not be enough to separate the
+ // spans. Even if the counts work out, what if the spanw aren't correctly
+ // sorted? It feels better in such a case to match the span's other span
+ // pointer since both coincident segments must contain the same spans.
+ void addTCancel(double startT, double endT, Segment& other,
+ double oStartT, double oEndT) {
+ SkASSERT(endT - startT >= FLT_EPSILON);
+ SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ int index = 0;
+ while (startT - fTs[index].fT >= FLT_EPSILON) {
+ ++index;
+ }
+ int oCount = other.fTs.count();
+ while (other.fTs[--oCount].fT - oEndT >= FLT_EPSILON)
+ ;
+ int oIndex = oCount;
+ while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON)
+ ;
+ Span* test = &fTs[index];
+ Span* oTest = &other.fTs[oIndex];
+ SkDEBUGCODE(int testWindValue = test->fWindValue);
+ SkDEBUGCODE(int oTestWindValue = oTest->fWindValue);
+ SkDEBUGCODE(int startIndex = index);
+ SkTDArray<double> outsideTs;
+ SkTDArray<double> oOutsideTs;
+ do {
+ bool decrement = test->fWindValue && oTest->fWindValue;
+ Span* end = test;
+ double startT = end->fT;
+ double oStartT = oTest->fT;
+ do {
+ SkASSERT(testWindValue == end->fWindValue);
+ if (decrement) {
+ if (--(end->fWindValue) == 0) {
+ end->fDone = true;
+ ++fDoneSpans;
+ *outsideTs.append() = end->fT;
+ *outsideTs.append() = oStartT;
+ }
+ }
+ end = &fTs[++index];
+ } while (end->fT - test->fT < FLT_EPSILON);
+ SkASSERT(oCount - oIndex == index - startIndex);
+ Span* oTestStart = oTest;
+ SkDEBUGCODE(oCount = oIndex);
+ do {
+ SkASSERT(oTestWindValue == oTestStart->fWindValue);
+ if (decrement) {
+ if (--(oTestStart->fWindValue) == 0) {
+ oTestStart->fDone = true;
+ ++other.fDoneSpans;
+ *oOutsideTs.append() = oTestStart->fT;
+ *oOutsideTs.append() = startT;
+ }
+ }
+ if (!oIndex) {
+ break;
+ }
+ oTestStart = &other.fTs[--oIndex];
+ } while (oTest->fT - oTestStart->fT < FLT_EPSILON);
+ test = end;
+ oTest = oTestStart;
+ } while (test->fT < endT - FLT_EPSILON);
+ SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON);
+#if 0
+ if (!done() && outsideTs.count()) {
+ addTOutsides(outsideTs, &other, oStartT);
+ }
+ if (!other.done() && oOutsideTs.count()) {
+ other.addTOutsides(oOutsideTs, this, startT);
+ }
+#endif
+ }
+
+ // set spans from start to end to increment the greater by one and decrement
+ // the lesser
+ void addTCoincident(double startT, double endT, Segment& other,
+ double oStartT, double oEndT) {
+ SkASSERT(endT - startT >= FLT_EPSILON);
+ SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ int index = 0;
+ while (startT - fTs[index].fT >= FLT_EPSILON) {
+ ++index;
+ }
+ int oIndex = 0;
+ while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) {
+ ++oIndex;
+ }
+ Span* test = &fTs[index];
+ Span* oTest = &other.fTs[oIndex];
+ SkDEBUGCODE(int testWindValue = test->fWindValue);
+ SkDEBUGCODE(int oTestWindValue = oTest->fWindValue);
+ SkTDArray<double> outsideTs;
+ SkTDArray<double> oOutsideTs;
+ do {
+ bool decrementOther = test->fWindValue >= oTest->fWindValue;
+ Span* end = test;
+ double startT = end->fT;
+ double oStartT = oTest->fT;
+ do {
+ SkASSERT(testWindValue == end->fWindValue);
+ if (decrementOther) {
+ ++(end->fWindValue);
+ } else {
+ if (--(end->fWindValue) == 0) {
+ end->fDone = true;
+ ++fDoneSpans;
+ *outsideTs.append() = end->fT;
+ *outsideTs.append() = oStartT;
+ }
+ }
+ end = &fTs[++index];
+ } while (end->fT - test->fT < FLT_EPSILON);
+ Span* oEnd = oTest;
+ do {
+ SkASSERT(oTestWindValue == oEnd->fWindValue);
+ if (decrementOther) {
+ if (--(oEnd->fWindValue) == 0) {
+ oEnd->fDone = true;
+ ++other.fDoneSpans;
+ *oOutsideTs.append() = oEnd->fT;
+ *oOutsideTs.append() = startT;
+ }
+ } else {
+ ++(oEnd->fWindValue);
+ }
+ oEnd = &other.fTs[++oIndex];
+ } while (oEnd->fT - oTest->fT < FLT_EPSILON);
+ test = end;
+ oTest = oEnd;
+ } while (test->fT < endT - FLT_EPSILON);
+ SkASSERT(oTest->fT < oEndT + FLT_EPSILON);
+ SkASSERT(oTest->fT > oEndT - FLT_EPSILON);
+ if (!done() && outsideTs.count()) {
+ addTOutsides(outsideTs, &other, oEndT);
+ }
+ if (!other.done() && oOutsideTs.count()) {
+ other.addTOutsides(oOutsideTs, this, endT);
+ }
+ }
+
+ void addTOutsides(const SkTDArray<double>& outsideTs, Segment* other,
+ double otherEnd) {
+ int count = outsideTs.count();
+ double endT = 0;
+ int endSpan = 0;
+ for (int index = 0; index < count; index += 2) {
+ double t = outsideTs[index];
+ double otherT = outsideTs[index + 1];
+ if (t > 1 - FLT_EPSILON) {
+ return;
+ }
+ if (t - endT > FLT_EPSILON) {
+ endSpan = addTPair(t, other, otherT);
+ }
+ do {
+ endT = fTs[++endSpan].fT;
+ } while (endT - t < FLT_EPSILON);
+ }
+ addTPair(endT, other, otherEnd);
+ }
+
+ int addTPair(double t, Segment* other, double otherT) {
+ int insertedAt = addT(t, other);
+ int otherInsertedAt = other->addT(otherT, this);
+ addOtherT(insertedAt, otherT, otherInsertedAt);
+ other->addOtherT(otherInsertedAt, t, insertedAt);
+ return insertedAt;
+ }
+
+ void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
// add edge leading into junction
- addAngle(angles, end, start);
+ if (fTs[SkMin32(end, start)].fWindValue > 0) {
+ addAngle(angles, end, start);
+ }
// add edge leading away from junction
int step = SkSign32(end - start);
int tIndex = nextSpan(end, step);
- if (tIndex >= 0) {
+ if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) {
addAngle(angles, end, tIndex);
}
}
@@ -710,15 +978,14 @@
}
void buildAngles(int index, SkTDArray<Angle>& angles) const {
- SkASSERT(!done());
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT == fTs[lesser].fT) {
+ while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
- } while (++index < fTs.count() && referenceT == fTs[index].fT);
+ } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
}
void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
@@ -731,15 +998,22 @@
int oIndex = span->fOtherIndex;
// if done == -1, prior span has already been processed
int step = 1;
- int next = other->nextSpanEnd(oIndex, step);
+ int next = other->nextSpan(oIndex, step);
if (next < 0) {
step = -step;
- next = other->nextSpanEnd(oIndex, step);
+ next = other->nextSpan(oIndex, step);
}
- oIndex = other->coincidentEnd(oIndex, -step);
// add candidate into and away from junction
other->addTwoAngles(next, oIndex, angles);
- }
+ }
+
+ // OPTIMIZATION: inefficient, refactor
+ bool cancels(const Segment& other) const {
+ SkTDArray<Angle> angles;
+ addAngle(angles, 0, fTs.count() - 1);
+ other.addAngle(angles, 0, other.fTs.count() - 1);
+ return angles[0].cancels(angles[1]);
+ }
// figure out if the segment's ascending T goes clockwise or not
// not enough context to write this as shown
@@ -752,45 +1026,41 @@
return false;
}
- static bool Coincident(const Angle* current, const Angle* next) {
- const Segment* segment = current->segment();
- const Span& span = segment->fTs[current->start()];
- if (!span.fCoincident) {
- return false;
- }
- const Segment* nextSegment = next->segment();
- const Span& nextSpan = nextSegment->fTs[next->start()];
- if (!nextSpan.fCoincident) {
- return false;
- }
- // use angle dx/dy instead of other since 3 or more may be coincident
- return current->slopeEquals(*next);
- }
-
- static bool CoincidentCancels(const Angle* current, const Angle* next) {
- return SkSign32(current->start() - current->end())
- != SkSign32(next->start() - next->end());
- }
-
- int coincidentEnd(int from, int step) const {
- double fromT = fTs[from].fT;
- int count = fTs.count();
- int to = from;
- while (step > 0 ? ++to < count : --to >= 0) {
- const Span& span = fTs[to];
- if (fromT != span.fT) {
- // FIXME: we assume that if the T changes, we don't care about
- // coincident -- but in nextSpan, we require that both the T
- // and actual loc change to represent a span. This asymettry may
- // be OK or may be trouble -- if trouble, probably will need to
- // detect coincidence earlier or sort differently
- break;
+ int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const {
+ int start = 0;
+ int bestT = -1;
+ SkScalar top = bounds().fTop;
+ SkScalar bottom = bounds().fBottom;
+ int end;
+ do {
+ end = nextSpan(start, 1);
+ SkPoint edge[4];
+ // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can
+ // work with the original data directly
+ (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge);
+ // start here; intersect ray starting at basePt with edge
+ Intersections intersections;
+ int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
+ false, intersections);
+ if (pts == 0) {
+ continue;
}
- if (span.fCoincident == step) {
- return to;
+ if (pts > 1 && fVerb == SkPath::kLine_Verb) {
+ // if the intersection is edge on, wait for another one
+ continue;
}
- }
- return from;
+ SkASSERT(pts == 1); // FIXME: more code required to disambiguate
+ SkPoint pt;
+ double foundT = intersections.fT[0][0];
+ (*SegmentXYAtT[fVerb])(fPts, foundT, &pt);
+ if (bestY < pt.fY) {
+ bestY = pt.fY;
+ bestT = foundT < 1 ? start : end;
+ hitT = foundT;
+ }
+ start = end;
+ } while (fTs[end].fT != 1);
+ return bestT;
}
bool done() const {
@@ -798,37 +1068,46 @@
return fDoneSpans == fTs.count();
}
+ // so the span needs to contain the pairing info found here
+ // this should include the winding computed for the edge, and
+ // what edge it connects to, and whether it is discarded
+ // (maybe discarded == abs(winding) > 1) ?
+ // only need derivatives for duration of sorting, add a new struct
+ // for pairings, remove extra spans that have zero length and
+ // reference an unused other
+ // for coincident, the last span on the other may be marked done
+ // (always?)
+
+ // if loop is exhausted, contour may be closed.
+ // FIXME: pass in close point so we can check for closure
+
+ // given a segment, and a sense of where 'inside' is, return the next
+ // segment. If this segment has an intersection, or ends in multiple
+ // segments, find the mate that continues the outside.
+ // note that if there are multiples, but no coincidence, we can limit
+ // choices to connections in the correct direction
+
+ // mark found segments as done
+
// start is the index of the beginning T of this edge
// it is guaranteed to have an end which describes a non-zero length (?)
// winding -1 means ccw, 1 means cw
- // step is in/out -1 or 1
- // spanIndex is returned
+ // firstFind allows coincident edges to be treated differently
Segment* findNext(int winding, const int startIndex, const int endIndex,
- int& nextStart, int& nextEnd) {
+ int& nextStart, int& nextEnd, bool firstFind) {
SkASSERT(startIndex != endIndex);
int count = fTs.count();
SkASSERT(startIndex < endIndex ? startIndex < count - 1
: startIndex > 0);
-
int step = SkSign32(endIndex - startIndex);
- int end = nextSpanEnd(startIndex, step);
+ int end = nextSpan(startIndex, step);
SkASSERT(end >= 0);
-
- // preflight for coincidence -- if present, it may change winding
- // considerations and whether reversed edges can be followed
-
- // Discard opposing direction candidates if no coincidence was found.
Span* endSpan = &fTs[end];
Segment* other;
- if (isSimple(end, step)) {
+ if (isSimple(end)) {
// mark the smaller of startIndex, endIndex done, and all adjacent
// spans with the same T value (but not 'other' spans)
markDone(SkMin32(startIndex, endIndex), winding);
- // move in winding direction until edge in correct direction
- // balance wrong direction edges before finding correct one
- // this requres that the intersection is angularly sorted
- // for a single intersection, special case -- choose the opposite
- // edge that steps the same
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
nextEnd = nextStart + step;
@@ -857,106 +1136,65 @@
}
}
// back up if prior edge is coincident with firstIndex
- int prior = firstIndex;
- do {
- if (--prior < 0) {
- prior = angleCount - 1;
- }
- SkASSERT(prior != angleIndex);
- if (!Coincident(sorted[prior], sorted[firstIndex])) {
- break;
- }
- firstIndex = prior;
- angle = sorted[prior];
- } while (true);
-
- // put some thought into handling coincident edges
- // 1) defer the initial moveTo/curveTo until we know that firstIndex
- // isn't coincident (although maybe findTop could tell us that)
- // 2) allow the below to mark and skip coincident pairs
- // 3) return something (null?) if all segments cancel each other out
- // 4) if coincident edges don't cancel, figure out which to return (follow)
-
+ // adjustFirst(sorted, firstIndex, winding, firstFind);
SkASSERT(firstIndex >= 0);
int startWinding = winding;
- int nextIndex = firstIndex;
- const Angle* nextAngle;
- Segment* nextSegment;
+ int nextIndex = firstIndex + 1;
+ int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
+ const Angle* foundAngle = NULL;
+ // bool alreadyMarked = angle->segment()->fTs[SkMin32(angle->start(),
+ // angle->end())].fDone;
+ // iterate through the angle, and compute everyone's winding
+ bool firstEdge = true;
do {
- if (++nextIndex == angleCount) {
+ if (nextIndex == angleCount) {
nextIndex = 0;
}
- SkASSERT(nextIndex != firstIndex); // should never wrap around
- nextAngle = sorted[nextIndex];
+ const Angle* nextAngle = sorted[nextIndex];
int maxWinding = winding;
- winding -= nextAngle->sign();
- nextSegment = nextAngle->segment();
- if (nextSegment->done()) {
- if (!winding) {
- break;
- }
- continue;
- }
- bool pairCoincides = Coincident(angle, nextAngle);
- bool pairCancels = pairCoincides
- && CoincidentCancels(angle, nextAngle);
- if (pairCancels) {
- angle->segment()->markAndChaseCoincident(angle->start(),
- angle->end(), nextSegment);
- return NULL;
- }
+ Segment* nextSegment = nextAngle->segment();
+ int windValue = nextSegment->windValue(nextAngle);
+ SkASSERT(windValue > 0);
+ winding -= nextAngle->sign() * windValue;
+ firstEdge = false;
if (!winding) {
- break;
- }
- if (pairCoincides) {
- bool markNext = abs(maxWinding) < abs(winding);
- if (markNext) {
- nextSegment->markDone(SkMin32(nextAngle->start(),
- nextAngle->end()), winding);
- } else {
- angle->segment()->markDone(SkMin32(angle->start(),
- angle->end()), maxWinding);
+ if (!foundAngle) {
+ foundAngle = nextAngle;
}
+ goto doNext;
+ }
+ if (nextSegment->done()) {
+ goto doNext;
}
// if the winding is non-zero, nextAngle does not connect to
// current chain. If we haven't done so already, mark the angle
// as done, record the winding value, and mark connected unambiguous
// segments as well.
- else if (nextSegment->winding(nextAngle) == 0) {
+ if (nextSegment->winding(nextAngle) == SK_MinS32) {
if (abs(maxWinding) < abs(winding)) {
maxWinding = winding;
}
- nextSegment->markAndChaseWinding(nextAngle, maxWinding);
+ if (foundAngle) {
+ nextSegment->markAndChaseWinding(nextAngle, maxWinding);
+ } else {
+ nextSegment->markAndChaseDone(nextAngle, maxWinding);
+ }
}
- } while ((angle = nextAngle)); // always true
- markDone(SkMin32(startIndex, endIndex), startWinding);
- nextStart = nextAngle->start();
- nextEnd = nextAngle->end();
- return nextSegment;
+ doNext:
+ angle = nextAngle;
+ } while (++nextIndex != lastIndex);
+ // if (!alreadyMarked) {
+ sorted[firstIndex]->segment()->
+ markDone(SkMin32(startIndex, endIndex), startWinding);
+ // }
+ if (!foundAngle) {
+ return NULL;
+ }
+ nextStart = foundAngle->start();
+ nextEnd = foundAngle->end();
+ return foundAngle->segment();
}
-
- // so the span needs to contain the pairing info found here
- // this should include the winding computed for the edge, and
- // what edge it connects to, and whether it is discarded
- // (maybe discarded == abs(winding) > 1) ?
- // only need derivatives for duration of sorting, add a new struct
- // for pairings, remove extra spans that have zero length and
- // reference an unused other
- // for coincident, the last span on the other may be marked done
- // (always?)
-
- // if loop is exhausted, contour may be closed.
- // FIXME: pass in close point so we can check for closure
-
- // given a segment, and a sense of where 'inside' is, return the next
- // segment. If this segment has an intersection, or ends in multiple
- // segments, find the mate that continues the outside.
- // note that if there are multiples, but no coincidence, we can limit
- // choices to connections in the correct direction
-
- // mark found segments as done
-
// FIXME: this is tricky code; needs its own unit test
void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered
int count = fTs.count();
@@ -985,7 +1223,7 @@
// so, the span from here to there is coincident.
for (int index = matchIndex + 1; index < count; ++index) {
Span* test = &fTs[index];
- if (test->fCoincident) {
+ if (test->fDone) {
continue;
}
Segment* tOther = test->fOther;
@@ -1007,7 +1245,7 @@
double moStartT, moEndT;
for (int moIndex = 0; moIndex < moCount; ++moIndex) {
Span& moSpan = mOther->fTs[moIndex];
- if (moSpan.fCoincident) {
+ if (moSpan.fDone) {
continue;
}
if (moSpan.fOther == this) {
@@ -1060,11 +1298,16 @@
|| !tOther->isLinear(toStart, toEnd)) {
continue;
}
- // FIXME: may need to resort if we depend on coincidence first, last
- mOther->fTs[moStart].fCoincident = -1;
- tOther->fTs[toStart].fCoincident = -1;
- mOther->fTs[moEnd].fCoincident = 1;
- tOther->fTs[toEnd].fCoincident = 1;
+ // FIXME: defer implementation until the rest works
+ // this may share code with regular coincident detection
+ SkASSERT(0);
+ #if 0
+ if (flipped) {
+ mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd);
+ } else {
+ mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd);
+ }
+ #endif
}
}
@@ -1077,10 +1320,10 @@
SkASSERT(!done());
int firstT;
int lastT;
- int firstCoinT;
SkPoint topPt;
topPt.fY = SK_ScalarMax;
int count = fTs.count();
+ // see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
for (int index = 0; index < count; ++index) {
const Span& span = fTs[index];
@@ -1089,22 +1332,13 @@
if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
&& topPt.fX > intercept.fX)) {
topPt = intercept;
- firstT = lastT = firstCoinT = index;
+ firstT = lastT = index;
} else if (topPt == intercept) {
lastT = index;
- if (span.fCoincident) {
- firstCoinT = index;
- }
}
}
lastDone = span.fDone;
}
- // if there's only a pair of segments, go with the endpoint chosen above
- if (firstT == lastT) {
- tIndex = firstT;
- endIndex = firstT > 0 ? tIndex - 1 : tIndex + 1;
- return this;
- }
// sort the edges to find the leftmost
int step = 1;
int end = nextSpan(firstT, step);
@@ -1117,7 +1351,7 @@
// look for left-ness from tLeft to firstT (matching y of other)
SkTDArray<Angle> angles;
SkASSERT(firstT - end != 0);
- addTwoAngles(end, firstCoinT, angles);
+ addTwoAngles(end, firstT, angles);
buildAngles(firstT, angles);
SkTDArray<Angle*> sorted;
sortAngles(angles, sorted);
@@ -1150,93 +1384,14 @@
Span& oSpan = other->fTs[o];
if (oT == oSpan.fT && this == oSpan.fOther) {
iSpan.fOtherIndex = o;
+ break;
}
}
}
}
// OPTIMIZATION: uses tail recursion. Unwise?
- void innerCoincidentChase(int step, Segment* other) {
- // find other at index
- SkASSERT(!done());
- const Span* start = NULL;
- const Span* end = NULL;
- int index, startIndex, endIndex;
- int count = fTs.count();
- for (index = 0; index < count; ++index) {
- const Span& span = fTs[index];
- if (!span.fCoincident || span.fOther != other) {
- continue;
- }
- if (!start) {
- if (span.fDone) {
- continue;
- }
- startIndex = index;
- start = &span;
- } else {
- SkASSERT(!end);
- endIndex = index;
- end = &span;
- }
- }
- if (!end) {
- return;
- }
- Segment* next;
- Segment* nextOther;
- if (step < 0) {
- next = start->fT == 0 ? NULL : this;
- nextOther = other->fTs[start->fOtherIndex].fT == 1 ? NULL : other;
- } else {
- next = end->fT == 1 ? NULL : this;
- nextOther = other->fTs[end->fOtherIndex].fT == 0 ? NULL : other;
- }
- SkASSERT(!next || !nextOther);
- for (index = 0; index < count; ++index) {
- const Span& span = fTs[index];
- if (span.fCoincident || span.fOther == other) {
- continue;
- }
- bool checkNext = !next && (step < 0 ? span.fT == 0
- && span.fOtherT == 1 : span.fT == 1 && span.fOtherT == 0);
- bool checkOther = !nextOther && (step < 0 ? span.fT == start->fT
- && span.fOtherT == 0 : span.fT == end->fT && span.fOtherT == 1);
- if (!checkNext && !checkOther) {
- continue;
- }
- Segment* oSegment = span.fOther;
- if (oSegment->done()) {
- continue;
- }
- int oCount = oSegment->fTs.count();
- for (int oIndex = 0; oIndex < oCount; ++oIndex) {
- const Span& oSpan = oSegment->fTs[oIndex];
- if (oSpan.fT > 0 && oSpan.fT < 1) {
- continue;
- }
- if (!oSpan.fCoincident) {
- continue;
- }
- if (checkNext && (oSpan.fT == 0 ^ step < 0)) {
- next = oSegment;
- checkNext = false;
- }
- if (checkOther && (oSpan.fT == 1 ^ step < 0)) {
- nextOther = oSegment;
- checkOther = false;
- }
- }
- }
- markDone(SkMin32(startIndex, endIndex), 0);
- other->markDone(SkMin32(start->fOtherIndex, end->fOtherIndex), 0);
- if (next && nextOther) {
- next->innerCoincidentChase(step, nextOther);
- }
- }
-
- // OPTIMIZATION: uses tail recursion. Unwise?
- void innerChase(int index, int step, int winding) {
+ void innerChaseDone(int index, int step, int winding) {
int end = nextSpan(index, step);
if (multipleSpans(end, step)) {
return;
@@ -1245,15 +1400,32 @@
Segment* other = endSpan.fOther;
index = endSpan.fOtherIndex;
int otherEnd = other->nextSpan(index, step);
- other->innerChase(index, step, winding);
+ other->innerChaseDone(index, step, winding);
other->markDone(SkMin32(index, otherEnd), winding);
}
+ void innerChaseWinding(int index, int step, int winding) {
+ int end = nextSpan(index, step);
+ if (multipleSpans(end, step)) {
+ return;
+ }
+ const Span& endSpan = fTs[end];
+ Segment* other = endSpan.fOther;
+ index = endSpan.fOtherIndex;
+ int otherEnd = other->nextSpan(index, step);
+ int min = SkMin32(index, otherEnd);
+ if (other->fTs[min].fWindSum != SK_MinS32) {
+ SkASSERT(other->fTs[index].fWindSum == winding);
+ return;
+ }
+ other->innerChaseWinding(index, step, winding);
+ other->markWinding(min, winding);
+ }
+
void init(const SkPoint pts[], SkPath::Verb verb) {
fPts = pts;
fVerb = verb;
fDoneSpans = 0;
- fCoincident = 0;
}
bool intersected() const {
@@ -1276,27 +1448,19 @@
}
}
- bool isSimple(int index, int step) const {
+ bool isSimple(int end) const {
int count = fTs.count();
if (count == 2) {
return true;
}
- double spanT = fTs[index].fT;
- if (spanT > 0 && spanT < 1) {
- return false;
+ double t = fTs[end].fT;
+ if (t < FLT_EPSILON) {
+ return fTs[1].fT >= FLT_EPSILON;
}
- if (step < 0) {
- const Span& secondSpan = fTs[1];
- if (secondSpan.fT == 0) {
- return false;
- }
- return xyAtT(&fTs[0]) != xyAtT(&secondSpan);
+ if (t > 1 - FLT_EPSILON) {
+ return fTs[count - 2].fT <= 1 - FLT_EPSILON;
}
- const Span& penultimateSpan = fTs[count - 2];
- if (penultimateSpan.fT == 1) {
- return false;
- }
- return xyAtT(&fTs[count - 1]) != xyAtT(&penultimateSpan);
+ return false;
}
bool isHorizontal() const {
@@ -1311,51 +1475,101 @@
return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT);
}
- void markAndChaseCoincident(int index, int endIndex, Segment* other) {
- int step = SkSign32(endIndex - index);
- innerCoincidentChase(step, other);
- }
-
// this span is excluded by the winding rule -- chase the ends
// as long as they are unambiguous to mark connections as done
// and give them the same winding value
- void markAndChaseWinding(const Angle* angle, int winding) {
+ void markAndChaseDone(const Angle* angle, int winding) {
int index = angle->start();
int endIndex = angle->end();
int step = SkSign32(endIndex - index);
- innerChase(index, step, winding);
+ innerChaseDone(index, step, winding);
markDone(SkMin32(index, endIndex), winding);
}
+ void markAndChaseWinding(const Angle* angle, int winding) {
+ int index = angle->start();
+ int endIndex = angle->end();
+ int min = SkMin32(index, endIndex);
+ int step = SkSign32(endIndex - index);
+ innerChaseWinding(index, step, winding);
+ markWinding(min, winding);
+ }
+
// FIXME: this should also mark spans with equal (x,y)
+ // This may be called when the segment is already marked done. While this
+ // wastes time, it shouldn't do any more than spin through the T spans.
+ // OPTIMIZATION: abort on first done found (assuming that this code is
+ // always called to mark segments done).
void markDone(int index, int winding) {
- SkASSERT(!done());
+ // SkASSERT(!done());
double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && referenceT == fTs[lesser].fT) {
+ while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
Span& span = fTs[lesser];
- // FIXME: this needs to assert that all are not done or one or more are
- // coincident
- // SkASSERT(!span.fDone || span.fCoincident);
if (span.fDone) {
continue;
}
+ #if DEBUG_MARK_DONE
+ const SkPoint& pt = xyAtT(&span);
+ SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
+ __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding);
+ #endif
span.fDone = true;
- SkASSERT(!span.fWinding || span.fWinding == winding);
- span.fWinding = winding;
+ SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
+ span.fWindSum = winding;
fDoneSpans++;
}
do {
Span& span = fTs[index];
+ // SkASSERT(!span.fDone);
+ if (span.fDone) {
+ continue;
+ }
+ #if DEBUG_MARK_DONE
+ const SkPoint& pt = xyAtT(&span);
+ SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
+ __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding);
+ #endif
+ span.fDone = true;
+ SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
+ span.fWindSum = winding;
+ fDoneSpans++;
+ } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ }
+
+ void markWinding(int index, int winding) {
+ SkASSERT(!done());
+ double referenceT = fTs[index].fT;
+ int lesser = index;
+ while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ Span& span = fTs[lesser];
+ if (span.fDone) {
+ continue;
+ }
+ SkASSERT(span.fWindValue == 1 || winding == 0);
+ SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
+ #if DEBUG_MARK_DONE
+ const SkPoint& pt = xyAtT(&span);
+ SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
+ __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding);
+ #endif
+ span.fWindSum = winding;
+ }
+ do {
+ Span& span = fTs[index];
// SkASSERT(!span.fDone || span.fCoincident);
if (span.fDone) {
continue;
}
- span.fDone = true;
- SkASSERT(!span.fWinding || span.fWinding == winding);
- span.fWinding = winding;
- fDoneSpans++;
- } while (++index < fTs.count() && referenceT == fTs[index].fT);
+ SkASSERT(span.fWindValue == 1 || winding == 0);
+ SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
+ #if DEBUG_MARK_DONE
+ const SkPoint& pt = xyAtT(&span);
+ SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n",
+ __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding);
+ #endif
+ span.fWindSum = winding;
+ } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
}
bool multipleSpans(int end, int step) const {
@@ -1368,18 +1582,14 @@
// coincidence is found when the beginning Ts contain -step and the end
// contains step. When it is looking for the beginning of the next, the
// first Ts found can be ignored and the last Ts should contain -step.
+ // OPTIMIZATION: probably should split into two functions
int nextSpan(int from, int step) const {
const Span& fromSpan = fTs[from];
int count = fTs.count();
int to = from;
while (step > 0 ? ++to < count : --to >= 0) {
const Span& span = fTs[to];
- if (fromSpan.fT == span.fT) {
- continue;
- }
- const SkPoint& loc = xyAtT(&span);
- const SkPoint& fromLoc = xyAtT(&fromSpan);
- if (fromLoc == loc) {
+ if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) {
continue;
}
return to;
@@ -1387,16 +1597,6 @@
return -1;
}
- // once past current span, if step>0, look for coicident==1
- // if step<0, look for coincident==-1
- int nextSpanEnd(int from, int step) const {
- int result = nextSpan(from, step);
- if (result < 0) {
- return result;
- }
- return coincidentEnd(result, step);
- }
-
const SkPoint* pts() const {
return fPts;
}
@@ -1411,6 +1611,11 @@
const Span& span(int tIndex) const {
return fTs[tIndex];
}
+
+ int spanSign(int startIndex, int endIndex) const {
+ return startIndex < endIndex ? -fTs[startIndex].fWindValue :
+ fTs[endIndex].fWindValue;
+ }
// OPTIMIZATION: mark as debugging only if used solely by tests
double t(int tIndex) const {
@@ -1424,18 +1629,64 @@
SkPath::Verb verb() const {
return fVerb;
}
+
+ // if the only remaining spans are small, ignore them, and mark done
+ bool virtuallyDone() {
+ int count = fTs.count();
+ double previous = 0;
+ bool previousDone = fTs[0].fDone;
+ for (int index = 1; index < count; ++index) {
+ Span& span = fTs[index];
+ double t = span.fT;
+ if (t - previous < FLT_EPSILON) {
+ if (span.fDone && !previousDone) {
+ int prior = --index;
+ int winding = span.fWindSum;
+ do {
+ Span& priorSpan = fTs[prior];
+ priorSpan.fDone = true;
+ priorSpan.fWindSum = winding;
+ fDoneSpans++;
+ } while (--prior >= 0 && t - fTs[prior].fT < FLT_EPSILON);
+ }
+ } else if (!previousDone) {
+ return false;
+ }
+ previous = t;
+ previousDone = span.fDone;
+ }
+ SkASSERT(done());
+ return true;
+ }
+
+ int winding(int tIndex) const {
+ return fTs[tIndex].fWindSum;
+ }
- bool winding(const Angle* angle) {
+ int winding(const Angle* angle) const {
int start = angle->start();
int end = angle->end();
int index = SkMin32(start, end);
- Span& span = fTs[index];
- return span.fWinding;
+ return winding(index);
}
- SkScalar xAtT(double t) const {
- SkASSERT(t >= 0 && t <= 1);
- return (*SegmentXAtT[fVerb])(fPts, t);
+ int windValue(int tIndex) const {
+ return fTs[tIndex].fWindValue;
+ }
+
+ int windValue(const Angle* angle) const {
+ int start = angle->start();
+ int end = angle->end();
+ int index = SkMin32(start, end);
+ return windValue(index);
+ }
+
+ SkScalar xAtT(const Span* span) const {
+ return xyAtT(span).fX;
+ }
+
+ const SkPoint& xyAtT(int index) const {
+ return xyAtT(&fTs[index]);
}
const SkPoint& xyAtT(const Span* span) const {
@@ -1452,10 +1703,13 @@
}
return *span->fPt;
}
+
+ SkScalar yAtT(int index) const {
+ return yAtT(&fTs[index]);
+ }
- SkScalar yAtT(double t) const {
- SkASSERT(t >= 0 && t <= 1);
- return (*SegmentYAtT[fVerb])(fPts, t);
+ SkScalar yAtT(const Span* span) const {
+ return xyAtT(span).fY;
}
#if DEBUG_DUMP
@@ -1466,10 +1720,10 @@
SkPoint out;
(*SegmentXYAtT[fVerb])(fPts, t(i), &out);
SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d"
- " otherT=%1.9g winding=%d\n",
+ " otherT=%1.9g windSum=%d\n",
tab + sizeof(className), className, fID,
kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY,
- fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWinding);
+ fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum);
}
SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)",
tab + sizeof(className), className, fID,
@@ -1486,14 +1740,17 @@
// be allocated as needed instead of always initialized -- though maybe
// the initialization is lightweight enough that it hardly matters
mutable SkTDArray<SkPoint> fIntersections;
- // FIXME: coincident only needs two bits (-1, 0, 1)
- int fCoincident; // non-zero if some coincident span inside
int fDoneSpans; // used for quick check that segment is finished
#if DEBUG_DUMP
int fID;
#endif
};
+struct Coincidence {
+ Segment* fSegments[2];
+ double fTs[2][2];
+};
+
class Contour {
public:
Contour() {
@@ -1509,6 +1766,26 @@
: fBounds.fTop < rh.fBounds.fTop;
}
+ void addCoincident(int index, Contour* other, int otherIndex,
+ const Intersections& ts, bool swap) {
+ Coincidence& coincidence = *fCoincidences.append();
+ coincidence.fSegments[0] = &fSegments[index];
+ coincidence.fSegments[1] = &other->fSegments[otherIndex];
+ coincidence.fTs[swap][0] = ts.fT[0][0];
+ coincidence.fTs[swap][1] = ts.fT[0][1];
+ coincidence.fTs[!swap][0] = ts.fT[1][0];
+ coincidence.fTs[!swap][1] = ts.fT[1][1];
+ }
+
+ void addCross(const Contour* crosser) {
+#ifdef DEBUG_CROSS
+ for (int index = 0; index < fCrosses.count(); ++index) {
+ SkASSERT(fCrosses[index] != crosser);
+ }
+#endif
+ *fCrosses.append() = crosser;
+ }
+
void addCubic(const SkPoint pts[4]) {
fSegments.push_back().addCubic(pts);
fContainsCurves = true;
@@ -1518,6 +1795,10 @@
fSegments.push_back().addLine(pts);
return fSegments.count();
}
+
+ void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) {
+ fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
+ }
int addQuad(const SkPoint pts[3]) {
fSegments.push_back().addQuad(pts);
@@ -1525,6 +1806,11 @@
return fSegments.count();
}
+ int addT(int segIndex, double newT, Contour* other, int otherIndex) {
+ containsIntercepts();
+ return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]);
+ }
+
const Bounds& bounds() const {
return fBounds;
}
@@ -1538,6 +1824,48 @@
fContainsIntercepts = true;
}
+ const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY,
+ int &tIndex, double& hitT) {
+ int segmentCount = fSegments.count();
+ const Segment* bestSegment = NULL;
+ for (int test = 0; test < segmentCount; ++test) {
+ Segment* testSegment = &fSegments[test];
+ const SkRect& bounds = testSegment->bounds();
+ if (bounds.fTop < bestY) {
+ continue;
+ }
+ if (bounds.fTop > basePt.fY) {
+ continue;
+ }
+ if (bounds.fLeft > basePt.fX) {
+ continue;
+ }
+ if (bounds.fRight < basePt.fX) {
+ continue;
+ }
+ double testHitT;
+ int testT = testSegment->crossedSpan(basePt, bestY, testHitT);
+ if (testT >= 0) {
+ bestSegment = testSegment;
+ tIndex = testT;
+ hitT = testHitT;
+ }
+ }
+ return bestSegment;
+ }
+
+ bool crosses(const Contour* crosser) const {
+ if (this == crosser) {
+ return true;
+ }
+ for (int index = 0; index < fCrosses.count(); ++index) {
+ if (fCrosses[index] == crosser) {
+ return true;
+ }
+ }
+ return false;
+ }
+
void findTooCloseToCall(int winding) {
int segmentCount = fSegments.count();
for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
@@ -1556,44 +1884,118 @@
fSegments.reset();
fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
fContainsCurves = fContainsIntercepts = false;
+ fWindingSum = -1;
}
+ void resolveCoincidence(int winding) {
+ int count = fCoincidences.count();
+ for (int index = 0; index < count; ++index) {
+ Coincidence& coincidence = fCoincidences[index];
+ Segment* thisOne = coincidence.fSegments[0];
+ Segment* other = coincidence.fSegments[1];
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ if (startT > endT) {
+ SkTSwap<double>(startT, endT);
+ }
+ SkASSERT(endT - startT >= FLT_EPSILON);
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT > oEndT) {
+ SkTSwap<double>(oStartT, oEndT);
+ }
+ SkASSERT(oEndT - oStartT >= FLT_EPSILON);
+ if (winding > 0 || thisOne->cancels(*other)) {
+ thisOne->addTCancel(startT, endT, *other, oStartT, oEndT);
+ } else {
+ thisOne->addTCoincident(startT, endT, *other, oStartT, oEndT);
+ }
+ }
+ }
+
+ const SkTArray<Segment>& segments() {
+ return fSegments;
+ }
+
+ void setWinding(int winding) {
+ SkASSERT(fWindingSum < 0);
+ fWindingSum = winding;
+ }
+
// OPTIMIZATION: feel pretty uneasy about this. It seems like once again
// we need to sort and walk edges in y, but that on the surface opens the
// same can of worms as before. But then, this is a rough sort based on
// segments' top, and not a true sort, so it could be ameniable to regular
// sorting instead of linear searching. Still feel like I'm missing something
- Segment* topSegment() {
+ Segment* topSegment(SkScalar& bestY) {
int segmentCount = fSegments.count();
SkASSERT(segmentCount > 0);
int best = -1;
Segment* bestSegment = NULL;
while (++best < segmentCount) {
Segment* testSegment = &fSegments[best];
+ #if 0 // FIXME: remove if not needed
+ if (testSegment->virtuallyDone()) {
+ continue;
+ }
+ #else
if (testSegment->done()) {
continue;
}
+ #endif
bestSegment = testSegment;
break;
}
if (!bestSegment) {
return NULL;
}
- SkScalar bestTop = bestSegment->bounds().fTop;
+ SkScalar bestTop = bestSegment->activeTop();
for (int test = best + 1; test < segmentCount; ++test) {
Segment* testSegment = &fSegments[test];
if (testSegment->done()) {
continue;
}
- SkScalar testTop = testSegment->bounds().fTop;
+ if (testSegment->bounds().fTop > bestTop) {
+ continue;
+ }
+ SkScalar testTop = testSegment->activeTop();
if (bestTop > testTop) {
bestTop = testTop;
bestSegment = testSegment;
}
}
+ bestY = bestTop;
return bestSegment;
}
+ int updateSegment(int index, const SkPoint* pts) {
+ Segment& segment = fSegments[index];
+ segment.updatePts(pts);
+ return segment.verb() + 1;
+ }
+
+ int winding() {
+ if (fWindingSum >= 0) {
+ return fWindingSum;
+ }
+ // check peers
+ int count = fCrosses.count();
+ for (int index = 0; index < count; ++index) {
+ const Contour* crosser = fCrosses[index];
+ if (0 <= crosser->fWindingSum) {
+ fWindingSum = crosser->fWindingSum;
+ break;
+ }
+ }
+ return fWindingSum;
+ }
+
+#if DEBUG_TEST
+ SkTArray<Segment>& debugSegments() {
+ return fSegments;
+ }
+#endif
+
#if DEBUG_DUMP
void dump() {
int i;
@@ -1627,17 +2029,18 @@
}
fBounds = fSegments.front().bounds();
for (int index = 1; index < count; ++index) {
- fBounds.growToInclude(fSegments[index].bounds());
+ fBounds.add(fSegments[index].bounds());
}
}
-public:
- SkTArray<Segment> fSegments; // not worth accessor functions?
-
private:
+ SkTArray<Segment> fSegments;
+ SkTDArray<Coincidence> fCoincidences;
+ SkTDArray<const Contour*> fCrosses;
Bounds fBounds;
bool fContainsIntercepts;
bool fContainsCurves;
+ int fWindingSum; // initial winding number outside
#if DEBUG_DUMP
int fID;
#endif
@@ -1661,7 +2064,7 @@
protected:
void complete() {
- if (fCurrentContour && fCurrentContour->fSegments.count()) {
+ if (fCurrentContour && fCurrentContour->segments().count()) {
fCurrentContour->complete();
fCurrentContour = NULL;
}
@@ -1755,25 +2158,24 @@
SkASSERT(fCurrentContour);
}
complete();
- if (fCurrentContour && !fCurrentContour->fSegments.count()) {
+ if (fCurrentContour && !fCurrentContour->segments().count()) {
fContours.pop_back();
}
// correct pointers in contours since fReducePts may have moved as it grew
int cIndex = 0;
- fCurrentContour = &fContours[0];
int extraCount = fExtra.count();
- SkASSERT(fExtra[0] == -1);
+ SkASSERT(extraCount == 0 || fExtra[0] == -1);
int eIndex = 0;
int rIndex = 0;
while (++eIndex < extraCount) {
int offset = fExtra[eIndex];
if (offset < 0) {
- fCurrentContour = &fContours[++cIndex];
+ ++cIndex;
continue;
}
- Segment& segment = fCurrentContour->fSegments[offset - 1];
- segment.updatePts(&fReducePts[rIndex]);
- rIndex += segment.verb() + 1;
+ fCurrentContour = &fContours[cIndex];
+ rIndex += fCurrentContour->updateSegment(offset - 1,
+ &fReducePts[rIndex]);
}
fExtra.reset(); // we're done with this
}
@@ -1797,11 +2199,15 @@
kQuad_Segment = SkPath::kQuad_Verb,
kCubic_Segment = SkPath::kCubic_Verb,
};
+
+ void addCoincident(Work& other, const Intersections& ts, bool swap) {
+ fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap);
+ }
// FIXME: does it make sense to write otherIndex now if we're going to
// fix it up later?
void addOtherT(int index, double otherT, int otherIndex) {
- fContour->fSegments[fIndex].addOtherT(index, otherT, otherIndex);
+ fContour->addOtherT(fIndex, index, otherT, otherIndex);
}
// Avoid collapsing t values that are close to the same since
@@ -1809,10 +2215,8 @@
// be nearly equal, any problems caused by this should be taken care
// of later.
// On the edge or out of range values are negative; add 2 to get end
- int addT(double newT, const Work& other, int coincident) {
- fContour->containsIntercepts();
- return fContour->fSegments[fIndex].addT(newT,
- other.fContour->fSegments[other.fIndex], coincident);
+ int addT(double newT, const Work& other) {
+ return fContour->addT(fIndex, newT, other.fContour, other.fIndex);
}
bool advance() {
@@ -1824,7 +2228,7 @@
}
const Bounds& bounds() const {
- return fContour->fSegments[fIndex].bounds();
+ return fContour->segments()[fIndex].bounds();
}
const SkPoint* cubic() const {
@@ -1834,7 +2238,7 @@
void init(Contour* contour) {
fContour = contour;
fIndex = 0;
- fLast = contour->fSegments.count();
+ fLast = contour->segments().count();
}
SkScalar left() const {
@@ -1852,7 +2256,7 @@
}
const SkPoint* pts() const {
- return fContour->fSegments[fIndex].pts();
+ return fContour->segments()[fIndex].pts();
}
SkScalar right() const {
@@ -1864,7 +2268,7 @@
}
SegmentType segmentType() const {
- const Segment& segment = fContour->fSegments[fIndex];
+ const Segment& segment = fContour->segments()[fIndex];
SegmentType type = (SegmentType) segment.verb();
if (type != kLine_Segment) {
return type;
@@ -1888,7 +2292,7 @@
}
SkPath::Verb verb() const {
- return fContour->fSegments[fIndex].verb();
+ return fContour->segments()[fIndex].verb();
}
SkScalar x() const {
@@ -1904,7 +2308,7 @@
}
bool yFlipped() const {
- return y() != pts()[0].fX;
+ return y() != pts()[0].fY;
}
protected:
@@ -1959,6 +2363,7 @@
}
Work wt;
wt.init(test);
+ bool foundCommonContour = test == next;
do {
Work wn;
wn.init(next);
@@ -2116,70 +2521,155 @@
default:
SkASSERT(0);
}
+ if (!foundCommonContour && pts > 0) {
+ test->addCross(next);
+ next->addCross(test);
+ foundCommonContour = true;
+ }
// in addition to recording T values, record matching segment
- int testCoin;
- int nextCoin;
if (pts == 2 && wn.segmentType() <= Work::kLine_Segment
&& wt.segmentType() <= Work::kLine_Segment) {
- // pass coincident so that smaller T is -1, larger T is 1
- testCoin = ts.fT[swap][0] < ts.fT[swap][1] ? -1 : 1;
- nextCoin = ts.fT[!swap][0] < ts.fT[!swap][1] ? -1 : 1;
- } else {
- testCoin = nextCoin = 0;
+ wt.addCoincident(wn, ts, swap);
+ continue;
}
for (int pt = 0; pt < pts; ++pt) {
SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
- int testTAt = wt.addT(ts.fT[swap][pt], wn, testCoin);
- int nextTAt = wn.addT(ts.fT[!swap][pt], wt, nextCoin);
+ int testTAt = wt.addT(ts.fT[swap][pt], wn);
+ int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt);
wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt);
- testCoin = -testCoin;
- nextCoin = -nextCoin;
}
} while (wn.advance());
} while (wt.advance());
return true;
}
+// resolve any coincident pairs found while intersecting, and
// see if coincidence is formed by clipping non-concident segments
static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) {
int contourCount = contourList.count();
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
+ contour->resolveCoincidence(winding);
+ }
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ Contour* contour = contourList[cIndex];
contour->findTooCloseToCall(winding);
}
}
+// project a ray from the top of the contour up and see if it hits anything
+// note: when we compute line intersections, we keep track of whether
+// two contours touch, so we need only look at contours not touching this one.
+// OPTIMIZATION: sort contourList vertically to avoid linear walk
+static int innerContourCheck(SkTDArray<Contour*>& contourList,
+ Contour* baseContour, const SkPoint& basePt) {
+ int contourCount = contourList.count();
+ int winding = 0;
+ SkScalar bestY = SK_ScalarMin;
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ Contour* contour = contourList[cTest];
+ if (basePt.fY < contour->bounds().fTop) {
+ continue;
+ }
+ if (bestY > contour->bounds().fBottom) {
+ continue;
+ }
+ if (baseContour->crosses(contour)) {
+ continue;
+ }
+ int tIndex;
+ double tHit;
+ const Segment* test = contour->crossedSegment(basePt, bestY, tIndex,
+ tHit);
+ if (!test) {
+ continue;
+ }
+ // If the ray hit the end of a span, we need to construct the wheel of
+ // angles to find the span closest to the ray -- even if there are just
+ // two spokes on the wheel.
+ if (tHit == test->t(tIndex)) {
+ SkTDArray<Angle> angles;
+ int end = test->nextSpan(tIndex, 1);
+ if (end < 0) {
+ end = test->nextSpan(tIndex, -1);
+ }
+ test->addTwoAngles(tIndex, end, angles);
+ // test->buildAnglesInner(tIndex, angles);
+ test->buildAngles(tIndex, angles);
+ SkTDArray<Angle*> sorted;
+ sortAngles(angles, sorted);
+ const Angle* angle = sorted[0];
+ test = angle->segment();
+ SkScalar testDx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit);
+ if (testDx == 0) {
+ angle = *(sorted.end() - 1);
+ test = angle->segment();
+ SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0);
+ }
+ tIndex = angle->start(); // lesser Y
+ winding = test->winding(SkMin32(tIndex, angle->end()));
+ #if DEBUG_WINDING
+ SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding);
+ #endif
+ } else {
+ winding = test->winding(tIndex);
+ #if DEBUG_WINDING
+ SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding);
+ #endif
+ }
+ // see if a + change in T results in a +/- change in X (compute x'(T))
+ SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit);
+ #if DEBUG_WINDING
+ SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx);
+ #endif
+ SkASSERT(dx != 0);
+ if (winding * dx > 0) { // if same signs, result is negative
+ winding += dx > 0 ? -1 : 1;
+ #if DEBUG_WINDING
+ SkDebugf("%s 3 winding=%d\n", __FUNCTION__, winding);
+ #endif
+ }
+ }
+ baseContour->setWinding(winding);
+ return winding;
+}
// OPTIMIZATION: not crazy about linear search here to find top active y.
// seems like we should break down and do the sort, or maybe sort each
// contours' segments?
// Once the segment array is built, there's no reason I can think of not to
// sort it in Y. hmmm
+// FIXME: return the contour found to pass to inner contour check
static Segment* findTopContour(SkTDArray<Contour*>& contourList,
- int contourCount) {
+ Contour*& topContour) {
+ int contourCount = contourList.count();
int cIndex = 0;
Segment* topStart;
+ SkScalar bestY = SK_ScalarMax;
+ Contour* contour;
do {
- Contour* topContour = contourList[cIndex];
- topStart = topContour->topSegment();
+ contour = contourList[cIndex];
+ topStart = contour->topSegment(bestY);
} while (!topStart && ++cIndex < contourCount);
if (!topStart) {
return NULL;
}
- SkScalar top = topStart->bounds().fTop;
- for (int cTest = cIndex + 1; cTest < contourCount; ++cTest) {
- Contour* contour = contourList[cTest];
- if (top < contour->bounds().fTop) {
+ topContour = contour;
+ while (++cIndex < contourCount) {
+ contour = contourList[cIndex];
+ if (bestY < contour->bounds().fTop) {
continue;
}
- Segment* test = contour->topSegment();
- if (top > test->bounds().fTop) {
- cIndex = cTest;
- topStart = test;
- top = test->bounds().fTop;
+ SkScalar testY = SK_ScalarMax;
+ Segment* test = contour->topSegment(testY);
+ if (!test || bestY <= testY) {
+ continue;
}
+ topContour = contour;
+ topStart = test;
+ bestY = testY;
}
return topStart;
}
@@ -2194,36 +2684,65 @@
// since we start with leftmost top edge, we'll traverse through a
// smaller angle counterclockwise to get to the next edge.
static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) {
- int contourCount = contourList.count();
+ // after findTopContour has already been called once, check if
+ // result of subsequent findTopContour has no winding set
+ bool firstContour = true;
do {
- Segment* topStart = findTopContour(contourList, contourCount);
+ Contour* topContour;
+ Segment* topStart = findTopContour(contourList, topContour);
if (!topStart) {
break;
}
- // FIXME: if this contour is inside others, winding will not be zero initially
- int winding = 0; // zero says there are no contours outside this one
// Start at the top. Above the top is outside, below is inside.
// follow edges to intersection by changing the index by direction.
int index, endIndex;
Segment* current = topStart->findTop(index, endIndex);
- winding += SkSign32(index - endIndex);
+ int winding;
+ int contourWinding;
+ if (firstContour) {
+ topContour->setWinding(0);
+ contourWinding = 0;
+ firstContour = false;
+ winding = 0;
+ } else {
+ winding = topContour->winding();
+ #if DEBUG_WINDING
+ SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding);
+ #endif
+ if (!winding) {
+ const SkPoint& topPoint = current->xyAtT(endIndex);
+ winding = innerContourCheck(contourList, topContour, topPoint);
+ #if DEBUG_WINDING
+ SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding);
+ #endif
+ }
+ }
const SkPoint* firstPt = NULL;
SkPoint lastPt;
+ bool active = winding >= -1 && winding <= 1;
+ bool firstTime = true;
+ int spanWinding = current->spanSign(index, endIndex);
+ #if DEBUG_WINDING
+ SkDebugf("%s spanWinding=%d\n", __FUNCTION__, startWinding);
+ #endif
do {
SkASSERT(!current->done());
int nextStart, nextEnd;
- Segment* next = current->findNext(winding, index, endIndex,
- nextStart, nextEnd);
+ Segment* next = current->findNext(winding + spanWinding, index,
+ endIndex, nextStart, nextEnd, firstTime);
if (!next) {
break;
}
if (!firstPt) {
- firstPt = ¤t->addMoveTo(index, simple);
+ firstPt = ¤t->addMoveTo(index, simple, active);
}
- lastPt = current->addCurveTo(index, endIndex, simple);
+ lastPt = current->addCurveTo(index, endIndex, simple, active);
current = next;
index = nextStart;
endIndex = nextEnd;
+ spanWinding = SkSign32(spanWinding) * next->windValue(
+ SkMin32(nextStart, nextEnd));
+ firstTime = false;
} while (*firstPt != lastPt);
if (firstPt) {
#if DEBUG_PATH_CONSTRUCTION
@@ -2232,8 +2751,6 @@
simple.close();
}
} while (true);
- // FIXME: more work to be done for contained (but not intersecting)
- // segments
}
static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {