blob: 1fb5afa028af33e894a82fe890e8b03af185f52a [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 "SkOpContour.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
};
const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done,
bool* sortable) const {
if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) {
return result;
}
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0
&& (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) {
return result;
}
}
do {
if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) {
return result;
}
if (++index == fTs.count()) {
break;
}
if (fTs[index - 1].fTiny) {
referenceT = fTs[index].fT;
continue;
}
} while (precisely_negative(fTs[index].fT - referenceT));
return NULL;
}
const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done,
bool* sortable) const {
int next = nextExactSpan(index, 1);
if (next > 0) {
const SkOpSpan& upSpan = fTs[index];
if (upSpan.fWindValue || upSpan.fOppValue) {
if (*end < 0) {
*start = index;
*end = next;
}
if (!upSpan.fDone) {
if (upSpan.fWindSum != SK_MinS32) {
return spanToAngle(index, next);
}
*done = false;
}
} else {
SkASSERT(upSpan.fDone);
}
}
int prev = nextExactSpan(index, -1);
// edge leading into junction
if (prev >= 0) {
const SkOpSpan& downSpan = fTs[prev];
if (downSpan.fWindValue || downSpan.fOppValue) {
if (*end < 0) {
*start = index;
*end = prev;
}
if (!downSpan.fDone) {
if (downSpan.fWindSum != SK_MinS32) {
return spanToAngle(index, prev);
}
*done = false;
}
} else {
SkASSERT(downSpan.fDone);
}
}
return NULL;
}
const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done,
bool* sortable) const {
const SkOpSpan* span = &fTs[index];
SkOpSegment* other = span->fOther;
int oIndex = span->fOtherIndex;
return other->activeAngleInner(oIndex, start, end, done, sortable);
}
SkPoint SkOpSegment::activeLeftTop(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;
double lastT = -1;
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
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;
}
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 DEBUG_LIMIT_WIND_SUM
SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
#endif
if (fOperand) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding);
}
bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
int* sumMiWinding, int* sumSuWinding) {
int maxWinding, sumWinding, oppMaxWinding, 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 id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
__FUNCTION__, debugID(), span(index).fT, span(endIndex).fT,
SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
#endif
return result;
}
bool SkOpSegment::activeWinding(int index, int endIndex) {
int sumWinding = updateWinding(endIndex, index);
return activeWinding(index, endIndex, &sumWinding);
}
bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) {
int maxWinding;
setUpWinding(index, endIndex, &maxWinding, sumWinding);
bool from = maxWinding != 0;
bool to = *sumWinding != 0;
bool result = gUnaryActiveEdge[from][to];
return result;
}
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
SkPoint copy = fTs[tIndexStart].fPt; // add t pair may move the point array
addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false, copy);
}
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
SkPoint copy = fTs[tIndex].fPt; // add t pair may move the point array
addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, copy);
}
} 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);
int ttIndex = tIndex;
bool checkOtherTMatch = false;
do {
const SkOpSpan& span = fTs[ttIndex];
if (startPt != span.fPt) {
break;
}
if (span.fOther == other && span.fPt == startPt) {
checkOtherTMatch = true;
break;
}
} while (++ttIndex < count());
do {
++oIndex;
} while (startPt != other->fTs[oIndex].fPt);
bool skipAdd = false;
if (checkOtherTMatch) {
int ooIndex = oIndex;
do {
const SkOpSpan& oSpan = other->fTs[ooIndex];
if (startPt != oSpan.fPt) {
break;
}
if (oSpan.fT == fTs[ttIndex].fOtherT) {
skipAdd = true;
break;
}
} while (++ooIndex < other->count());
}
if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) {
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);
const SkPoint* oWorkPt;
do {
oWorkPt = &other->fTs[++oIndex].fPt;
} while (nextPt == *oWorkPt);
nextPt = *workPt;
double tStart = fTs[tIndex].fT;
double oStart = other->fTs[oIndex].fT;
if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
break;
}
if (*workPt == *oWorkPt) {
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::addEndSpan(int endIndex) {
SkASSERT(span(endIndex).fT == 1 || (span(endIndex).fTiny
// && approximately_greater_than_one(span(endIndex).fT)
));
int spanCount = fTs.count();
int startIndex = endIndex - 1;
while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) {
--startIndex;
SkASSERT(startIndex > 0);
--endIndex;
}
SkOpAngle& angle = fAngles.push_back();
angle.set(this, spanCount - 1, startIndex);
#if DEBUG_ANGLE
debugCheckPointsEqualish(endIndex, spanCount);
#endif
setFromAngle(endIndex, &angle);
}
void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) {
int spanCount = fTs.count();
do {
fTs[endIndex].fFromAngle = angle;
} while (++endIndex < spanCount);
}
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);
}
SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
int spanIndex = count() - 1;
int startIndex = nextExactSpan(spanIndex, -1);
SkASSERT(startIndex >= 0);
SkOpAngle& angle = fAngles.push_back();
*anglePtr = &angle;
angle.set(this, spanIndex, startIndex);
setFromAngle(spanIndex, &angle);
SkOpSegment* other;
int oStartIndex, oEndIndex;
do {
const SkOpSpan& span = fTs[spanIndex];
SkASSERT(span.fT > 0);
other = span.fOther;
oStartIndex = span.fOtherIndex;
oEndIndex = other->nextExactSpan(oStartIndex, 1);
if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) {
break;
}
oEndIndex = oStartIndex;
oStartIndex = other->nextExactSpan(oEndIndex, -1);
--spanIndex;
} while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum);
SkOpAngle& oAngle = other->fAngles.push_back();
oAngle.set(other, oStartIndex, oEndIndex);
other->setToAngle(oEndIndex, &oAngle);
*otherPtr = other;
return &oAngle;
}
SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
int endIndex = nextExactSpan(0, 1);
SkASSERT(endIndex > 0);
SkOpAngle& angle = fAngles.push_back();
*anglePtr = &angle;
angle.set(this, 0, endIndex);
setToAngle(endIndex, &angle);
int spanIndex = 0;
SkOpSegment* other;
int oStartIndex, oEndIndex;
do {
const SkOpSpan& span = fTs[spanIndex];
SkASSERT(span.fT < 1);
other = span.fOther;
oEndIndex = span.fOtherIndex;
oStartIndex = other->nextExactSpan(oEndIndex, -1);
if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) {
break;
}
oStartIndex = oEndIndex;
oEndIndex = other->nextExactSpan(oStartIndex, 1);
++spanIndex;
} while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue);
SkOpAngle& oAngle = other->fAngles.push_back();
oAngle.set(other, oEndIndex, oStartIndex);
other->setFromAngle(oEndIndex, &oAngle);
*otherPtr = other;
return &oAngle;
}
SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
SkOpSegment* other;
SkOpAngle* angle, * otherAngle;
if (step > 0) {
otherAngle = addSingletonAngleUp(&other, &angle);
} else {
otherAngle = addSingletonAngleDown(&other, &angle);
}
angle->insert(otherAngle);
return angle;
}
void SkOpSegment::addStartSpan(int endIndex) {
int index = 0;
SkOpAngle& angle = fAngles.push_back();
angle.set(this, index, endIndex);
#if DEBUG_ANGLE
debugCheckPointsEqualish(index, endIndex);
#endif
setToAngle(endIndex, &angle);
}
void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) {
int index = 0;
do {
fTs[index].fToAngle = angle;
} while (++index < endIndex);
}
// 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) {
SkASSERT(this != other || fVerb == SkPath::kCubic_Verb);
#if 0 // this needs an even rougher association to be useful
SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt));
#endif
const SkPoint& firstPt = fPts[0];
const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
SkASSERT(newT == 0 || !precisely_zero(newT));
SkASSERT(newT == 1 || !precisely_equal(newT, 1));
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
int tCount = fTs.count();
for (int 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->fOtherT = -1;
span->fOther = other;
span->fPt = pt;
#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->fFromAngle = NULL;
span->fToAngle = NULL;
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
span->fOppValue = 0;
span->fChased = false;
span->fCoincident = false;
span->fLoop = false;
span->fNear = false;
span->fMultiple = false;
span->fSmall = false;
span->fTiny = false;
if ((span->fDone = newT == 1)) {
++fDoneSpans;
}
setSpanFlags(pt, newT, span);
return insertedAt;
}
void SkOpSegment::setSpanFlags(const SkPoint& pt, double newT, SkOpSpan* span) {
int less = -1;
// FIXME: note that this relies on spans being a continguous array
// find range of spans with nearly the same point as this one
// FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the moment
while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
if (fVerb == SkPath::kCubic_Verb) {
double tInterval = newT - span[less].fT;
double tMid = newT - tInterval / 2;
SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
if (!midPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
--less;
}
int more = 1;
// FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the moment
while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) {
if (fVerb == SkPath::kCubic_Verb) {
double tEndInterval = span[more].fT - newT;
double tMid = newT - tEndInterval / 2;
SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
if (!midEndPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
++more;
}
++less;
--more;
while (more - 1 > less && span[more].fPt == span[more - 1].fPt
&& span[more].fT == span[more - 1].fT) {
--more;
}
if (less == more) {
return;
}
if (precisely_negative(span[more].fT - span[less].fT)) {
return;
}
// if the total range of t values is big enough, mark all tiny
bool tiny = span[less].fPt == span[more].fPt;
int index = less;
do {
fSmall = span[index].fSmall = true;
fTiny |= span[index].fTiny = tiny;
if (!span[index].fDone) {
span[index].fDone = true;
++fDoneSpans;
}
} while (++index < more);
return;
}
void SkOpSegment::resetSpanFlags() {
fSmall = fTiny = false;
fDoneSpans = 0;
int start = 0;
int last = this->count() - 1;
do {
SkOpSpan* startSpan = &this->fTs[start];
double startT = startSpan->fT;
startSpan->fSmall = startSpan->fTiny = false; // sets range initial
bool terminus = startT == 1;
if ((startSpan->fDone = !startSpan->fWindValue | terminus)) {
++fDoneSpans;
}
++start; // range initial + 1
if (terminus) {
continue;
}
const SkPoint& pt = startSpan->fPt;
int end = start; // range initial + 1
while (end <= last) {
const SkOpSpan& endSpan = this->span(end);
if (!AlmostEqualUlps(endSpan.fPt, pt)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = (startSpan->fT + endSpan.fT) / 2;
SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
if (!midEndPt.approximatelyEqual(xyAtT(startSpan))) {
break;
}
}
++end;
}
if (start == end) { // end == range final + 1
continue;
}
while (--end >= start) { // end == range final
const SkOpSpan& endSpan = this->span(end);
const SkOpSpan& priorSpan = this->span(end - 1);
if (endSpan.fPt != priorSpan.fPt || endSpan.fT != priorSpan.fT) {
break; // end == range final + 1
}
}
if (end < start) { // end == range final + 1
continue;
}
int index = start - 1; // index == range initial
start = end; // start = range final + 1
const SkOpSpan& nextSpan = this->span(end);
if (precisely_negative(nextSpan.fT - startSpan->fT)) {
while (++index < end) {
startSpan = &this->fTs[index];
startSpan->fSmall = startSpan->fTiny = false; // sets range initial + 1
if ((startSpan->fDone = !startSpan->fWindValue)) {
++fDoneSpans;
}
}
continue;
}
if (!startSpan->fWindValue) {
--fDoneSpans; // added back below
}
bool tiny = nextSpan.fPt == startSpan->fPt;
do {
fSmall = startSpan->fSmall = true; // sets range initial
fTiny |= startSpan->fTiny = tiny;
startSpan->fDone = true;
++fDoneSpans;
startSpan = &this->fTs[++index];
} while (index < end); // loop through tiny small range end (last)
} while (start <= last);
}
// 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 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) {
--index;
}
bool oFoundEnd = false;
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 || precisely_equal(oStartT, other->fTs[oIndex].fT)) {
if (!oIndex) {
return; // tiny spans may move in the wrong direction
}
}
SkOpSpan* test = &fTs[index];
SkOpSpan* oTest = &other->fTs[oIndex];
SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
bool decrement, track, bigger;
int originalWindValue;
const SkPoint* testPt;
const SkPoint* oTestPt;
do {
SkASSERT(test->fT < 1);
SkASSERT(oTest->fT < 1);
decrement = test->fWindValue && oTest->fWindValue;
track = test->fWindValue || oTest->fWindValue;
bigger = test->fWindValue >= oTest->fWindValue;
testPt = &test->fPt;
double testT = test->fT;
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 || precisely_equal(testT, test->fT));
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;
}
oFoundEnd |= endPt == oTest->fPt;
oTest = &other->fTs[--oIndex];
} while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT));
} while (endPt != test->fPt && test->fT < 1);
// FIXME: determine if canceled edges need outside ts added
if (!oFoundEnd) {
for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) {
SkOpSpan* oTst2 = &other->fTs[oIdx2];
if (originalWindValue != oTst2->fWindValue) {
goto skipAdvanceOtherCancel;
}
if (!oTst2->fWindValue) {
goto skipAdvanceOtherCancel;
}
if (endPt == other->fTs[oIdx2].fPt) {
break;
}
}
oFoundEnd = endPt == oTest->fPt;
do {
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];
oFoundEnd |= endPt == oTest->fPt;
} while (!oFoundEnd || endPt == oTest->fPt);
}
skipAdvanceOtherCancel:
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);
}
setCoincidentRange(startPt, endPt, other);
other->setCoincidentRange(startPt, endPt, this);
}
int SkOpSegment::addSelfT(const SkPoint& pt, double newT) {
// if the tail nearly intersects itself but not quite, the caller records this separately
int result = addT(this, pt, newT);
SkOpSpan* span = &fTs[result];
fLoop = span->fLoop = true;
return result;
}
// find the starting or ending span with an existing loop of angles
// FIXME? replicate for all identical starting/ending spans?
// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
// FIXME? assert that only one other span has a valid windValue or oppValue
void SkOpSegment::addSimpleAngle(int index) {
SkOpSpan* span = &fTs[index];
int idx;
int start, end;
if (span->fT == 0) {
idx = 0;
span = &fTs[0];
do {
if (span->fToAngle) {
SkASSERT(span->fToAngle->loopCount() == 2);
SkASSERT(!span->fFromAngle);
span->fFromAngle = span->fToAngle->next();
return;
}
span = &fTs[++idx];
} while (span->fT == 0);
SkASSERT(!fTs[0].fTiny && fTs[idx].fT > 0);
addStartSpan(idx);
start = 0;
end = idx;
} else {
idx = count() - 1;
span = &fTs[idx];
do {
if (span->fFromAngle) {
SkASSERT(span->fFromAngle->loopCount() == 2);
SkASSERT(!span->fToAngle);
span->fToAngle = span->fFromAngle->next();
return;
}
span = &fTs[--idx];
} while (span->fT == 1);
SkASSERT(!fTs[idx].fTiny && fTs[idx].fT < 1);
addEndSpan(++idx);
start = idx;
end = count();
}
SkOpSegment* other;
SkOpSpan* oSpan;
index = start;
do {
span = &fTs[index];
other = span->fOther;
int oFrom = span->fOtherIndex;
oSpan = &other->fTs[oFrom];
if (oSpan->fT < 1 && oSpan->fWindValue) {
break;
}
if (oSpan->fT == 0) {
continue;
}
oFrom = other->nextExactSpan(oFrom, -1);
SkOpSpan* oFromSpan = &other->fTs[oFrom];
SkASSERT(oFromSpan->fT < 1);
if (oFromSpan->fWindValue) {
break;
}
} while (++index < end);
SkOpAngle* angle, * oAngle;
if (span->fT == 0) {
SkASSERT(span->fOtherIndex - 1 >= 0);
SkASSERT(span->fOtherT == 1);
SkDEBUGCODE(int oPriorIndex = other->nextExactSpan(span->fOtherIndex, -1));
SkDEBUGCODE(const SkOpSpan& oPrior = other->span(oPriorIndex));
SkASSERT(!oPrior.fTiny && oPrior.fT < 1);
other->addEndSpan(span->fOtherIndex);
angle = span->fToAngle;
oAngle = oSpan->fFromAngle;
} else {
SkASSERT(span->fOtherIndex + 1 < other->count());
SkASSERT(span->fOtherT == 0);
SkASSERT(!oSpan->fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0
|| (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL
&& other->fTs[span->fOtherIndex + 1].fToAngle == NULL)));
int oIndex = 1;
do {
const SkOpSpan& osSpan = other->span(oIndex);
if (osSpan.fFromAngle || osSpan.fT > 0) {
break;
}
++oIndex;
SkASSERT(oIndex < other->count());
} while (true);
other->addStartSpan(oIndex);
angle = span->fFromAngle;
oAngle = oSpan->fToAngle;
}
angle->insert(oAngle);
}
void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
debugValidate();
int count = this->count();
for (int index = 0; index < count; ++index) {
SkOpSpan& span = fTs[index];
if (!span.fMultiple) {
continue;
}
int end = nextExactSpan(index, 1);
SkASSERT(end > index + 1);
const SkPoint& thisPt = span.fPt;
while (index < end - 1) {
SkOpSegment* other1 = span.fOther;
int oCnt = other1->count();
for (int idx2 = index + 1; idx2 < end; ++idx2) {
SkOpSpan& span2 = fTs[idx2];
SkOpSegment* other2 = span2.fOther;
for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
SkOpSpan& oSpan = other1->fTs[oIdx];
if (oSpan.fOther != other2) {
continue;
}
if (oSpan.fPt == thisPt) {
goto skipExactMatches;
}
}
for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
SkOpSpan& oSpan = other1->fTs[oIdx];
if (oSpan.fOther != other2) {
continue;
}
if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) {
SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex];
if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT)
|| zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) {
return;
}
if (!way_roughly_equal(span.fOtherT, oSpan.fT)
|| !way_roughly_equal(span2.fOtherT, oSpan2.fT)
|| !way_roughly_equal(span2.fOtherT, oSpan.fOtherT)
|| !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) {
return;
}
alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT,
other2, &oSpan, alignedArray);
alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT,
other1, &oSpan2, alignedArray);
break;
}
}
skipExactMatches:
;
}
++index;
}
}
debugValidate();
}
void SkOpSegment::alignRange(int lower, int upper,
const SkOpSegment* other, int oLower, int oUpper) {
for (int oIndex = oLower; oIndex <= oUpper; ++oIndex) {
const SkOpSpan& oSpan = other->span(oIndex);
const SkOpSegment* oOther = oSpan.fOther;
if (oOther == this) {
continue;
}
SkOpSpan* matchSpan;
int matchIndex;
const SkOpSpan* refSpan;
for (int iIndex = lower; iIndex <= upper; ++iIndex) {
const SkOpSpan& iSpan = this->span(iIndex);
const SkOpSegment* iOther = iSpan.fOther;
if (iOther == other) {
continue;
}
if (iOther == oOther) {
goto nextI;
}
}
{
// oSpan does not have a match in this
int iCount = this->count();
const SkOpSpan* iMatch = NULL;
double iMatchTDiff;
matchIndex = -1;
for (int iIndex = 0; iIndex < iCount; ++iIndex) {
const SkOpSpan& iSpan = this->span(iIndex);
const SkOpSegment* iOther = iSpan.fOther;
if (iOther != oOther) {
continue;
}
double testTDiff = fabs(iSpan.fOtherT - oSpan.fOtherT);
if (!iMatch || testTDiff < iMatchTDiff) {
matchIndex = iIndex;
iMatch = &iSpan;
iMatchTDiff = testTDiff;
}
}
if (matchIndex < 0) {
continue; // the entry is missing, & will be picked up later (FIXME: fix it here?)
}
matchSpan = &this->fTs[matchIndex];
refSpan = &this->span(lower);
if (!SkDPoint::ApproximatelyEqual(matchSpan->fPt, refSpan->fPt)) {
goto nextI;
}
if (matchIndex != lower - 1 && matchIndex != upper + 1) {
// the consecutive spans need to be rearranged to get the missing one close
continue; // FIXME: more work to do
}
}
{
this->fixOtherTIndex();
SkScalar newT;
if (matchSpan->fT != 0 && matchSpan->fT != 1) {
newT = matchSpan->fT = refSpan->fT;
matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = refSpan->fT;
} else { // leave span at the start or end there and adjust the neighbors
newT = matchSpan->fT;
for (int iIndex = lower; iIndex <= upper; ++iIndex) {
matchSpan = &this->fTs[iIndex];
matchSpan->fT = newT;
matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = newT;
}
}
this->resetSpanFlags(); // fix up small / tiny / done
// align ts of other ranges with adjacent spans that match the aligned points
lower = SkTMin(lower, matchIndex);
while (lower > 0) {
const SkOpSpan& span = this->span(lower - 1);
if (span.fT != newT) {
break;
}
--lower;
}
upper = SkTMax(upper, matchIndex);
int last = this->count() - 1;
while (upper < last) {
const SkOpSpan& span = this->span(upper + 1);
if (span.fT != newT) {
break;
}
++upper;
}
for (int iIndex = lower; iIndex <= upper; ++iIndex) {
const SkOpSpan& span = this->span(iIndex);
SkOpSegment* aOther = span.fOther;
int aLower = span.fOtherIndex;
SkScalar aT = span.fOtherT;
bool aResetFlags = false;
while (aLower > 0) {
SkOpSpan* aSpan = &aOther->fTs[aLower - 1];
for (int iIndex = lower; iIndex <= upper; ++iIndex) {
if (aSpan->fPt == this->fTs[iIndex].fPt) {
goto matchFound;
}
}
break;
matchFound:
--aLower;
}
int aUpper = span.fOtherIndex;
int aLast = aOther->count() - 1;
while (aUpper < aLast) {
SkOpSpan* aSpan = &aOther->fTs[aUpper + 1];
for (int iIndex = lower; iIndex <= upper; ++iIndex) {
if (aSpan->fPt == this->fTs[iIndex].fPt) {
goto matchFound2;
}
}
break;
matchFound2:
++aUpper;
}
if (aOther->fTs[aLower].fT == 0) {
aT = 0;
} else if (aOther->fTs[aUpper].fT == 1) {
aT = 1;
}
bool aFixed = false;
for (int aIndex = aLower; aIndex <= aUpper; ++aIndex) {
SkOpSpan* aSpan = &aOther->fTs[aIndex];
if (aSpan->fT == aT) {
continue;
}
SkASSERT(way_roughly_equal(aSpan->fT, aT));
if (!aFixed) {
aOther->fixOtherTIndex();
aFixed = true;
}
aSpan->fT = aT;
aSpan->fOther->fTs[aSpan->fOtherIndex].fOtherT = aT;
aResetFlags = true;
}
if (aResetFlags) {
aOther->resetSpanFlags();
}
}
}
nextI: ;
}
}
void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other,
double otherT, const SkOpSegment* other2, SkOpSpan* oSpan,
SkTDArray<AlignedSpan>* alignedArray) {
AlignedSpan* aligned = alignedArray->append();
aligned->fOldPt = oSpan->fPt;
aligned->fPt = newPt;
aligned->fOldT = oSpan->fT;
aligned->fT = newT;
aligned->fSegment = this; // OPTIMIZE: may be unused, can remove
aligned->fOther1 = other;
aligned->fOther2 = other2;
SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt));
oSpan->fPt = newPt;
// SkASSERT(way_roughly_equal(oSpan->fT, newT));
oSpan->fT = newT;
// SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT));
oSpan->fOtherT = otherT;
}
bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) {
bool aligned = false;
SkOpSpan* span = &fTs[index];
SkOpSegment* other = span->fOther;
int oIndex = span->fOtherIndex;
SkOpSpan* oSpan = &other->fTs[oIndex];
if (span->fT != thisT) {
span->fT = thisT;
oSpan->fOtherT = thisT;
aligned = true;
}
if (span->fPt != thisPt) {
span->fPt = thisPt;
oSpan->fPt = thisPt;
aligned = true;
}
double oT = oSpan->fT;
if (oT == 0) {
return aligned;
}
int oStart = other->nextSpan(oIndex, -1) + 1;
oSpan = &other->fTs[oStart];
int otherIndex = oStart;
if (oT == 1) {
if (aligned) {
while (oSpan->fPt == thisPt && oSpan->fT != 1) {
oSpan->fTiny = true;
++oSpan;
}
}
return aligned;
}
oT = oSpan->fT;
int oEnd = other->nextSpan(oIndex, 1);
bool oAligned = false;
if (oSpan->fPt != thisPt) {
oAligned |= other->alignSpan(oStart, oT, thisPt);
}
while (++otherIndex < oEnd) {
SkOpSpan* oNextSpan = &other->fTs[otherIndex];
if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) {
oAligned |= other->alignSpan(otherIndex, oT, thisPt);
}
}
if (oAligned) {
other->alignSpanState(oStart, oEnd);
}
return aligned;
}
void SkOpSegment::alignSpanState(int start, int end) {
SkOpSpan* lastSpan = &fTs[--end];
bool allSmall = lastSpan->fSmall;
bool allTiny = lastSpan->fTiny;
bool allDone = lastSpan->fDone;
SkDEBUGCODE(int winding = lastSpan->fWindValue);
SkDEBUGCODE(int oppWinding = lastSpan->fOppValue);
int index = start;
while (index < end) {
SkOpSpan* span = &fTs[index];
span->fSmall = allSmall;
span->fTiny = allTiny;
if (span->fDone != allDone) {
span->fDone = allDone;
fDoneSpans += allDone ? 1 : -1;
}
SkASSERT(span->fWindValue == winding);
SkASSERT(span->fOppValue == oppWinding);
++index;
}
}
void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) {
bool binary = fOperand != other->fOperand;
int index = 0;
int last = this->count();
do {
SkOpSpan& span = this->fTs[--last];
if (span.fT != 1 && !span.fSmall) {
break;
}
span.fCoincident = true;
} while (true);
int oIndex = other->count();
do {
SkOpSpan& oSpan = other->fTs[--oIndex];
if (oSpan.fT != 1 && !oSpan.fSmall) {
break;
}
oSpan.fCoincident = true;
} while (true);
do {
SkOpSpan* test = &this->fTs[index];
int baseWind = test->fWindValue;
int baseOpp = test->fOppValue;
int endIndex = index;
while (++endIndex <= last) {
SkOpSpan* endSpan = &this->fTs[endIndex];
SkASSERT(endSpan->fT < 1);
if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
break;
}
endSpan->fCoincident = true;
}
SkOpSpan* oTest = &other->fTs[oIndex];
int oBaseWind = oTest->fWindValue;
int oBaseOpp = oTest->fOppValue;
int oStartIndex = oIndex;
while (--oStartIndex >= 0) {
SkOpSpan* oStartSpan = &other->fTs[oStartIndex];
if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) {
break;
}
oStartSpan->fCoincident = true;
}
bool decrement = baseWind && oBaseWind;
bool bigger = baseWind >= oBaseWind;
do {
SkASSERT(test->fT < 1);
if (decrement) {
if (binary && bigger) {
test->fOppValue--;
} else {
decrementSpan(test);
}
}
test->fCoincident = true;
test = &fTs[++index];
} while (index < endIndex);
do {
SkASSERT(oTest->fT < 1);
if (decrement) {
if (binary && !bigger) {
oTest->fOppValue--;
} else {
other->decrementSpan(oTest);
}
}
oTest->fCoincident = true;
oTest = &other->fTs[--oIndex];
} while (oIndex > oStartIndex);
} while (index <= last && oIndex >= 0);
SkASSERT(index > last);
SkASSERT(oIndex < 0);
}
void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) {
bool binary = fOperand != other->fOperand;
int index = 0;
int last = this->count();
do {
SkOpSpan& span = this->fTs[--last];
if (span.fT != 1 && !span.fSmall) {
break;
}
span.fCoincident = true;
} while (true);
int oIndex = 0;
int oLast = other->count();
do {
SkOpSpan& oSpan = other->fTs[--oLast];
if (oSpan.fT != 1 && !oSpan.fSmall) {
break;
}
oSpan.fCoincident = true;
} while (true);
do {
SkOpSpan* test = &this->fTs[index];
int baseWind = test->fWindValue;
int baseOpp = test->fOppValue;
int endIndex = index;
SkOpSpan* endSpan;
while (++endIndex <= last) {
endSpan = &this->fTs[endIndex];
SkASSERT(endSpan->fT < 1);
if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
break;
}
endSpan->fCoincident = true;
}
SkOpSpan* oTest = &other->fTs[oIndex];
int oBaseWind = oTest->fWindValue;
int oBaseOpp = oTest->fOppValue;
int oEndIndex = oIndex;
SkOpSpan* oEndSpan;
while (++oEndIndex <= oLast) {
oEndSpan = &this->fTs[oEndIndex];
SkASSERT(oEndSpan->fT < 1);
if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) {
break;
}
oEndSpan->fCoincident = true;
}
// consolidate the winding count even if done
if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) {
if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
bumpCoincidentBlind(binary, index, endIndex);
other->bumpCoincidentOBlind(oIndex, oEndIndex);
} else {
other->bumpCoincidentBlind(binary, oIndex, oEndIndex);
bumpCoincidentOBlind(index, endIndex);
}
}
index = endIndex;
oIndex = oEndIndex;
} while (index <= last && oIndex <= oLast);
SkASSERT(index > last);
SkASSERT(oIndex > oLast);
}
void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) {
const SkOpSpan& oTest = fTs[index];
int oWindValue = oTest.fWindValue;
int oOppValue = oTest.fOppValue;
if (binary) {
SkTSwap<int>(oWindValue, oOppValue);
}
do {
(void) bumpSpan(&fTs[index], oWindValue, oOppValue);
} while (++index < endIndex);
}
bool 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 (end->fDone && !end->fTiny && !end->fSmall) { // extremely large paths trigger this
return false;
}
if (bumpSpan(end, oWindValue, oOppValue)) {
TrackOutside(outsideTs, oStartPt);
}
end = &fTs[++index];
} while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1);
*indexPtr = index;
return true;
}
void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) {
do {
zeroSpan(&fTs[index]);
} while (++index < endIndex);
}
// 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
bool SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
SkTArray<SkPoint, true>* oOutsidePts, const SkPoint& oEndPt) {
int oIndex = *oIndexPtr;
SkOpSpan* const oTest = &fTs[oIndex];
SkOpSpan* oEnd = oTest;
const SkPoint& oStartPt = oTest->fPt;
double oStartT = oTest->fT;
#if 0 // FIXME : figure out what disabling this breaks
const SkPoint& startPt = test.fPt;
// this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition
if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
TrackOutside(oOutsidePts, startPt);
}
#endif
bool foundEnd = false;
while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
foundEnd |= oEndPt == oEnd->fPt;
zeroSpan(oEnd);
oEnd = &fTs[++oIndex];
}
*oIndexPtr = oIndex;
return foundEnd;
}
// 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
bool 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 && precisely_equal(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 && precisely_equal(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;
// paths with extreme data will fail this test and eject out of pathops altogether later on
// SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
do {
SkASSERT(test->fT < 1);
if (oTest->fT == 1) {
// paths with extreme data may be so mismatched that we fail here
return false;
}
// consolidate the winding count even if done
bool foundEnd = false;
if ((test->fWindValue == 0 && test->fOppValue == 0)
|| (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
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) {
if (!bumpCoincidentThis(*oTest, binary, &index, &outsidePts)) {
return false;
}
foundEnd = other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts, endPt);
} else {
if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts)) {
return false;
}
foundEnd = bumpCoincidentOther(*oTest, &index, &outsidePts, endPt);
}
}
test = &fTs[index];
testPt = &test->fPt;
testT = test->fT;
oTest = &other->fTs[oIndex];
oTestPt = &oTest->fPt;
if (endPt == *testPt || precisely_equal(endT, testT)) {
break;
}
if (0 && foundEnd) { // FIXME: this is likely needed but wait until a test case triggers it
break;
}
// SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
} while (endPt != *oTestPt);
// in rare cases, one may have ended before the other
if (endPt != *testPt && !precisely_equal(endT, testT)) {
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) {
SkASSERT(!test->fDone);
test->fDone = true;
++fDoneSpans;
}
}
test = &fTs[++index];
testPt = &test->fPt;
} while (endPt != *testPt);
}
if (endPt != *oTestPt) {
// look ahead to see if zeroing more spans will allows us to catch up
int oPeekIndex = oIndex;
bool success = true;
SkOpSpan* oPeek;
int oCount = other->count();
do {
oPeek = &other->fTs[oPeekIndex];
if (++oPeekIndex == oCount) {
success = false;
break;
}
} while (endPt != oPeek->fPt);
if (success) {
// make sure the matching point completes the coincidence span
success = false;
do {
if (oPeek->fOther == this) {
success = true;
break;
}
if (++oPeekIndex == oCount) {
break;
}
oPeek = &other->fTs[oPeekIndex];
} while (endPt == oPeek->fPt);
}
if (success) {
do {
if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
if (other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts, endPt)) {
break;
}
} else {
if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts)) {
return false;
}
}
oTest = &other->fTs[oIndex];
oTestPt = &oTest->fPt;
} while (endPt != *oTestPt);
}
}
int outCount = outsidePts.count();
if (!done() && outCount) {
addCoinOutsides(outsidePts[0], endPt, other);
}
if (!other->done() && oOutsidePts.count()) {
other->addCoinOutsides(oOutsidePts[0], endPt, this);
}
setCoincidentRange(startPt, endPt, other);
other->setCoincidentRange(startPt, endPt, this);
return true;
}
// FIXME: this doesn't prevent the same span from being added twice
// fix in caller, SkASSERT here?
// FIXME: this may erroneously reject adds for cubic loops
const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
const SkPoint& pt, const SkPoint& pt2) {
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const SkOpSpan& span = fTs[tIndex];
if (!approximately_negative(span.fT - t)) {
break;
}
if (span.fOther == other) {
bool tsMatch = approximately_equal(span.fT, t);
bool otherTsMatch = approximately_equal(span.fOtherT, otherT);
// FIXME: add cubic loop detecting logic here
// if fLoop bit is set on span, that could be enough if addOtherT copies the bit
// or if a new bit is added ala fOtherLoop
if (tsMatch || otherTsMatch) {
#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 NULL;
}
}
}
int oCount = other->count();
for (int oIndex = 0; oIndex < oCount; ++oIndex) {
const SkOpSpan& oSpan = other->span(oIndex);
if (!approximately_negative(oSpan.fT - otherT)) {
break;
}
if (oSpan.fOther == this) {
bool otherTsMatch = approximately_equal(oSpan.fT, otherT);
bool tsMatch = approximately_equal(oSpan.fOtherT, t);
if (otherTsMatch || tsMatch) {
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair other duplicate this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
return NULL;
}
}
}
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
SkASSERT(other != this);
int insertedAt = addT(other, pt, t);
int otherInsertedAt = other->addT(this, pt2, otherT);
this->addOtherT(insertedAt, otherT, otherInsertedAt);
other->addOtherT(otherInsertedAt, t, insertedAt);
this->matchWindingValue(insertedAt, t, borrowWind);
other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
SkOpSpan& span = this->fTs[insertedAt];
if (pt != pt2) {
span.fNear = true;
SkOpSpan& oSpan = other->fTs[otherInsertedAt];
oSpan.fNear = true;
}
// if the newly inserted spans match a neighbor on one but not the other, make them agree
int lower = this->nextExactSpan(insertedAt, -1) + 1;
int upper = this->nextExactSpan(insertedAt, 1) - 1;
if (upper < 0) {
upper = this->count() - 1;
}
int oLower = other->nextExactSpan(otherInsertedAt, -1) + 1;
int oUpper = other->nextExactSpan(otherInsertedAt, 1) - 1;
if (oUpper < 0) {
oUpper = other->count() - 1;
}
if (lower == upper && oLower == oUpper) {
return &span;
}
#if DEBUG_CONCIDENT
SkDebugf("%s id=%d lower=%d upper=%d other=%d oLower=%d oUpper=%d\n", __FUNCTION__,
debugID(), lower, upper, other->debugID(), oLower, oUpper);
#endif
// find the nearby spans in one range missing in the other
this->alignRange(lower, upper, other, oLower, oUpper);
other->alignRange(oLower, oUpper, this, lower, upper);
return &span;
}
const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
const SkPoint& pt) {
return addTPair(t, other, otherT, borrowWind, pt, pt);
}
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);
}
// in extreme cases (like the buffer overflow test) return false to abort
// for now, if one t value represents two different points, then the values are too extreme
// to generate meaningful results
bool SkOpSegment::calcAngles() {
int spanCount = fTs.count();
if (spanCount <= 2) {
return spanCount == 2;
}
int index = 1;
const SkOpSpan* firstSpan = &fTs[index];
int activePrior = checkSetAngle(0);
const SkOpSpan* span = &fTs[0];
if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) {
index = findStartSpan(0); // curve start intersects
if (fTs[index].fT == 0) {
return false;
}
SkASSERT(index > 0);
if (activePrior >= 0) {
addStartSpan(index);
}
}
bool addEnd;
int endIndex = spanCount - 1;
span = &fTs[endIndex - 1];
if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects
endIndex = findEndSpan(endIndex);
SkASSERT(endIndex > 0);
} else {
addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts();
}
SkASSERT(endIndex >= index);
int prior = 0;
while (index < endIndex) {
const SkOpSpan& fromSpan = fTs[index]; // for each intermediate intersection
const SkOpSpan* lastSpan;
span = &fromSpan;
int start = index;
do {
lastSpan = span;
span = &fTs[++index];
SkASSERT(index < spanCount);
if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) {
break;
}
if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) {
return false;
}
} while (true);
SkOpAngle* angle = NULL;
SkOpAngle* priorAngle;
if (activePrior >= 0) {
int pActive = firstActive(prior);
SkASSERT(pActive < start);
priorAngle = &fAngles.push_back();
priorAngle->set(this, start, pActive);
}
int active = checkSetAngle(start);
if (active >= 0) {
SkASSERT(active < index);
angle = &fAngles.push_back();
angle->set(this, active, index);
}
#if DEBUG_ANGLE
debugCheckPointsEqualish(start, index);
#endif
prior = start;
do {
const SkOpSpan* startSpan = &fTs[start - 1];
if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle
|| startSpan->fToAngle) {
break;
}
--start;
} while (start > 0);
do {
if (activePrior >= 0) {
SkASSERT(fTs[start].fFromAngle == NULL);
fTs[start].fFromAngle = priorAngle;
}
if (active >= 0) {
SkASSERT(fTs[start].fToAngle == NULL);
fTs[start].fToAngle = angle;
}
} while (++start < index);
activePrior = active;
}
if (addEnd && activePrior >= 0) {
addEndSpan(endIndex);
}
return true;
}
int SkOpSegment::checkSetAngle(int tIndex) const {
const SkOpSpan* span = &fTs[tIndex];
while (span->fTiny /* || span->fSmall */) {
span = &fTs[++tIndex];
}
return isCanceled(tIndex) ? -1 : tIndex;
}
// at this point, the span is already ordered, or unorderable
int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) {
SkASSERT(includeType != SkOpAngle::kUnaryXor);
SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex);
if (NULL == firstAngle || NULL == firstAngle->next()) {
return SK_NaN32;
}
// 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 both are next to orderable angles,
// and one has winding computed, transfer to the other
SkOpAngle* baseAngle = NULL;
bool tryReverse = false;
// look for counterclockwise transfers
SkOpAngle* angle = firstAngle->previous();
SkOpAngle* next = angle->next();
firstAngle = next;
do {
SkOpAngle* prior = angle;
angle = next;
next = angle->next();
SkASSERT(prior->next() == angle);
SkASSERT(angle->next() == next);
if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
baseAngle = NULL;
continue;
}
int testWinding = angle->segment()->windSum(angle);
if (SK_MinS32 != testWinding) {
baseAngle = angle;
tryReverse = true;
continue;
}
if (baseAngle) {
ComputeOneSum(baseAngle, angle, includeType);
baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
}
} while (next != firstAngle);
if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
firstAngle = baseAngle;
tryReverse = true;
}
if (tryReverse) {
baseAngle = NULL;
SkOpAngle* prior = firstAngle;
do {
angle = prior;
prior = angle->previous();
SkASSERT(prior->next() == angle);
next = angle->next();
if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
baseAngle = NULL;
continue;
}
int testWinding = angle->segment()->windSum(angle);
if (SK_MinS32 != testWinding) {
baseAngle = angle;
continue;
}
if (baseAngle) {
ComputeOneSumReverse(baseAngle, angle, includeType);
baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
}
} while (prior != firstAngle);
}
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,
nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
&maxWinding, &sumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, 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,
nextAngle);
} else {
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
&maxWinding, &sumWinding);
last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
}
nextAngle->setLastMarked(last);
}
bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
int step = index < endIndex ? 1 : -1;
do {
const SkOpSpan& span = this->span(index);
if (span.fPt == pt) {
const SkOpSpan& endSpan = this->span(endIndex);
return span.fT == endSpan.fT && pt != endSpan.fPt;
}
index += step;
} while (index != endIndex);
return false;
}
bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const {
int count = this->count();
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
if (t < span.fT) {
return false;
}
if (t == span.fT) {
if (other != span.fOther) {
continue;
}
if (other->fVerb != SkPath::kCubic_Verb) {
return true;
}
if (!other->fLoop) {
return true;
}
double otherMidT = (otherT + span.fOtherT) / 2;
SkPoint otherPt = other->ptAtT(otherMidT);
return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
}
}
return false;
}
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)
intersections.allowNear(false);
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) {
if (!span->fDone) {
span->fDone = true;
++fDoneSpans;
}
return true;
}
return false;
}
const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const {
const SkOpSpan* firstSpan = &thisSpan; // rewind to the start
const SkOpSpan* beginSpan = fTs.begin();
const SkPoint& testPt = thisSpan.fPt;
while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) {
--firstSpan;
}
return *firstSpan;
}
const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const {
const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small
const SkOpSpan* lastSpan = &thisSpan; // find the end
const SkPoint& testPt = thisSpan.fPt;
while (lastSpan < endSpan && lastSpan[1].fPt == testPt) {
++lastSpan;
}
return *lastSpan;
}
// with a loop, the comparison is move involved
// scan backwards and forwards to count all matching points
// (verify that there are twp scans marked as loops)
// compare that against 2 matching scans for loop plus other results
bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) {
const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start
const SkOpSpan& lastSpan = this->lastSpan(thisSpan); // find the end
double firstLoopT = -1, lastLoopT = -1;
const SkOpSpan* testSpan = &firstSpan - 1;
while (++testSpan <= &lastSpan) {
if (testSpan->fLoop) {
firstLoopT = testSpan->fT;
break;
}
}
testSpan = &lastSpan + 1;
while (--testSpan >= &firstSpan) {
if (testSpan->fLoop) {
lastLoopT = testSpan->fT;
break;
}
}
SkASSERT((firstLoopT == -1) == (lastLoopT == -1));
if (firstLoopT == -1) {
return false;
}
SkASSERT(firstLoopT < lastLoopT);
testSpan = &firstSpan - 1;
smallCounts[0] = smallCounts[1] = 0;
while (++testSpan <= &lastSpan) {
SkASSERT(approximately_equal(testSpan->fT, firstLoopT) +
approximately_equal(testSpan->fT, lastLoopT) == 1);
smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++;
}
return true;
}
double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max,
double hiEnd, const SkOpSegment* other, int thisStart) {
if (max >= hiEnd) {
return -1;
}
int end = findOtherT(hiEnd, ref);
if (end < 0) {
return -1;
}
double tHi = span(end).fT;
double tLo, refLo;
if (thisStart >= 0) {
tLo = span(thisStart).fT;
refLo = min;
} else {
int start1 = findOtherT(loEnd, ref);
SkASSERT(start1 >= 0);
tLo = span(start1).fT;
refLo = loEnd;
}
double missingT = (max - refLo) / (hiEnd - refLo);
missingT = tLo + missingT * (tHi - tLo);
return missingT;
}
double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max,
double hiEnd, const SkOpSegment* other, int thisEnd) {
if (min <= loEnd) {
return -1;
}
int start = findOtherT(loEnd, ref);
if (start < 0) {
return -1;
}
double tLo = span(start).fT;
double tHi, refHi;
if (thisEnd >= 0) {
tHi = span(thisEnd).fT;
refHi = max;
} else {
int end1 = findOtherT(hiEnd, ref);
if (end1 < 0) {
return -1;
}
tHi = span(end1).fT;
refHi = hiEnd;
}
double missingT = (min - loEnd) / (refHi - loEnd);
missingT = tLo + missingT * (tHi - tLo);
return missingT;
}
// see if spans with two or more intersections have the same number on the other end
void SkOpSegment::checkDuplicates() {
debugValidate();
SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
int index;
int endIndex = 0;
bool endFound;
do {
index = endIndex;
endIndex = nextExactSpan(index, 1);
if ((endFound = endIndex < 0)) {
endIndex = count();
}
int dupCount = endIndex - index;
if (dupCount < 2) {
continue;
}
do {
const SkOpSpan* thisSpan = &fTs[index];
if (thisSpan->fNear) {
continue;
}
SkOpSegment* other = thisSpan->fOther;
int oIndex = thisSpan->fOtherIndex;
int oStart = other->nextExactSpan(oIndex, -1) + 1;
int oEnd = other->nextExactSpan(oIndex, 1);
if (oEnd < 0) {
oEnd = other->count();
}
int oCount = oEnd - oStart;
// force the other to match its t and this pt if not on an end point
if (oCount != dupCount) {
MissingSpan& missing = missingSpans.push_back();
missing.fOther = NULL;
SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
missing.fPt = thisSpan->fPt;
const SkOpSpan& oSpan = other->span(oIndex);
if (oCount > dupCount) {
missing.fSegment = this;
missing.fT = thisSpan->fT;
other->checkLinks(&oSpan, &missingSpans);
} else {
missing.fSegment = other;
missing.fT = oSpan.fT;
checkLinks(thisSpan, &missingSpans);
}
if (!missingSpans.back().fOther) {
missingSpans.pop_back();
}
}
} while (++index < endIndex);
} while (!endFound);
int missingCount = missingSpans.count();
if (missingCount == 0) {
return;
}
SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence;
for (index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
SkOpSegment* missingOther = missing.fOther;
if (missing.fSegment == missing.fOther) {
continue;
}
#if 0 // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks
// skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why
if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) {
#if DEBUG_DUPLICATES
SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID,
missing.fT, missing.fOther->fID, missing.fOtherT);
#endif
continue;
}
if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) {
#if DEBUG_DUPLICATES
SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID,
missing.fOtherT, missing.fSegment->fID, missing.fT);
#endif
continue;
}
#endif
// skip if adding would insert point into an existing coincindent span
if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther)
&& missingOther->inCoincidentSpan(missing.fOtherT, this)) {
continue;
}
// skip if the created coincident spans are small
if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther)
&& missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) {
continue;
}
const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther,
missing.fOtherT, false, missing.fPt);
if (added && added->fSmall) {
missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence);
}
}
for (index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
missing.fSegment->fixOtherTIndex();
missing.fOther->fixOtherTIndex();
}
for (index = 0; index < missingCoincidence.count(); ++index) {
MissingSpan& missing = missingCoincidence[index];
missing.fSegment->fixOtherTIndex();
}
debugValidate();
}
// look to see if the curve end intersects an intermediary that intersects the other
bool 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;
double tBottom = -1;
int tStart = -1;
int tLast = count;
bool lastSmall = false;
double afterT = t;
for (int inner = 0; inner < count; ++inner) {
double innerT = fTs[inner].fT;
if (innerT <= t && innerT > tBottom) {
if (innerT < t || !lastSmall) {
tStart = inner - 1;
}
tBottom = innerT;
}
if (innerT > afterT) {
if (t == afterT && lastSmall) {
afterT = innerT;
} else {
tLast = inner;
break;
}
}
lastSmall = innerT <= t ? fTs[inner].fSmall : false;
}
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.fT == t
&& lastMissing.fOther == match
&& lastMissing.fOtherT == matchT) {
SkASSERT(SkDPoint::ApproximatelyEqual(lastMissing.fPt, peekSpan.fPt));
continue;
}
}
if (this == match) {
return false; // extremely large paths can trigger this
}
#if DEBUG_CHECK_ALIGN
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.fT = t;
SkASSERT(this != match);
missing.fOther = match;
missing.fOtherT = matchT;
missing.fPt = peekSpan.fPt;
}
break;
nextPeekIndex:
;
}
}
if (missingSpans.count() == 0) {
debugValidate();
return true;
}
debugValidate();
int missingCount = missingSpans.count();
for (int index = 0; index < missingCount; ++index) {
MissingSpan& missing = missingSpans[index];
if (this != missing.fOther) {
addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
}
}
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) {
missingSpans[index].fOther->fixOtherTIndex();
}
debugValidate();
return true;
}
void SkOpSegment::checkLinks(const