blob: 4d11eb39e8259b73c79e313c109e1aa314f94402 [file] [log] [blame]
/*
* Copyright 2012 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkIntersections.h"
#include "SkOpSegment.h"
#include "SkPathWriter.h"
#include "SkTSort.h"
#define F (false) // discard the edge
#define T (true) // keep the edge
static const bool gUnaryActiveEdge[2][2] = {
// from=0 from=1
// to=0,1 to=0,1
{F, T}, {T, F},
};
static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
// miFrom=0 miFrom=1
// miTo=0 miTo=1 miTo=0 miTo=1
// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
{{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
{{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
{{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
{{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
};
#undef F
#undef T
enum {
kOutsideTrackedTCount = 16, // FIXME: determine what this should be
kMissingSpanCount = 4, // FIXME: determine what this should be
};
// note that this follows the same logic flow as build angles
bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
if (activeAngleInner(index, done, angles)) {
return true;
}
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0
&& (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
if (activeAngleOther(lesser, done, angles)) {
return true;
}
}
do {
if (activeAngleOther(index, done, angles)) {
return true;
}
if (++index == fTs.count()) {
break;
}
if (fTs[index - 1].fTiny) {
referenceT = fTs[index].fT;
continue;
}
} while (precisely_negative(fTs[index].fT - referenceT));
return false;
}
bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
SkOpSpan* span = &fTs[index];
SkOpSegment* other = span->fOther;
int oIndex = span->fOtherIndex;
return other->activeAngleInner(oIndex, done, angles);
}
bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
int next = nextExactSpan(index, 1);
if (next > 0) {
SkOpSpan& upSpan = fTs[index];
if (upSpan.fWindValue || upSpan.fOppValue) {
addAngle(angles, index, next);
if (upSpan.fDone || upSpan.fUnsortableEnd) {
(*done)++;
} else if (upSpan.fWindSum != SK_MinS32) {
return true;
}
} else if (!upSpan.fDone) {
upSpan.fDone = true;
fDoneSpans++;
}
}
int prev = nextExactSpan(index, -1);
// edge leading into junction
if (prev >= 0) {
SkOpSpan& downSpan = fTs[prev];
if (downSpan.fWindValue || downSpan.fOppValue) {
addAngle(angles, index, prev);
if (downSpan.fDone) {
(*done)++;
} else if (downSpan.fWindSum != SK_MinS32) {
return true;
}
} else if (!downSpan.fDone) {
downSpan.fDone = true;
fDoneSpans++;
}
}
return false;
}
SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const {
SkASSERT(!done());
SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
int count = fTs.count();
// see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
bool lastUnsortable = false;
double lastT = -1;
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
goto next;
}
if (span.fDone && lastDone) {
goto next;
}
if (approximately_negative(span.fT - lastT)) {
goto next;
}
{
const SkPoint& xy = xyAtT(&span);
if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
topPt = xy;
if (firstT) {
*firstT = index;
}
}
if (fVerb != SkPath::kLine_Verb && !lastDone) {
SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
&& topPt.fX > curveTop.fX)) {
topPt = curveTop;
if (firstT) {
*firstT = index;
}
}
}
lastT = span.fT;
}
next:
lastDone = span.fDone;
lastUnsortable = span.fUnsortableEnd;
}
return topPt;
}
bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
int sumMiWinding = updateWinding(endIndex, index);
int sumSuWinding = updateOppWinding(endIndex, index);
if (fOperand) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding,
&maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
}
bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
bool miFrom;
bool miTo;
bool suFrom;
bool suTo;
if (operand()) {
miFrom = (*oppMaxWinding & xorMiMask) != 0;
miTo = (*oppSumWinding & xorMiMask) != 0;
suFrom = (*maxWinding & xorSuMask) != 0;
suTo = (*sumWinding & xorSuMask) != 0;
} else {
miFrom = (*maxWinding & xorMiMask) != 0;
miTo = (*sumWinding & xorMiMask) != 0;
suFrom = (*oppMaxWinding & xorSuMask) != 0;
suTo = (*oppSumWinding & xorSuMask) != 0;
}
bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
#if DEBUG_ACTIVE_OP
SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
#endif
return result;
}
bool SkOpSegment::activeWinding(int index, int endIndex) {
int sumWinding = updateWinding(endIndex, index);
int maxWinding;
return activeWinding(index, endIndex, &maxWinding, &sumWinding);
}
bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
setUpWinding(index, endIndex, maxWinding, sumWinding);
bool from = *maxWinding != 0;
bool to = *sumWinding != 0;
bool result = gUnaryActiveEdge[from][to];
return result;
}
void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
SkASSERT(start != end);
SkOpAngle& angle = anglesPtr->push_back();
angle.set(this, start, end);
}
void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
SkOpSegment* other) {
int tIndex = -1;
int tCount = fTs.count();
int oIndex = -1;
int oCount = other->fTs.count();
do {
++tIndex;
} while (startPt != fTs[tIndex].fPt && tIndex < tCount);
int tIndexStart = tIndex;
do {
++oIndex;
} while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
int oIndexStart = oIndex;
const SkPoint* nextPt;
do {
nextPt = &fTs[++tIndex].fPt;
SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
} while (startPt == *nextPt);
double nextT = fTs[tIndex].fT;
const SkPoint* oNextPt;
do {
oNextPt = &other->fTs[++oIndex].fPt;
SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
} while (endPt == *oNextPt);
double oNextT = other->fTs[oIndex].fT;
// at this point, spans before and after are at:
// fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
// if tIndexStart == 0, no prior span
// if nextT == 1, no following span
// advance the span with zero winding
// if the following span exists (not past the end, non-zero winding)
// connect the two edges
if (!fTs[tIndexStart].fWindValue) {
if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other->fID, tIndexStart - 1,
fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
xyAtT(tIndexStart).fY);
#endif
addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
fTs[tIndexStart].fPt);
}
if (nextT < 1 && fTs[tIndex].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other->fID, tIndex,
fTs[tIndex].fT, xyAtT(tIndex).fX,
xyAtT(tIndex).fY);
#endif
addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
}
} else {
SkASSERT(!other->fTs[oIndexStart].fWindValue);
if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other->fID, oIndexStart - 1,
other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
other->xyAtT(oIndexStart).fY);
other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
#endif
}
if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other->fID, oIndex,
other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
other->xyAtT(oIndex).fY);
other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
#endif
}
}
}
void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
SkOpSegment* other) {
// walk this to startPt
// walk other to startPt
// if either is > 0, add a pointer to the other, copying adjacent winding
int tIndex = -1;
int oIndex = -1;
do {
++tIndex;
} while (startPt != fTs[tIndex].fPt);
do {
++oIndex;
} while (startPt != other->fTs[oIndex].fPt);
if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) {
addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
}
SkPoint nextPt = startPt;
do {
const SkPoint* workPt;
do {
workPt = &fTs[++tIndex].fPt;
} while (nextPt == *workPt);
do {
workPt = &other->fTs[++oIndex].fPt;
} while (nextPt == *workPt);
nextPt = *workPt;
double tStart = fTs[tIndex].fT;
double oStart = other->fTs[oIndex].fT;
if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
break;
}
addTPair(tStart, other, oStart, false, nextPt);
} while (endPt != nextPt);
}
void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
init(pts, SkPath::kCubic_Verb, operand, evenOdd);
fBounds.setCubicBounds(pts);
}
void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
SkPoint edge[4];
const SkPoint* ePtr;
int lastT = fTs.count() - 1;
if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
ePtr = fPts;
} else {
// OPTIMIZE? if not active, skip remainder and return xyAtT(end)
subDivide(start, end, edge);
ePtr = edge;
}
if (active) {
bool reverse = ePtr == fPts && start != 0;
if (reverse) {
path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
switch (fVerb) {
case SkPath::kLine_Verb:
path->deferredLine(ePtr[0]);
break;
case SkPath::kQuad_Verb:
path->quadTo(ePtr[1], ePtr[0]);
break;
case SkPath::kCubic_Verb:
path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
break;
default:
SkASSERT(0);
}
// return ePtr[0];
} else {
path->deferredMoveLine(ePtr[0]);
switch (fVerb) {
case SkPath::kLine_Verb:
path->deferredLine(ePtr[1]);
break;
case SkPath::kQuad_Verb:
path->quadTo(ePtr[1], ePtr[2]);
break;
case SkPath::kCubic_Verb:
path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
break;
default:
SkASSERT(0);
}
}
}
// return ePtr[SkPathOpsVerbToPoints(fVerb)];
}
void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
init(pts, SkPath::kLine_Verb, operand, evenOdd);
fBounds.set(pts, 2);
}
// add 2 to edge or out of range values to get T extremes
void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
SkOpSpan& span = fTs[index];
if (precisely_zero(otherT)) {
otherT = 0;
} else if (precisely_equal(otherT, 1)) {
otherT = 1;
}
span.fOtherT = otherT;
span.fOtherIndex = otherIndex;
}
void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
init(pts, SkPath::kQuad_Verb, operand, evenOdd);
fBounds.setQuadBounds(pts);
}
// Defer all coincident edge processing until
// after normal intersections have been computed
// no need to be tricky; insert in normal T order
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear) {
if (precisely_zero(newT)) {
newT = 0;
} else if (precisely_equal(newT, 1)) {
newT = 1;
}
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
size_t tCount = fTs.count();
const SkPoint& firstPt = fPts[0];
const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
for (size_t index = 0; index < tCount; ++index) {
// OPTIMIZATION: if there are three or more identical Ts, then
// the fourth and following could be further insertion-sorted so
// that all the edges are clockwise or counterclockwise.
// This could later limit segment tests to the two adjacent
// neighbors, although it doesn't help with determining which
// circular direction to go in.
const SkOpSpan& span = fTs[index];
if (newT < span.fT) {
insertedAt = index;
break;
}
if (newT == span.fT) {
if (pt == span.fPt) {
insertedAt = index;
break;
}
if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
insertedAt = index;
break;
}
}
}
SkOpSpan* span;
if (insertedAt >= 0) {
span = fTs.insert(insertedAt);
} else {
insertedAt = tCount;
span = fTs.append();
}
span->fT = newT;
span->fOther = other;
span->fPt = pt;
span->fNear = isNear;
#if 0
// cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
&& approximately_equal(xyAtT(newT).fY, pt.fY));
#endif
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
span->fOppValue = 0;
span->fSmall = false;
span->fTiny = false;
span->fLoop = false;
if ((span->fDone = newT == 1)) {
++fDoneSpans;
}
span->fUnsortableStart = false;
span->fUnsortableEnd = false;
int less = -1;
while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) {
if (span[less].fDone) {
break;
}
double tInterval = newT - span[less].fT;
if (precisely_negative(tInterval)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tInterval / 2;
SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
if (!midPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
span[less].fSmall = true;
bool tiny = span[less].fPt == span->fPt;
span[less].fTiny = tiny;
span[less].fDone = true;
if (approximately_negative(newT - span[less].fT) && tiny) {
if (approximately_greater_than_one(newT)) {
SkASSERT(&span[less] - fTs.begin() < fTs.count());
span[less].fUnsortableStart = true;
if (&span[less - 1] - fTs.begin() >= 0) {
span[less - 1].fUnsortableEnd = true;
}
}
if (approximately_less_than_zero(span[less].fT)) {
SkASSERT(&span[less + 1] - fTs.begin() < fTs.count());
SkASSERT(&span[less] - fTs.begin() >= 0);
span[less + 1].fUnsortableStart = true;
span[less].fUnsortableEnd = true;
}
}
++fDoneSpans;
--less;
}
int more = 1;
while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
if (span[more - 1].fDone) {
break;
}
double tEndInterval = span[more].fT - newT;
if (precisely_negative(tEndInterval)) {
if ((span->fTiny = span[more].fTiny)) {
span->fDone = true;
++fDoneSpans;
}
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tEndInterval / 2;
SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
if (!midEndPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
span[more - 1].fSmall = true;
bool tiny = span[more].fPt == span->fPt;
span[more - 1].fTiny = tiny;
span[more - 1].fDone = true;
if (approximately_negative(span[more].fT - newT) && tiny) {
if (approximately_greater_than_one(span[more].fT)) {
span[more + 1].fUnsortableStart = true;
span[more].fUnsortableEnd = true;
}
if (approximately_less_than_zero(newT)) {
span[more].fUnsortableStart = true;
span[more - 1].fUnsortableEnd = true;
}
}
++fDoneSpans;
++more;
}
return insertedAt;
}
// set spans from start to end to decrement by one
// note this walks other backwards
// FIXME: there's probably an edge case that can be constructed where
// two span in one segment are separated by float epsilon on one span but
// not the other, if one segment is very small. For this
// case the counts asserted below may or may not be enough to separate the
// spans. Even if the counts work out, what if the spans aren't correctly
// sorted? It feels better in such a case to match the span's other span
// pointer since both coincident segments must contain the same spans.
// FIXME? It seems that decrementing by one will fail for complex paths that
// have three or more coincident edges. Shouldn't this subtract the difference
// between the winding values?
/* |--> |-->
this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4
other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0
^ ^ <--| <--|
startPt endPt test/oTest first pos test/oTest final pos
*/
void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
bool binary = fOperand != other->fOperand;
int index = 0;
while (startPt != fTs[index].fPt) {
SkASSERT(index < fTs.count());
++index;
}
while (index > 0 && fTs[index].fT == fTs[index - 1].fT) {
--index;
}
int oIndex = other->fTs.count();
while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match
SkASSERT(oIndex > 0);
}
double oStartT = other->fTs[oIndex].fT;
// look for first point beyond match
while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) {
SkASSERT(oIndex > 0);
}
SkOpSpan* test = &fTs[index];
SkOpSpan* oTest = &other->fTs[oIndex];
SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
do {
SkASSERT(test->fT < 1);
SkASSERT(oTest->fT < 1);
bool decrement = test->fWindValue && oTest->fWindValue;
bool track = test->fWindValue || oTest->fWindValue;
bool bigger = test->fWindValue >= oTest->fWindValue;
const SkPoint& testPt = test->fPt;
double testT = test->fT;
const SkPoint& oTestPt = oTest->fPt;
double oTestT = oTest->fT;
do {
if (decrement) {
if (binary && bigger) {
test->fOppValue--;
} else {
decrementSpan(test);
}
} else if (track) {
TrackOutsidePair(&outsidePts, testPt, oTestPt);
}
SkASSERT(index < fTs.count() - 1);
test = &fTs[++index];
} while (testPt == test->fPt || testT == test->fT);
SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
do {
SkASSERT(oTest->fT < 1);
SkASSERT(originalWindValue == oTest->fWindValue);
if (decrement) {
if (binary && !bigger) {
oTest->fOppValue--;
} else {
other->decrementSpan(oTest);
}
} else if (track) {
TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
}
if (!oIndex) {
break;
}
oTest = &other->fTs[--oIndex];
} while (oTestPt == oTest->fPt || oTestT == oTest->fT);
} while (endPt != test->fPt && test->fT < 1);
// FIXME: determine if canceled edges need outside ts added
int outCount = outsidePts.count();
if (!done() && outCount) {
addCancelOutsides(outsidePts[0], outsidePts[1], other);
if (outCount > 2) {
addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
}
}
if (!other->done() && oOutsidePts.count()) {
other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
}
}
int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
// if the tail nearly intersects itself but not quite, the caller records this separately
int result = addT(other, pt, newT, SkOpSpan::kPointIsExact);
SkOpSpan* span = &fTs[result];
span->fLoop = true;
return result;
}
void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
SkTArray<SkPoint, true>* outsideTs) {
int index = *indexPtr;
int oWindValue = oTest.fWindValue;
int oOppValue = oTest.fOppValue;
if (binary) {
SkTSwap<int>(oWindValue, oOppValue);
}
SkOpSpan* const test = &fTs[index];
SkOpSpan* end = test;
const SkPoint& oStartPt = oTest.fPt;
do {
if (bumpSpan(end, oWindValue, oOppValue)) {
TrackOutside(outsideTs, oStartPt);
}
end = &fTs[++index];
} while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1);
*indexPtr = index;
}
bool SkOpSegment::bumpCoincident(SkOpSpan* test, bool bigger, bool binary) {
if (bigger) {
if (binary) {
if (fOppXor) {
test->fOppValue ^= 1;
} else {
test->fOppValue++;
}
} else {
if (fXor) {
test->fWindValue ^= 1;
} else {
test->fWindValue++;
}
}
if (!test->fWindValue && !test->fOppValue) {
test->fDone = true;
++fDoneSpans;
return true;
}
return false;
}
return decrementSpan(test);
}
// because of the order in which coincidences are resolved, this and other
// may not have the same intermediate points. Compute the corresponding
// intermediate T values (using this as the master, other as the follower)
// and walk other conditionally -- hoping that it catches up in the end
void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
SkTArray<SkPoint, true>* oOutsidePts) {
int oIndex = *oIndexPtr;
SkOpSpan* const oTest = &fTs[oIndex];
SkOpSpan* oEnd = oTest;
const SkPoint& startPt = test.fPt;
const SkPoint& oStartPt = oTest->fPt;
double oStartT = oTest->fT;
if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
TrackOutside(oOutsidePts, startPt);
}
while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
zeroSpan(oEnd);
oEnd = &fTs[++oIndex];
}
*oIndexPtr = oIndex;
}
// FIXME: need to test this case:
// contourA has two segments that are coincident
// contourB has two segments that are coincident in the same place
// each ends up with +2/0 pairs for winding count
// since logic below doesn't transfer count (only increments/decrements) can this be
// resolved to +4/0 ?
// set spans from start to end to increment the greater by one and decrement
// the lesser
void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
SkOpSegment* other) {
bool binary = fOperand != other->fOperand;
int index = 0;
while (startPt != fTs[index].fPt) {
SkASSERT(index < fTs.count());
++index;
}
double startT = fTs[index].fT;
while (index > 0 && fTs[index - 1].fT == startT) {
--index;
}
int oIndex = 0;
while (startPt != other->fTs[oIndex].fPt) {
SkASSERT(oIndex < other->fTs.count());
++oIndex;
}
double oStartT = other->fTs[oIndex].fT;
while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) {
--oIndex;
}
SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
SkOpSpan* test = &fTs[index];
const SkPoint* testPt = &test->fPt;
double testT = test->fT;
SkOpSpan* oTest = &other->fTs[oIndex];
const SkPoint* oTestPt = &oTest->fPt;
SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
do {
SkASSERT(test->fT < 1);
SkASSERT(oTest->fT < 1);
#if 0
if (test->fDone || oTest->fDone) {
#else // consolidate the winding count even if done
if ((test->fWindValue == 0 && test->fOppValue == 0)
|| (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
#endif
SkDEBUGCODE(int firstWind = test->fWindValue);
SkDEBUGCODE(int firstOpp = test->fOppValue);
do {
SkASSERT(firstWind == fTs[index].fWindValue);
SkASSERT(firstOpp == fTs[index].fOppValue);
++index;
SkASSERT(index < fTs.count());
} while (*testPt == fTs[index].fPt);
SkDEBUGCODE(firstWind = oTest->fWindValue);
SkDEBUGCODE(firstOpp = oTest->fOppValue);
do {
SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
++oIndex;
SkASSERT(oIndex < other->fTs.count());
} while (*oTestPt == other->fTs[oIndex].fPt);
} else {
if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
} else {
other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
bumpCoincidentOther(*oTest, &index, &outsidePts);
}
}
test = &fTs[index];
testPt = &test->fPt;
testT = test->fT;
if (endPt == *testPt || endT == testT) {
break;
}
oTest = &other->fTs[oIndex];
oTestPt = &oTest->fPt;
SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
} while (endPt != *oTestPt);
if (endPt != *testPt && endT != testT) { // in rare cases, one may have ended before the other
int lastWind = test[-1].fWindValue;
int lastOpp = test[-1].fOppValue;
bool zero = lastWind == 0 && lastOpp == 0;
do {
if (test->fWindValue || test->fOppValue) {
test->fWindValue = lastWind;
test->fOppValue = lastOpp;
if (zero) {
test->fDone = true;
++fDoneSpans;
}
}
test = &fTs[++index];
testPt = &test->fPt;
} while (endPt != *testPt);
}
int outCount = outsidePts.count();
if (!done() && outCount) {
addCoinOutsides(outsidePts[0], endPt, other);
}
if (!other->done() && oOutsidePts.count()) {
other->addCoinOutsides(oOutsidePts[0], endPt, this);
}
}
// FIXME: this doesn't prevent the same span from being added twice
// fix in caller, SkASSERT here?
void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
const SkPoint& pt) {
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const SkOpSpan& span = fTs[tIndex];
if (!approximately_negative(span.fT - t)) {
break;
}
if (approximately_negative(span.fT - t) && span.fOther == other
&& approximately_equal(span.fOtherT, otherT)) {
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
return;
}
}
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
int insertedAt = addT(other, pt, t, SkOpSpan::kPointIsExact);
int otherInsertedAt = other->addT(this, pt, otherT, SkOpSpan::kPointIsExact);
addOtherT(insertedAt, otherT, otherInsertedAt);
other->addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
}
void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const {
// add edge leading into junction
int min = SkMin32(end, start);
if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
addAngle(angles, end, start);
}
// add edge leading away from junction
int step = SkSign32(end - start);
int tIndex = nextExactSpan(end, step);
min = SkMin32(end, tIndex);
if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
addAngle(angles, end, tIndex);
}
}
SkOpSegment::MissingSpan::Command SkOpSegment::adjustThisNear(double startT, const SkPoint& startPt,
const SkPoint& endPt, SkTArray<MissingSpan, true>* missingSpans) {
// see if endPt exists on this curve, and if it has the same t or a different T than the startT
int count = this->count();
SkASSERT(count > 0);
int startIndex, endIndex, step;
if (startT == 0) {
startIndex = 0;
endIndex = count;
step = 1;
} else {
SkASSERT(startT == 1);
startIndex = count - 1;
endIndex = -1;
step = -1;
}
int index = startIndex;
do {
const SkOpSpan& span = fTs[index];
if (span.fPt != endPt) {
continue;
}
if (span.fT == startT) {
// check to see if otherT matches some other mid curve intersection
int inner = startIndex;
do {
if (inner == index) {
continue;
}
const SkOpSpan& matchSpan = fTs[inner];
double matchT = span.fOther->missingNear(span.fOtherT, matchSpan.fOther, startPt,
endPt);
if (matchT >= 0) {
SkASSERT(missingSpans);
MissingSpan& missingSpan = missingSpans->push_back();
SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
missingSpan.fCommand = MissingSpan::kRemoveNear;
missingSpan.fT = startT;
missingSpan.fSegment = this;
missingSpan.fOther = span.fOther;
missingSpan.fOtherT = matchT;
return missingSpan.fCommand;
}
} while ((inner += step) != endIndex);
break;
}
double midT = (startT + span.fT) / 2;
if (betweenPoints(midT, startPt, endPt)) {
if (!missingSpans) {
return MissingSpan::kZeroSpan;
}
MissingSpan& missingSpan = missingSpans->push_back();
SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
missingSpan.fCommand = MissingSpan::kZeroSpan;
missingSpan.fT = SkTMin(startT, span.fT);
missingSpan.fEndT = SkTMax(startT, span.fT);
missingSpan.fSegment = this;
return missingSpan.fCommand;
}
} while ((index += step) != endIndex);
return MissingSpan::kNoAction;
}
void SkOpSegment::adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
SkTArray<MissingSpan, true>* missingSpans) {
int count = this->count();
SkASSERT(count > 0);
int startIndex, endIndex, step;
if (startT == 0) {
startIndex = 0;
endIndex = count;
step = 1;
} else {
SkASSERT(startT == 1);
startIndex = count - 1;
endIndex = -1;
step = -1;
}
int index = startIndex;
do {
const SkOpSpan& span = fTs[index];
if (span.fT != startT) {
return;
}
SkOpSegment* other = span.fOther;
if (other->fPts[0] == endPt) {
other->adjustThisNear(0, endPt, startPt, missingSpans);
} else if (other->fPts[0] == startPt) {
other->adjustThisNear(0, startPt, endPt, missingSpans);
}
if (other->ptAtT(1) == endPt) {
other->adjustThisNear(1, endPt, startPt, missingSpans);
} else if (other->ptAtT(1) == startPt) {
other->adjustThisNear(1, startPt, endPt, missingSpans);
}
} while ((index += step) != endIndex);
}
void SkOpSegment::adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
SkTArray<MissingSpan, true>* missingSpans) {
int count = missingSpans->count();
for (int index = 0; index < count; ) {
MissingSpan& missing = (*missingSpans)[index];
SkOpSegment* other = missing.fOther;
MissingSpan::Command command = MissingSpan::kNoAction;
if (missing.fPt == startPt) {
if (missingNear(missing.fT, other, startPt, endPt) >= 0) {
command = MissingSpan::kZeroSpan;
} else if (other->ptAtT(0) == endPt) {
command = other->adjustThisNear(0, endPt, startPt, NULL);
} else if (other->ptAtT(1) == endPt) {
command = other->adjustThisNear(1, endPt, startPt, NULL);
}
} else if (missing.fPt == endPt) {
if (missingNear(missing.fT, other, endPt, startPt) >= 0) {
command = MissingSpan::kZeroSpan;
} else if (other->ptAtT(0) == startPt) {
command = other->adjustThisNear(0, startPt, endPt, NULL);
} else if (other->ptAtT(1) == startPt) {
command = other->adjustThisNear(1, startPt, endPt, NULL);
}
}
if (command == MissingSpan::kZeroSpan) {
#if 1
missing = missingSpans->back();
missingSpans->pop_back();
#else // if this is supported in the future ...
missingSpans->removeShuffle(index);
#endif
--count;
continue;
}
++index;
}
}
void SkOpSegment::adjustNear(double startT, const SkPoint& endPt,
SkTArray<MissingSpan, true>* missingSpans) {
const SkPoint startPt = ptAtT(startT);
adjustMissingNear(startPt, endPt, missingSpans);
adjustThisNear(startT, startPt, endPt, missingSpans);
adjustOtherNear(startT, startPt, endPt, missingSpans);
}
int SkOpSegment::advanceCoincidentThis(int index) {
SkOpSpan* const test = &fTs[index];
SkOpSpan* end;
do {
end = &fTs[++index];
} while (approximately_negative(end->fT - test->fT));
return index;
}
int SkOpSegment::advanceCoincidentOther(double oEndT, int oIndex) {
SkOpSpan* const oTest = &fTs[oIndex];
SkOpSpan* oEnd = oTest;
const double oStartT = oTest->fT;
while (!approximately_negative(oEndT - oEnd->fT)
&& approximately_negative(oEnd->fT - oStartT)) {
oEnd = &fTs[++oIndex];
}
return oIndex;
}
bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
const SkPoint midPt = ptAtT(midT);
SkPathOpsBounds bounds;
bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
bounds.sort();
return bounds.almostContains(midPt);
}
bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
if (lesser > greater) {
SkTSwap<int>(lesser, greater);
}
return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
}
// note that this follows the same logic flow as active angle
bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const {
double referenceT = fTs[index].fT;
const SkPoint& referencePt = fTs[index].fPt;
int lesser = index;
while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand)
&& (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
if (++index == fTs.count()) {
break;
}
if (!allowOpp && fTs[index].fOther->fOperand != fOperand) {
break;
}
if (fTs[index - 1].fTiny) {
referenceT = fTs[index].fT;
continue;
}
if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) {
// FIXME
// testQuad8 generates the wrong output unless false is returned here. Other tests will
// take this path although they aren't required to. This means that many go much slower
// because of this sort fail.
// SkDebugf("!!!\n");
return false;
}
} while (precisely_negative(fTs[index].fT - referenceT));
return true;
}
void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const {
const SkOpSpan* span = &fTs[index];
SkOpSegment* other = span->fOther;
// if there is only one live crossing, and no coincidence, continue
// in the same direction
// if there is coincidence, the only choice may be to reverse direction
// find edge on either side of intersection
int oIndex = span->fOtherIndex;
// if done == -1, prior span has already been processed
int step = 1;
int next = other->nextExactSpan(oIndex, step);
if (next < 0) {
step = -step;
next = other->nextExactSpan(oIndex, step);
}
// add candidate into and away from junction
other->addTwoAngles(next, oIndex, angles);
}
int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) {
addTwoAngles(startIndex, endIndex, angles);
if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) {
return SK_NaN32;
}
int angleCount = angles->count();
// abort early before sorting if an unsortable (not an unorderable) angle is found
if (includeType != SkOpAngle::kUnaryXor) {
int firstIndex = -1;
while (++firstIndex < angleCount) {
const SkOpAngle& angle = (*angles)[firstIndex];
if (angle.segment()->windSum(&angle) != SK_MinS32) {
break;
}
}
if (firstIndex == angleCount) {
return SK_MinS32;
}
}
bool sortable = SortAngles2(*angles, sorted);
#if DEBUG_SORT_RAW
if (sorted->count() > 0) {
(*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable);
}
#endif
if (!sortable) {
return SK_NaN32;
}
if (includeType == SkOpAngle::kUnaryXor) {
return SK_MinS32;
}
// if all angles have a computed winding,
// or if no adjacent angles are orderable,
// or if adjacent orderable angles have no computed winding,
// there's nothing to do
// if two orderable angles are adjacent, and one has winding computed, transfer to the other
const SkOpAngle* baseAngle = NULL;
int last = angleCount;
int finalInitialOrderable = -1;
bool tryReverse = false;
// look for counterclockwise transfers
do {
int index = 0;
do {
SkOpAngle* testAngle = (*sorted)[index];
int testWinding = testAngle->segment()->windSum(testAngle);
if (SK_MinS32 != testWinding && !testAngle->unorderable()) {
baseAngle = testAngle;
continue;
}
if (testAngle->unorderable()) {
baseAngle = NULL;
tryReverse = true;
continue;
}
if (baseAngle) {
ComputeOneSum(baseAngle, testAngle, includeType);
baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
: NULL;
tryReverse |= !baseAngle;
continue;
}
if (finalInitialOrderable + 1 == index) {
finalInitialOrderable = index;
}
} while (++index != last);
if (finalInitialOrderable < 0) {
break;
}
last = finalInitialOrderable + 1;
finalInitialOrderable = -2; // make this always negative the second time through
} while (baseAngle);
if (tryReverse) {
baseAngle = NULL;
last = 0;
finalInitialOrderable = angleCount;
do {
int index = angleCount;
while (--index >= last) {
SkOpAngle* testAngle = (*sorted)[index];
int testWinding = testAngle->segment()->windSum(testAngle);
if (SK_MinS32 != testWinding) {
baseAngle = testAngle;
continue;
}
if (testAngle->unorderable()) {
baseAngle = NULL;
continue;
}
if (baseAngle) {
ComputeOneSumReverse(baseAngle, testAngle, includeType);
baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
: NULL;
continue;
}
if (finalInitialOrderable - 1 == index) {
finalInitialOrderable = index;
}
}
if (finalInitialOrderable >= angleCount) {
break;
}
last = finalInitialOrderable;
finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through
} while (baseAngle);
}
int minIndex = SkMin32(startIndex, endIndex);
return windSum(minIndex);
}
void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType includeType) {
const SkOpSegment* baseSegment = baseAngle->segment();
int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
int sumSuWinding;
bool binary = includeType >= SkOpAngle::kBinarySingle;
if (binary) {
sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
if (baseSegment->operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
}
SkOpSegment* nextSegment = nextAngle->segment();
int maxWinding, sumWinding;
SkOpSpan* last;
if (binary) {
int oppMaxWinding, oppSumWinding;
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
&sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
true, nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
&maxWinding, &sumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
}
nextAngle->setLastMarked(last);
}
void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType includeType) {
const SkOpSegment* baseSegment = baseAngle->segment();
int sumMiWinding = baseSegment->updateWinding(baseAngle);
int sumSuWinding;
bool binary = includeType >= SkOpAngle::kBinarySingle;
if (binary) {
sumSuWinding = baseSegment->updateOppWinding(baseAngle);
if (baseSegment->operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
}
SkOpSegment* nextSegment = nextAngle->segment();
int maxWinding, sumWinding;
SkOpSpan* last;
if (binary) {
int oppMaxWinding, oppSumWinding;
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
&sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
true, nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
&maxWinding, &sumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
}
nextAngle->setLastMarked(last);
}
int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
bool* hitSomething, double mid, bool opp, bool current) const {
SkScalar bottom = fBounds.fBottom;
int bestTIndex = -1;
if (bottom <= *bestY) {
return bestTIndex;
}
SkScalar top = fBounds.fTop;
if (top >= basePt.fY) {
return bestTIndex;
}
if (fBounds.fLeft > basePt.fX) {
return bestTIndex;
}
if (fBounds.fRight < basePt.fX) {
return bestTIndex;
}
if (fBounds.fLeft == fBounds.fRight) {
// if vertical, and directly above test point, wait for another one
return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
}
// intersect ray starting at basePt with edge
SkIntersections intersections;
// 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 = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
(fPts, top, bottom, basePt.fX, false);
if (pts == 0 || (current && pts == 1)) {
return bestTIndex;
}
if (current) {
SkASSERT(pts > 1);
int closestIdx = 0;
double closest = fabs(intersections[0][0] - mid);
for (int idx = 1; idx < pts; ++idx) {
double test = fabs(intersections[0][idx] - mid);
if (closest > test) {
closestIdx = idx;
closest = test;
}
}
intersections.quickRemoveOne(closestIdx, --pts);
}
double bestT = -1;
for (int index = 0; index < pts; ++index) {
double foundT = intersections[0][index];
if (approximately_less_than_zero(foundT)
|| approximately_greater_than_one(foundT)) {
continue;
}
SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
if (approximately_negative(testY - *bestY)
|| approximately_negative(basePt.fY - testY)) {
continue;
}
if (pts > 1 && fVerb == SkPath::kLine_Verb) {
return SK_MinS32; // if the intersection is edge on, wait for another one
}
if (fVerb > SkPath::kLine_Verb) {
SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
if (approximately_zero(dx)) {
return SK_MinS32; // hit vertical, wait for another one
}
}
*bestY = testY;
bestT = foundT;
}
if (bestT < 0) {
return bestTIndex;
}
SkASSERT(bestT >= 0);
SkASSERT(bestT <= 1);
int start;
int end = 0;
do {
start = end;
end = nextSpan(start, 1);
} while (fTs[end].fT < bestT);
// FIXME: see next candidate for a better pattern to find the next start/end pair
while (start + 1 < end && fTs[start].fDone) {
++start;
}
if (!isCanceled(start)) {
*hitT = bestT;
bestTIndex = start;
*hitSomething = true;
}
return bestTIndex;
}
bool SkOpSegment::decrementSpan(SkOpSpan* span) {
SkASSERT(span->fWindValue > 0);
if (--(span->fWindValue) == 0) {
if (!span->fOppValue && !span->fDone) {
span->fDone = true;
++fDoneSpans;
return true;
}
}
return false;
}
bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
SkASSERT(!span->fDone || span->fTiny || span->fSmall);
span->fWindValue += windDelta;
SkASSERT(span->fWindValue >= 0);
span->fOppValue += oppDelta;
SkASSERT(span->fOppValue >= 0);
if (fXor) {
span->fWindValue &= 1;
}
if (fOppXor) {
span->fOppValue &= 1;
}
if (!span->fWindValue && !span->fOppValue) {
span->fDone = true;
++fDoneSpans;
return true;
}
return false;
}
// look to see if the curve end intersects an intermediary that intersects the other
void SkOpSegment::checkEnds() {
debugValidate();
SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
int count = fTs.count();
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
double otherT = span.fOtherT;
if (otherT != 0 && otherT != 1) { // only check ends
continue;
}
const SkOpSegment* other = span.fOther;
// peek start/last describe the range of spans that match the other t of this span
int peekStart = span.fOtherIndex;
while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
;
int otherCount = other->fTs.count();
int peekLast = span.fOtherIndex;
while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
;
if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
continue;
}
// t start/last describe the range of spans that match the t of this span
double t = span.fT;
int tStart = index;
while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny))
;
int tLast = index;
while (fTs[tLast].fTiny) {
++tLast;
}
while (++tLast < count && t == fTs[tLast].fT)
;
for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
continue;
}
const SkOpSpan& peekSpan = other->fTs[peekIndex];
SkOpSegment* match = peekSpan.fOther;
if (match->done()) {
continue; // if the edge has already been eaten (likely coincidence), ignore it
}
const double matchT = peekSpan.fOtherT;
// see if any of the spans match the other spans
for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
const SkOpSpan& tSpan = fTs[tIndex];
if (tSpan.fOther == match) {
if (tSpan.fOtherT == matchT) {
goto nextPeekIndex;
}
double midT = (tSpan.fOtherT + matchT) / 2;
if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
goto nextPeekIndex;
}
}
}
if (missingSpans.count() > 0) {
const MissingSpan& lastMissing = missingSpans.back();
if (lastMissing.fCommand == MissingSpan::kAddMissing
&& lastMissing.fT == t
&& lastMissing.fOther == match
&& lastMissing.fOtherT == matchT) {
SkASSERT(lastMissing.fPt == peekSpan.fPt);
continue;
}
}
#if DEBUG_CHECK_ENDS
SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
__FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
#endif
// this segment is missing a entry that the other contains
// remember so we can add the missing one and recompute the indices
{
MissingSpan& missing = missingSpans.push_back();
SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
missing.fCommand = MissingSpan::kAddMissing;
missing.fT = t;
missing.fOther = match;
missing.fOtherT = matchT;
missing.fPt = peekSpan.fPt;
}
break;
nextPeekIndex:
;
}
}
if (missingSpans.count() == 0) {
debugValidate();
return;
}
// if one end is near the other point, look for a coincident span
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
if (span.fT > 0) {
break;
}
const SkOpSpan& otherSpan = span.fOther->span(span.fOtherIndex);
if (span.fNear) {
SkASSERT(otherSpan.fPt == fPts[0]);
adjustNear(0, span.fPt, &missingSpans);
continue;
}
if (otherSpan.fNear) {
SkASSERT(span.fPt == fPts[0]);
adjustNear(0, otherSpan.fPt, &missingSpans);
}
}
for (int index = count; --index >= 0; ) {
const SkOpSpan& span = fTs[index];
if (span.fT < 1) {
break;
}
const SkOpSegment* other = span.fOther;
if (span.fNear) {
SkASSERT(other->ptAtT(span.fOtherT) == ptAtT(1));
const SkPoint& otherPt = other->xyAtT(span.fOtherIndex);
SkASSERT(otherPt != ptAtT(1));
adjustNear(1, otherPt, &missingSpans);
continue;
}
const SkOpSpan& otherSpan = other->span(span.fOtherIndex);
if (otherSpan.fNear) {
SkASSERT(otherSpan.fPt == ptAtT(1));
SkPoint otherPt = other->ptAtT(span.fOtherT);
SkASSERT(otherPt != ptAtT(1));
adjustNear(1, otherPt, &missingSpans);
}
}
debugValidate();
int missingCount = missingSpans.count();
for (int index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
switch (missing.fCommand) {
case MissingSpan::kNoAction:
break;
case MissingSpan::kAddMissing:
addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
break;
case MissingSpan::kRemoveNear: {
SkOpSegment* segment = missing.fSegment;
int count = segment->count();
for (int inner = 0; inner < count; ++inner) {
const SkOpSpan& span = segment->span(inner);
if (span.fT != missing.fT && span.fOther != missing.fOther) {
continue;
}
SkASSERT(span.fNear);
SkOpSegment* other = span.fOther;
int otherCount = other->count();
for (int otherIndex = 0; otherIndex < otherCount; ++otherIndex) {
const SkOpSpan& otherSpan = other->span(otherIndex);
if (otherSpan.fT == span.fOtherT && otherSpan.fOther == segment
&& otherSpan.fOtherT == span.fT) {
if (otherSpan.fDone) {
other->fDoneSpans--;
}
other->fTs.remove(otherIndex);
// FIXME: remove may leave a tiny dangling -- recompute tiny w/index
break;
}
}
if (span.fDone) {
segment->fDoneSpans--;
}
segment->fTs.remove(inner);
// FIXME: remove may leave a tiny dangling -- recompute tiny w/index
break;
}
break;
}
case MissingSpan::kZeroSpan: {
SkOpSegment* segment = missing.fSegment;
int count = segment->count();
for (int inner = 0; inner < count; ++inner) {
SkOpSpan& span = segment->fTs[inner];
if (span.fT < missing.fT) {
continue;
}
if (span.fT >= missing.fEndT) {
break;
}
span.fWindValue = span.fOppValue = 0;
if (!span.fDone) {
span.fDone = true;
++segment->fDoneSpans;
}
}
break;
}
}
}
fixOtherTIndex();
// OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
// avoid this
for (int index = 0; index < missingCount; ++index) {
const MissingSpan& missing = missingSpans[index];
switch (missing.fCommand) {
case MissingSpan::kNoAction:
break;
case MissingSpan::kAddMissing:
missing.fOther->fixOtherTIndex();
break;
case MissingSpan::kRemoveNear:
missing.fSegment->fixOtherTIndex();
missing.fOther->fixOtherTIndex();
break;
case MissingSpan::kZeroSpan:
break;
}
}
debugValidate();
}
bool SkOpSegment::checkSmall(int index) const {
if (fTs[index].fSmall) {
return true;
}
double tBase = fTs[index].fT;
while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
;
return fTs[index].fSmall;
}
// if pair of spans on either side of tiny have the same end point and mid point, mark
// them as parallel
// OPTIMIZATION : mark the segment to note that some span is tiny
void SkOpSegment::checkTiny() {
SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
SkOpSpan* thisSpan = fTs.begin() - 1;
const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny
while (++thisSpan < endSpan) {
if (!thisSpan->fTiny) {
continue;
}
SkOpSpan* nextSpan = thisSpan + 1;
double thisT = thisSpan->fT;
double nextT = nextSpan->fT;
if (thisT == nextT) {
continue;
}
SkASSERT(thisT < nextT);
SkASSERT(thisSpan->fPt == nextSpan->fPt);
SkOpSegment* thisOther = thisSpan->fOther;
SkOpSegment* nextOther = nextSpan->fOther;
int oIndex = thisSpan->fOtherIndex;
for (int oStep = -1; oStep <= 1; oStep += 2) {
int oEnd = thisOther->nextExactSpan(oIndex, oStep);
if (oEnd < 0) {
continue;
}
const SkOpSpan& oSpan = thisOther->span(oEnd);
int nIndex = nextSpan->fOtherIndex;
for (int nStep = -1; nStep <= 1; nStep += 2) {
int nEnd = nextOther->nextExactSpan(nIndex, nStep);
if (nEnd < 0) {
continue;
}
const SkOpSpan& nSpan = nextOther->span(nEnd);
if (oSpan.fPt != nSpan.fPt) {
continue;
}
double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
const SkPoint& oPt = thisOther->ptAtT(oMidT);
double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
const SkPoint& nPt = nextOther->ptAtT(nMidT);
if (!AlmostEqualUlps(oPt, nPt)) {
continue;
}
#if DEBUG_CHECK_TINY
SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
thisOther->fID, nextOther->fID);
#endif
// this segment is missing a entry that the other contains
// remember so we can add the missing one and recompute the indices
MissingSpan& missing = missingSpans.push_back();
SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
missing.fCommand = MissingSpan::kAddMissing;
missing.fSegment = thisOther;
missing.fT = thisSpan->fOtherT;
missing.fOther = nextOther;
missing.fOtherT = nextSpan->fOtherT;
missing.fPt = thisSpan->fPt;
}
}
}
int missingCount = missingSpans.count();
if (!missingCount) {
return;
}
for (int index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
}
for (int index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
missing.fSegment->fixOtherTIndex();
missing.fOther->fixOtherTIndex();
}
}
/*
The M and S variable name parts stand for the operators.
Mi stands for Minuend (see wiki subtraction, analogous to difference)
Su stands for Subtrahend
The Opp variable name part designates that the value is for the Opposite operator.
Opposite values result from combining coincident spans.
*/
SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable, SkPathOp op, const int xorMiMask,
const int xorSuMask) {
const int startIndex = *nextStart;
const int endIndex = *nextEnd;
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(const int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
const int step = SkSign32(endIndex - startIndex);
const int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
SkOpSpan* endSpan = &fTs[end];
SkOpSegment* other;
if (isSimple(end)) {
// mark the smaller of startIndex, endIndex done, and all adjacent
// spans with the same T value (but not 'other' spans)
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
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;
*nextEnd = *nextStart;
do {
*nextEnd += step;
} while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
*unsortable = true;
return NULL;
}
return other;
}
// more than one viable candidate -- measure angles to find best
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
bool sortable = calcWinding != SK_NaN32;
if (sortable && sorted.count() == 0) {
// if no edge has a computed winding sum, we can go no further
*unsortable = true;
return NULL;
}
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
if (!sortable) {
*unsortable = true;
return NULL;
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
sorted[firstIndex]->sign());
#endif
int sumMiWinding = updateWinding(endIndex, startIndex);
int sumSuWinding = updateOppWinding(endIndex, startIndex);
if (operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const SkOpAngle* foundAngle = NULL;
bool foundDone = false;
// iterate through the angle, and compute everyone's winding
SkOpSegment* nextSegment;
int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
nextIndex = 0;
}
const SkOpAngle* nextAngle = sorted[nextIndex];
nextSegment = nextAngle->segment();
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
nextAngle->end(), op, &sumMiWinding, &sumSuWinding,
&maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle);
}
}
if (nextSegment->done()) {
continue;
}
if (nextSegment->isTiny(nextAngle)) {
continue;
}
if (!activeAngle) {
nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
}
SkOpSpan* last = nextAngle->lastMarked();
if (last) {
*chase->append() = last;
#if DEBUG_WINDING
SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
last->fSmall);
#endif
}
} while (++nextIndex != lastIndex);
markDoneBinary(SkMin32(startIndex, endIndex));
if (!foundAngle) {
return NULL;
}
*nextStart = foundAngle->start();
*nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
#if DEBUG_WINDING
SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
__FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
#endif
return nextSegment;
}
SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
int* nextEnd, bool* unsortable) {
const int startIndex = *nextStart;
const int endIndex = *nextEnd;
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(const int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
const int step = SkSign32(endIndex - startIndex);
const int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
SkOpSpan* endSpan = &fTs[end];
SkOpSegment* other;
if (isSimple(end)) {
// mark the smaller of startIndex, endIndex done, and all adjacent
// spans with the same T value (but not 'other' spans)
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
int min = SkMin32(startIndex, endIndex);
if (fTs[min].fDone) {
return NULL;
}
markDoneUnary(min);
other = endSpan->fOther;
*nextStart = endSpan->fOtherIndex;
double startT = other->fTs[*nextStart].fT;
*nextEnd = *nextStart;
do {
*nextEnd += step;
} while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
*unsortable = true;
return NULL;
}
return other;
}
// more than one viable candidate -- measure angles to find best
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted);
bool sortable = calcWinding != SK_NaN32;
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
if (!sortable) {
*unsortable = true;
return NULL;
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
sorted[firstIndex]->sign());
#endif
int sumWinding = updateWinding(endIndex, startIndex);
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const SkOpAngle* foundAngle = NULL;
bool foundDone = false;
// iterate through the angle, and compute everyone's winding
SkOpSegment* nextSegment;
int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
nextIndex = 0;
}
const SkOpAngle* nextAngle = sorted[nextIndex];
nextSegment = nextAngle->segment();
int maxWinding;
bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
&maxWinding, &sumWinding);
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle);
}
}
if (nextSegment->done()) {
continue;
}
if (nextSegment->isTiny(nextAngle)) {
continue;
}
if (!activeAngle) {
nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
}
SkOpSpan* last = nextAngle->lastMarked();
if (last) {
*chase->append() = last;
#if DEBUG_WINDING
SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
last->fSmall);
#endif
}
} while (++nextIndex != lastIndex);
markDoneUnary(SkMin32(startIndex, endIndex));
if (!foundAngle) {
return NULL;
}
*nextStart = foundAngle->start();
*nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
#if DEBUG_WINDING
SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
__FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
#endif
return nextSegment;
}
SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
const int startIndex = *nextStart;
const int endIndex = *nextEnd;
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
int step = SkSign32(endIndex - startIndex);
int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
SkOpSpan* endSpan = &fTs[end];
SkOpSegment* other;
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;
// FIXME: I don't know why the logic here is difference from the winding case
SkDEBUGCODE(bool firstLoop = true;)
if ((approximately_less_than_zero(startT) && step < 0)
|| (approximately_greater_than_one(startT) && step > 0)) {
step = -step;
SkDEBUGCODE(firstLoop = false;)
}
do {
*nextEnd = *nextStart;
do {
*nextEnd += step;
} while (precisely_zero(startT - other->fTs[*nextEnd].fT));
if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
break;
}
SkASSERT(firstLoop);
SkDEBUGCODE(firstLoop = false;)
step = -step;
} while (true);
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
return other;
}
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted);
bool sortable = calcWinding != SK_NaN32;
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
#endif
if (!sortable) {
*unsortable = true;
return NULL;
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
sorted[firstIndex]->sign());
#endif
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const SkOpAngle* foundAngle = NULL;
bool foundDone = false;
SkOpSegment* nextSegment;
int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
nextIndex = 0;
}
const SkOpAngle* nextAngle = sorted[nextIndex];
nextSegment = nextAngle->segment();
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
return NULL;
}
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle);
}
if (nextSegment->done()) {
continue;
}
} while (++nextIndex != lastIndex);
markDone(SkMin32(startIndex, endIndex), 1);
if (!foundAngle) {
return NULL;
}
*nextStart = foundAngle->start();
*nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
#if DEBUG_WINDING
SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
__FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
#endif
return nextSegment;
}
int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) {
int angleCount = sorted.count();
int firstIndex = -1;
for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
const SkOpAngle* angle = sorted[angleIndex];
if (angle->segment() == this && angle->start() == end &&
angle->end() == start) {
firstIndex = angleIndex;
break;
}
}
return firstIndex;
}
// FIXME: either:
// a) mark spans with either end unsortable as done, or
// b) rewrite findTop / findTopSegment / findTopContour to iterate further
// when encountering an unsortable span
// 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
SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, 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());
int firstT = -1;
/* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);
if (firstT < 0) {
*unsortable = true;
firstT = 0;
while (fTs[firstT].fDone) {
SkASSERT(firstT < fTs.count());
++firstT;
}
*tIndexPtr = firstT;
*endIndexPtr = nextExactSpan(firstT, 1);
return this;
}
// sort the edges to find the leftmost
int step = 1;
int end = nextSpan(firstT, step);
if (end == -1) {
step = -1;
end = nextSpan(firstT, step);
SkASSERT(end != -1);
}
// if the topmost T is not on end, or is three-way or more, find left
// look for left-ness from tLeft to firstT (matching y of other)
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(firstT - end != 0);
addTwoAngles(end, firstT, &angles);
if (!buildAngles(firstT, &angles, true) && onlySortable) {
// *unsortable = true;
// return NULL;
}
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
if (onlySortable && !sortable) {
*unsortable = true;
return NULL;
}
int first = SK_MaxS32;
SkScalar top = SK_ScalarMax;
int count = sorted.count();
for (int index = 0; index < count; ++index) {
const SkOpAngle* angle = sorted[index];
if (onlySortable && angle->unorderable()) {
continue;
}
SkOpSegment* next = angle->segment();
SkPathOpsBounds bounds;
next->subDivideBounds(angle->end(), angle->start(), &bounds);
if (approximately_greater(top, bounds.fTop)) {
top = bounds.fTop;
first = index;
}
}
SkASSERT(first < SK_MaxS32);
#if DEBUG_SORT // || DEBUG_SWAP_TOP
sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
#endif
// skip edges that have already been processed
firstT = first - 1;
SkOpSegment* leftSegment;
do {
if (++firstT == count) {
firstT = 0;
}
const SkOpAngle* angle = sorted[firstT];
SkASSERT(!onlySortable || !angle->unsortable());
leftSegment = angle->segment();
*tIndexPtr = angle->end();
*endIndexPtr = angle->start();
} while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone);
if (leftSegment->verb() >= SkPath::kQuad_Verb) {
const int tIndex = *tIndexPtr;
const int endIndex = *endIndexPtr;
if (!leftSegment->clockwise(tIndex, endIndex)) {
bool swap = !leftSegment->monotonicInY(tIndex, endIndex)
&& !leftSegment->serpentine(tIndex, endIndex);
#if DEBUG_SWAP_TOP
SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__,
swap,
leftSegment->serpentine(tIndex, endIndex),
leftSegment->controlsContainedByEnds(tIndex, endIndex),
leftSegment->monotonicInY(tIndex, endIndex));
#endif
if (swap) {
// FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
// sorted but merely the first not already processed (i.e., not done)
SkTSwap(*tIndexPtr, *endIndexPtr);
}
}
}
SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
return leftSegment;
}
// FIXME: not crazy about this
// when the intersections are performed, the other index is into an
// incomplete array. As the array grows, the indices become incorrect
// while the following fixes the indices up again, it isn't smart about
// skipping segments whose indices are already correct
// assuming we leave the code that wrote the index in the first place
// FIXME: if called after remove, this needs to correct tiny
void SkOpSegment::fixOtherTIndex() {
int iCount = fTs.count();
for (int i = 0; i < iCount; ++i) {
SkOpSpan& iSpan = fTs[i];
double oT = iSpan.fOtherT;
SkOpSegment* other = iSpan.fOther;
int oCount = other->fTs.count();
SkDEBUGCODE(iSpan.fOtherIndex = -1);
for (int o = 0; o < oCount; ++o) {
SkOpSpan& oSpan = other->fTs[o];
if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
iSpan.fOtherIndex = o;
oSpan.fOtherIndex = i;
break;
}
}
SkASSERT(iSpan.fOtherIndex >= 0);
}
}
void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
fDoneSpans = 0;
fOperand = operand;
fXor = evenOdd;
fPts = pts;
fVerb = verb;
}
void SkOpSegment::initWinding(int start, int end) {
int local = spanSign(start, end);
int oppLocal = oppSign(start, end);
(void) markAndChaseWinding(start, end, local, oppLocal);
// OPTIMIZATION: the reverse mark and chase could skip the first marking
(void) markAndChaseWinding(end, start, local, oppLocal);
}
/*
when we start with a vertical intersect, we try to use the dx to determine if the edge is to
the left or the right of vertical. This determines if we need to add the span's
sign or not. However, this isn't enough.
If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
from has the same x direction as this span, the winding should change. If the dx is opposite, then
the same winding is shared by both.
*/
void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
int oppWind, SkScalar hitOppDx) {
SkASSERT(hitDx || !winding);
SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
SkASSERT(dx);
int windVal = windValue(SkMin32(start, end));
#if DEBUG_WINDING_AT_T
SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
#endif
if (!winding) {
winding = dx < 0 ? windVal : -windVal;
} else if (winding * dx < 0) {
int sideWind = winding + (dx < 0 ? windVal : -windVal);
if (abs(winding) < abs(sideWind)) {
winding = sideWind;
}
}
#if DEBUG_WINDING_AT_T
SkDebugf(" winding=%d\n", winding);
#endif
SkDEBUGCODE(int oppLocal = oppSign(start, end));
SkASSERT(hitOppDx || !oppWind || !oppLocal);
int oppWindVal = oppValue(SkMin32(start, end));
if (!oppWind) {
oppWind = dx < 0 ? oppWindVal : -oppWindVal;
} else if (hitOppDx * dx >= 0) {
int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
if (abs(oppWind) < abs(oppSideWind)) {
oppWind = oppSideWind;
}
}
(void) markAndChaseWinding(start, end, winding, oppWind);
// OPTIMIZATION: the reverse mark and chase could skip the first marking
(void) markAndChaseWinding(end, start, winding, oppWind);
}
// OPTIMIZE: successive calls could start were the last leaves off
// or calls could specialize to walk forwards or backwards
bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
size_t tCount = fTs.count();
for (size_t index = 0; index < tCount; ++index) {
const SkOpSpan& span = fTs[index];
if (approximately_zero(startT - span.fT) && pt == span.fPt) {
return