1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkOpContour.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,388 @@
1.4 +/*
1.5 +* Copyright 2013 Google Inc.
1.6 +*
1.7 +* Use of this source code is governed by a BSD-style license that can be
1.8 +* found in the LICENSE file.
1.9 +*/
1.10 +#include "SkIntersections.h"
1.11 +#include "SkOpContour.h"
1.12 +#include "SkPathWriter.h"
1.13 +#include "SkTSort.h"
1.14 +
1.15 +bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
1.16 + const SkIntersections& ts, bool swap) {
1.17 + SkPoint pt0 = ts.pt(0).asSkPoint();
1.18 + SkPoint pt1 = ts.pt(1).asSkPoint();
1.19 + if (pt0 == pt1) {
1.20 + // FIXME: one could imagine a case where it would be incorrect to ignore this
1.21 + // suppose two self-intersecting cubics overlap to be coincident --
1.22 + // this needs to check that by some measure the t values are far enough apart
1.23 + // or needs to check to see if the self-intersection bit was set on the cubic segment
1.24 + return false;
1.25 + }
1.26 + SkCoincidence& coincidence = fCoincidences.push_back();
1.27 + coincidence.fOther = other;
1.28 + coincidence.fSegments[0] = index;
1.29 + coincidence.fSegments[1] = otherIndex;
1.30 + coincidence.fTs[swap][0] = ts[0][0];
1.31 + coincidence.fTs[swap][1] = ts[0][1];
1.32 + coincidence.fTs[!swap][0] = ts[1][0];
1.33 + coincidence.fTs[!swap][1] = ts[1][1];
1.34 + coincidence.fPts[0] = pt0;
1.35 + coincidence.fPts[1] = pt1;
1.36 + return true;
1.37 +}
1.38 +
1.39 +SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
1.40 + int segmentCount = fSortedSegments.count();
1.41 + SkASSERT(segmentCount > 0);
1.42 + for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
1.43 + SkOpSegment* testSegment = fSortedSegments[sortedIndex];
1.44 + if (testSegment->done()) {
1.45 + continue;
1.46 + }
1.47 + *start = *end = 0;
1.48 + while (testSegment->nextCandidate(start, end)) {
1.49 + if (!testSegment->isVertical(*start, *end)) {
1.50 + return testSegment;
1.51 + }
1.52 + }
1.53 + }
1.54 + return NULL;
1.55 +}
1.56 +
1.57 +// first pass, add missing T values
1.58 +// second pass, determine winding values of overlaps
1.59 +void SkOpContour::addCoincidentPoints() {
1.60 + int count = fCoincidences.count();
1.61 + for (int index = 0; index < count; ++index) {
1.62 + SkCoincidence& coincidence = fCoincidences[index];
1.63 + int thisIndex = coincidence.fSegments[0];
1.64 + SkOpSegment& thisOne = fSegments[thisIndex];
1.65 + SkOpContour* otherContour = coincidence.fOther;
1.66 + int otherIndex = coincidence.fSegments[1];
1.67 + SkOpSegment& other = otherContour->fSegments[otherIndex];
1.68 + if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
1.69 + // OPTIMIZATION: remove from array
1.70 + continue;
1.71 + }
1.72 + #if DEBUG_CONCIDENT
1.73 + thisOne.debugShowTs("-");
1.74 + other.debugShowTs("o");
1.75 + #endif
1.76 + double startT = coincidence.fTs[0][0];
1.77 + double endT = coincidence.fTs[0][1];
1.78 + bool startSwapped, oStartSwapped, cancelers;
1.79 + if ((cancelers = startSwapped = startT > endT)) {
1.80 + SkTSwap(startT, endT);
1.81 + }
1.82 + if (startT == endT) { // if one is very large the smaller may have collapsed to nothing
1.83 + if (endT <= 1 - FLT_EPSILON) {
1.84 + endT += FLT_EPSILON;
1.85 + SkASSERT(endT <= 1);
1.86 + } else {
1.87 + startT -= FLT_EPSILON;
1.88 + SkASSERT(startT >= 0);
1.89 + }
1.90 + }
1.91 + SkASSERT(!approximately_negative(endT - startT));
1.92 + double oStartT = coincidence.fTs[1][0];
1.93 + double oEndT = coincidence.fTs[1][1];
1.94 + if ((oStartSwapped = oStartT > oEndT)) {
1.95 + SkTSwap(oStartT, oEndT);
1.96 + cancelers ^= true;
1.97 + }
1.98 + SkASSERT(!approximately_negative(oEndT - oStartT));
1.99 + if (cancelers) {
1.100 + // make sure startT and endT have t entries
1.101 + const SkPoint& startPt = coincidence.fPts[startSwapped];
1.102 + if (startT > 0 || oEndT < 1
1.103 + || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
1.104 + thisOne.addTPair(startT, &other, oEndT, true, startPt);
1.105 + }
1.106 + const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
1.107 + if (oStartT > 0 || endT < 1
1.108 + || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
1.109 + other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
1.110 + }
1.111 + } else {
1.112 + const SkPoint& startPt = coincidence.fPts[startSwapped];
1.113 + if (startT > 0 || oStartT > 0
1.114 + || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
1.115 + thisOne.addTPair(startT, &other, oStartT, true, startPt);
1.116 + }
1.117 + const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
1.118 + if (endT < 1 || oEndT < 1
1.119 + || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
1.120 + other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
1.121 + }
1.122 + }
1.123 + #if DEBUG_CONCIDENT
1.124 + thisOne.debugShowTs("+");
1.125 + other.debugShowTs("o");
1.126 + #endif
1.127 + }
1.128 +}
1.129 +
1.130 +bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
1.131 + const SkIntersections& ts, int ptIndex, bool swap) {
1.132 + SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
1.133 + SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
1.134 + if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
1.135 + // FIXME: one could imagine a case where it would be incorrect to ignore this
1.136 + // suppose two self-intersecting cubics overlap to form a partial coincidence --
1.137 + // although it isn't clear why the regular coincidence could wouldn't pick this up
1.138 + // this is exceptional enough to ignore for now
1.139 + return false;
1.140 + }
1.141 + SkCoincidence& coincidence = fPartialCoincidences.push_back();
1.142 + coincidence.fOther = other;
1.143 + coincidence.fSegments[0] = index;
1.144 + coincidence.fSegments[1] = otherIndex;
1.145 + coincidence.fTs[swap][0] = ts[0][ptIndex];
1.146 + coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
1.147 + coincidence.fTs[!swap][0] = ts[1][ptIndex];
1.148 + coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
1.149 + coincidence.fPts[0] = pt0;
1.150 + coincidence.fPts[1] = pt1;
1.151 + return true;
1.152 +}
1.153 +
1.154 +void SkOpContour::calcCoincidentWinding() {
1.155 + int count = fCoincidences.count();
1.156 +#if DEBUG_CONCIDENT
1.157 + if (count > 0) {
1.158 + SkDebugf("%s count=%d\n", __FUNCTION__, count);
1.159 + }
1.160 +#endif
1.161 + for (int index = 0; index < count; ++index) {
1.162 + SkCoincidence& coincidence = fCoincidences[index];
1.163 + calcCommonCoincidentWinding(coincidence);
1.164 + }
1.165 +}
1.166 +
1.167 +void SkOpContour::calcPartialCoincidentWinding() {
1.168 + int count = fPartialCoincidences.count();
1.169 +#if DEBUG_CONCIDENT
1.170 + if (count > 0) {
1.171 + SkDebugf("%s count=%d\n", __FUNCTION__, count);
1.172 + }
1.173 +#endif
1.174 + for (int index = 0; index < count; ++index) {
1.175 + SkCoincidence& coincidence = fPartialCoincidences[index];
1.176 + calcCommonCoincidentWinding(coincidence);
1.177 + }
1.178 +}
1.179 +
1.180 +void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
1.181 + int count = coincidences.count();
1.182 +#if DEBUG_CONCIDENT
1.183 + if (count > 0) {
1.184 + SkDebugf("%s count=%d\n", __FUNCTION__, count);
1.185 + }
1.186 +#endif
1.187 + // look for a lineup where the partial implies another adjoining coincidence
1.188 + for (int index = 0; index < count; ++index) {
1.189 + const SkCoincidence& coincidence = coincidences[index];
1.190 + int thisIndex = coincidence.fSegments[0];
1.191 + SkOpSegment& thisOne = fSegments[thisIndex];
1.192 + SkOpContour* otherContour = coincidence.fOther;
1.193 + int otherIndex = coincidence.fSegments[1];
1.194 + SkOpSegment& other = otherContour->fSegments[otherIndex];
1.195 + double startT = coincidence.fTs[0][0];
1.196 + double endT = coincidence.fTs[0][1];
1.197 + if (startT == endT) { // this can happen in very large compares
1.198 + continue;
1.199 + }
1.200 + double oStartT = coincidence.fTs[1][0];
1.201 + double oEndT = coincidence.fTs[1][1];
1.202 + if (oStartT == oEndT) {
1.203 + continue;
1.204 + }
1.205 + bool swapStart = startT > endT;
1.206 + bool swapOther = oStartT > oEndT;
1.207 + if (swapStart) {
1.208 + SkTSwap<double>(startT, endT);
1.209 + SkTSwap<double>(oStartT, oEndT);
1.210 + }
1.211 + bool cancel = swapOther != swapStart;
1.212 + int step = swapStart ? -1 : 1;
1.213 + int oStep = swapOther ? -1 : 1;
1.214 + double oMatchStart = cancel ? oEndT : oStartT;
1.215 + if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
1.216 + bool added = false;
1.217 + if (oMatchStart != 0) {
1.218 + added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
1.219 + }
1.220 + if (!cancel && startT != 0 && !added) {
1.221 + (void) other.joinCoincidence(&thisOne, startT, step, cancel);
1.222 + }
1.223 + }
1.224 + double oMatchEnd = cancel ? oStartT : oEndT;
1.225 + if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
1.226 + bool added = false;
1.227 + if (cancel && endT != 1 && !added) {
1.228 + (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
1.229 + }
1.230 + }
1.231 + }
1.232 +}
1.233 +
1.234 +void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
1.235 + int thisIndex = coincidence.fSegments[0];
1.236 + SkOpSegment& thisOne = fSegments[thisIndex];
1.237 + if (thisOne.done()) {
1.238 + return;
1.239 + }
1.240 + SkOpContour* otherContour = coincidence.fOther;
1.241 + int otherIndex = coincidence.fSegments[1];
1.242 + SkOpSegment& other = otherContour->fSegments[otherIndex];
1.243 + if (other.done()) {
1.244 + return;
1.245 + }
1.246 + double startT = coincidence.fTs[0][0];
1.247 + double endT = coincidence.fTs[0][1];
1.248 + const SkPoint* startPt = &coincidence.fPts[0];
1.249 + const SkPoint* endPt = &coincidence.fPts[1];
1.250 + bool cancelers;
1.251 + if ((cancelers = startT > endT)) {
1.252 + SkTSwap<double>(startT, endT);
1.253 + SkTSwap<const SkPoint*>(startPt, endPt);
1.254 + }
1.255 + if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
1.256 + if (endT <= 1 - FLT_EPSILON) {
1.257 + endT += FLT_EPSILON;
1.258 + SkASSERT(endT <= 1);
1.259 + } else {
1.260 + startT -= FLT_EPSILON;
1.261 + SkASSERT(startT >= 0);
1.262 + }
1.263 + }
1.264 + SkASSERT(!approximately_negative(endT - startT));
1.265 + double oStartT = coincidence.fTs[1][0];
1.266 + double oEndT = coincidence.fTs[1][1];
1.267 + if (oStartT > oEndT) {
1.268 + SkTSwap<double>(oStartT, oEndT);
1.269 + cancelers ^= true;
1.270 + }
1.271 + SkASSERT(!approximately_negative(oEndT - oStartT));
1.272 + if (cancelers) {
1.273 + thisOne.addTCancel(*startPt, *endPt, &other);
1.274 + } else {
1.275 + thisOne.addTCoincident(*startPt, *endPt, endT, &other);
1.276 + }
1.277 +#if DEBUG_CONCIDENT
1.278 + thisOne.debugShowTs("p");
1.279 + other.debugShowTs("o");
1.280 +#endif
1.281 +}
1.282 +
1.283 +void SkOpContour::sortSegments() {
1.284 + int segmentCount = fSegments.count();
1.285 + fSortedSegments.push_back_n(segmentCount);
1.286 + for (int test = 0; test < segmentCount; ++test) {
1.287 + fSortedSegments[test] = &fSegments[test];
1.288 + }
1.289 + SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
1.290 + fFirstSorted = 0;
1.291 +}
1.292 +
1.293 +void SkOpContour::toPath(SkPathWriter* path) const {
1.294 + int segmentCount = fSegments.count();
1.295 + const SkPoint& pt = fSegments.front().pts()[0];
1.296 + path->deferredMove(pt);
1.297 + for (int test = 0; test < segmentCount; ++test) {
1.298 + fSegments[test].addCurveTo(0, 1, path, true);
1.299 + }
1.300 + path->close();
1.301 +}
1.302 +
1.303 +void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
1.304 + SkOpSegment** topStart) {
1.305 + int segmentCount = fSortedSegments.count();
1.306 + SkASSERT(segmentCount > 0);
1.307 + int sortedIndex = fFirstSorted;
1.308 + fDone = true; // may be cleared below
1.309 + for ( ; sortedIndex < segmentCount; ++sortedIndex) {
1.310 + SkOpSegment* testSegment = fSortedSegments[sortedIndex];
1.311 + if (testSegment->done()) {
1.312 + if (sortedIndex == fFirstSorted) {
1.313 + ++fFirstSorted;
1.314 + }
1.315 + continue;
1.316 + }
1.317 + fDone = false;
1.318 + SkPoint testXY = testSegment->activeLeftTop(true, NULL);
1.319 + if (*topStart) {
1.320 + if (testXY.fY < topLeft.fY) {
1.321 + continue;
1.322 + }
1.323 + if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
1.324 + continue;
1.325 + }
1.326 + if (bestXY->fY < testXY.fY) {
1.327 + continue;
1.328 + }
1.329 + if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
1.330 + continue;
1.331 + }
1.332 + }
1.333 + *topStart = testSegment;
1.334 + *bestXY = testXY;
1.335 + }
1.336 +}
1.337 +
1.338 +SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
1.339 + int segmentCount = fSegments.count();
1.340 + for (int test = 0; test < segmentCount; ++test) {
1.341 + SkOpSegment* testSegment = &fSegments[test];
1.342 + if (testSegment->done()) {
1.343 + continue;
1.344 + }
1.345 + testSegment->undoneSpan(start, end);
1.346 + return testSegment;
1.347 + }
1.348 + return NULL;
1.349 +}
1.350 +
1.351 +#if DEBUG_SHOW_WINDING
1.352 +int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
1.353 + int count = fSegments.count();
1.354 + int sum = 0;
1.355 + for (int index = 0; index < count; ++index) {
1.356 + sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
1.357 + }
1.358 +// SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
1.359 + return sum;
1.360 +}
1.361 +
1.362 +void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
1.363 +// int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
1.364 +// int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
1.365 + int ofInterest = 1 << 5 | 1 << 8;
1.366 + int total = 0;
1.367 + int index;
1.368 + for (index = 0; index < contourList.count(); ++index) {
1.369 + total += contourList[index]->segments().count();
1.370 + }
1.371 + int sum = 0;
1.372 + for (index = 0; index < contourList.count(); ++index) {
1.373 + sum += contourList[index]->debugShowWindingValues(total, ofInterest);
1.374 + }
1.375 +// SkDebugf("%s total=%d\n", __FUNCTION__, sum);
1.376 +}
1.377 +#endif
1.378 +
1.379 +void SkOpContour::setBounds() {
1.380 + int count = fSegments.count();
1.381 + if (count == 0) {
1.382 + SkDebugf("%s empty contour\n", __FUNCTION__);
1.383 + SkASSERT(0);
1.384 + // FIXME: delete empty contour?
1.385 + return;
1.386 + }
1.387 + fBounds = fSegments.front().bounds();
1.388 + for (int index = 1; index < count; ++index) {
1.389 + fBounds.add(fSegments[index].bounds());
1.390 + }
1.391 +}
