aboutsummaryrefslogtreecommitdiffhomepage
path: root/experimental
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-07-11 17:52:32 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2012-07-11 17:52:32 +0000
commitfa4a6e964691ff9a88bc047418abe2d4324dfcae (patch)
tree3e442544da8a7fed46517409b9c52ef4e5bc44c4 /experimental
parent91bd45967c6ca1ec408a0fefd3de0dcf3d03294a (diff)
shape ops work in progress
M Intersection/SimplifyRect4x4_Test.cpp M Intersection/Simplify.cpp M Intersection/SimplifyFindNext_Test.cpp M Intersection/SimplifyNew_Test.cpp M Intersection/op.htm git-svn-id: http://skia.googlecode.com/svn/trunk@4543 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'experimental')
-rw-r--r--experimental/Intersection/Simplify.cpp414
-rw-r--r--experimental/Intersection/SimplifyFindNext_Test.cpp7
-rw-r--r--experimental/Intersection/SimplifyNew_Test.cpp68
-rw-r--r--experimental/Intersection/SimplifyRect4x4_Test.cpp41
-rw-r--r--experimental/Intersection/op.htm119
5 files changed, 502 insertions, 147 deletions
diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp
index c6fca6fab8..6946921363 100644
--- a/experimental/Intersection/Simplify.cpp
+++ b/experimental/Intersection/Simplify.cpp
@@ -41,9 +41,9 @@
#define DEBUG_CROSS 1
#define DEBUG_DUMP 1
#define DEBUG_PATH_CONSTRUCTION 1
-#define DEBUG_WINDING 0
+#define DEBUG_WINDING 01
#define DEBUG_UNUSED 0 // set to expose unused functions
-#define DEBUG_MARK_DONE 0
+#define DEBUG_MARK_DONE 01
#endif
@@ -645,7 +645,36 @@ public:
fID = ++gSegmentID;
#endif
}
-
+
+ bool activeAngles(int index) const {
+ double referenceT = fTs[index].fT;
+ int lesser = index;
+ while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) {
+ if (activeAnglesInner(lesser)) {
+ return true;
+ }
+ }
+ do {
+ if (activeAnglesInner(index)) {
+ return true;
+ }
+ } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
+ return false;
+ }
+
+ bool activeAnglesInner(int index) const {
+ Span* span = &fTs[index];
+ Segment* other = span->fOther;
+ int oIndex = span->fOtherIndex;
+ int next = other->nextSpan(oIndex, 1);
+ if (next > 0 && !other->fTs[oIndex].fDone) {
+ return true;
+ }
+ int prev = other->nextSpan(oIndex, -1);
+ // edge leading into junction
+ return prev >= 0 && !other->fTs[prev].fDone;
+ }
+
SkScalar activeTop() const {
SkASSERT(!done());
int count = fTs.count();
@@ -926,7 +955,7 @@ public:
return;
}
if (t - endT > FLT_EPSILON) {
- endSpan = addTPair(t, other, otherT);
+ endSpan = addTDonePair(t, other, otherT);
}
do {
endT = fTs[++endSpan].fT;
@@ -935,6 +964,26 @@ public:
addTPair(endT, other, otherEnd);
}
+ // match the other.fWindValue to its mates
+ int addTDonePair(double t, Segment& other, double otherT) {
+ int insertedAt = addTPair(t, other, otherT);
+ Span& end = fTs[insertedAt];
+ SkASSERT(end.fWindValue == 1);
+ end.fWindValue = 0;
+ end.fDone = true;
+ ++fDoneSpans;
+ Span& otherEnd = other.fTs[end.fOtherIndex];
+ Span* match = NULL;
+ if (end.fOtherIndex > 0) {
+ match = &other.fTs[end.fOtherIndex - 1];
+ }
+ if (!match || match->fT < otherT) {
+ match = &other.fTs[end.fOtherIndex + 1];
+ }
+ otherEnd.fWindValue = match->fWindValue;
+ return insertedAt;
+ }
+
int addTPair(double t, Segment& other, double otherT) {
int insertedAt = addT(t, &other);
int otherInsertedAt = other.addT(otherT, this);
@@ -1021,7 +1070,7 @@ public:
// 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
+ // intersect ray starting at basePt with edge
Intersections intersections;
int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX,
false, intersections);
@@ -1076,8 +1125,9 @@ public:
// it is guaranteed to have an end which describes a non-zero length (?)
// winding -1 means ccw, 1 means cw
// firstFind allows coincident edges to be treated differently
- Segment* findNext(int winding, const int startIndex, const int endIndex,
- int& nextStart, int& nextEnd, bool firstFind) {
+ Segment* findNext(SkTDArray<Span*>& chase, int winding, const int startIndex,
+ const int endIndex,
+ int& nextStart, int& nextEnd, int& flipped, bool firstFind) {
SkASSERT(startIndex != endIndex);
int count = fTs.count();
SkASSERT(startIndex < endIndex ? startIndex < count - 1
@@ -1105,28 +1155,14 @@ public:
buildAngles(end, angles);
SkTDArray<Angle*> sorted;
sortAngles(angles, sorted);
- // find the starting edge
- int firstIndex = -1;
int angleCount = angles.count();
- int angleIndex;
- const Angle* angle;
- for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
- angle = sorted[angleIndex];
- if (angle->segment() == this && angle->start() == end &&
- angle->end() == startIndex) {
- firstIndex = angleIndex;
- break;
- }
- }
- // back up if prior edge is coincident with firstIndex
- // adjustFirst(sorted, firstIndex, winding, firstFind);
+ int firstIndex = findStartingEdge(sorted, startIndex, end);
+
SkASSERT(firstIndex >= 0);
int startWinding = winding;
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 {
@@ -1139,37 +1175,45 @@ public:
int windValue = nextSegment->windValue(nextAngle);
SkASSERT(windValue > 0);
winding -= nextAngle->sign() * windValue;
+ #if DEBUG_WINDING
+ SkDebugf("%s maxWinding=%d winding=%d\n", __FUNCTION__, maxWinding,
+ winding);
+ #endif
+ if (maxWinding * winding < 0) {
+ flipped = -flipped;
+ SkDebugf("flipped sign %d %d\n", maxWinding, winding);
+ }
firstEdge = false;
if (!winding) {
if (!foundAngle) {
foundAngle = nextAngle;
}
- goto doNext;
+ continue;
}
if (nextSegment->done()) {
- goto doNext;
+ continue;
}
// 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.
- if (nextSegment->winding(nextAngle) == SK_MinS32) {
+ if (nextSegment->windSum(nextAngle) == SK_MinS32) {
if (abs(maxWinding) < abs(winding)) {
maxWinding = winding;
}
+ Span* last;
if (foundAngle) {
- nextSegment->markAndChaseWinding(nextAngle, maxWinding);
+ last = nextSegment->markAndChaseWinding(nextAngle, maxWinding);
} else {
- nextSegment->markAndChaseDone(nextAngle, maxWinding);
+ last = nextSegment->markAndChaseDone(nextAngle, maxWinding);
+ }
+ if (last) {
+ *chase.append() = last;
}
}
- doNext:
- angle = nextAngle;
} while (++nextIndex != lastIndex);
- // if (!alreadyMarked) {
- sorted[firstIndex]->segment()->
- markDone(SkMin32(startIndex, endIndex), startWinding);
- // }
+ sorted[firstIndex]->segment()->
+ markDone(SkMin32(startIndex, endIndex), startWinding);
if (!foundAngle) {
return NULL;
}
@@ -1177,7 +1221,21 @@ public:
nextEnd = foundAngle->end();
return foundAngle->segment();
}
-
+
+ int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) {
+ int angleCount = sorted.count();
+ int firstIndex = -1;
+ for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
+ const Angle* angle = sorted[angleIndex];
+ if (angle->segment() == this && angle->start() == end &&
+ angle->end() == start) {
+ firstIndex = angleIndex;
+ break;
+ }
+ }
+ return firstIndex;
+ }
+
// FIXME: this is tricky code; needs its own unit test
void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered
int count = fTs.count();
@@ -1374,23 +1432,24 @@ public:
}
// OPTIMIZATION: uses tail recursion. Unwise?
- void innerChaseDone(int index, int step, int winding) {
+ Span* innerChaseDone(int index, int step, int winding) {
int end = nextSpan(index, step);
- if (multipleSpans(end, step)) {
- return;
+ if (multipleSpans(index, end)) {
+ return index >= 0 ? &fTs[index] : NULL;
}
const Span& endSpan = fTs[end];
Segment* other = endSpan.fOther;
index = endSpan.fOtherIndex;
int otherEnd = other->nextSpan(index, step);
- other->innerChaseDone(index, step, winding);
+ Span* last = other->innerChaseDone(index, step, winding);
other->markDone(SkMin32(index, otherEnd), winding);
+ return last;
}
- void innerChaseWinding(int index, int step, int winding) {
+ Span* innerChaseWinding(int index, int step, int winding) {
int end = nextSpan(index, step);
- if (multipleSpans(end, step)) {
- return;
+ if (multipleSpans(index, end)) {
+ return index >= 0 ? &fTs[index] : NULL;
}
const Span& endSpan = fTs[end];
Segment* other = endSpan.fOther;
@@ -1399,10 +1458,11 @@ public:
int min = SkMin32(index, otherEnd);
if (other->fTs[min].fWindSum != SK_MinS32) {
SkASSERT(other->fTs[index].fWindSum == winding);
- return;
+ return NULL;
}
- other->innerChaseWinding(index, step, winding);
+ Span* last = other->innerChaseWinding(index, step, winding);
other->markWinding(min, winding);
+ return last;
}
void init(const SkPoint pts[], SkPath::Verb verb) {
@@ -1473,21 +1533,23 @@ public:
// 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 markAndChaseDone(const Angle* angle, int winding) {
+ Span* markAndChaseDone(const Angle* angle, int winding) {
int index = angle->start();
int endIndex = angle->end();
int step = SkSign32(endIndex - index);
- innerChaseDone(index, step, winding);
+ Span* last = innerChaseDone(index, step, winding);
markDone(SkMin32(index, endIndex), winding);
+ return last;
}
- void markAndChaseWinding(const Angle* angle, int winding) {
+ Span* 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);
+ Span* last = innerChaseWinding(index, step, winding);
markWinding(min, winding);
+ return last;
}
// FIXME: this should also mark spans with equal (x,y)
@@ -1567,8 +1629,17 @@ public:
} while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON);
}
- bool multipleSpans(int end, int step) const {
- return step > 0 ? ++end < fTs.count() : end > 0;
+ bool multipleSpans(int& index, int end) const {
+ if (end > index ? end + 1 >= fTs.count() : end <= 0) {
+ return false;
+ }
+ // return span if when chasing, two or more radiating spans are not done
+ int lesser = SkMin32(index, end);
+ if (!activeAngles(lesser)) {
+ index = -1;
+ }
+ index = lesser;
+ return true;
}
// This has callers for two different situations: one establishes the end
@@ -1625,44 +1696,15 @@ public:
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 {
+ int windSum(int tIndex) const {
return fTs[tIndex].fWindSum;
}
- int winding(const Angle* angle) const {
+ int windSum(const Angle* angle) const {
int start = angle->start();
int end = angle->end();
int index = SkMin32(start, end);
- return winding(index);
+ return windSum(index);
}
int windValue(int tIndex) const {
@@ -1951,15 +1993,9 @@ public:
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;
}
@@ -1991,7 +2027,7 @@ public:
return segment.verb() + 1;
}
- int winding() {
+ int windSum() {
if (fWindingSum >= 0) {
return fWindingSum;
}
@@ -2578,11 +2614,11 @@ 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);
+ contour->findTooCloseToCall(winding);
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
Contour* contour = contourList[cIndex];
- contour->findTooCloseToCall(winding);
+ contour->resolveCoincidence(winding);
}
}
@@ -2636,12 +2672,12 @@ static int innerContourCheck(SkTDArray<Contour*>& contourList,
SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0);
}
tIndex = angle->start(); // lesser Y
- winding = test->winding(SkMin32(tIndex, angle->end()));
+ winding = test->windSum(SkMin32(tIndex, angle->end()));
#if DEBUG_WINDING
SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding);
#endif
} else {
- winding = test->winding(tIndex);
+ winding = test->windSum(tIndex);
#if DEBUG_WINDING
SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding);
#endif
@@ -2701,6 +2737,76 @@ static Segment* findTopContour(SkTDArray<Contour*>& contourList,
return topStart;
}
+static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) {
+ while (chase.count()) {
+ Span* span;
+ chase.pop(&span);
+ const Span& backPtr = span->fOther->span(span->fOtherIndex);
+ Segment* segment = backPtr.fOther;
+ tIndex = backPtr.fOtherIndex;
+ if (segment->activeAngles(tIndex)) {
+ endIndex = segment->nextSpan(tIndex, 1);
+ if (span->fDone) {
+ SkTDArray<Angle> angles;
+ segment->addTwoAngles(endIndex, tIndex, angles);
+ segment->buildAngles(tIndex, angles);
+ SkTDArray<Angle*> sorted;
+ sortAngles(angles, sorted);
+ // find first angle, initialize winding to computed fWindSum
+ int winding = span->fWindSum;
+ int firstIndex = segment->findStartingEdge(sorted, endIndex, tIndex);
+ int firstSign = sorted[firstIndex]->sign();
+ if (firstSign * winding > 0) {
+ winding -= firstSign;
+ }
+ SkDebugf("%s firstSign=%d\n", __FUNCTION__, firstSign);
+ // we care about first sign and whether wind sum indicates this
+ // edge is inside or outside. Maybe need to pass span winding
+ // or first winding or something into this function?
+ SkASSERT(firstIndex >= 0);
+ // advance to first undone angle, then return it and winding
+ // (to set whether edges are active or not)
+ int nextIndex = firstIndex + 1;
+ int angleCount = sorted.count();
+ int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
+ do {
+ SkASSERT(nextIndex != firstIndex);
+ if (nextIndex == angleCount) {
+ nextIndex = 0;
+ }
+ const Angle* angle = sorted[nextIndex];
+ segment = angle->segment();
+ int windValue = segment->windValue(angle);
+ SkASSERT(windValue > 0);
+ int maxWinding = winding;
+ winding -= angle->sign() * windValue;
+ if (maxWinding * winding < 0) {
+ SkDebugf("%s flipped sign %d %d\n", __FUNCTION__, maxWinding, winding);
+ }
+ tIndex = angle->start();
+ endIndex = angle->end();
+ int lesser = SkMin32(tIndex, endIndex);
+ const Span& nextSpan = segment->span(lesser);
+ if (!nextSpan.fDone) {
+ // FIXME: this be wrong. assign startWinding if edge is in
+ // same direction. If the direction is opposite, winding to
+ // assign is flipped sign or +/- 1?
+ if (abs(maxWinding) < abs(winding)) {
+ maxWinding = winding;
+ }
+ segment->markWinding(lesser, maxWinding);
+ break;
+ }
+ } while (++nextIndex != lastIndex);
+ } else {
+ SkASSERT(endIndex > tIndex);
+ }
+ return segment;
+ }
+ }
+ return NULL;
+}
+
// 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
@@ -2711,70 +2817,100 @@ static Segment* findTopContour(SkTDArray<Contour*>& contourList,
// 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) {
- // after findTopContour has already been called once, check if
- // result of subsequent findTopContour has no winding set
bool firstContour = true;
do {
Contour* topContour;
Segment* topStart = findTopContour(contourList, topContour);
if (!topStart) {
break;
- }
+ }
// 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);
- int winding = 0;
- if (!firstContour) {
- int contourWinding = topContour->winding();
- #if DEBUG_WINDING
- SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding);
- #endif
- if (contourWinding == SK_MinS32) {
- const SkPoint& topPoint = current->xyAtT(endIndex);
- winding = innerContourCheck(contourList, topContour, topPoint);
- #if DEBUG_WINDING
- SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding);
- #endif
- }
+ int contourWinding;
+ if (firstContour) {
+ contourWinding = 0;
+ firstContour = false;
+ } else {
+ const SkPoint& topPoint = current->xyAtT(endIndex);
+ contourWinding = innerContourCheck(contourList, topContour, topPoint);
+#if DEBUG_WINDING
+ SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding);
+#endif
}
- const SkPoint* firstPt = NULL;
SkPoint lastPt;
bool firstTime = true;
+ int winding = contourWinding;
int spanWinding = current->spanSign(index, endIndex);
- if (firstContour) {
- topContour->setWinding(spanWinding);
- firstContour = false;
- }
- bool active = winding * spanWinding <= 0;
+ // int firstWinding = contourWinding + spanWinding;
+ // FIXME: needs work. While it works in limited situations, it does
+ // not always compute winding correctly. Active should be removed and instead
+ // the initial winding should be correctly passed in so that if the
+ // inner contour is wound the same way, it never finds an accumulated
+ // winding of zero. Inside 'find next', we need to look for transitions
+ // other than zero when resolving sorted angles.
+ SkTDArray<Span*> chaseArray;
do {
- SkASSERT(!current->done());
- int nextStart, nextEnd;
- Segment* next = current->findNext(winding + spanWinding, index,
- endIndex, nextStart, nextEnd, firstTime);
- if (!next) {
+ bool active = winding * spanWinding <= 0;
+ const SkPoint* firstPt = NULL;
+ do {
+ SkASSERT(!current->done());
+ int nextStart, nextEnd, flipped = 1;
+ Segment* next = current->findNext(chaseArray,
+ winding + spanWinding, index,
+ endIndex, nextStart, nextEnd, flipped, firstTime);
+ if (!next) {
+ break;
+ }
+ if (!firstPt) {
+ firstPt = &current->addMoveTo(index, simple, active);
+ }
+ lastPt = current->addCurveTo(index, endIndex, simple, active);
+ current = next;
+ index = nextStart;
+ endIndex = nextEnd;
+ spanWinding = SkSign32(spanWinding) * flipped * next->windValue(
+ SkMin32(nextStart, nextEnd));
+ #if DEBUG_WINDING
+ SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding);
+ #endif
+ firstTime = false;
+ } while (*firstPt != lastPt && (active || !current->done()));
+ if (firstPt && active) {
+ #if DEBUG_PATH_CONSTRUCTION
+ SkDebugf("%s close\n", __FUNCTION__);
+ #endif
+ simple.close();
+ }
+ current = findChase(chaseArray, index, endIndex);
+ if (!current) {
break;
}
- if (!firstPt) {
- firstPt = &current->addMoveTo(index, simple, active);
+ int lesser = SkMin32(index, endIndex);
+ spanWinding = current->windSum(lesser);
+ int spanValue = current->windValue(lesser);
+ SkASSERT(spanWinding != SK_MinS32);
+ int spanSign = current->spanSign(index, endIndex);
+ #if DEBUG_WINDING
+ SkDebugf("%s spanWinding=%d spanSign=%d winding=%d spanValue=%d\n",
+ __FUNCTION__, spanWinding, spanSign, winding, spanValue);
+ #endif
+ if (spanWinding * spanSign < 0) {
+ #if DEBUG_WINDING
+ SkDebugf("%s spanWinding * spanSign < 0\n", __FUNCTION__);
+ #endif
+ SkTSwap<int>(index, endIndex);
+ }
+ if (abs(spanWinding) > spanValue) {
+ #if DEBUG_WINDING
+ SkDebugf("%s abs(spanWinding) > spanValue\n", __FUNCTION__);
+ #endif
+ winding = spanWinding;
+ spanWinding = spanValue * SkSign32(spanWinding);
+ winding -= spanWinding;
}
- lastPt = current->addCurveTo(index, endIndex, simple, active);
- current = next;
- index = nextStart;
- endIndex = nextEnd;
- spanWinding = SkSign32(spanWinding) * next->windValue(
- SkMin32(nextStart, nextEnd));
- #if DEBUG_WINDING
- SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding);
- #endif
- firstTime = false;
- } while (*firstPt != lastPt);
- if (firstPt) {
- #if DEBUG_PATH_CONSTRUCTION
- SkDebugf("%s close\n", __FUNCTION__);
- #endif
- simple.close();
- }
+ } while (true);
} while (true);
}
diff --git a/experimental/Intersection/SimplifyFindNext_Test.cpp b/experimental/Intersection/SimplifyFindNext_Test.cpp
index c8ca984c8d..4edc53254f 100644
--- a/experimental/Intersection/SimplifyFindNext_Test.cpp
+++ b/experimental/Intersection/SimplifyFindNext_Test.cpp
@@ -32,9 +32,10 @@ static const SimplifyFindNextTest::Segment* testCommon(
SimplifyFindNextTest::Segment& segment = contours[0].debugSegments()[0];
SkPoint pts[2];
pts[0] = segment.xyAtT(&segment.span(endIndex));
- int nextStart, nextEnd;
- SimplifyFindNextTest::Segment* next = segment.findNext(winding,
- startIndex, endIndex, nextStart, nextEnd, true);
+ int nextStart, nextEnd, flipped = 1;
+ SkTDArray<SimplifyFindNextTest::Span*> chaseArray;
+ SimplifyFindNextTest::Segment* next = segment.findNext(chaseArray, winding,
+ startIndex, endIndex, nextStart, nextEnd, flipped, true);
pts[1] = next->xyAtT(&next->span(nextStart));
SkASSERT(pts[0] == pts[1]);
return next;
diff --git a/experimental/Intersection/SimplifyNew_Test.cpp b/experimental/Intersection/SimplifyNew_Test.cpp
index 022518b8b3..2296688da3 100644
--- a/experimental/Intersection/SimplifyNew_Test.cpp
+++ b/experimental/Intersection/SimplifyNew_Test.cpp
@@ -100,6 +100,27 @@ static void testLine7() {
testSimplifyx(path);
}
+static void testLine7a() {
+ SkPath path, simple;
+ path.moveTo(0,0);
+ path.lineTo(4,0);
+ path.lineTo(2,2);
+ path.close();
+ testSimplifyx(path);
+}
+
+static void testLine7b() {
+ SkPath path, simple;
+ path.moveTo(0,0);
+ path.lineTo(4,0);
+ path.close();
+ path.moveTo(6,0);
+ path.lineTo(2,0);
+ path.lineTo(4,2);
+ path.close();
+ testSimplifyx(path);
+}
+
static void testLine8() {
SkPath path, simple;
path.moveTo(0,4);
@@ -313,6 +334,44 @@ static void testLine27() {
testSimplifyx(path);
}
+static void testLine28() {
+ SkPath path, simple;
+ path.addRect(0, 6, 12, 12, (SkPath::Direction) 0);
+ path.addRect(0, 0, 9, 9, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
+static void testLine29() {
+ SkPath path, simple;
+ path.addRect(0, 18, 12, 12, (SkPath::Direction) 0);
+ path.addRect(12, 12, 21, 21, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
+static void testLine30() {
+ SkPath path, simple;
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 4, 13, 13, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
+static void testLine31() {
+ SkPath path, simple;
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(0, 4, 9, 9, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
+static void testLine32() {
+ SkPath path, simple;
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 12, 13, 13, (SkPath::Direction) 0);
+ testSimplifyx(path);
+}
+
#define TEST(name) { name, #name }
static struct {
@@ -325,6 +384,8 @@ static struct {
TEST(testLine4),
TEST(testLine5),
TEST(testLine6),
+ TEST(testLine7a),
+ TEST(testLine7b),
TEST(testLine7),
TEST(testLine8),
TEST(testLine9),
@@ -348,11 +409,16 @@ static struct {
TEST(testLine25),
TEST(testLine26),
TEST(testLine27),
+ TEST(testLine28),
+ TEST(testLine29),
+ TEST(testLine30),
+ TEST(testLine31),
+ TEST(testLine32),
};
static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
-static void (*firstTest)() = 0;
+static void (*firstTest)() = testLine32;
static bool skipAll = false;
void SimplifyNew_Test() {
diff --git a/experimental/Intersection/SimplifyRect4x4_Test.cpp b/experimental/Intersection/SimplifyRect4x4_Test.cpp
index b83c1cd032..ef468068ae 100644
--- a/experimental/Intersection/SimplifyRect4x4_Test.cpp
+++ b/experimental/Intersection/SimplifyRect4x4_Test.cpp
@@ -9,6 +9,7 @@
#include "ShapeOps.h"
#include "SkBitmap.h"
#include "SkCanvas.h"
+#include "SkStream.h"
#include <assert.h>
#include <pthread.h>
@@ -165,6 +166,46 @@ static void* testSimplify4x4RectsMain(void* data)
__FUNCTION__, state.a, state.b, state.c, state.d,
aXAlign, aYAlign, bXAlign, bYAlign,
cXAlign, cYAlign, dXAlign, dYAlign);
+ SkFILEStream inFile("../../experimental/Intersection/op.htm");
+ if (!inFile.isValid()) {
+ continue;
+ }
+ SkTDArray<char> inData;
+ inData.setCount(inFile.getLength());
+ size_t inLen = inData.count();
+ inFile.read(inData.begin(), inLen);
+ inFile.setPath(NULL);
+ SkFILEWStream outFile("../../experimental/Intersection/xop.htm");
+ if (!outFile.isValid()) {
+ continue;
+ }
+ const char marker[] =
+ "</div>\n"
+ "\n"
+ "<script type=\"text/javascript\">\n"
+ "\n"
+ "var testDivs = [\n";
+ const char testLineStr[] = " testLine";
+ char* insert = strstr(inData.begin(), marker);
+ if (!insert) {
+ continue;
+ }
+ size_t startLen = insert - inData.begin();
+ insert += sizeof(marker);
+ const char* numLoc = insert + sizeof(testLineStr);
+ int testNumber = atoi(numLoc) + 1;
+ outFile.write(inData.begin(), startLen);
+ outFile.writeText("<div id=\"testLine");
+ outFile.writeDecAsText(testNumber);
+ outFile.writeText("\">\n");
+ outFile.writeText(pathStr);
+ outFile.writeText("</div>\n\n");
+ outFile.writeText(marker);
+ outFile.writeText(testLineStr);
+ outFile.writeDecAsText(testNumber);
+ outFile.writeText(",\n");
+ outFile.write(insert, inLen - startLen - sizeof(marker));
+ outFile.flush();
}
}
}
diff --git a/experimental/Intersection/op.htm b/experimental/Intersection/op.htm
index f496f7c16a..186bbe158b 100644
--- a/experimental/Intersection/op.htm
+++ b/experimental/Intersection/op.htm
@@ -312,7 +312,32 @@ path.close();
testSimplifyx(path);
</div>
-<!-- don't support addRect yet -->
+<div id="testLine7">
+ SkPath path, simple;
+ path.moveTo(0,0);
+ path.lineTo(4,0);
+ path.lineTo(2,2);
+ path.close();
+ path.moveTo(6,0);
+ path.lineTo(2,0);
+ path.lineTo(4,2);
+ path.close();
+ testSimplifyx(path);
+</div>
+
+<div id="testLine9">
+ SkPath path, simple;
+ path.moveTo(0,4);
+ path.lineTo(4,4);
+ path.lineTo(2,2);
+ path.close();
+ path.moveTo(6,4);
+ path.lineTo(2,4);
+ path.lineTo(4,2);
+ path.close();
+ testSimplifyx(path);
+</div>
+
<div id="testLine17">
SkPath path, simple;
path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
@@ -320,12 +345,51 @@ path.close();
testSimplifyx(path);
</div>
+<div id="testLine28">
+ SkPath path, simple;
+ path.addRect(0, 6, 12, 12, (SkPath::Direction) 0);
+ path.addRect(0, 0, 9, 9, (SkPath::Direction) 0);
+ testSimplifyx(path);
+</div>
+
+<div id="testLine29">
+ SkPath path, simple;
+ path.addRect(0, 18, 12, 12, (SkPath::Direction) 0);
+ path.addRect(12, 12, 21, 21, (SkPath::Direction) 0);
+ testSimplifyx(path);
+</div>
+
+<div id="testLine30">
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 4, 13, 13, (SkPath::Direction) 0);
+</div>
+
+<div id="testLine31">
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(0, 4, 9, 9, (SkPath::Direction) 0);
+</div>
+
+<div id="testLine32">
+ path.addRect(0, 0, 20, 20, (SkPath::Direction) 0);
+ path.addRect(0, 0, 12, 12, (SkPath::Direction) 0);
+ path.addRect(4, 12, 13, 13, (SkPath::Direction) 0);
+</div>
+
</div>
<script type="text/javascript">
var testDivs = [
- testLine6,
+ testLine9,
+ testLine7,
+ testLine30,
+ testLine32,
+ testLine31,
+ testLine29,
+ testLine28,
+ testLine17,
testSimplifyQuadratic21,
testSimplifyQuadratic20,
testSimplifyQuadratic19,
@@ -397,9 +461,52 @@ function parse(test) {
tests.push(contours);
}
+function parseRect(test) {
+ var contours = [];
+ var rectStrs = test.split("path.addRect");
+ var pattern = /-?\d+\.*\d*/g;
+ for (var r in rectStrs) {
+ var rect = rectStrs[r];
+ var sideStrs = rect.match(pattern);
+ var sides = [];
+ for (var wd in sideStrs) {
+ var num = parseFloat(sideStrs[wd]);
+ if (isNaN(num)) continue;
+ sides.push(num);
+ }
+ if (sides.length == 0)
+ continue;
+ var verbs = [];
+ var topLeft = [];
+ topLeft.push(sides[0]); topLeft.push(sides[1]);
+ var topRight = [];
+ topRight.push(sides[2]); topRight.push(sides[1]);
+ var botLeft = [];
+ botLeft.push(sides[0]); botLeft.push(sides[3]);
+ var botRight = [];
+ botRight.push(sides[2]); botRight.push(sides[3]);
+ verbs.push(topLeft);
+ if (sides[4] == 0) {
+ verbs.push(topRight);
+ verbs.push(botRight);
+ verbs.push(botLeft);
+ } else {
+ verbs.push(botLeft);
+ verbs.push(botRight);
+ verbs.push(topRight);
+ }
+ verbs.push(topLeft);
+ contours.push(verbs);
+ }
+ if (contours.length > 0)
+ tests.push(contours);
+}
+
function init(test) {
var canvas = document.getElementById('canvas');
if (!canvas.getContext) return;
+ canvas.width = document.width;
+ canvas.height = document.height;
ctx = canvas.getContext('2d');
var xmin = Infinity;
var xmax = -Infinity;
@@ -599,7 +706,11 @@ function doKeyPress(evt) {
function start() {
for (i = 0; i < testDivs.length; ++i) {
var str = testDivs[i].firstChild.data;
- parse(str);
+ if (str.split("addRect").length > 1) {
+ parseRect(str);
+ } else {
+ parse(str);
+ }
}
drawTop();
window.addEventListener('keypress', doKeyPress, true);
@@ -609,7 +720,7 @@ function start() {
</head>
<body onLoad="start();">
-<canvas id="canvas" width="1500" height="1000"
+<canvas id="canvas" width="750" height="500"
onmousemove="handleMouseOver()"
onclick="handleMouseClick()"
></canvas >