blob: 56813b8b1f207171e05c2ad0a2e25ff3323e0f1b [file] [log] [blame]
/*
* Copyright 2013 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkPathOpsDebug.h"
#include "SkPath.h"
#if defined SK_DEBUG || !FORCE_RELEASE
const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
#if defined(SK_DEBUG) || !FORCE_RELEASE
int SkPathOpsDebug::gContourID = 0;
int SkPathOpsDebug::gSegmentID = 0;
#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
int SkPathOpsDebug::gSortCount;
#endif
#if DEBUG_ACTIVE_OP
const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
#endif
bool SkPathOpsDebug::ChaseContains(const SkTDArray<SkOpSpan *>& chaseArray,
const SkOpSpan* span) {
for (int index = 0; index < chaseArray.count(); ++index) {
const SkOpSpan* entry = chaseArray[index];
if (entry == span) {
return true;
}
}
return false;
}
void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
size_t len = strlen(str);
bool num = false;
for (size_t idx = 0; idx < len; ++idx) {
if (num && str[idx] == 'e') {
if (len + 2 >= bufferLen) {
return;
}
memmove(&str[idx + 2], &str[idx + 1], len - idx);
str[idx] = '*';
str[idx + 1] = '^';
++len;
}
num = str[idx] >= '0' && str[idx] <= '9';
}
}
bool SkPathOpsDebug::ValidWind(int wind) {
return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
}
void SkPathOpsDebug::WindingPrintf(int wind) {
if (wind == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", wind);
}
}
#if DEBUG_SHOW_TEST_NAME
void* SkPathOpsDebug::CreateNameStr() {
return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH);
}
void SkPathOpsDebug::DeleteNameStr(void* v) {
SkDELETE_ARRAY(reinterpret_cast<char* >(v));
}
void SkPathOpsDebug::BumpTestName(char* test) {
char* num = test + strlen(test);
while (num[-1] >= '0' && num[-1] <= '9') {
--num;
}
if (num[0] == '\0') {
return;
}
int dec = atoi(num);
if (dec == 0) {
return;
}
++dec;
SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
}
#endif
#if !DEBUG_SHOW_TEST_NAME // enable when building without extended test
void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name) {
}
#endif
#endif // defined SK_DEBUG || !FORCE_RELEASE
#include "SkOpAngle.h"
#include "SkOpSegment.h"
#if DEBUG_SORT
void SkOpAngle::debugLoop() const {
const SkOpAngle* first = this;
const SkOpAngle* next = this;
do {
next->debugOne(true);
SkDebugf("\n");
next = next->fNext;
} while (next && next != first);
}
void SkOpAngle::debugOne(bool functionHeader) const {
// fSegment->debugValidate();
const SkOpSpan& mSpan = fSegment->span(SkMin32(fStart, fEnd));
if (functionHeader) {
SkDebugf("%s ", __FUNCTION__);
}
SkDebugf("[%d", fSegment->debugID());
#if DEBUG_ANGLE
SkDebugf("/%d", fID);
#endif
SkDebugf("] next=");
if (fNext) {
SkDebugf("%d", fNext->fSegment->debugID());
#if DEBUG_ANGLE
SkDebugf("/%d", fNext->fID);
#endif
} else {
SkDebugf("?");
}
SkDebugf(" sect=%d/%d ", fSectorStart, fSectorEnd);
SkDebugf(" s=%1.9g [%d] e=%1.9g [%d]", fSegment->span(fStart).fT, fStart,
fSegment->span(fEnd).fT, fEnd);
SkDebugf(" sgn=%d windVal=%d", sign(), mSpan.fWindValue);
#if DEBUG_WINDING
SkDebugf(" windSum=");
SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
#endif
if (mSpan.fOppValue != 0 || mSpan.fOppSum != SK_MinS32) {
SkDebugf(" oppVal=%d", mSpan.fOppValue);
#if DEBUG_WINDING
SkDebugf(" oppSum=");
SkPathOpsDebug::WindingPrintf(mSpan.fOppSum);
#endif
}
if (mSpan.fDone) {
SkDebugf(" done");
}
if (unorderable()) {
SkDebugf(" unorderable");
}
if (small()) {
SkDebugf(" small");
}
if (mSpan.fTiny) {
SkDebugf(" tiny");
}
if (fSegment->operand()) {
SkDebugf(" operand");
}
if (fStop) {
SkDebugf(" stop");
}
}
#endif
#if DEBUG_ANGLE
void SkOpAngle::debugSameAs(const SkOpAngle* compare) const {
SK_ALWAYSBREAK(fSegment == compare->fSegment);
const SkOpSpan& startSpan = fSegment->span(fStart);
const SkOpSpan& oStartSpan = fSegment->span(compare->fStart);
SK_ALWAYSBREAK(startSpan.fToAngleIndex == oStartSpan.fToAngleIndex);
SK_ALWAYSBREAK(startSpan.fFromAngleIndex == oStartSpan.fFromAngleIndex);
const SkOpSpan& endSpan = fSegment->span(fEnd);
const SkOpSpan& oEndSpan = fSegment->span(compare->fEnd);
SK_ALWAYSBREAK(endSpan.fToAngleIndex == oEndSpan.fToAngleIndex);
SK_ALWAYSBREAK(endSpan.fFromAngleIndex == oEndSpan.fFromAngleIndex);
}
#endif
#if DEBUG_VALIDATE
void SkOpAngle::debugValidateNext() const {
const SkOpAngle* first = this;
const SkOpAngle* next = first;
SkTDArray<const SkOpAngle*>(angles);
do {
SK_ALWAYSBREAK(next->fSegment->debugContains(next));
angles.push(next);
next = next->next();
if (next == first) {
break;
}
SK_ALWAYSBREAK(!angles.contains(next));
if (!next) {
return;
}
} while (true);
}
void SkOpAngle::debugValidateLoop() const {
const SkOpAngle* first = this;
const SkOpAngle* next = first;
SK_ALWAYSBREAK(first->next() != first);
int signSum = 0;
int oppSum = 0;
bool firstOperand = fSegment->operand();
bool unorderable = false;
do {
unorderable |= next->fUnorderable;
const SkOpSegment* segment = next->fSegment;
bool operandsMatch = firstOperand == segment->operand();
signSum += operandsMatch ? segment->spanSign(next) : segment->oppSign(next);
oppSum += operandsMatch ? segment->oppSign(next) : segment->spanSign(next);
const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd));
if (segment->_xor()) {
// SK_ALWAYSBREAK(span.fWindValue == 1);
// SK_ALWAYSBREAK(span.fWindSum == SK_MinS32 || span.fWindSum == 1);
}
if (segment->oppXor()) {
SK_ALWAYSBREAK(span.fOppValue == 0 || abs(span.fOppValue) == 1);
// SK_ALWAYSBREAK(span.fOppSum == SK_MinS32 || span.fOppSum == 0 || abs(span.fOppSum) == 1);
}
next = next->next();
if (!next) {
return;
}
} while (next != first);
if (unorderable) {
return;
}
SK_ALWAYSBREAK(!signSum || fSegment->_xor());
SK_ALWAYSBREAK(!oppSum || fSegment->oppXor());
int lastWinding;
int lastOppWinding;
int winding;
int oppWinding;
do {
const SkOpSegment* segment = next->fSegment;
const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd));
winding = span.fWindSum;
if (winding != SK_MinS32) {
// SK_ALWAYSBREAK(winding != 0);
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(winding));
lastWinding = winding;
int diffWinding = segment->spanSign(next);
if (!segment->_xor()) {
SK_ALWAYSBREAK(diffWinding != 0);
bool sameSign = (winding > 0) == (diffWinding > 0);
winding -= sameSign ? diffWinding : -diffWinding;
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(winding));
SK_ALWAYSBREAK(abs(winding) <= abs(lastWinding));
if (!sameSign) {
SkTSwap(winding, lastWinding);
}
}
lastOppWinding = oppWinding = span.fOppSum;
if (oppWinding != SK_MinS32 && !segment->oppXor()) {
int oppDiffWinding = segment->oppSign(next);
// SK_ALWAYSBREAK(abs(oppDiffWinding) <= abs(diffWinding) || segment->_xor());
if (oppDiffWinding) {
bool oppSameSign = (oppWinding > 0) == (oppDiffWinding > 0);
oppWinding -= oppSameSign ? oppDiffWinding : -oppDiffWinding;
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(oppWinding));
SK_ALWAYSBREAK(abs(oppWinding) <= abs(lastOppWinding));
if (!oppSameSign) {
SkTSwap(oppWinding, lastOppWinding);
}
}
}
firstOperand = segment->operand();
break;
}
SK_ALWAYSBREAK(span.fOppSum == SK_MinS32);
next = next->next();
} while (next != first);
if (winding == SK_MinS32) {
return;
}
SK_ALWAYSBREAK(oppWinding == SK_MinS32 || SkPathOpsDebug::ValidWind(oppWinding));
first = next;
next = next->next();
do {
const SkOpSegment* segment = next->fSegment;
lastWinding = winding;
lastOppWinding = oppWinding;
bool operandsMatch = firstOperand == segment->operand();
if (operandsMatch) {
if (!segment->_xor()) {
winding -= segment->spanSign(next);
SK_ALWAYSBREAK(winding != lastWinding);
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(winding));
}
if (!segment->oppXor()) {
int oppDiffWinding = segment->oppSign(next);
if (oppWinding != SK_MinS32) {
oppWinding -= oppDiffWinding;
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(oppWinding));
} else {
SK_ALWAYSBREAK(oppDiffWinding == 0);
}
}
} else {
if (!segment->oppXor()) {
winding -= segment->oppSign(next);
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(winding));
}
if (!segment->_xor()) {
oppWinding -= segment->spanSign(next);
SK_ALWAYSBREAK(oppWinding != lastOppWinding);
SK_ALWAYSBREAK(SkPathOpsDebug::ValidWind(oppWinding));
}
}
bool useInner = SkOpSegment::UseInnerWinding(lastWinding, winding);
int sumWinding = useInner ? winding : lastWinding;
bool oppUseInner = SkOpSegment::UseInnerWinding(lastOppWinding, oppWinding);
int oppSumWinding = oppUseInner ? oppWinding : lastOppWinding;
if (!operandsMatch) {
SkTSwap(useInner, oppUseInner);
SkTSwap(sumWinding, oppSumWinding);
}
const SkOpSpan& span = segment->span(SkMin32(next->fStart, next->fEnd));
if (winding == -lastWinding) {
if (span.fWindSum != SK_MinS32) {
SkDebugf("%s useInner=%d spanSign=%d lastWinding=%d winding=%d windSum=%d\n",
__FUNCTION__,
useInner, segment->spanSign(next), lastWinding, winding, span.fWindSum);
}
}
if (oppWinding != SK_MinS32) {
if (span.fOppSum != SK_MinS32) {
SK_ALWAYSBREAK(span.fOppSum == oppSumWinding || segment->oppXor() || segment->_xor());
}
} else {
SK_ALWAYSBREAK(!firstOperand);
SK_ALWAYSBREAK(!segment->operand());
SK_ALWAYSBREAK(!span.fOppValue);
}
next = next->next();
} while (next != first);
}
#endif
#if DEBUG_SWAP_TOP
bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
if (fVerb != SkPath::kCubic_Verb) {
return false;
}
SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
return dst.controlsContainedByEnds();
}
#endif
#if DEBUG_CONCIDENT
// SK_ALWAYSBREAK if pair has not already been added
void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const {
for (int i = 0; i < fTs.count(); ++i) {
if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
return;
}
}
SK_ALWAYSBREAK(0);
}
#endif
#if DEBUG_ANGLE
void SkOpSegment::debugCheckPointsEqualish(int tStart, int tEnd) const {
const SkPoint& basePt = fTs[tStart].fPt;
while (++tStart < tEnd) {
const SkPoint& cmpPt = fTs[tStart].fPt;
SK_ALWAYSBREAK(SkDPoint::ApproximatelyEqual(basePt, cmpPt));
}
}
#endif
#if DEBUG_VALIDATE
bool SkOpSegment::debugContains(const SkOpAngle* angle) const {
for (int index = 0; index < fAngles.count(); ++index) {
if (&fAngles[index] == angle) {
return true;
}
}
for (int index = 0; index < fSingletonAngles.count(); ++index) {
if (&fSingletonAngles[index] == angle) {
return true;
}
}
return false;
}
#endif
#if DEBUG_SWAP_TOP
int SkOpSegment::debugInflections(int tStart, int tEnd) const {
if (fVerb != SkPath::kCubic_Verb) {
return false;
}
SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
double inflections[2];
return dst.findInflections(inflections);
}
#endif
void SkOpSegment::debugReset() {
fTs.reset();
fAngles.reset();
}
#if DEBUG_CONCIDENT
void SkOpSegment::debugShowTs(const char* prefix) const {
SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID);
int lastWind = -1;
int lastOpp = -1;
double lastT = -1;
int i;
for (i = 0; i < fTs.count(); ++i) {
bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
|| lastOpp != fTs[i].fOppValue;
if (change && lastWind >= 0) {
SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
}
if (change) {
SkDebugf(" [o=%d", fTs[i].fOther->fID);
lastWind = fTs[i].fWindValue;
lastOpp = fTs[i].fOppValue;
lastT = fTs[i].fT;
} else {
SkDebugf(",%d", fTs[i].fOther->fID);
}
}
if (i <= 0) {
return;
}
SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
if (fOperand) {
SkDebugf(" operand");
}
if (done()) {
SkDebugf(" done");
}
SkDebugf("\n");
}
#endif
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void SkOpSegment::debugShowActiveSpans() const {
debugValidate();
if (done()) {
return;
}
#if DEBUG_ACTIVE_SPANS_SHORT_FORM
int lastId = -1;
double lastT = -1;
#endif
for (int i = 0; i < fTs.count(); ++i) {
if (fTs[i].fDone) {
continue;
}
SK_ALWAYSBREAK(i < fTs.count() - 1);
#if DEBUG_ACTIVE_SPANS_SHORT_FORM
if (lastId == fID && lastT == fTs[i].fT) {
continue;
}
lastId = fID;
lastT = fTs[i].fT;
#endif
SkDebugf("%s id=%d", __FUNCTION__, fID);
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
}
const SkOpSpan* span = &fTs[i];
SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span));
int iEnd = i + 1;
while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
++iEnd;
}
SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
const SkOpSegment* other = fTs[i].fOther;
SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
if (fTs[i].fWindSum == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", fTs[i].fWindSum);
}
SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
}
}
#endif
#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) {
const SkPoint& pt = xyAtT(&span);
SkDebugf("%s id=%d", fun, fID);
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
}
SK_ALWAYSBREAK(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=",
span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
(&span)[1].fT, winding);
if (span.fWindSum == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", span.fWindSum);
}
SkDebugf(" windValue=%d\n", span.fWindValue);
}
void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding,
int oppWinding) {
const SkPoint& pt = xyAtT(&span);
SkDebugf("%s id=%d", fun, fID);
SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
}
SK_ALWAYSBREAK(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=",
span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
(&span)[1].fT, winding, oppWinding);
if (span.fOppSum == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", span.fOppSum);
}
SkDebugf(" windSum=");
if (span.fWindSum == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", span.fWindSum);
}
SkDebugf(" windValue=%d\n", span.fWindValue);
}
#endif
#if DEBUG_SHOW_WINDING
int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
if (!(1 << fID & ofInterest)) {
return 0;
}
int sum = 0;
SkTArray<char, true> slots(slotCount * 2);
memset(slots.begin(), ' ', slotCount * 2);
for (int i = 0; i < fTs.count(); ++i) {
// if (!(1 << fTs[i].fOther->fID & ofInterest)) {
// continue;
// }
sum += fTs[i].fWindValue;
slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
sum += fTs[i].fOppValue;
slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
}
SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
slots.begin() + slotCount);
return sum;
}
#endif
void SkOpSegment::debugValidate() const {
#if DEBUG_VALIDATE
int count = fTs.count();
SK_ALWAYSBREAK(count >= 2);
SK_ALWAYSBREAK(fTs[0].fT == 0);
SK_ALWAYSBREAK(fTs[count - 1].fT == 1);
int done = 0;
double t = -1;
const SkOpSpan* last = NULL;
bool tinyTFound = false;
bool hasLoop = false;
for (int i = 0; i < count; ++i) {
const SkOpSpan& span = fTs[i];
SK_ALWAYSBREAK(t <= span.fT);
t = span.fT;
int otherIndex = span.fOtherIndex;
const SkOpSegment* other = span.fOther;
SK_ALWAYSBREAK(other != this || fVerb == SkPath::kCubic_Verb);
const SkOpSpan& otherSpan = other->fTs[otherIndex];
SK_ALWAYSBREAK(otherSpan.fPt == span.fPt);
SK_ALWAYSBREAK(otherSpan.fOtherT == t);
SK_ALWAYSBREAK(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
done += span.fDone;
if (last) {
bool tsEqual = last->fT == span.fT;
bool tsPreciselyEqual = precisely_equal(last->fT, span.fT);
SK_ALWAYSBREAK(!tsEqual || tsPreciselyEqual);
bool pointsEqual = last->fPt == span.fPt;
bool pointsNearlyEqual = AlmostEqualUlps(last->fPt, span.fPt);
#if 0 // bufferOverflow test triggers this
SK_ALWAYSBREAK(!tsPreciselyEqual || pointsNearlyEqual);
#endif
// SK_ALWAYSBREAK(!last->fTiny || !tsPreciselyEqual || span.fTiny || tinyTFound);
SK_ALWAYSBREAK(last->fTiny || tsPreciselyEqual || !pointsEqual || hasLoop);
SK_ALWAYSBREAK(!last->fTiny || pointsEqual);
SK_ALWAYSBREAK(!last->fTiny || last->fDone);
SK_ALWAYSBREAK(!last->fSmall || pointsNearlyEqual);
SK_ALWAYSBREAK(!last->fSmall || last->fDone);
// SK_ALWAYSBREAK(!last->fSmall || last->fTiny);
// SK_ALWAYSBREAK(last->fTiny || !pointsEqual || last->fDone == span.fDone);
if (last->fTiny) {
tinyTFound |= !tsPreciselyEqual;
} else {
tinyTFound = false;
}
}
last = &span;
hasLoop |= last->fLoop;
}
SK_ALWAYSBREAK(done == fDoneSpans);
if (fAngles.count() ) {
fAngles.begin()->debugValidateLoop();
}
#endif
}