1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkPathOpsOp.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,320 @@
1.4 +/*
1.5 + * Copyright 2012 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 "SkAddIntersections.h"
1.11 +#include "SkOpEdgeBuilder.h"
1.12 +#include "SkPathOpsCommon.h"
1.13 +#include "SkPathWriter.h"
1.14 +
1.15 +// FIXME: this and find chase should be merge together, along with
1.16 +// other code that walks winding in angles
1.17 +// OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
1.18 +// so it isn't duplicated by walkers like this one
1.19 +static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) {
1.20 + while (chase.count()) {
1.21 + SkOpSpan* span;
1.22 + chase.pop(&span);
1.23 + const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
1.24 + SkOpSegment* segment = backPtr.fOther;
1.25 + nextStart = backPtr.fOtherIndex;
1.26 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.27 + int done = 0;
1.28 + if (segment->activeAngle(nextStart, &done, &angles)) {
1.29 + SkOpAngle* last = angles.end() - 1;
1.30 + nextStart = last->start();
1.31 + nextEnd = last->end();
1.32 + #if TRY_ROTATE
1.33 + *chase.insert(0) = span;
1.34 + #else
1.35 + *chase.append() = span;
1.36 + #endif
1.37 + return last->segment();
1.38 + }
1.39 + if (done == angles.count()) {
1.40 + continue;
1.41 + }
1.42 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.43 + bool sortable = SkOpSegment::SortAngles(angles, &sorted,
1.44 + SkOpSegment::kMayBeUnordered_SortAngleKind);
1.45 + int angleCount = sorted.count();
1.46 +#if DEBUG_SORT
1.47 + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
1.48 +#endif
1.49 + if (!sortable) {
1.50 + continue;
1.51 + }
1.52 + // find first angle, initialize winding to computed fWindSum
1.53 + int firstIndex = -1;
1.54 + const SkOpAngle* angle;
1.55 + bool foundAngle = true;
1.56 + do {
1.57 + ++firstIndex;
1.58 + if (firstIndex >= angleCount) {
1.59 + foundAngle = false;
1.60 + break;
1.61 + }
1.62 + angle = sorted[firstIndex];
1.63 + segment = angle->segment();
1.64 + } while (segment->windSum(angle) == SK_MinS32);
1.65 + if (!foundAngle) {
1.66 + continue;
1.67 + }
1.68 + #if DEBUG_SORT
1.69 + segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
1.70 + #endif
1.71 + int sumMiWinding = segment->updateWindingReverse(angle);
1.72 + int sumSuWinding = segment->updateOppWindingReverse(angle);
1.73 + if (segment->operand()) {
1.74 + SkTSwap<int>(sumMiWinding, sumSuWinding);
1.75 + }
1.76 + int nextIndex = firstIndex + 1;
1.77 + int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1.78 + SkOpSegment* first = NULL;
1.79 + do {
1.80 + SkASSERT(nextIndex != firstIndex);
1.81 + if (nextIndex == angleCount) {
1.82 + nextIndex = 0;
1.83 + }
1.84 + angle = sorted[nextIndex];
1.85 + segment = angle->segment();
1.86 + int start = angle->start();
1.87 + int end = angle->end();
1.88 + int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1.89 + segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
1.90 + &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1.91 + if (!segment->done(angle)) {
1.92 + if (!first) {
1.93 + first = segment;
1.94 + nextStart = start;
1.95 + nextEnd = end;
1.96 + }
1.97 + (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
1.98 + oppSumWinding, angle);
1.99 + }
1.100 + } while (++nextIndex != lastIndex);
1.101 + if (first) {
1.102 + #if TRY_ROTATE
1.103 + *chase.insert(0) = span;
1.104 + #else
1.105 + *chase.append() = span;
1.106 + #endif
1.107 + return first;
1.108 + }
1.109 + }
1.110 + return NULL;
1.111 +}
1.112 +
1.113 +/*
1.114 +static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
1.115 + bool windingIsOp, PathOp op) {
1.116 + bool active = windingIsActive(winding, spanWinding);
1.117 + if (!active) {
1.118 + return false;
1.119 + }
1.120 + if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
1.121 + switch (op) {
1.122 + case kIntersect_Op:
1.123 + case kUnion_Op:
1.124 + return true;
1.125 + case kDifference_Op: {
1.126 + int absSpan = abs(spanWinding);
1.127 + int absOpp = abs(oppSpanWinding);
1.128 + return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
1.129 + }
1.130 + case kXor_Op:
1.131 + return spanWinding != oppSpanWinding;
1.132 + default:
1.133 + SkASSERT(0);
1.134 + }
1.135 + }
1.136 + bool opActive = oppWinding != 0;
1.137 + return gOpLookup[op][opActive][windingIsOp];
1.138 +}
1.139 +*/
1.140 +
1.141 +static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
1.142 + const int xorMask, const int xorOpMask, SkPathWriter* simple) {
1.143 + bool firstContour = true;
1.144 + bool unsortable = false;
1.145 + bool topUnsortable = false;
1.146 + SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
1.147 + do {
1.148 + int index, endIndex;
1.149 + bool done;
1.150 + SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
1.151 + &index, &endIndex, &topLeft, &topUnsortable, &done);
1.152 + if (!current) {
1.153 + if (topUnsortable || !done) {
1.154 + topUnsortable = false;
1.155 + SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
1.156 + topLeft.fX = topLeft.fY = SK_ScalarMin;
1.157 + continue;
1.158 + }
1.159 + break;
1.160 + }
1.161 + SkTDArray<SkOpSpan*> chaseArray;
1.162 + do {
1.163 + if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
1.164 + do {
1.165 + if (!unsortable && current->done()) {
1.166 + #if DEBUG_ACTIVE_SPANS
1.167 + DebugShowActiveSpans(contourList);
1.168 + #endif
1.169 + if (simple->isEmpty()) {
1.170 + simple->init();
1.171 + }
1.172 + break;
1.173 + }
1.174 + SkASSERT(unsortable || !current->done());
1.175 + int nextStart = index;
1.176 + int nextEnd = endIndex;
1.177 + SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd,
1.178 + &unsortable, op, xorMask, xorOpMask);
1.179 + if (!next) {
1.180 + if (!unsortable && simple->hasMove()
1.181 + && current->verb() != SkPath::kLine_Verb
1.182 + && !simple->isClosed()) {
1.183 + current->addCurveTo(index, endIndex, simple, true);
1.184 + SkASSERT(simple->isClosed());
1.185 + }
1.186 + break;
1.187 + }
1.188 + #if DEBUG_FLOW
1.189 + SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
1.190 + current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
1.191 + current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
1.192 + #endif
1.193 + current->addCurveTo(index, endIndex, simple, true);
1.194 + current = next;
1.195 + index = nextStart;
1.196 + endIndex = nextEnd;
1.197 + } while (!simple->isClosed() && (!unsortable
1.198 + || !current->done(SkMin32(index, endIndex))));
1.199 + if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
1.200 + // FIXME : add to simplify, xor cpaths
1.201 + int min = SkMin32(index, endIndex);
1.202 + if (!unsortable && !simple->isEmpty()) {
1.203 + unsortable = current->checkSmall(min);
1.204 + }
1.205 + SkASSERT(unsortable || simple->isEmpty());
1.206 + if (!current->done(min)) {
1.207 + current->addCurveTo(index, endIndex, simple, true);
1.208 + current->markDoneBinary(min);
1.209 + }
1.210 + }
1.211 + simple->close();
1.212 + } else {
1.213 + SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
1.214 + if (last && !last->fLoop) {
1.215 + *chaseArray.append() = last;
1.216 + }
1.217 + }
1.218 + current = findChaseOp(chaseArray, index, endIndex);
1.219 + #if DEBUG_ACTIVE_SPANS
1.220 + DebugShowActiveSpans(contourList);
1.221 + #endif
1.222 + if (!current) {
1.223 + break;
1.224 + }
1.225 + } while (true);
1.226 + } while (true);
1.227 + return simple->someAssemblyRequired();
1.228 +}
1.229 +
1.230 +// pretty picture:
1.231 +// https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
1.232 +static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
1.233 +// inside minuend outside minuend
1.234 +// inside subtrahend outside subtrahend inside subtrahend outside subtrahend
1.235 + {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
1.236 + {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
1.237 + {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }},
1.238 + {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }},
1.239 + {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }},
1.240 +};
1.241 +
1.242 +static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
1.243 + {{ false, false }, { true, false }}, // diff
1.244 + {{ false, false }, { false, true }}, // sect
1.245 + {{ false, true }, { true, true }}, // union
1.246 + {{ false, true }, { true, false }}, // xor
1.247 + {{ false, true }, { false, false }}, // rev diff
1.248 +};
1.249 +
1.250 +bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
1.251 +#if DEBUG_SHOW_TEST_NAME
1.252 + char* debugName = DEBUG_FILENAME_STRING;
1.253 + if (debugName && debugName[0]) {
1.254 + SkPathOpsDebug::BumpTestName(debugName);
1.255 + SkPathOpsDebug::ShowPath(one, two, op, debugName);
1.256 + }
1.257 +#endif
1.258 + op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
1.259 + SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
1.260 + ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
1.261 + const SkPath* minuend = &one;
1.262 + const SkPath* subtrahend = &two;
1.263 + if (op == kReverseDifference_PathOp) {
1.264 + minuend = &two;
1.265 + subtrahend = &one;
1.266 + op = kDifference_PathOp;
1.267 + }
1.268 +#if DEBUG_SORT || DEBUG_SWAP_TOP
1.269 + SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
1.270 +#endif
1.271 + // turn path into list of segments
1.272 + SkTArray<SkOpContour> contours;
1.273 + // FIXME: add self-intersecting cubics' T values to segment
1.274 + SkOpEdgeBuilder builder(*minuend, contours);
1.275 + const int xorMask = builder.xorMask();
1.276 + builder.addOperand(*subtrahend);
1.277 + if (!builder.finish()) {
1.278 + return false;
1.279 + }
1.280 + result->reset();
1.281 + result->setFillType(fillType);
1.282 + const int xorOpMask = builder.xorMask();
1.283 + SkTArray<SkOpContour*, true> contourList;
1.284 + MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
1.285 + xorOpMask == kEvenOdd_PathOpsMask);
1.286 + SkOpContour** currentPtr = contourList.begin();
1.287 + if (!currentPtr) {
1.288 + return true;
1.289 + }
1.290 + SkOpContour** listEnd = contourList.end();
1.291 + // find all intersections between segments
1.292 + do {
1.293 + SkOpContour** nextPtr = currentPtr;
1.294 + SkOpContour* current = *currentPtr++;
1.295 + if (current->containsCubics()) {
1.296 + AddSelfIntersectTs(current);
1.297 + }
1.298 + SkOpContour* next;
1.299 + do {
1.300 + next = *nextPtr++;
1.301 + } while (AddIntersectTs(current, next) && nextPtr != listEnd);
1.302 + } while (currentPtr != listEnd);
1.303 + // eat through coincident edges
1.304 +
1.305 + int total = 0;
1.306 + int index;
1.307 + for (index = 0; index < contourList.count(); ++index) {
1.308 + total += contourList[index]->segments().count();
1.309 + }
1.310 + HandleCoincidence(&contourList, total);
1.311 + // construct closed contours
1.312 + SkPathWriter wrapper(*result);
1.313 + bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
1.314 + { // if some edges could not be resolved, assemble remaining fragments
1.315 + SkPath temp;
1.316 + temp.setFillType(fillType);
1.317 + SkPathWriter assembled(temp);
1.318 + Assemble(wrapper, &assembled);
1.319 + *result = *assembled.nativePath();
1.320 + result->setFillType(fillType);
1.321 + }
1.322 + return true;
1.323 +}
