shape ops work in progress
refined line/quad intersection, made more robust
still working on edge cases
git-svn-id: http://skia.googlecode.com/svn/trunk@6017 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/EdgeDemo.cpp b/experimental/Intersection/EdgeDemo.cpp
index 973b981..1d2c2b8 100644
--- a/experimental/Intersection/EdgeDemo.cpp
+++ b/experimental/Intersection/EdgeDemo.cpp
@@ -233,9 +233,9 @@
SkScalar cellWidth = overall.width() / divs * 2;
SkScalar cellHeight = overall.height() / divs * 2;
SkRect target;
- if (true) {
- int xDiv = 28;
- int yDiv = 17;
+ if (1) {
+ int xDiv = 27;
+ int yDiv = 11;
target.setXYWH(overall.fLeft + (overall.width() - cellWidth) * xDiv / divs,
overall.fTop + (overall.height() - cellHeight) * yDiv / divs,
cellWidth, cellHeight);
diff --git a/experimental/Intersection/EdgeDemoApp.mm b/experimental/Intersection/EdgeDemoApp.mm
index b65a295..8acc283 100644
--- a/experimental/Intersection/EdgeDemoApp.mm
+++ b/experimental/Intersection/EdgeDemoApp.mm
@@ -16,9 +16,9 @@
};
protected:
virtual void onDraw(SkCanvas* canvas) {
- static int step = 0; // 12752; // 17908 ; // 17904; // drawLetters first error
+ static int step = 0; // 17909 ; // drawLetters first error
// drawStars triggers error at 23275
- // error is not easy to debug in its current state
+ // drawStars error not easy to debug last time I checked
static double seconds;
if (step == -1) {
timeval t;
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 8a8cb30..c379fb2 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -15,14 +15,14 @@
void Intersection_Tests() {
int testsRun = 0;
SimplifyNew_Test();
- QuadraticIntersection_Test();
+ LineQuadraticIntersection_Test();
MiniSimplify_Test();
+ QuadraticIntersection_Test();
SimplifyAngle_Test();
QuarticRoot_Test();
// QuadraticIntersection_Test();
Simplify4x4QuadraticsThreaded_Test(testsRun);
QuadLineIntersectThreaded_Test(testsRun);
- LineQuadraticIntersection_Test();
Simplify4x4RectsThreaded_Test(testsRun);
SimplifyNondegenerate4x4TrianglesThreaded_Test(testsRun);
SimplifyDegenerate4x4TrianglesThreaded_Test(testsRun);
diff --git a/experimental/Intersection/Intersections.h b/experimental/Intersection/Intersections.h
index c1421e3..fe12b25 100644
--- a/experimental/Intersection/Intersections.h
+++ b/experimental/Intersection/Intersections.h
@@ -143,6 +143,8 @@
++fUsed;
}
+ // FIXME: all callers should be moved to regular insert. Failures are likely
+ // if two separate callers differ on whether ts are equal or not
void insertOne(double t, int side) {
int used = side ? fUsed2 : fUsed;
assert(used <= 1 || fT[side][0] < fT[side][1]);
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index f730250..b3303cf 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -88,7 +88,7 @@
*/
-class LineQuadraticIntersections : public Intersections {
+class LineQuadraticIntersections {
public:
LineQuadraticIntersections(const Quadratic& q, const _Line& l, Intersections& i)
@@ -97,7 +97,7 @@
, intersections(i) {
}
-int intersectRay() {
+int intersectRay(double roots[2]) {
/*
solve by rotating line+quad so line is horizontal, then finding the roots
set up matrix to rotate quad to x-axis
@@ -124,77 +124,128 @@
double C = r[0];
A += C - 2 * B; // A = a - 2*b + c
B -= C; // B = -(b - c)
- return quadraticRoots(A, B, C, intersections.fT[0]);
+ return quadraticRoots(A, B, C, roots);
}
int intersect() {
- int roots = intersectRay();
- for (int index = 0; index < roots; ) {
- double lineT = findLineT(intersections.fT[0][index]);
- if (lineIntersects(lineT, index, roots)) {
- ++index;
+ addEndPoints();
+ double rootVals[2];
+ int roots = intersectRay(rootVals);
+ for (int index = 0; index < roots; ++index) {
+ double quadT = rootVals[index];
+ double lineT = findLineT(quadT);
+ if (pinTs(quadT, lineT)) {
+ intersections.insert(quadT, lineT);
}
}
- return roots;
+ return intersections.fUsed;
}
-int horizontalIntersect(double axisIntercept) {
+int horizontalIntersect(double axisIntercept, double roots[2]) {
double D = quad[2].y; // f
double E = quad[1].y; // e
double F = quad[0].y; // d
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
- return quadraticRoots(D, E, F, intersections.fT[0]);
+ return quadraticRoots(D, E, F, roots);
}
-int horizontalIntersect(double axisIntercept, double left, double right) {
- int roots = horizontalIntersect(axisIntercept);
- for (int index = 0; index < roots; ) {
+int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
+ addHorizontalEndPoints(left, right, axisIntercept);
+ double rootVals[2];
+ int roots = horizontalIntersect(axisIntercept, rootVals);
+ for (int index = 0; index < roots; ++index) {
double x;
- xy_at_t(quad, intersections.fT[0][index], x, *(double*) NULL);
+ double quadT = rootVals[index];
+ xy_at_t(quad, quadT, x, *(double*) NULL);
double lineT = (x - left) / (right - left);
- if (lineIntersects(lineT, index, roots)) {
- ++index;
+ if (pinTs(quadT, lineT)) {
+ intersections.insert(quadT, lineT);
}
}
- return roots;
+ if (flipped) {
+ flip();
+ }
+ return intersections.fUsed;
}
-int verticalIntersect(double axisIntercept) {
+int verticalIntersect(double axisIntercept, double roots[2]) {
double D = quad[2].x; // f
double E = quad[1].x; // e
double F = quad[0].x; // d
D += F - 2 * E; // D = d - 2*e + f
E -= F; // E = -(d - e)
F -= axisIntercept;
- return quadraticRoots(D, E, F, intersections.fT[0]);
+ return quadraticRoots(D, E, F, roots);
}
-int verticalIntersect(double axisIntercept, double top, double bottom) {
- int roots = verticalIntersect(axisIntercept);
- for (int index = 0; index < roots; ) {
+int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
+ addVerticalEndPoints(top, bottom, axisIntercept);
+ double rootVals[2];
+ int roots = verticalIntersect(axisIntercept, rootVals);
+ for (int index = 0; index < roots; ++index) {
double y;
- xy_at_t(quad, intersections.fT[0][index], *(double*) NULL, y);
+ double quadT = rootVals[index];
+ xy_at_t(quad, quadT, *(double*) NULL, y);
double lineT = (y - top) / (bottom - top);
- if (lineIntersects(lineT, index, roots)) {
- ++index;
+ if (pinTs(quadT, lineT)) {
+ intersections.insert(quadT, lineT);
}
}
- return roots;
+ if (flipped) {
+ flip();
+ }
+ return intersections.fUsed;
}
protected:
+// add endpoints first to get zero and one t values exactly
+void addEndPoints()
+{
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ for (int lIndex = 0; lIndex < 2; lIndex++) {
+ if (quad[qIndex] == line[lIndex]) {
+ intersections.insert(qIndex >> 1, lIndex);
+ }
+ }
+ }
+}
+
+void addHorizontalEndPoints(double left, double right, double y)
+{
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ if (quad[qIndex].y != y) {
+ continue;
+ }
+ if (quad[qIndex].x == left) {
+ intersections.insert(qIndex >> 1, 0);
+ }
+ if (quad[qIndex].x == right) {
+ intersections.insert(qIndex >> 1, 1);
+ }
+ }
+}
+
+void addVerticalEndPoints(double top, double bottom, double x)
+{
+ for (int qIndex = 0; qIndex < 3; qIndex += 2) {
+ if (quad[qIndex].x != x) {
+ continue;
+ }
+ if (quad[qIndex].y == top) {
+ intersections.insert(qIndex >> 1, 0);
+ }
+ if (quad[qIndex].y == bottom) {
+ intersections.insert(qIndex >> 1, 1);
+ }
+ }
+}
+
double findLineT(double t) {
double x, y;
xy_at_t(quad, t, x, y);
- if (approximately_equal(x, line[0].x) && approximately_equal(y, line[0].y)) {
- return 0;
- }
- if (approximately_equal(x, line[1].x) && approximately_equal(y, line[1].y)) {
- return 1;
- }
double dx = line[1].x - line[0].x;
double dy = line[1].y - line[0].y;
if (fabs(dx) > fabs(dy)) {
@@ -203,19 +254,31 @@
return (y - line[0].y) / dy;
}
-bool lineIntersects(double lineT, const int x, int& roots) {
- if (!approximately_zero_or_more(lineT) || !approximately_one_or_less(lineT)) {
- if (x < --roots) {
- intersections.fT[0][x] = intersections.fT[0][roots];
- }
+void flip() {
+ // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
+ int roots = intersections.fUsed;
+ for (int index = 0; index < roots; ++index) {
+ intersections.fT[1][index] = 1 - intersections.fT[1][index];
+ }
+}
+
+bool pinTs(double& quadT, double& lineT) {
+ if (!approximately_one_or_less(lineT)) {
return false;
}
- if (approximately_less_than_zero(lineT)) {
+ if (!approximately_zero_or_more(lineT)) {
+ return false;
+ }
+ if (quadT < 0) {
+ quadT = 0;
+ } else if (quadT > 1) {
+ quadT = 1;
+ }
+ if (lineT < 0) {
lineT = 0;
- } else if (approximately_greater_than_one(lineT)) {
+ } else if (lineT > 1) {
lineT = 1;
}
- intersections.fT[1][x] = lineT;
return true;
}
@@ -228,12 +291,12 @@
// utility for pairs of coincident quads
static double horizontalIntersect(const Quadratic& quad, const _Point& pt) {
- Intersections intersections;
- LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int roots = q.horizontalIntersect(pt.y);
+ LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+ double rootVals[2];
+ int roots = q.horizontalIntersect(pt.y, rootVals);
for (int index = 0; index < roots; ++index) {
double x;
- double t = intersections.fT[0][index];
+ double t = rootVals[index];
xy_at_t(quad, t, x, *(double*) 0);
if (approximately_equal(x, pt.x)) {
return t;
@@ -243,12 +306,12 @@
}
static double verticalIntersect(const Quadratic& quad, const _Point& pt) {
- Intersections intersections;
- LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int roots = q.verticalIntersect(pt.x);
+ LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+ double rootVals[2];
+ int roots = q.verticalIntersect(pt.x, rootVals);
for (int index = 0; index < roots; ++index) {
double y;
- double t = intersections.fT[0][index];
+ double t = rootVals[index];
xy_at_t(quad, t, *(double*) 0, y);
if (approximately_equal(y, pt.y)) {
return t;
@@ -266,17 +329,17 @@
int horizontalIntersect(const Quadratic& quad, double left, double right,
double y, double tRange[2]) {
- Intersections i;
- LineQuadraticIntersections q(quad, *((_Line*) 0), i);
- int result = q.horizontalIntersect(y);
+ LineQuadraticIntersections q(quad, *((_Line*) 0), *((Intersections*) 0));
+ double rootVals[2];
+ int result = q.horizontalIntersect(y, rootVals);
int tCount = 0;
for (int index = 0; index < result; ++index) {
double x, y;
- xy_at_t(quad, i.fT[0][index], x, y);
+ xy_at_t(quad, rootVals[index], x, y);
if (x < left || x > right) {
continue;
}
- tRange[tCount++] = i.fT[0][index];
+ tRange[tCount++] = rootVals[index];
}
return tCount;
}
@@ -284,27 +347,13 @@
int horizontalIntersect(const Quadratic& quad, double left, double right, double y,
bool flipped, Intersections& intersections) {
LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int result = q.horizontalIntersect(y, left, right);
- if (flipped) {
- // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x
- for (int index = 0; index < result; ++index) {
- intersections.fT[1][index] = 1 - intersections.fT[1][index];
- }
- }
- return result;
+ return q.horizontalIntersect(y, left, right, flipped);
}
int verticalIntersect(const Quadratic& quad, double top, double bottom, double x,
bool flipped, Intersections& intersections) {
LineQuadraticIntersections q(quad, *((_Line*) 0), intersections);
- int result = q.verticalIntersect(x, top, bottom);
- if (flipped) {
- // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y
- for (int index = 0; index < result; ++index) {
- intersections.fT[1][index] = 1 - intersections.fT[1][index];
- }
- }
- return result;
+ return q.verticalIntersect(x, top, bottom, flipped);
}
int intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
@@ -314,5 +363,5 @@
int intersectRay(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
- return q.intersectRay();
+ return q.intersectRay(i.fT[0]);
}
diff --git a/experimental/Intersection/QuadraticImplicit.cpp b/experimental/Intersection/QuadraticImplicit.cpp
index 268d7d3..9960117 100644
--- a/experimental/Intersection/QuadraticImplicit.cpp
+++ b/experimental/Intersection/QuadraticImplicit.cpp
@@ -93,8 +93,7 @@
for (int i1 = 0; i1 < 3; i1 += 2) {
for (int i2 = 0; i2 < 3; i2 += 2) {
if (q1[i1] == q2[i2]) {
- i.insertOne(i1 >> 1, 0);
- i.insertOne(i2 >> 1, 1);
+ i.insert(i1 >> 1, i2 >> 1);
}
}
}
@@ -110,7 +109,6 @@
// if the quads share an end point, check to see if they overlap
if (onlyEndPtsInCommon(q1, q2, i)) {
- assert(i.insertBalanced());
return i.intersected();
}
QuadImplicitForm i1(q1);
diff --git a/experimental/Intersection/ShapeOps.cpp b/experimental/Intersection/ShapeOps.cpp
index f33c8b1..4785e86 100644
--- a/experimental/Intersection/ShapeOps.cpp
+++ b/experimental/Intersection/ShapeOps.cpp
@@ -20,6 +20,8 @@
const int aXorMask, const int bXorMask, SkPath& simple) {
bool firstContour = true;
do {
+
+#if SORTABLE_CONTOURS // old way
Segment* topStart = findTopContour(contourList);
if (!topStart) {
break;
@@ -28,6 +30,13 @@
// follow edges to intersection by changing the index by direction.
int index, endIndex;
Segment* current = topStart->findTop(index, endIndex);
+#else // new way: iterate while top is unsortable
+ int index, endIndex;
+ Segment* current = findSortableTop(contourList, index, endIndex);
+ if (!current) {
+ break;
+ }
+#endif
int contourWinding;
if (firstContour) {
contourWinding = 0;
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index 402661e..62439d0 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -26,10 +26,12 @@
#endif
#define PRECISE_T_SORT 1
+#define SORTABLE_CONTOURS 0 // set to 1 for old code that works most of the time
#define DEBUG_UNUSED 0 // set to expose unused functions
+#define FORCE_RELEASE 0
-#if 1 // set to 1 for multiple thread -- no debugging
+#if FORCE_RELEASE || defined SK_RELEASE // set force release to 1 for multiple thread -- no debugging
const bool gRunTestsInOneThread = false;
@@ -498,7 +500,6 @@
// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
// may provide some help, but nothing has been figured out yet.
- // start here
/*(
for quads and cubics, set up a parameterized line (e.g. LineParameters )
for points [0] to [1]. See if point [2] is on that line, or on one side
@@ -820,6 +821,10 @@
fID = ++gSegmentID;
#endif
}
+
+ bool operator<(const Segment& rh) const {
+ return fBounds.fTop < rh.fBounds.fTop;
+ }
bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const {
if (activeAngleInner(index, done, angles)) {
@@ -848,7 +853,7 @@
}
bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const {
- int next = nextSpan(index, 1);
+ int next = nextExactSpan(index, 1);
if (next > 0) {
const Span& upSpan = fTs[index];
if (upSpan.fWindValue) {
@@ -860,7 +865,7 @@
}
}
}
- int prev = nextSpan(index, -1);
+ int prev = nextExactSpan(index, -1);
// edge leading into junction
if (prev >= 0) {
const Span& downSpan = fTs[prev];
@@ -1658,7 +1663,7 @@
const Span& mSpan = fTs[SkMin32(start, end)];
return mSpan.fDone;
}
-
+
Segment* findNextOp(SkTDArray<Span*>& chase, bool active,
int& nextStart, int& nextEnd, int& winding, int& spanWinding,
bool& unsortable, ShapeOp op,
@@ -2345,10 +2350,9 @@
int count = fTs.count();
// see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
- bool lastUnsortableEnd;
for (int index = 0; index < count; ++index) {
const Span& span = fTs[index];
- if ((!span.fDone && !span.fUnsortableStart) || (!lastDone && !lastUnsortableEnd)) {
+ if (!span.fDone || !lastDone) {
const SkPoint& intercept = xyAtT(&span);
if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY
&& topPt.fX > intercept.fX)) {
@@ -2359,7 +2363,6 @@
}
}
lastDone = span.fDone;
- lastUnsortableEnd = span.fUnsortableEnd;
}
// sort the edges to find the leftmost
int step = 1;
@@ -2387,8 +2390,12 @@
const Angle* angle = sorted[++firstT];
if (angle->unsortable()) {
// FIXME: if all angles are unsortable, find next topmost
- SkASSERT(firstT < angles.count() - 1);
- continue;
+ if (firstT >= angles.count() - 1) {
+ #if SORTABLE_CONTOURS
+ SkASSERT(0);
+ #endif
+ return NULL;
+ }
}
leftSegment = angle->segment();
tIndex = angle->end();
@@ -2422,7 +2429,7 @@
// OPTIMIZATION: uses tail recursion. Unwise?
Span* innerChaseDone(int index, int step, int winding) {
- int end = nextSpan(index, step);
+ int end = nextExactSpan(index, step);
SkASSERT(end >= 0);
if (multipleSpans(end)) {
return &fTs[end];
@@ -2430,14 +2437,14 @@
const Span& endSpan = fTs[end];
Segment* other = endSpan.fOther;
index = endSpan.fOtherIndex;
- int otherEnd = other->nextSpan(index, step);
+ int otherEnd = other->nextExactSpan(index, step);
Span* last = other->innerChaseDone(index, step, winding);
other->markDone(SkMin32(index, otherEnd), winding);
return last;
}
Span* innerChaseWinding(int index, int step, int winding) {
- int end = nextSpan(index, step);
+ int end = nextExactSpan(index, step);
SkASSERT(end >= 0);
if (multipleSpans(end)) {
return &fTs[end];
@@ -2445,7 +2452,7 @@
const Span& endSpan = fTs[end];
Segment* other = endSpan.fOther;
index = endSpan.fOtherIndex;
- int otherEnd = other->nextSpan(index, step);
+ int otherEnd = other->nextExactSpan(index, step);
int min = SkMin32(index, otherEnd);
if (other->fTs[min].fWindSum != SK_MinS32) {
SkASSERT(other->fTs[min].fWindSum == winding);
@@ -2600,6 +2607,21 @@
span.fWindSum = winding;
return &span;
}
+
+ void markUnsortable(int start, int end) {
+ Span* span = &fTs[start];
+ if (start < end) {
+ span->fUnsortableStart = true;
+ } else {
+ --span;
+ span->fUnsortableEnd = true;
+ }
+ if (span->fDone) {
+ return;
+ }
+ span->fDone = true;
+ fDoneSpans++;
+ }
void markWinding(int index, int winding) {
// SkASSERT(!done());
@@ -2685,6 +2707,8 @@
// FIXME
// this returns at any difference in T, vs. a preset minimum. It may be
// that all callers to nextSpan should use this instead.
+ // OPTIMIZATION splitting this into separate loops for up/down steps
+ // would allow using precisely_negative instead of precisely_zero
int nextExactSpan(int from, int step) const {
const Span& fromSpan = fTs[from];
int count = fTs.count();
@@ -2736,14 +2760,7 @@
Angle& angle = angles[angleIndex];
if (angle.unsortable()) {
// so that it is available for early exclusion in findTop and others
- const SkTDArray<Span>* spans = angle.spans();
- Span* span = const_cast<Span*>(&(*spans)[angle.start()]);
- if (angle.start() < angle.end()) {
- span->fUnsortableStart = true;
- } else {
- --span;
- span->fUnsortableEnd = true;
- }
+ angle.segment()->markUnsortable(angle.start(), angle.end());
result = false;
}
}
@@ -2800,6 +2817,10 @@
end = index;
}
+ bool unsortable(int index) const {
+ return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
+ }
+
void updatePts(const SkPoint pts[]) {
fPts = pts;
}
@@ -2997,8 +3018,10 @@
for (int vIndex = 1; vIndex <= fVerb; ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
}
- SkDebugf(") t=%1.9g (%1.9g,%1.9g) newWindSum=%d windSum=",
- span.fT, pt.fX, pt.fY, winding);
+ SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
+ fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
+ SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) newWindSum=%d windSum=",
+ span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY, winding);
if (span.fWindSum == SK_MinS32) {
SkDebugf("?");
} else {
@@ -3031,15 +3054,21 @@
lastSum = windSum;
windSum -= segment.spanSign(&angle);
}
- SkDebugf("%s [%d] %s id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
- " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n",
- __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE ***" : "",
+ SkDebugf("%s [%d] %sid=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)"
+ " sign=%d windValue=%d windSum=",
+ __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : "",
segment.fID, kLVerbStr[segment.fVerb],
- start, segment.xAtT(&sSpan),
- segment.yAtT(&sSpan), end, segment.xAtT(&eSpan),
- segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue,
- lastSum, windSum, useInnerWinding(lastSum, windSum)
- ? windSum : lastSum, mSpan.fDone);
+ start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
+ segment.xAtT(&eSpan), segment.yAtT(&eSpan), angle.sign(),
+ mSpan.fWindValue);
+ if (mSpan.fWindSum == SK_MinS32) {
+ SkDebugf("?");
+ } else {
+ SkDebugf("%d", mSpan.fWindSum);
+ }
+ SkDebugf(" winding: %d->%d (max=%d) done=%d\n", lastSum, windSum,
+ useInnerWinding(lastSum, windSum) ? windSum : lastSum,
+ mSpan.fDone);
#if false && DEBUG_ANGLE
angle.debugShow(segment.xyAtT(&sSpan));
#endif
@@ -3327,6 +3356,18 @@
fXor = isXor;
}
+#if !SORTABLE_CONTOURS
+ void sortSegments() {
+ int segmentCount = fSegments.count();
+ fSortedSegments.setReserve(segmentCount);
+ for (int test = 0; test < segmentCount; ++test) {
+ *fSortedSegments.append() = &fSegments[test];
+ }
+ QSort<Segment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+ fFirstSorted = 0;
+ }
+#endif
+
// 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
@@ -3367,6 +3408,28 @@
return bestSegment;
}
+#if !SORTABLE_CONTOURS
+ Segment* topSortableSegment(SkScalar& bestY) {
+ int segmentCount = fSortedSegments.count();
+ SkASSERT(segmentCount > 0);
+ Segment* bestSegment = NULL;
+ while (fFirstSorted < segmentCount) {
+ Segment* testSegment = fSortedSegments[fFirstSorted];
+ if (testSegment->done()) {
+ fFirstSorted++;
+ continue;
+ }
+ bestSegment = testSegment;
+ break;
+ }
+ if (!bestSegment) {
+ return NULL;
+ }
+ bestY = bestSegment->activeTop();
+ return bestSegment;
+ }
+#endif
+
Segment* undoneSegment(int& start, int& end) {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
@@ -3445,6 +3508,10 @@
private:
SkTArray<Segment> fSegments;
+#if !SORTABLE_CONTOURS
+ SkTDArray<Segment*> fSortedSegments;
+ int fFirstSorted;
+#endif
SkTDArray<Coincidence> fCoincidences;
SkTDArray<const Contour*> fCrosses;
Bounds fBounds;
@@ -3769,6 +3836,7 @@
#if DEBUG_ADD_INTERSECTING_TS
static void debugShowLineIntersection(int pts, const Work& wt,
const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ return;
if (!pts) {
SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n",
__FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
@@ -3795,6 +3863,37 @@
SkDebugf("\n");
}
+static void debugShowQuadLineIntersection(int pts, const Work& wt,
+ const Work& wn, const double wtTs[2], const double wnTs[2]) {
+ if (!pts) {
+ SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
+ " (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)\n",
+ __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+ wn.pts()[0].fX, wn.pts()[0].fY, wn.pts()[1].fX, wn.pts()[1].fY,
+ wt.pts()[2].fX, wt.pts()[2].fY );
+ return;
+ }
+ SkPoint wtOutPt, wnOutPt;
+ QuadXYAtT(wt.pts(), wtTs[0], &wtOutPt);
+ LineXYAtT(wn.pts(), wnTs[0], &wnOutPt);
+ SkDebugf("%s wtTs[0]=%1.9g (%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+ __FUNCTION__,
+ wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY,
+ wt.pts()[1].fX, wt.pts()[1].fY, wt.pts()[2].fX, wt.pts()[2].fY,
+ wtOutPt.fX, wtOutPt.fY);
+ if (pts == 2) {
+ SkDebugf(" wtTs[1]=%1.9g", wtTs[1]);
+ }
+ SkDebugf(" wnTs[0]=%g (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g)",
+ wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY,
+ wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY);
+ if (pts == 2) {
+ SkDebugf(" wnTs[1]=%1.9g", wnTs[1]);
+ }
+ SkDebugf("\n");
+}
+
static void debugShowQuadIntersection(int pts, const Work& wt,
const Work& wn, const double wtTs[2], const double wnTs[2]) {
if (!pts) {
@@ -3831,6 +3930,10 @@
const Work& , const double [2], const double [2]) {
}
+static void debugShowQuadLineIntersection(int , const Work& ,
+ const Work& , const double [2], const double [2]) {
+}
+
static void debugShowQuadIntersection(int , const Work& ,
const Work& , const double [2], const double [2]) {
}
@@ -3938,6 +4041,8 @@
case Work::kQuad_Segment: {
swap = true;
pts = QuadLineIntersect(wn.pts(), wt.pts(), ts);
+ debugShowQuadLineIntersection(pts, wt, wn,
+ ts.fT[1], ts.fT[0]);
break;
}
case Work::kCubic_Segment: {
@@ -3961,6 +4066,8 @@
break;
case Work::kLine_Segment: {
pts = QuadLineIntersect(wt.pts(), wn.pts(), ts);
+ debugShowQuadLineIntersection(pts, wt, wn,
+ ts.fT[1], ts.fT[0]);
break;
}
case Work::kQuad_Segment: {
@@ -4028,12 +4135,6 @@
}
}
- int pt2 = 0;
- int pt2inc = 1;
- if (ts.fFlip) {
- pt2 = pts - 1;
- pt2inc = -1;
- }
for (int pt = 0; pt < pts; ++pt) {
SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1);
SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1);
@@ -4041,7 +4142,6 @@
int nextTAt = wn.addT(ts.fT[!swap][pt], wt);
wt.addOtherT(testTAt, ts.fT[!swap][pt ^ ts.fFlip], nextTAt);
wn.addOtherT(nextTAt, ts.fT[swap][pt ^ ts.fFlip], testTAt);
- pt2 += pt2inc;
}
} while (wn.advance());
} while (wt.advance());
@@ -4232,6 +4332,7 @@
return winding;
}
+#if SORTABLE_CONTOURS
// 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?
@@ -4266,6 +4367,7 @@
}
return topStart;
}
+#endif
static Segment* findUndone(SkTDArray<Contour*>& contourList, int& start, int& end) {
int contourCount = contourList.count();
@@ -4393,6 +4495,42 @@
&& (!winding || !spanWinding || winding == -spanWinding);
}
+#if !SORTABLE_CONTOURS
+static Segment* findSortableTop(SkTDArray<Contour*>& contourList, int& index,
+ int& endIndex) {
+ Segment* result;
+ do {
+ int contourCount = contourList.count();
+ int cIndex = 0;
+ Segment* topStart;
+ SkScalar bestY = SK_ScalarMax;
+ Contour* contour;
+ do {
+ contour = contourList[cIndex];
+ topStart = contour->topSortableSegment(bestY);
+ } while (!topStart && ++cIndex < contourCount);
+ if (!topStart) {
+ return NULL;
+ }
+ while (++cIndex < contourCount) {
+ contour = contourList[cIndex];
+ if (bestY < contour->bounds().fTop) {
+ continue;
+ }
+ SkScalar testY = SK_ScalarMax;
+ Segment* test = contour->topSortableSegment(testY);
+ if (!test || bestY <= testY) {
+ continue;
+ }
+ topStart = test;
+ bestY = testY;
+ }
+ result = topStart->findTop(index, endIndex);
+ } while (!result);
+ return result;
+}
+#endif
+
// 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
@@ -4407,6 +4545,7 @@
bool firstContour = true;
bool unsortable = false;
do {
+#if SORTABLE_CONTOURS // old way
Segment* topStart = findTopContour(contourList);
if (!topStart) {
break;
@@ -4415,6 +4554,13 @@
// follow edges to intersection by changing the index by direction.
int index, endIndex;
Segment* current = topStart->findTop(index, endIndex);
+#else // new way: iterate while top is unsortable
+ int index, endIndex;
+ Segment* current = findSortableTop(contourList, index, endIndex);
+ if (!current) {
+ break;
+ }
+#endif
int contourWinding;
if (firstContour) {
contourWinding = 0;
@@ -4568,6 +4714,16 @@
}
}
+#if !SORTABLE_CONTOURS
+static void sortSegments(SkTDArray<Contour*>& contourList) {
+ int contourCount = contourList.count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ Contour* contour = contourList[cTest];
+ contour->sortSegments();
+ }
+}
+#endif
+
static void makeContourList(SkTArray<Contour>& contours,
SkTDArray<Contour*>& list) {
int count = contours.count();
@@ -4614,6 +4770,9 @@
// eat through coincident edges
coincidenceCheck(contourList);
fixOtherTIndex(contourList);
+#if !SORTABLE_CONTOURS
+ sortSegments(contourList);
+#endif
// construct closed contours
if (builder.xorMask() == kWinding_Mask
? !bridgeWinding(contourList, simple)
diff --git a/experimental/Intersection/SimplifyFindTop_Test.cpp b/experimental/Intersection/SimplifyFindTop_Test.cpp
index 0c9c2e0..11b083f 100644
--- a/experimental/Intersection/SimplifyFindTop_Test.cpp
+++ b/experimental/Intersection/SimplifyFindTop_Test.cpp
@@ -27,9 +27,13 @@
addIntersectTs(contourList[1], contourList[1]);
}
fixOtherTIndex(contourList);
+#if SORTABLE_CONTOURS // old way
SimplifyFindTopTest::Segment* topStart = findTopContour(contourList);
const SimplifyFindTopTest::Segment* topSegment = topStart->findTop(index,
end);
+#else
+ const SimplifyFindTopTest::Segment* topSegment = findSortableTop(contourList, index, end);
+#endif
return topSegment;
}
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 9841176..4cd7f01 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -2828,12 +2828,26 @@
testSimplifyx(path);
}
-static void (*firstTest)() = testQuadratic7;
+static void testQuadratic51() {
+ SkPath path;
+ path.moveTo(369.863983f, 145.645813f);
+ path.quadTo(382.380371f, 121.254936f, 406.236359f, 121.254936f);
+ path.lineTo(369.863983f, 145.645813f);
+ path.close();
+ path.moveTo(369.970581f, 137.94342f);
+ path.quadTo(383.98465f, 121.254936f, 406.235992f, 121.254936f);
+ path.lineTo(369.970581f, 137.94342f);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void (*firstTest)() = testQuadratic51;
static struct {
void (*fun)();
const char* str;
} tests[] = {
+ TEST(testQuadratic51),
TEST(testQuadratic38),
TEST(testQuadratic37),
TEST(testQuadratic36),
@@ -3113,7 +3127,7 @@
static bool skipAll = false;
static bool runSubTests = false;
-static bool runReverse = false;
+static bool runReverse = true;
void SimplifyNew_Test() {
if (skipAll) {
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index eb737ab..e1c0188 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -2317,11 +2317,114 @@
path.quadTo(353.161499,190.31131, 353.161499,195.011719);
</div>
+<div id="testQuadratic48o">
+path.moveTo(366.608826, 151.196014);
+path.quadTo(378.803101, 136.674606, 398.164948, 136.674606);
+path.lineTo(354.009216, 208.816208);
+path.lineTo(393.291473, 102.232819);
+path.lineTo(359.978058, 136.581512);
+path.quadTo(378.315979, 136.581512, 388.322723, 149.613556);
+path.lineTo(364.390686, 157.898193);
+path.quadTo(375.281769, 136.674606, 396.039917, 136.674606);
+path.lineTo(350, 120);
+path.lineTo(366.608826, 151.196014);
+path.close();
+</div>
+
+<div id="testQuadratic48s">
+path.moveTo(369.285553, 126.984779);
+path.lineTo(393.291473,102.232819);
+path.lineTo(382.416199,131.740402);
+path.lineTo(396.039917,136.674606);
+path.quadTo(387.290802,136.674606, 380.294495,140.44487);
+path.quadTo(379.623352,140.760971, 378.965302,141.103577);
+path.lineTo(378.917297,141.233856);
+path.quadTo(378.86972,141.206131, 378.822021,141.178574);
+path.quadTo(372.011871,144.761871, 366.608826,151.196014);
+path.lineTo(350,120);
+path.lineTo(369.285553,126.984779);
+path.close();
+</div>
+
+<div id="testQuadratic49s">
+path.moveTo(366.400513, 204.162521);
+path.lineTo(411.545044, 81.6732483);
+path.lineTo(366.400513, 204.162521);
+path.close();
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188, 121.147957, 368.11853, 121.147957);
+path.quadTo(389.193115, 121.147957, 400.693176, 136.124817);
+path.lineTo(331.585693, 138.050415);
+path.close();
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
+<div id="testQuadratic50o">
+path.moveTo(366.400513, 204.162521);
+path.lineTo(411.545044, 81.6732483);
+path.lineTo(366.400513, 204.162521);
+path.close();
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188, 121.147957, 368.11853, 121.147957);
+path.quadTo(389.193115, 121.147957, 400.693176, 136.124817);
+path.lineTo(331.585693, 138.050415);
+path.close();
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
+<div id="testQuadratic50s">
+path.moveTo(331.585693, 138.050415);
+path.quadTo(345.867188,121.147957, 368.11853,121.147957);
+path.quadTo(378.797424,121.147957, 387.017914,124.993469);
+path.quadTo(391.577667,123.030998, 396.645874,122.098694);
+path.quadTo(401.232697,121.254936, 406.235992,121.254936);
+path.lineTo(395.061676,126.397095);
+path.lineTo(391.979187,127.81559);
+path.quadTo(393.010406,128.517273, 393.994415,129.292801);
+path.quadTo(394.053131,129.339066, 394.111664,129.385605);
+path.lineTo(393.910492,129.520508);
+path.lineTo(383.340973,136.608322);
+path.lineTo(375.350006,136.830978);
+path.quadTo(376.20224,135.708145, 377.092102,134.66626);
+path.lineTo(372.197113,136.918823);
+</div>
+
+<div id="testQuadratic51">
+path.moveTo(369.863983, 145.645813);
+path.quadTo(382.380371, 121.254936, 406.236359, 121.254936);
+path.lineTo(369.863983, 145.645813);
+path.close();
+path.moveTo(369.970581, 137.94342);
+path.quadTo(383.98465, 121.254936, 406.235992, 121.254936);
+path.lineTo(369.970581, 137.94342);
+path.close();
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
+ testQuadratic51,
+ testQuadratic50o,
+ testQuadratic50s,
+ testQuadratic49s,
+ testQuadratic48o,
+ testQuadratic48s,
testQuadratic47o,
testQuadratic47s,
testQuadratic46o,