shape ops work in progress
things work pretty well up to this point
it's time to apply recent deletion of binary code
algorithms to the unary code path
git-svn-id: http://skia.googlecode.com/svn/trunk@6788 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index 69bd27b..33d88fa 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -104,6 +104,10 @@
return x > -FLT_EPSILON;
}
+inline bool approximately_positive_squared(double x) {
+ return x > -(FLT_EPSILON * FLT_EPSILON);
+}
+
inline bool approximately_zero_or_more(double x) {
return x > -FLT_EPSILON;
}
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 23ce5be..6170946 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -14,20 +14,21 @@
void Intersection_Tests() {
int testsRun = 0;
+
SimplifyNew_Test();
- ShapeOps4x4RectsThreaded_Test(testsRun);
- QuadraticIntersection_Test();
- LineQuadraticIntersection_Test();
- MiniSimplify_Test();
- SimplifyAngle_Test();
- QuarticRoot_Test();
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
Simplify4x4RectsThreaded_Test(testsRun);
SimplifyNondegenerate4x4TrianglesThreaded_Test(testsRun);
SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
Simplify4x4QuadralateralsThreaded_Test(testsRun);
+ ShapeOps4x4RectsThreaded_Test(testsRun);
SkDebugf("%s total testsRun=%d\n", __FUNCTION__, testsRun);
+ QuadraticIntersection_Test();
+ LineQuadraticIntersection_Test();
+ MiniSimplify_Test();
+ SimplifyAngle_Test();
+ QuarticRoot_Test();
QuadraticBezierClip_Test();
SimplifyFindNext_Test();
SimplifyFindTop_Test();
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 3288882..bab6c73 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -59,6 +59,8 @@
}
static const Quadratic testSet[] = {
+{{0, 0}, {1, 0}, {0, 3}},
+{{1, 0}, {0, 1}, {1, 1}},
{{369.848602,145.680267}, {382.360413,121.298294}, {406.207703,121.298294}},
{{369.961151,137.980698}, {383.970093,121.298294}, {406.213287,121.298294}},
{{353.2948,194.351074}, {353.2948,173.767563}, {364.167572,160.819855}},
diff --git a/experimental/Intersection/QuarticRoot.cpp b/experimental/Intersection/QuarticRoot.cpp
index 7a95b24..66ce3bf 100644
--- a/experimental/Intersection/QuarticRoot.cpp
+++ b/experimental/Intersection/QuarticRoot.cpp
@@ -46,9 +46,13 @@
/* normal form: x^2 + px + q = 0 */
const double p = B / (2 * A);
const double q = C / A;
- const double D = p * p - q;
+ double D = p * p - q;
if (D < 0) {
- return 0;
+ if (approximately_positive_squared(D)) {
+ D = 0;
+ } else {
+ return 0;
+ }
}
double sqrt_D = sqrt(D);
if (approximately_less_than_zero(sqrt_D)) {
diff --git a/experimental/Intersection/ShapeOpRect4x4_Test.cpp b/experimental/Intersection/ShapeOpRect4x4_Test.cpp
index 69b567f..d149377 100644
--- a/experimental/Intersection/ShapeOpRect4x4_Test.cpp
+++ b/experimental/Intersection/ShapeOpRect4x4_Test.cpp
@@ -23,7 +23,7 @@
bzero(pathStr, sizeof(pathStr));
do {
for (int a = 0 ; a < 6; ++a) {
- for (int b = a + 1 ; a < 7; ++b) {
+ for (int b = a + 1 ; b < 7; ++b) {
for (int c = 0 ; c < 6; ++c) {
for (int d = c + 1 ; d < 7; ++d) {
for (int op = 0 ; op < kShapeOp_Count; ++op) {
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index 1231ea3..6814f7d 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -129,35 +129,74 @@
}
*/
+static Segment* findSortableTopNew(SkTDArray<Contour*>& contourList, bool& firstContour, int& index,
+ int& endIndex, SkPoint& topLeft, bool& unsortable) {
+ Segment* current;
+ bool allowTies = true;
+ bool first = true;
+ do {
+ current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, allowTies,
+ true);
+ if (!current) {
+ if (first) {
+ return NULL;
+ }
+ break;
+ }
+ first = false;
+ if (firstContour) {
+ current->initWinding(index, endIndex, 0, 0);
+ firstContour = false;
+ return current;
+ }
+ int minIndex = SkMin32(index, endIndex);
+ int sumWinding = current->windSum(minIndex);
+ if (sumWinding == SK_MinS32) {
+ sumWinding = current->computeSum(index, endIndex, true);
+ if (sumWinding != SK_MinS32) {
+ return current;
+ }
+ }
+ allowTies = false;
+ int contourWinding = innerContourCheck(contourList, current, index, endIndex, false);
+ if (contourWinding == SK_MinS32) {
+ continue;
+ }
+ int oppContourWinding = innerContourCheck(contourList, current, index, endIndex, true);
+ if (oppContourWinding == SK_MinS32) {
+ continue;
+ }
+ current->initWinding(index, endIndex, contourWinding, oppContourWinding);
+ return current;
+ } while (true);
+ // the simple upward projection of the unresolved points hit unsortable angles
+ // shoot rays at right angles to the segment to find its winding, ignoring angle cases
+ SkASSERT(0); // steal code from findSortableTopOld and put it here
+ return current;
+}
+
static bool bridgeOp(SkTDArray<Contour*>& contourList, const ShapeOp op,
const int xorMask, const int xorOpMask, PathWrapper& simple) {
bool firstContour = true;
bool unsortable = false;
+ bool topUnsortable = false;
+ bool firstRetry = false;
bool closable = true;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
int index, endIndex;
- Segment* current = findSortableTop(contourList, index, endIndex, topLeft);
+ Segment* current = findSortableTopNew(contourList, firstContour, index, endIndex, topLeft,
+ topUnsortable);
if (!current) {
+ if (topUnsortable) {
+ topUnsortable = false;
+ SkASSERT(!firstRetry);
+ firstRetry = true;
+ topLeft.fX = topLeft.fY = SK_ScalarMin;
+ continue;
+ }
break;
}
- if (firstContour) {
- current->initWinding(index, endIndex, 0, 0);
- firstContour = false;
- } else {
- int minIndex = SkMin32(index, endIndex);
- int sumWinding = current->windSum(minIndex);
- if (sumWinding == SK_MinS32) {
- sumWinding = current->computeSum(index, endIndex, true);
- }
- if (sumWinding == SK_MinS32) {
- int contourWinding = innerContourCheck(contourList, current,
- index, endIndex, false);
- int oppContourWinding = innerContourCheck(contourList, current,
- index, endIndex, true);
- current->initWinding(index, endIndex, contourWinding, oppContourWinding);
- }
- }
SkTDArray<Span*> chaseArray;
do {
if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index e416554..d0b22ce 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -29,7 +29,7 @@
#define TRY_ROTATE 1
#define DEBUG_UNUSED 0 // set to expose unused functions
-#define FORCE_RELEASE 1 // set force release to 1 for multiple thread -- no debugging
+#define FORCE_RELEASE 0 // set force release to 1 for multiple thread -- no debugging
#if FORCE_RELEASE || defined SK_RELEASE
@@ -40,8 +40,10 @@
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
#define DEBUG_ANGLE 0
+#define DEBUG_ASSEMBLE 0
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
+#define DEBUG_FLOW 0
#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 0
#define DEBUG_SHOW_WINDING 0
@@ -58,8 +60,10 @@
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
+#define DEBUG_ASSEMBLE 1
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
+#define DEBUG_FLOW 1
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SHOW_WINDING 0
@@ -151,6 +155,14 @@
return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
}
+static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,
+ SkScalar , SkScalar , bool , Intersections& ) = {
+ NULL,
+ HLineIntersect,
+ HQuadIntersect,
+ HCubicIntersect
+};
+
static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
SkScalar x, bool flipped, Intersections& intersections) {
MAKE_CONST_LINE(aLine, a);
@@ -294,6 +306,31 @@
CubicDXAtT
};
+static SkScalar LineDYAtT(const SkPoint a[2], double ) {
+ return a[1].fY - a[0].fY;
+}
+
+static SkScalar QuadDYAtT(const SkPoint a[3], double t) {
+ MAKE_CONST_QUAD(quad, a);
+ double y;
+ dxdy_at_t(quad, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar CubicDYAtT(const SkPoint a[4], double t) {
+ MAKE_CONST_CUBIC(cubic, a);
+ double y;
+ dxdy_at_t(cubic, t, *(double*) 0, y);
+ return SkDoubleToScalar(y);
+}
+
+static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {
+ NULL,
+ LineDYAtT,
+ QuadDYAtT,
+ CubicDYAtT
+};
+
static void LineSubDivide(const SkPoint a[2], double startT, double endT,
SkPoint sub[2]) {
MAKE_CONST_LINE(aLine, a);
@@ -569,6 +606,12 @@
rh.fUnsortable = true;
return this < &rh; // even with no solution, return a stable sort
}
+ if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
+ || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
+ fUnsortable = true;
+ rh.fUnsortable = true;
+ return this < &rh; // even with no solution, return a stable sort
+ }
SkASSERT(fVerb == SkPath::kQuad_Verb); // worry about cubics later
SkASSERT(rh.fVerb == SkPath::kQuad_Verb);
// FIXME: until I can think of something better, project a ray from the
@@ -714,10 +757,13 @@
fUnsortable = true;
return;
}
+#if 0
if (index != fStart && (*fSpans)[index].fUnsortableEnd) {
+ SkASSERT(0);
fUnsortable = true;
return;
}
+#endif
}
}
@@ -795,6 +841,13 @@
add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
}
+ void add(const SkPoint& pt) {
+ if (pt.fX < fLeft) fLeft = pt.fX;
+ if (pt.fY < fTop) fTop = pt.fY;
+ if (pt.fX > fRight) fRight = pt.fX;
+ if (pt.fY > fBottom) fBottom = pt.fY;
+ }
+
bool isEmpty() {
return fLeft > fRight || fTop > fBottom
|| (fLeft == fRight && fTop == fBottom)
@@ -817,6 +870,11 @@
set((float) dRect.left, (float) dRect.top, (float) dRect.right,
(float) dRect.bottom);
}
+
+ void setPoint(const SkPoint& pt) {
+ fLeft = fRight = pt.fX;
+ fTop = fBottom = pt.fY;
+ }
};
// OPTIMIZATION: does the following also work, and is it any faster?
@@ -1581,7 +1639,7 @@
SkTDArray<double> oOutsideTs;
do {
// if either span has an opposite value and the operands don't match, resolve first
- SkASSERT(!test->fDone || !oTest->fDone);
+ // SkASSERT(!test->fDone || !oTest->fDone);
if (test->fDone || oTest->fDone) {
index = advanceCoincidentThis(oTest, opp, index);
oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
@@ -1794,7 +1852,8 @@
if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
oMaxWinding = oWinding;
}
- (void) segment->markAndChaseWinding(angle, maxWinding, binary ? oMaxWinding : 0);
+ (void) segment->markAndChaseWinding(angle, maxWinding,
+ binary ? oMaxWinding : 0);
}
}
} while (++nextIndex != lastIndex);
@@ -1802,7 +1861,59 @@
return windSum(minIndex);
}
- int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const {
+ int crossedSpanX(const SkPoint& basePt, SkScalar& bestX, double& hitT, bool opp) const {
+ int bestT = -1;
+ SkScalar left = bounds().fLeft;
+ SkScalar right = bounds().fRight;
+ int end = 0;
+ do {
+ int start = end;
+ end = nextSpan(start, 1);
+ if ((opp ? fTs[start].fOppValue : fTs[start].fWindValue) == 0) {
+ continue;
+ }
+ SkPoint edge[4];
+ double startT = fTs[start].fT;
+ double endT = fTs[end].fT;
+ (*SegmentSubDivide[fVerb])(fPts, startT, endT, edge);
+ // intersect ray starting at basePt with edge
+ Intersections intersections;
+ // FIXME: always use original and limit results to T values within
+ // start t and end t.
+ // OPTIMIZE: use specialty function that intersects ray with curve,
+ // returning t values only for curve (we don't care about t on ray)
+ int pts = (*HSegmentIntersect[fVerb])(edge, left, right, basePt.fY,
+ false, intersections);
+ if (pts == 0) {
+ continue;
+ }
+ if (pts > 1 && fVerb == SkPath::kLine_Verb) {
+ // if the intersection is edge on, wait for another one
+ continue;
+ }
+ for (int index = 0; index < pts; ++index) {
+ double foundT = intersections.fT[0][index];
+ double testT = startT + (endT - startT) * foundT;
+ SkScalar testX = (*SegmentXAtT[fVerb])(fPts, testT);
+ if (bestX < testX && testX < basePt.fX) {
+ if (fVerb > SkPath::kLine_Verb
+ && !approximately_less_than_zero(foundT)
+ && !approximately_greater_than_one(foundT)) {
+ SkScalar dy = (*SegmentDYAtT[fVerb])(fPts, testT);
+ if (approximately_zero(dy)) {
+ continue;
+ }
+ }
+ bestX = testX;
+ bestT = foundT < 1 ? start : end;
+ hitT = testT;
+ }
+ }
+ } while (fTs[end].fT != 1);
+ return bestT;
+ }
+
+ int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool opp) const {
int bestT = -1;
SkScalar top = bounds().fTop;
SkScalar bottom = bounds().fBottom;
@@ -1810,7 +1921,7 @@
do {
int start = end;
end = nextSpan(start, 1);
- if (fTs[start].fWindValue == 0) {
+ if ((opp ? fTs[start].fOppValue : fTs[start].fWindValue) == 0) {
continue;
}
SkPoint edge[4];
@@ -1833,11 +1944,10 @@
continue;
}
for (int index = 0; index < pts; ++index) {
- SkPoint pt;
double foundT = intersections.fT[0][index];
double testT = startT + (endT - startT) * foundT;
- (*SegmentXYAtT[fVerb])(fPts, testT, &pt);
- if (bestY < pt.fY && pt.fY < basePt.fY) {
+ SkScalar testY = (*SegmentYAtT[fVerb])(fPts, testT);
+ if (bestY < testY && testY < basePt.fY) {
if (fVerb > SkPath::kLine_Verb
&& !approximately_less_than_zero(foundT)
&& !approximately_greater_than_one(foundT)) {
@@ -1846,7 +1956,7 @@
continue;
}
}
- bestY = pt.fY;
+ bestY = testY;
bestT = foundT < 1 ? start : end;
hitT = testT;
}
@@ -1855,40 +1965,6 @@
return bestT;
}
- bool crossedSpanHalves(const SkPoint& basePt, bool leftHalf, bool rightHalf) {
- // if a segment is connected to this one, consider it crossing
- int tIndex;
- if (fPts[0].fX == basePt.fX) {
- tIndex = 0;
- do {
- const Span& sSpan = fTs[tIndex];
- const Segment* sOther = sSpan.fOther;
- if (!sOther->fTs[sSpan.fOtherIndex].fWindValue) {
- continue;
- }
- if (leftHalf ? sOther->fBounds.fLeft < basePt.fX
- : sOther->fBounds.fRight > basePt.fX) {
- return true;
- }
- } while (fTs[++tIndex].fT == 0);
- }
- if (fPts[fVerb].fX == basePt.fX) {
- tIndex = fTs.count() - 1;
- do {
- const Span& eSpan = fTs[tIndex];
- const Segment* eOther = eSpan.fOther;
- if (!eOther->fTs[eSpan.fOtherIndex].fWindValue) {
- continue;
- }
- if (leftHalf ? eOther->fBounds.fLeft < basePt.fX
- : eOther->fBounds.fRight > basePt.fX) {
- return true;
- }
- } while (fTs[--tIndex].fT == 1);
- }
- return false;
- }
-
void decrementSpan(Span* span) {
SkASSERT(span->fWindValue > 0);
if (--(span->fWindValue) == 0) {
@@ -1968,7 +2044,11 @@
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
- markDoneBinary(SkMin32(startIndex, endIndex));
+ int min = SkMin32(startIndex, endIndex);
+ if (fTs[min].fDone) {
+ return NULL;
+ }
+ markDoneBinary(min);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
@@ -2113,7 +2193,11 @@
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
- markDone(SkMin32(startIndex, endIndex), outerWinding);
+ int min = SkMin32(startIndex, endIndex);
+ if (fTs[min].fDone) {
+ return NULL;
+ }
+ markDone(min, outerWinding);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
@@ -2279,11 +2363,15 @@
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
- markDone(SkMin32(startIndex, endIndex), 1);
if (isSimple(end)) {
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
+ int min = SkMin32(startIndex, endIndex);
+ if (fTs[min].fDone) {
+ return NULL;
+ }
+ markDone(min, 1);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
@@ -2318,34 +2406,38 @@
buildAngles(end, angles, false);
SkTDArray<Angle*> sorted;
bool sortable = SortAngles(angles, sorted);
+ if (!sortable) {
+ unsortable = true;
+ return NULL;
+ }
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0);
#endif
- if (!sortable) {
- unsortable = true;
- return NULL;
- }
SkASSERT(sorted[firstIndex]->segment() == this);
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const Angle* nextAngle;
Segment* nextSegment;
+ bool foundAngle = false;
do {
if (nextIndex == angleCount) {
nextIndex = 0;
}
nextAngle = sorted[nextIndex];
nextSegment = nextAngle->segment();
- if (!nextSegment->done(nextAngle)) {
+ if (!nextSegment->done(nextAngle) || nextSegment->tiny(nextAngle)) {
+ foundAngle = true;
break;
}
- if (++nextIndex == lastIndex) {
- return NULL;
- }
- } while (true);
+ } while (++nextIndex != lastIndex);
+ markDone(SkMin32(startIndex, endIndex), 1);
+ if (!foundAngle) {
+ nextIndex = firstIndex + 1 == angleCount ? 0 : firstIndex + 1;
+ nextAngle = sorted[nextIndex];
+ }
nextStart = nextAngle->start();
nextEnd = nextAngle->end();
return nextSegment;
@@ -2503,7 +2595,7 @@
// OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
// and use more concise logic like the old edge walker code?
// FIXME: this needs to deal with coincident edges
- Segment* findTop(int& tIndex, int& endIndex) {
+ Segment* findTop(int& tIndex, int& endIndex, bool& unsortable, bool onlySortable) {
// iterate through T intersections and return topmost
// topmost tangent from y-min to first pt is closer to horizontal
SkASSERT(!done());
@@ -2516,7 +2608,7 @@
bool lastUnsortable = false;
for (int index = 0; index < count; ++index) {
const Span& span = fTs[index];
- if (span.fUnsortableStart | lastUnsortable) {
+ if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
goto next;
}
if (!span.fDone | !lastDone) {
@@ -2551,7 +2643,8 @@
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
#endif
- if (!sortable) {
+ if (onlySortable && !sortable) {
+ unsortable = true;
return NULL;
}
// skip edges that have already been processed
@@ -2559,11 +2652,12 @@
Segment* leftSegment;
do {
const Angle* angle = sorted[++firstT];
- SkASSERT(!angle->unsortable());
+ SkASSERT(!onlySortable || !angle->unsortable());
leftSegment = angle->segment();
tIndex = angle->end();
endIndex = angle->start();
} while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone);
+ SkASSERT(!leftSegment->fTs[SkMin32(tIndex, endIndex)].fTiny);
return leftSegment;
}
@@ -2716,6 +2810,9 @@
Span* last;
Segment* other = this;
while ((other = other->nextChase(index, step, min, last))) {
+ if (other->done()) {
+ return NULL;
+ }
other->markDoneBinary(min);
}
return last;
@@ -3070,6 +3167,11 @@
return fTs[tIndex].fOppValue;
}
+ int oppValue(const Angle* angle) const {
+ int lesser = SkMin32(angle->start(), angle->end());
+ return fTs[lesser].fOppValue;
+ }
+
const SkPoint* pts() const {
return fPts;
}
@@ -3775,8 +3877,41 @@
fContainsIntercepts = true;
}
- const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY,
- int &tIndex, double& hitT) {
+ const Segment* crossedSegmentX(const SkPoint& basePt, SkScalar& bestX,
+ int &tIndex, double& hitT, bool opp) {
+ 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.fRight <= bestX) {
+ continue;
+ }
+ if (bounds.fLeft >= basePt.fX) {
+ continue;
+ }
+ if (bounds.fTop > basePt.fY) {
+ continue;
+ }
+ if (bounds.fBottom < basePt.fY) {
+ continue;
+ }
+ if (bounds.fTop == bounds.fBottom) {
+ continue;
+ }
+ double testHitT;
+ int testT = testSegment->crossedSpanX(basePt, bestX, testHitT, opp);
+ if (testT >= 0) {
+ bestSegment = testSegment;
+ tIndex = testT;
+ hitT = testHitT;
+ }
+ }
+ return bestSegment;
+ }
+
+ const Segment* crossedSegmentY(const SkPoint& basePt, SkScalar& bestY,
+ int &tIndex, double& hitT, bool opp) {
int segmentCount = fSegments.count();
const Segment* bestSegment = NULL;
for (int test = 0; test < segmentCount; ++test) {
@@ -3797,16 +3932,8 @@
if (bounds.fLeft == bounds.fRight) {
continue;
}
- #if 0
- bool leftHalf = bounds.fLeft == basePt.fX;
- bool rightHalf = bounds.fRight == basePt.fX;
- if ((leftHalf || rightHalf) && !testSegment->crossedSpanHalves(
- basePt, leftHalf, rightHalf)) {
- continue;
- }
- #endif
double testHitT;
- int testT = testSegment->crossedSpan(basePt, bestY, testHitT);
+ int testT = testSegment->crossedSpanY(basePt, bestY, testHitT, opp);
if (testT >= 0) {
bestSegment = testSegment;
tIndex = testT;
@@ -4023,7 +4150,8 @@
}
#endif
- Segment* topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY) {
+ // FIXME: get rid of allowTies logic if we don't need it
+ Segment* topSortableSegment(const SkPoint& topLeft, SkPoint& bestXY, bool allowTies) {
int segmentCount = fSortedSegments.count();
SkASSERT(segmentCount > 0);
Segment* bestSegment = NULL;
@@ -4041,7 +4169,8 @@
if (testXY.fY < topLeft.fY) {
continue;
}
- if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
+ if (testXY.fY == topLeft.fY && ( /* allowTies ? testXY.fX < topLeft.fX : */
+ testXY.fX <= topLeft.fX)) {
continue;
}
if (bestXY.fY < testXY.fY) {
@@ -4830,6 +4959,118 @@
}
}
+static int contourRangeCheckX(SkTDArray<Contour*>& contourList, double mid,
+ const Segment* current, int index, int endIndex, bool opp) {
+ const SkPoint& basePt = current->xyAtT(endIndex);
+ int contourCount = contourList.count();
+ SkScalar bestX = SK_ScalarMin;
+ const Segment* test = NULL;
+ int tIndex;
+ double tHit;
+ bool crossOpp;
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ Contour* contour = contourList[cTest];
+ bool testOpp = contour->operand() ^ current->operand() ^ opp;
+ if (basePt.fX < contour->bounds().fLeft) {
+ continue;
+ }
+ if (bestX > contour->bounds().fRight) {
+ continue;
+ }
+ const Segment* next = contour->crossedSegmentX(basePt, bestX, tIndex, tHit, testOpp);
+ if (next) {
+ test = next;
+ crossOpp = testOpp;
+ }
+ }
+ if (!test) {
+ return 0;
+ }
+ if (approximately_zero(tHit - test->t(tIndex))) { // if we hit the end of a span, disregard
+ return SK_MinS32;
+ }
+ int winding = crossOpp ? test->oppSum(tIndex) : test->windSum(tIndex);
+ SkASSERT(winding != SK_MinS32);
+ int windValue = crossOpp ? test->oppValue(tIndex) : test->windValue(tIndex);
+#if DEBUG_WINDING
+ SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
+ windValue);
+#endif
+ // see if a + change in T results in a +/- change in X (compute x'(T))
+ SkScalar dy = (*SegmentDYAtT[test->verb()])(test->pts(), tHit);
+ if (test->verb() > SkPath::kLine_Verb && approximately_zero(dy)) {
+ const SkPoint* pts = test->pts();
+ dy = pts[2].fY - pts[1].fY - dy;
+ }
+#if DEBUG_WINDING
+ SkDebugf("%s dy=%1.9g\n", __FUNCTION__, dy);
+#endif
+ SkASSERT(dy != 0);
+ if (winding * dy > 0) { // if same signs, result is negative
+ winding += dy > 0 ? -windValue : windValue;
+#if DEBUG_WINDING
+ SkDebugf("%s final winding=%d\n", __FUNCTION__, winding);
+#endif
+ }
+ return winding;
+}
+
+static int contourRangeCheckY(SkTDArray<Contour*>& contourList, double mid,
+ const Segment* current, int index, int endIndex, bool opp) {
+ const SkPoint& basePt = current->xyAtT(endIndex);
+ int contourCount = contourList.count();
+ SkScalar bestY = SK_ScalarMin;
+ const Segment* test = NULL;
+ int tIndex;
+ double tHit;
+ bool crossOpp;
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ Contour* contour = contourList[cTest];
+ bool testOpp = contour->operand() ^ current->operand() ^ opp;
+ if (basePt.fY < contour->bounds().fTop) {
+ continue;
+ }
+ if (bestY > contour->bounds().fBottom) {
+ continue;
+ }
+ const Segment* next = contour->crossedSegmentY(basePt, bestY, tIndex, tHit, testOpp);
+ if (next) {
+ test = next;
+ crossOpp = testOpp;
+ }
+ }
+ if (!test) {
+ return 0;
+ }
+ if (approximately_zero(tHit - test->t(tIndex))) { // if we hit the end of a span, disregard
+ return SK_MinS32;
+ }
+ int winding = crossOpp ? test->oppSum(tIndex) : test->windSum(tIndex);
+ SkASSERT(winding != SK_MinS32);
+ int windValue = crossOpp ? test->oppValue(tIndex) : test->windValue(tIndex);
+#if DEBUG_WINDING
+ SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
+ windValue);
+#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 (test->verb() > SkPath::kLine_Verb && approximately_zero(dx)) {
+ const SkPoint* pts = test->pts();
+ dx = pts[2].fX - pts[1].fX - dx;
+ }
+#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 ? -windValue : windValue;
+#if DEBUG_WINDING
+ SkDebugf("%s final winding=%d\n", __FUNCTION__, winding);
+#endif
+ }
+ return 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.
@@ -4842,20 +5083,20 @@
const Segment* test = NULL;
int tIndex;
double tHit;
+ bool crossOpp;
for (int cTest = 0; cTest < contourCount; ++cTest) {
Contour* contour = contourList[cTest];
- if ((contour->operand() ^ current->operand()) != opp) {
- continue;
- }
+ bool testOpp = contour->operand() ^ current->operand() ^ opp;
if (basePt.fY < contour->bounds().fTop) {
continue;
}
if (bestY > contour->bounds().fBottom) {
continue;
}
- const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit);
+ const Segment* next = contour->crossedSegmentY(basePt, bestY, tIndex, tHit, testOpp);
if (next) {
test = next;
+ crossOpp = testOpp;
}
}
if (!test) {
@@ -4878,7 +5119,7 @@
#if DEBUG_SORT
SkDebugf("%s early return\n", __FUNCTION__);
#endif
- return 0;
+ return SK_MinS32;
}
test->buildAngles(tIndex, angles, false);
SkTDArray<Angle*> sorted;
@@ -4886,7 +5127,10 @@
// returns the first counterclockwise hour before 6 o'clock,
// or if the base point is rightmost, returns the first clockwise
// hour after 6 o'clock
- (void) Segment::SortAngles(angles, sorted);
+ bool sortable = Segment::SortAngles(angles, sorted);
+ if (!sortable) {
+ return SK_MinS32;
+ }
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
#endif
@@ -4932,10 +5176,21 @@
mid = index;
}
}
+ if ((left < 0 || right < 0) && mid >= 0) {
+ angle = sorted[mid];
+ Segment* midSeg = angle->segment();
+ int end = angle->end();
+ if (midSeg->unsortable(end)) {
+ return SK_MinS32;
+ }
+ }
if (left < 0 && right < 0) {
left = mid;
}
- SkASSERT(left >= 0 || right >= 0);
+ if (left < 0 && right < 0) {
+ SkASSERT(0);
+ return SK_MinS32; // unsortable
+ }
if (left < 0) {
left = right;
} else if (left >= 0 && mid >= 0 && right >= 0
@@ -4944,17 +5199,19 @@
}
angle = sorted[left];
test = angle->segment();
- winding = test->windSum(angle);
+ winding = crossOpp ? test->oppSum(angle) : test->windSum(angle);
SkASSERT(winding != SK_MinS32);
- windValue = test->windValue(angle);
+ windValue = crossOpp ? test->oppValue(angle) : test->windValue(angle);
#if DEBUG_WINDING
SkDebugf("%s angle winding=%d windValue=%d sign=%d\n", __FUNCTION__, winding,
windValue, angle->sign());
#endif
} else {
- winding = test->windSum(tIndex);
- SkASSERT(winding != SK_MinS32);
- windValue = test->windValue(tIndex);
+ winding = crossOpp ? test->oppSum(tIndex) : test->windSum(tIndex);
+ if (winding == SK_MinS32) {
+ return SK_MinS32; // unsortable
+ }
+ windValue = crossOpp ? test->oppValue(tIndex) : test->windValue(tIndex);
#if DEBUG_WINDING
SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding,
windValue);
@@ -5115,7 +5372,7 @@
}
static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
- int& endIndex, SkPoint& topLeft) {
+ int& endIndex, SkPoint& topLeft, bool& unsortable, bool allowTies, bool onlySortable) {
Segment* result;
do {
SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
@@ -5130,7 +5387,7 @@
if (bounds.fBottom == topLeft.fY && bounds.fRight < topLeft.fX) {
continue;
}
- Segment* test = contour->topSortableSegment(topLeft, bestXY);
+ Segment* test = contour->topSortableSegment(topLeft, bestXY, allowTies);
if (test) {
topStart = test;
}
@@ -5139,7 +5396,7 @@
return NULL;
}
topLeft = bestXY;
- result = topStart->findTop(index, endIndex);
+ result = topStart->findTop(index, endIndex, unsortable, onlySortable);
} while (!result);
return result;
}
@@ -5163,6 +5420,87 @@
return winding;
}
+static Segment* findSortableTopOld(SkTDArray<Contour*>& contourList, bool& firstContour, int& index,
+ int& endIndex, SkPoint& topLeft, int& contourWinding, bool& unsortable) {
+ Segment* current;
+ bool allowTies = true;
+ do {
+ current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, allowTies,
+ true);
+ if (!current) {
+ break;
+ }
+ if (firstContour) {
+ contourWinding = 0;
+ firstContour = false;
+ break;
+ }
+ int sumWinding = current->windSum(SkMin32(index, endIndex));
+ // FIXME: don't I have to adjust windSum to get contourWinding?
+ if (sumWinding == SK_MinS32) {
+ sumWinding = current->computeSum(index, endIndex, false);
+ }
+ if (sumWinding == SK_MinS32) {
+ contourWinding = innerContourCheck(contourList, current, index, endIndex, false);
+ allowTies = false;
+ } else {
+ contourWinding = sumWinding;
+ int spanWinding = current->spanSign(index, endIndex);
+ bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding);
+ if (inner) {
+ contourWinding -= spanWinding;
+ }
+#if DEBUG_WINDING
+ SkDebugf("%s sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n",
+ __FUNCTION__, sumWinding, spanWinding, SkSign32(index - endIndex),
+ inner, contourWinding);
+#endif
+ }
+ } while (contourWinding == SK_MinS32);
+ if (contourWinding != SK_MinS32) {
+#if DEBUG_WINDING
+ SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
+#endif
+ return current;
+ }
+ // the simple upward projection of the unresolved points hit unsortable angles
+ // shoot rays at right angles to the segment to find its winding, ignoring angle cases
+ topLeft.fX = topLeft.fY = SK_ScalarMin;
+ do {
+ current = findSortableTop(contourList, index, endIndex, topLeft, unsortable, allowTies,
+ false);
+ SkASSERT(current); // FIXME: return to caller that path cannot be simplified (yet)
+ // find bounds
+ Bounds bounds;
+ bounds.setPoint(current->xyAtT(index));
+ bounds.add(current->xyAtT(endIndex));
+ SkScalar width = bounds.width();
+ SkScalar height = bounds.height();
+ int (*rangeChecker)(SkTDArray<Contour*>& contourList, double mid,
+ const Segment* current, int index, int endIndex, bool opp);
+ if (width > height) {
+ if (approximately_negative(width)) {
+ continue; // edge is too small to resolve meaningfully
+ }
+ rangeChecker = contourRangeCheckY;
+ } else {
+ if (approximately_negative(height)) {
+ continue; // edge is too small to resolve meaningfully
+ }
+ rangeChecker = contourRangeCheckX;
+ }
+ double test = 1;
+ do {
+ contourWinding = (*rangeChecker)(contourList, test, current, index, endIndex, false);
+ if (contourWinding != SK_MinS32) {
+ return current;
+ }
+ test /= 2;
+ } while (!approximately_negative(test));
+ } while (true);
+ return current;
+}
+
// Each segment may have an inside or an outside. Segments contained within
// winding may have insides on either side, and form a contour that should be
// ignored. Segments that are coincident with opposing direction segments may
@@ -5176,44 +5514,25 @@
static bool bridgeWinding(SkTDArray<Contour*>& contourList, PathWrapper& simple) {
bool firstContour = true;
bool unsortable = false;
+ bool topUnsortable = false;
+ bool firstRetry = false;
bool closable = true;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
int index, endIndex;
// iterates while top is unsortable
- Segment* current = findSortableTop(contourList, index, endIndex, topLeft);
- if (!current) {
- break;
- }
int contourWinding;
- if (firstContour) {
- contourWinding = 0;
- firstContour = false;
- } else {
- int sumWinding = current->windSum(SkMin32(index, endIndex));
- // FIXME: don't I have to adjust windSum to get contourWinding?
- if (sumWinding == SK_MinS32) {
- sumWinding = current->computeSum(index, endIndex, false);
+ Segment* current = findSortableTopOld(contourList, firstContour, index, endIndex, topLeft,
+ contourWinding, topUnsortable);
+ if (!current) {
+ if (topUnsortable) {
+ topUnsortable = false;
+ SkASSERT(!firstRetry);
+ firstRetry = true;
+ topLeft.fX = topLeft.fY = SK_ScalarMin;
+ continue;
}
- if (sumWinding == SK_MinS32) {
- contourWinding = innerContourCheck(contourList, current,
- index, endIndex, false);
- } else {
- contourWinding = sumWinding;
- int spanWinding = current->spanSign(index, endIndex);
- bool inner = useInnerWinding(sumWinding - spanWinding, sumWinding);
- if (inner) {
- contourWinding -= spanWinding;
- }
-#if DEBUG_WINDING
- SkDebugf("%s sumWinding=%d spanWinding=%d sign=%d inner=%d result=%d\n",
- __FUNCTION__, sumWinding, spanWinding, SkSign32(index - endIndex),
- inner, contourWinding);
-#endif
- }
-#if DEBUG_WINDING
- SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
-#endif
+ break;
}
int winding = contourWinding;
int spanWinding = current->spanSign(index, endIndex);
@@ -5246,6 +5565,11 @@
}
break;
}
+ #if DEBUG_FLOW
+ SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
+ current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
+ current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
+ #endif
current->addCurveTo(index, endIndex, simple, active);
current = next;
index = nextStart;
@@ -5258,8 +5582,7 @@
int min = SkMin32(index, endIndex);
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
- current->markDone(SkMin32(index, endIndex),
- winding ? winding : spanWinding);
+ current->markDone(min, winding ? winding : spanWinding);
}
closable = false;
}
@@ -5283,6 +5606,7 @@
Segment* current;
int start, end;
bool unsortable = false;
+ bool closable = true;
while ((current = findUndone(contourList, start, end))) {
do {
SkASSERT(unsortable || !current->done());
@@ -5290,7 +5614,7 @@
int nextEnd = end;
Segment* next = current->findNextXor(nextStart, nextEnd, unsortable);
if (!next) {
- if (simple.hasMove()
+ if (!unsortable && simple.hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple.isClosed()) {
current->addCurveTo(start, end, simple, true);
@@ -5298,20 +5622,31 @@
}
break;
}
+ #if DEBUG_FLOW
+ SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
+ current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
+ current->xyAtT(end).fX, current->xyAtT(end).fY);
+ #endif
current->addCurveTo(start, end, simple, true);
current = next;
start = nextStart;
end = nextEnd;
- } while (!simple.isClosed());
- // FIXME: add unsortable test
- if (simple.hasMove()) {
- simple.close();
+ } while (!simple.isClosed() && (!unsortable || !current->done()));
+ if (!simple.isClosed()) {
+ SkASSERT(unsortable);
+ int min = SkMin32(start, end);
+ if (!current->done(min)) {
+ current->addCurveTo(start, end, simple, true);
+ current->markDone(min, 1);
+ }
+ closable = false;
}
+ simple.close();
#if DEBUG_ACTIVE_SPANS
debugShowActiveSpans(contourList);
#endif
}
- return !unsortable;
+ return closable;
}
static void fixOtherTIndex(SkTDArray<Contour*>& contourList) {
@@ -5369,6 +5704,16 @@
const Contour& eContour = contours[outer];
const SkPoint& eStart = eContour.start();
const SkPoint& eEnd = eContour.end();
+#if DEBUG_ASSEMBLE
+ SkDebugf("%s contour", __FUNCTION__);
+ if (!approximatelyEqual(eStart, eEnd)) {
+ SkDebugf("[%d]", runs.count());
+ } else {
+ SkDebugf(" ");
+ }
+ SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
+ eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
+#endif
if (approximatelyEqual(eStart, eEnd)) {
eContour.toPath(simple);
continue;
@@ -5412,60 +5757,72 @@
double dx = iStart.fX - oStart.fX;
double dy = iStart.fY - oStart.fY;
double dist = dx * dx + dy * dy;
- if (bestStartDist > dist) {
- bestStartDist = dist;
+ if (bestStartDist > dist && sBest[iIndex] > dist) {
+ sBest[iIndex] = bestStartDist = dist;
sLink[rIndex] = ~iIndex;
sLink[iIndex] = ~rIndex;
}
dx = iEnd.fX - oStart.fX;
dy = iEnd.fY - oStart.fY;
dist = dx * dx + dy * dy;
- if (bestStartDist > dist) {
- bestStartDist = dist;
+ if (bestStartDist > dist && eBest[iIndex] > dist) {
+ eBest[iIndex] = bestStartDist = dist;
sLink[rIndex] = iIndex;
eLink[iIndex] = rIndex;
}
dx = iStart.fX - oEnd.fX;
dy = iStart.fY - oEnd.fY;
dist = dx * dx + dy * dy;
- if (bestEndDist > dist) {
- bestEndDist = dist;
+ if (bestEndDist > dist && sBest[iIndex] > dist) {
+ sBest[iIndex] = bestEndDist = dist;
sLink[iIndex] = rIndex;
eLink[rIndex] = iIndex;
}
dx = iEnd.fX - oEnd.fX;
dy = iEnd.fY - oEnd.fY;
dist = dx * dx + dy * dy;
- if (bestEndDist > dist) {
- bestEndDist = dist;
+ if (bestEndDist > dist && eBest[iIndex] > dist) {
+ eBest[iIndex] = bestEndDist = dist;
eLink[iIndex] = ~rIndex;
eLink[rIndex] = ~iIndex;
}
}
}
- rIndex = 0;
- bool forward = true;
- bool first = true;
- const SkPoint* startPtr;
- int sIndex = sLink[rIndex];
- SkASSERT(sIndex != INT_MAX);
- sLink[rIndex] = INT_MAX;
- int eIndex;
- if (sIndex < 0) {
- eIndex = sLink[~sIndex];
- sLink[~sIndex] = INT_MAX;
- } else {
- eIndex = eLink[sIndex];
- eLink[sIndex] = INT_MAX;
+#if DEBUG_ASSEMBLE
+ for (rIndex = 0; rIndex < count; ++rIndex) {
+ int s = sLink[rIndex];
+ int e = eLink[rIndex];
+ SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
+ s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
}
- SkASSERT(eIndex != INT_MAX);
+#endif
+ rIndex = 0;
do {
+ bool forward = true;
+ bool first = true;
+ int sIndex = sLink[rIndex];
+ SkASSERT(sIndex != INT_MAX);
+ sLink[rIndex] = INT_MAX;
+ int eIndex;
+ if (sIndex < 0) {
+ eIndex = sLink[~sIndex];
+ sLink[~sIndex] = INT_MAX;
+ } else {
+ eIndex = eLink[sIndex];
+ eLink[sIndex] = INT_MAX;
+ }
+ SkASSERT(eIndex != INT_MAX);
+#if DEBUG_ASSEMBLE
+ SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
+ sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
+ eIndex < 0 ? ~eIndex : eIndex);
+#endif
do {
outer = runs[rIndex];
const Contour& contour = contours[outer];
if (first) {
- startPtr = &contour.start();
first = false;
+ const SkPoint* startPtr = &contour.start();
simple.deferredMove(startPtr[0]);
}
if (forward) {
@@ -5473,9 +5830,13 @@
} else {
contour.toPartialBackward(simple);
}
- if (sIndex == eIndex) {
+#if DEBUG_ASSEMBLE
+ SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
+ eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
+ sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
+#endif
+ if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
simple.close();
- first = forward = true;
break;
}
if (forward) {
@@ -5513,7 +5874,12 @@
}
}
} while (rIndex < count);
- SkASSERT(first);
+#if DEBUG_ASSEMBLE
+ for (rIndex = 0; rIndex < count; ++rIndex) {
+ SkASSERT(sLink[rIndex] == INT_MAX);
+ SkASSERT(eLink[rIndex] == INT_MAX);
+ }
+#endif
}
void simplifyx(const SkPath& path, SkPath& result) {
diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp
index 3abcee1..057687c 100644
--- a/experimental/Intersection/SimplifyFindTop_Test.cpp
+++ b/experimental/Intersection/SimplifyFindTop_Test.cpp
@@ -33,8 +33,9 @@
end);
#else
SkPoint bestXY = {SK_ScalarMin, SK_ScalarMin};
+ bool unsortable = false;
const SimplifyFindTopTest::Segment* topSegment =
- findSortableTop(contourList, index, end, bestXY);
+ findSortableTop(contourList, index, end, bestXY, unsortable, true, true);
#endif
return topSegment;
}
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 40b79fb..3f17b1f 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2261,11 +2261,19 @@
testSimplifyx(path);
}
+static void testLine1a() {
+ SkPath path;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 12, 12, SkPath::kCW_Direction);
+ path.addRect(4, 0, 13, 13, SkPath::kCCW_Direction);
+ testSimplifyx(path);
+}
+
static void testLine1ax() {
SkPath path;
path.setFillType(SkPath::kEvenOdd_FillType);
path.addRect(0, 0, 12, 12, SkPath::kCW_Direction);
- path.addRect(4, 0, 13, 13, SkPath::kCW_Direction);
+ path.addRect(4, 0, 13, 13, SkPath::kCCW_Direction);
testSimplifyx(path);
}
@@ -2884,12 +2892,214 @@
testSimplifyx(path);
}
-static void (*firstTest)() = testLine79x;
+static void testQuadratic59x() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(2, 0);
+ path.quadTo(3, 1, 1, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic59() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(2, 0);
+ path.quadTo(3, 1, 1, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic63() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 1);
+ path.quadTo(2, 1, 2, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic64() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(1, 2);
+ path.lineTo(2, 2);
+ path.quadTo(0, 3, 3, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic65() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(2, 1);
+ path.lineTo(2, 2);
+ path.quadTo(0, 3, 1, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic67x() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 2, 1);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(2, 0);
+ path.quadTo(1, 1, 3, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic68() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 1, 2, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic69() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(1, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic70x() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 1, 2, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic71() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 1, 3, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic72() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic73() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 3);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic74() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 3);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testQuadratic75() {
+ SkPath path, pathB;
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic75;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic75),
+ TEST(testQuadratic74),
+ TEST(testQuadratic73),
+ TEST(testQuadratic72),
+ TEST(testQuadratic71),
+ TEST(testQuadratic70x),
+ TEST(testQuadratic69),
+ TEST(testQuadratic68),
+ TEST(testQuadratic67x),
+ TEST(testQuadratic65),
+ TEST(testQuadratic64),
+ TEST(testQuadratic63),
+ TEST(testLine1a),
+ TEST(testLine1ax),
+ TEST(testQuadratic59),
+ TEST(testQuadratic59x),
TEST(testQuadratic58),
TEST(testQuadratic56),
TEST(testQuadratic55),
@@ -3304,6 +3514,17 @@
testShapeOp(path, pathB, kDifference_Op);
}
+static void testOp2u() {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ path.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 3, 3, SkPath::kCW_Direction);
+ pathB.addRect(1, 1, 2, 2, SkPath::kCW_Direction);
+ testShapeOp(path, pathB, kUnion_Op);
+}
+
static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
static struct {
@@ -3326,11 +3547,12 @@
TEST(testOp5d),
TEST(testOp6d),
TEST(testOp7d),
+ TEST(testOp2u),
};
static const size_t subTestCount = sizeof(subTests) / sizeof(subTests[0]);
-static void (*firstBinaryTest)() = testOp2d;
+static void (*firstBinaryTest)() = 0;
static bool skipAll = false;
static bool runBinaryTestsFirst = false;
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index f2de8d2..e251a8e 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -2840,11 +2840,189 @@
path.close();
</div>
+<div id="testQuadratic62x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(2, 0);
+ path.quadTo(3, 1, 1, 2);
+ path.close();
+</div>
+
+<div id="testLine1a">
+ path.addRect(0, 0, 12, 12, SkPath::kCW_Direction);
+ path.addRect(4, 0, 13, 13, SkPath::kCCW_Direction);
+ path.close();
+</div>
+
+<div id="testQuadratic63">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(2, 1);
+ path.quadTo(2, 1, 2, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic64">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(1, 2);
+ path.lineTo(2, 2);
+ path.quadTo(0, 3, 3, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic65">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 0);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(2, 1);
+ path.lineTo(2, 2);
+ path.quadTo(0, 3, 1, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic66">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(1, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic67x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 2, 1);
+ path.lineTo(2, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(2, 0);
+ path.quadTo(1, 1, 3, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic68">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 1, 2, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic69">
+ path.moveTo(0, 0);
+ path.quadTo(0, 0, 0, 1);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(2, 0);
+ path.lineTo(1, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic70x">
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 1);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(0, 1, 2, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic71">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 1);
+ path.lineTo(3, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 0);
+ path.quadTo(1, 1, 3, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic72">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 2);
+ path.lineTo(1, 2);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.close();
+</div>
+
+<div id="testQuadratic73">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 0, 3);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 0);
+ path.quadTo(0, 1, 1, 1);
+ path.close();
+</div>
+
+<div id="testQuadratic74">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 3);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+</div>
+
+<div id="testQuadratic75">
+ path.moveTo(0, 0);
+ path.quadTo(1, 0, 1, 3);
+ path.lineTo(2, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(0, 1);
+ path.quadTo(3, 2, 2, 3);
+ path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic75,
+ testQuadratic74,
+ testQuadratic73,
+ testQuadratic72,
+ testQuadratic71,
+ testQuadratic70x,
+ testQuadratic69,
+ testQuadratic68,
+ testQuadratic67x,
+ testQuadratic66,
+ testQuadratic65,
+ testQuadratic64,
+ testQuadratic63,
+ testLine1a,
+ testQuadratic62x,
testLine81,
testQuadratic61,
testQuadratic60,