blob: 28c072a3c1340200c2cd7f1b2514bd20b19e2c05 [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 "SkIntersections.h"
#include "SkOpContour.h"
#include "SkPathWriter.h"
#include "SkTSort.h"
bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
const SkIntersections& ts, bool swap) {
SkPoint pt0 = ts.pt(0).asSkPoint();
SkPoint pt1 = ts.pt(1).asSkPoint();
if (pt0 == pt1 || ts[0][0] == ts[0][1] || ts[1][0] == ts[1][1]) {
// FIXME: one could imagine a case where it would be incorrect to ignore this
// suppose two self-intersecting cubics overlap to be coincident --
// this needs to check that by some measure the t values are far enough apart
// or needs to check to see if the self-intersection bit was set on the cubic segment
return false;
}
SkCoincidence& coincidence = fCoincidences.push_back();
coincidence.fOther = other;
coincidence.fSegments[0] = index;
coincidence.fSegments[1] = otherIndex;
coincidence.fTs[swap][0] = ts[0][0];
coincidence.fTs[swap][1] = ts[0][1];
coincidence.fTs[!swap][0] = ts[1][0];
coincidence.fTs[!swap][1] = ts[1][1];
coincidence.fPts[swap][0] = pt0;
coincidence.fPts[swap][1] = pt1;
bool nearStart = ts.nearlySame(0);
bool nearEnd = ts.nearlySame(1);
coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
coincidence.fNearly[0] = nearStart;
coincidence.fNearly[1] = nearEnd;
return true;
}
SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
int segmentCount = fSortedSegments.count();
SkASSERT(segmentCount > 0);
for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
SkOpSegment* testSegment = fSortedSegments[sortedIndex];
if (testSegment->done()) {
continue;
}
*start = *end = 0;
while (testSegment->nextCandidate(start, end)) {
if (!testSegment->isVertical(*start, *end)) {
return testSegment;
}
}
}
return NULL;
}
// if one is very large the smaller may have collapsed to nothing
static void bump_out_close_span(double* startTPtr, double* endTPtr) {
double startT = *startTPtr;
double endT = *endTPtr;
if (approximately_negative(endT - startT)) {
if (endT <= 1 - FLT_EPSILON) {
*endTPtr += FLT_EPSILON;
SkASSERT(*endTPtr <= 1);
} else {
*startTPtr -= FLT_EPSILON;
SkASSERT(*startTPtr >= 0);
}
}
}
// first pass, add missing T values
// second pass, determine winding values of overlaps
void SkOpContour::addCoincidentPoints() {
int count = fCoincidences.count();
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fCoincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
// OPTIMIZATION: remove from array
continue;
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs("-");
other.debugShowTs("o");
#endif
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
bool startSwapped, oStartSwapped, cancelers;
if ((cancelers = startSwapped = startT > endT)) {
SkTSwap(startT, endT);
}
bump_out_close_span(&startT, &endT);
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if ((oStartSwapped = oStartT > oEndT)) {
SkTSwap(oStartT, oEndT);
cancelers ^= true;
}
bump_out_close_span(&oStartT, &oEndT);
SkASSERT(!approximately_negative(oEndT - oStartT));
const SkPoint& startPt = coincidence.fPts[0][startSwapped];
if (cancelers) {
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
thisOne.addTPair(startT, &other, oEndT, true, startPt,
coincidence.fPts[1][startSwapped]);
}
const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
coincidence.fPts[0][oStartSwapped]);
}
} else {
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
thisOne.addTPair(startT, &other, oStartT, true, startPt,
coincidence.fPts[1][startSwapped]);
}
const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
coincidence.fPts[0][!oStartSwapped]);
}
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs("+");
other.debugShowTs("o");
#endif
}
// if there are multiple pairs of coincidence that share an edge, see if the opposite
// are also coincident
for (int index = 0; index < count - 1; ++index) {
const SkCoincidence& coincidence = fCoincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
for (int idx2 = 1; idx2 < count; ++idx2) {
const SkCoincidence& innerCoin = fCoincidences[idx2];
int innerThisIndex = innerCoin.fSegments[0];
if (thisIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
}
if (this == otherContour && otherIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
}
SkOpContour* innerOtherContour = innerCoin.fOther;
innerThisIndex = innerCoin.fSegments[1];
if (this == innerOtherContour && thisIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
}
if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
}
}
}
}
bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
const SkIntersections& ts, int ptIndex, bool swap) {
SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
// FIXME: one could imagine a case where it would be incorrect to ignore this
// suppose two self-intersecting cubics overlap to form a partial coincidence --
// although it isn't clear why the regular coincidence could wouldn't pick this up
// this is exceptional enough to ignore for now
return false;
}
SkCoincidence& coincidence = fPartialCoincidences.push_back();
coincidence.fOther = other;
coincidence.fSegments[0] = index;
coincidence.fSegments[1] = otherIndex;
coincidence.fTs[swap][0] = ts[0][ptIndex];
coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
coincidence.fTs[!swap][0] = ts[1][ptIndex];
coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
coincidence.fNearly[0] = 0;
coincidence.fNearly[1] = 0;
return true;
}
void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
SkCoincidence* coincidence) {
for (int idx2 = 0; idx2 < 2; ++idx2) {
if (coincidence->fPts[0][idx2] == aligned.fOldPt
&& coincidence->fTs[swap][idx2] == aligned.fOldT) {
SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
coincidence->fPts[0][idx2] = aligned.fPt;
SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
coincidence->fTs[swap][idx2] = aligned.fT;
}
}
}
void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
SkTArray<SkCoincidence, true>* coincidences) {
int count = coincidences->count();
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = (*coincidences)[index];
int thisIndex = coincidence.fSegments[0];
const SkOpSegment* thisOne = &fSegments[thisIndex];
const SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
const SkOpSegment* other = &otherContour->fSegments[otherIndex];
if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
align(aligned, false, &coincidence);
} else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
align(aligned, true, &coincidence);
}
}
}
void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
int zeroPt;
if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
alignPt(segmentIndex, point, zeroPt);
}
if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
other->alignPt(otherIndex, point, zeroPt);
}
}
void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
const SkOpSegment& segment = fSegments[index];
if (0 == zeroPt) {
*point = segment.pts()[0];
} else {
*point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
}
}
int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
double tVal = (*ts)[swap][tIndex];
if (tVal != 0 && precisely_zero(tVal)) {
ts->set(swap, tIndex, 0);
return 0;
}
if (tVal != 1 && precisely_equal(tVal, 1)) {
ts->set(swap, tIndex, 1);
return 1;
}
return -1;
}
bool SkOpContour::calcAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
if (!fSegments[test].calcAngles()) {
return false;
}
}
return true;
}
bool SkOpContour::calcCoincidentWinding() {
int count = fCoincidences.count();
#if DEBUG_CONCIDENT
if (count > 0) {
SkDebugf("%s count=%d\n", __FUNCTION__, count);
}
#endif
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fCoincidences[index];
if (!calcCommonCoincidentWinding(coincidence)) {
return false;
}
}
return true;
}
void SkOpContour::calcPartialCoincidentWinding() {
int count = fPartialCoincidences.count();
#if DEBUG_CONCIDENT
if (count > 0) {
SkDebugf("%s count=%d\n", __FUNCTION__, count);
}
#endif
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fPartialCoincidences[index];
calcCommonCoincidentWinding(coincidence);
}
// if there are multiple pairs of partial coincidence that share an edge, see if the opposite
// are also coincident
for (int index = 0; index < count - 1; ++index) {
const SkCoincidence& coincidence = fPartialCoincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
for (int idx2 = 1; idx2 < count; ++idx2) {
const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
int innerThisIndex = innerCoin.fSegments[0];
if (thisIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
}
if (this == otherContour && otherIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
}
SkOpContour* innerOtherContour = innerCoin.fOther;
innerThisIndex = innerCoin.fSegments[1];
if (this == innerOtherContour && thisIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
}
if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
}
}
}
}
void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
const SkCoincidence& twoCoin, int twoIdx, bool partial) {
SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
// look for common overlap
double min = SK_ScalarMax;
double max = SK_ScalarMin;
double min1 = oneCoin.fTs[!oneIdx][0];
double max1 = oneCoin.fTs[!oneIdx][1];
double min2 = twoCoin.fTs[!twoIdx][0];
double max2 = twoCoin.fTs[!twoIdx][1];
bool cancelers = (min1 < max1) != (min2 < max2);
if (min1 > max1) {
SkTSwap(min1, max1);
}
if (min2 > max2) {
SkTSwap(min2, max2);
}
if (between(min1, min2, max1)) {
min = min2;
}
if (between(min1, max2, max1)) {
max = max2;
}
if (between(min2, min1, max2)) {
min = SkTMin(min, min1);
}
if (between(min2, max1, max2)) {
max = SkTMax(max, max1);
}
if (min >= max) {
return; // no overlap
}
// look to see if opposite are different segments
int seg1Index = oneCoin.fSegments[oneIdx];
int seg2Index = twoCoin.fSegments[twoIdx];
if (seg1Index == seg2Index) {
return;
}
SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
// find opposite t value ranges corresponding to reference min/max range
const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
const int refSegIndex = oneCoin.fSegments[!oneIdx];
const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
int seg1Start = segment1->findOtherT(min, refSegment);
int seg1End = segment1->findOtherT(max, refSegment);
int seg2Start = segment2->findOtherT(min, refSegment);
int seg2End = segment2->findOtherT(max, refSegment);
// if the opposite pairs already contain min/max, we're done
if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
return;
}
double loEnd = SkTMin(min1, min2);
double hiEnd = SkTMax(max1, max2);
// insert the missing coincident point(s)
double missingT1 = -1;
double otherT1 = -1;
if (seg1Start < 0) {
if (seg2Start < 0) {
return;
}
missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
segment2, seg1End);
if (missingT1 < 0) {
return;
}
const SkOpSpan* missingSpan = &segment2->span(seg2Start);
otherT1 = missingSpan->fT;
} else if (seg2Start < 0) {
SkASSERT(seg1Start >= 0);
missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
segment1, seg2End);
if (missingT1 < 0) {
return;
}
const SkOpSpan* missingSpan = &segment1->span(seg1Start);
otherT1 = missingSpan->fT;
}
SkPoint missingPt1;
SkOpSegment* addTo1 = NULL;
SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
int minTIndex = refSegment->findExactT(min, addOther1);
SkASSERT(minTIndex >= 0);
if (missingT1 >= 0) {
missingPt1 = refSegment->span(minTIndex).fPt;
addTo1 = seg1Start < 0 ? segment1 : segment2;
}
double missingT2 = -1;
double otherT2 = -1;
if (seg1End < 0) {
if (seg2End < 0) {
return;
}
missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
segment2, seg1Start);
if (missingT2 < 0) {
return;
}
const SkOpSpan* missingSpan = &segment2->span(seg2End);
otherT2 = missingSpan->fT;
} else if (seg2End < 0) {
SkASSERT(seg1End >= 0);
missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
segment1, seg2Start);
if (missingT2 < 0) {
return;
}
const SkOpSpan* missingSpan = &segment1->span(seg1End);
otherT2 = missingSpan->fT;
}
SkPoint missingPt2;
SkOpSegment* addTo2 = NULL;
SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
int maxTIndex = refSegment->findExactT(max, addOther2);
SkASSERT(maxTIndex >= 0);
if (missingT2 >= 0) {
missingPt2 = refSegment->span(maxTIndex).fPt;
addTo2 = seg1End < 0 ? segment1 : segment2;
}
if (missingT1 >= 0) {
addTo1->pinT(missingPt1, &missingT1);
addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
} else {
SkASSERT(minTIndex >= 0);
missingPt1 = refSegment->span(minTIndex).fPt;
}
if (missingT2 >= 0) {
addTo2->pinT(missingPt2, &missingT2);
addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
} else {
SkASSERT(minTIndex >= 0);
missingPt2 = refSegment->span(maxTIndex).fPt;
}
if (!partial) {
return;
}
if (cancelers) {
if (missingT1 >= 0) {
if (addTo1->reversePoints(missingPt1, missingPt2)) {
SkTSwap(missingPt1, missingPt2);
}
addTo1->addTCancel(missingPt1, missingPt2, addOther1);
} else {
if (addTo2->reversePoints(missingPt1, missingPt2)) {
SkTSwap(missingPt1, missingPt2);
}
addTo2->addTCancel(missingPt1, missingPt2, addOther2);
}
} else if (missingT1 >= 0) {
SkAssertResult(addTo1->addTCoincident(missingPt1, missingPt2,
addTo1 == addTo2 ? missingT2 : otherT2, addOther1));
} else {
SkAssertResult(addTo2->addTCoincident(missingPt2, missingPt1,
addTo2 == addTo1 ? missingT1 : otherT1, addOther2));
}
}
void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
int count = coincidences.count();
#if DEBUG_CONCIDENT
if (count > 0) {
SkDebugf("%s count=%d\n", __FUNCTION__, count);
}
#endif
// look for a lineup where the partial implies another adjoining coincidence
for (int index = 0; index < count; ++index) {
const SkCoincidence& coincidence = coincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
if (thisOne.done()) {
continue;
}
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
if (other.done()) {
continue;
}
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
if (startT == endT) { // this can happen in very large compares
continue;
}
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if (oStartT == oEndT) {
continue;
}
bool swapStart = startT > endT;
bool swapOther = oStartT > oEndT;
const SkPoint* startPt = &coincidence.fPts[0][0];
const SkPoint* endPt = &coincidence.fPts[0][1];
if (swapStart) {
SkTSwap(startT, endT);
SkTSwap(oStartT, oEndT);
SkTSwap(startPt, endPt);
}
bool cancel = swapOther != swapStart;
int step = swapStart ? -1 : 1;
int oStep = swapOther ? -1 : 1;
double oMatchStart = cancel ? oEndT : oStartT;
if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
bool added = false;
if (oMatchStart != 0) {
const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt;
added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel);
}
if (!cancel && startT != 0 && !added) {
(void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel);
}
}
double oMatchEnd = cancel ? oStartT : oEndT;
if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
bool added = false;
if (cancel && endT != 1 && !added) {
(void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel);
}
}
}
}
bool SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
return true;
}
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
if (thisOne.done()) {
return true;
}
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
if (other.done()) {
return true;
}
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
const SkPoint* startPt = &coincidence.fPts[0][0];
const SkPoint* endPt = &coincidence.fPts[0][1];
bool cancelers;
if ((cancelers = startT > endT)) {
SkTSwap<double>(startT, endT);
SkTSwap<const SkPoint*>(startPt, endPt);
}
bump_out_close_span(&startT, &endT);
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if (oStartT > oEndT) {
SkTSwap<double>(oStartT, oEndT);
cancelers ^= true;
}
bump_out_close_span(&oStartT, &oEndT);
SkASSERT(!approximately_negative(oEndT - oStartT));
bool success = true;
if (cancelers) {
thisOne.addTCancel(*startPt, *endPt, &other);
} else {
success = thisOne.addTCoincident(*startPt, *endPt, endT, &other);
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs("p");
other.debugShowTs("o");
#endif
return success;
}
void SkOpContour::resolveNearCoincidence() {
int count = fCoincidences.count();
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fCoincidences[index];
if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
continue;
}
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
// OPTIMIZATION: remove from coincidence array
continue;
}
#if DEBUG_CONCIDENT
thisOne.debugShowTs("-");
other.debugShowTs("o");
#endif
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
bool cancelers;
if ((cancelers = startT > endT)) {
SkTSwap<double>(startT, endT);
}
if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
if (endT <= 1 - FLT_EPSILON) {
endT += FLT_EPSILON;
SkASSERT(endT <= 1);
} else {
startT -= FLT_EPSILON;
SkASSERT(startT >= 0);
}
}
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
if (oStartT > oEndT) {
SkTSwap<double>(oStartT, oEndT);
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
if (cancelers) {
thisOne.blindCancel(coincidence, &other);
} else {
thisOne.blindCoincident(coincidence, &other);
}
}
}
void SkOpContour::sortAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
fSegments[test].sortAngles();
}
}
void SkOpContour::sortSegments() {
int segmentCount = fSegments.count();
fSortedSegments.push_back_n(segmentCount);
for (int test = 0; test < segmentCount; ++test) {
fSortedSegments[test] = &fSegments[test];
}
SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
fFirstSorted = 0;
}
void SkOpContour::toPath(SkPathWriter* path) const {
int segmentCount = fSegments.count();
const SkPoint& pt = fSegments.front().pts()[0];
path->deferredMove(pt);
for (int test = 0; test < segmentCount; ++test) {
fSegments[test].addCurveTo(0, 1, path, true);
}
path->close();
}
void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
SkOpSegment** topStart) {
int segmentCount = fSortedSegments.count();
SkASSERT(segmentCount > 0);
int sortedIndex = fFirstSorted;
fDone = true; // may be cleared below
for ( ; sortedIndex < segmentCount; ++sortedIndex) {
SkOpSegment* testSegment = fSortedSegments[sortedIndex];
if (testSegment->done()) {
if (sortedIndex == fFirstSorted) {
++fFirstSorted;
}
continue;
}
fDone = false;
SkPoint testXY = testSegment->activeLeftTop(NULL);
if (*topStart) {
if (testXY.fY < topLeft.fY) {
continue;
}
if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
continue;
}
if (bestXY->fY < testXY.fY) {
continue;
}
if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
continue;
}
}
*topStart = testSegment;
*bestXY = testXY;
}
}
SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
SkOpSegment* testSegment = &fSegments[test];
if (testSegment->done()) {
continue;
}
testSegment->undoneSpan(start, end);
return testSegment;
}
return NULL;
}
#if DEBUG_SHOW_WINDING
int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
int count = fSegments.count();
int sum = 0;
for (int index = 0; index < count; ++index) {
sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
}
// SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
return sum;
}
void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
// int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
// int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
int ofInterest = 1 << 5 | 1 << 8;
int total = 0;
int index;
for (index = 0; index < contourList.count(); ++index) {
total += contourList[index]->segments().count();
}
int sum = 0;
for (index = 0; index < contourList.count(); ++index) {
sum += contourList[index]->debugShowWindingValues(total, ofInterest);
}
// SkDebugf("%s total=%d\n", __FUNCTION__, sum);
}
#endif
void SkOpContour::setBounds() {
int count = fSegments.count();
if (count == 0) {
SkDebugf("%s empty contour\n", __FUNCTION__);
SkASSERT(0);
// FIXME: delete empty contour?
return;
}
fBounds = fSegments.front().bounds();
for (int index = 1; index < count; ++index) {
fBounds.add(fSegments[index].bounds());
}
}