michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkAddIntersections.h"
michael@0: #include "SkOpEdgeBuilder.h"
michael@0: #include "SkPathOpsCommon.h"
michael@0: #include "SkPathWriter.h"
michael@0: 
michael@0: // FIXME: this and find chase should be merge together, along with
michael@0: // other code that walks winding in angles
michael@0: // OPTIMIZATION: Probably, the walked winding should be rolled into the angle structure
michael@0: // so it isn't duplicated by walkers like this one
michael@0: static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int& nextEnd) {
michael@0:     while (chase.count()) {
michael@0:         SkOpSpan* span;
michael@0:         chase.pop(&span);
michael@0:         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
michael@0:         SkOpSegment* segment = backPtr.fOther;
michael@0:         nextStart = backPtr.fOtherIndex;
michael@0:         SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:         int done = 0;
michael@0:         if (segment->activeAngle(nextStart, &done, &angles)) {
michael@0:             SkOpAngle* last = angles.end() - 1;
michael@0:             nextStart = last->start();
michael@0:             nextEnd = last->end();
michael@0:    #if TRY_ROTATE
michael@0:             *chase.insert(0) = span;
michael@0:    #else
michael@0:             *chase.append() = span;
michael@0:    #endif
michael@0:             return last->segment();
michael@0:         }
michael@0:         if (done == angles.count()) {
michael@0:             continue;
michael@0:         }
michael@0:         SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:         bool sortable = SkOpSegment::SortAngles(angles, &sorted,
michael@0:                 SkOpSegment::kMayBeUnordered_SortAngleKind);
michael@0:         int angleCount = sorted.count();
michael@0: #if DEBUG_SORT
michael@0:         sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, sortable);
michael@0: #endif
michael@0:         if (!sortable) {
michael@0:             continue;
michael@0:         }
michael@0:         // find first angle, initialize winding to computed fWindSum
michael@0:         int firstIndex = -1;
michael@0:         const SkOpAngle* angle;
michael@0:         bool foundAngle = true;
michael@0:         do {
michael@0:             ++firstIndex;
michael@0:             if (firstIndex >= angleCount) {
michael@0:                 foundAngle = false;
michael@0:                 break;
michael@0:             }
michael@0:             angle = sorted[firstIndex];
michael@0:             segment = angle->segment();
michael@0:         } while (segment->windSum(angle) == SK_MinS32);
michael@0:         if (!foundAngle) {
michael@0:             continue;
michael@0:         }
michael@0:     #if DEBUG_SORT
michael@0:         segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
michael@0:     #endif
michael@0:         int sumMiWinding = segment->updateWindingReverse(angle);
michael@0:         int sumSuWinding = segment->updateOppWindingReverse(angle);
michael@0:         if (segment->operand()) {
michael@0:             SkTSwap<int>(sumMiWinding, sumSuWinding);
michael@0:         }
michael@0:         int nextIndex = firstIndex + 1;
michael@0:         int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
michael@0:         SkOpSegment* first = NULL;
michael@0:         do {
michael@0:             SkASSERT(nextIndex != firstIndex);
michael@0:             if (nextIndex == angleCount) {
michael@0:                 nextIndex = 0;
michael@0:             }
michael@0:             angle = sorted[nextIndex];
michael@0:             segment = angle->segment();
michael@0:             int start = angle->start();
michael@0:             int end = angle->end();
michael@0:             int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
michael@0:             segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
michael@0:                     &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
michael@0:             if (!segment->done(angle)) {
michael@0:                 if (!first) {
michael@0:                     first = segment;
michael@0:                     nextStart = start;
michael@0:                     nextEnd = end;
michael@0:                 }
michael@0:                 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
michael@0:                     oppSumWinding, angle);
michael@0:             }
michael@0:         } while (++nextIndex != lastIndex);
michael@0:         if (first) {
michael@0:        #if TRY_ROTATE
michael@0:             *chase.insert(0) = span;
michael@0:        #else
michael@0:             *chase.append() = span;
michael@0:        #endif
michael@0:             return first;
michael@0:         }
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: /*
michael@0: static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
michael@0:         bool windingIsOp, PathOp op) {
michael@0:     bool active = windingIsActive(winding, spanWinding);
michael@0:     if (!active) {
michael@0:         return false;
michael@0:     }
michael@0:     if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
michael@0:         switch (op) {
michael@0:             case kIntersect_Op:
michael@0:             case kUnion_Op:
michael@0:                 return true;
michael@0:             case kDifference_Op: {
michael@0:                 int absSpan = abs(spanWinding);
michael@0:                 int absOpp = abs(oppSpanWinding);
michael@0:                 return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
michael@0:             }
michael@0:             case kXor_Op:
michael@0:                 return spanWinding != oppSpanWinding;
michael@0:             default:
michael@0:                 SkASSERT(0);
michael@0:         }
michael@0:     }
michael@0:     bool opActive = oppWinding != 0;
michael@0:     return gOpLookup[op][opActive][windingIsOp];
michael@0: }
michael@0: */
michael@0: 
michael@0: static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
michael@0:         const int xorMask, const int xorOpMask, SkPathWriter* simple) {
michael@0:     bool firstContour = true;
michael@0:     bool unsortable = false;
michael@0:     bool topUnsortable = false;
michael@0:     SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
michael@0:     do {
michael@0:         int index, endIndex;
michael@0:         bool done;
michael@0:         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
michael@0:                 &index, &endIndex, &topLeft, &topUnsortable, &done);
michael@0:         if (!current) {
michael@0:             if (topUnsortable || !done) {
michael@0:                 topUnsortable = false;
michael@0:                 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
michael@0:                 topLeft.fX = topLeft.fY = SK_ScalarMin;
michael@0:                 continue;
michael@0:             }
michael@0:             break;
michael@0:         }
michael@0:         SkTDArray<SkOpSpan*> chaseArray;
michael@0:         do {
michael@0:             if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
michael@0:                 do {
michael@0:                     if (!unsortable && current->done()) {
michael@0:             #if DEBUG_ACTIVE_SPANS
michael@0:                         DebugShowActiveSpans(contourList);
michael@0:             #endif
michael@0:                         if (simple->isEmpty()) {
michael@0:                             simple->init();
michael@0:                         }
michael@0:                         break;
michael@0:                     }
michael@0:                     SkASSERT(unsortable || !current->done());
michael@0:                     int nextStart = index;
michael@0:                     int nextEnd = endIndex;
michael@0:                     SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd,
michael@0:                             &unsortable, op, xorMask, xorOpMask);
michael@0:                     if (!next) {
michael@0:                         if (!unsortable && simple->hasMove()
michael@0:                                 && current->verb() != SkPath::kLine_Verb
michael@0:                                 && !simple->isClosed()) {
michael@0:                             current->addCurveTo(index, endIndex, simple, true);
michael@0:                             SkASSERT(simple->isClosed());
michael@0:                         }
michael@0:                         break;
michael@0:                     }
michael@0:         #if DEBUG_FLOW
michael@0:             SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
michael@0:                     current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
michael@0:                     current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
michael@0:         #endif
michael@0:                     current->addCurveTo(index, endIndex, simple, true);
michael@0:                     current = next;
michael@0:                     index = nextStart;
michael@0:                     endIndex = nextEnd;
michael@0:                 } while (!simple->isClosed() && (!unsortable
michael@0:                         || !current->done(SkMin32(index, endIndex))));
michael@0:                 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
michael@0:                     // FIXME : add to simplify, xor cpaths
michael@0:                     int min = SkMin32(index, endIndex);
michael@0:                     if (!unsortable && !simple->isEmpty()) {
michael@0:                         unsortable = current->checkSmall(min);
michael@0:                     }
michael@0:                     SkASSERT(unsortable || simple->isEmpty());
michael@0:                     if (!current->done(min)) {
michael@0:                         current->addCurveTo(index, endIndex, simple, true);
michael@0:                         current->markDoneBinary(min);
michael@0:                     }
michael@0:                 }
michael@0:                 simple->close();
michael@0:             } else {
michael@0:                 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
michael@0:                 if (last && !last->fLoop) {
michael@0:                     *chaseArray.append() = last;
michael@0:                 }
michael@0:             }
michael@0:             current = findChaseOp(chaseArray, index, endIndex);
michael@0:         #if DEBUG_ACTIVE_SPANS
michael@0:             DebugShowActiveSpans(contourList);
michael@0:         #endif
michael@0:             if (!current) {
michael@0:                 break;
michael@0:             }
michael@0:         } while (true);
michael@0:     } while (true);
michael@0:     return simple->someAssemblyRequired();
michael@0: }
michael@0: 
michael@0: // pretty picture:
michael@0: // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
michael@0: static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
michael@0: //                  inside minuend                               outside minuend
michael@0: //     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
michael@0:     {{ kDifference_PathOp,    kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
michael@0:     {{ kIntersect_PathOp,    kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
michael@0:     {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp,    kIntersect_PathOp }},
michael@0:     {{ kXOR_PathOp,                 kXOR_PathOp }, { kXOR_PathOp,                 kXOR_PathOp }},
michael@0:     {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp,    kDifference_PathOp }},
michael@0: };
michael@0: 
michael@0: static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
michael@0:     {{ false, false }, { true, false }},  // diff
michael@0:     {{ false, false }, { false, true }},  // sect
michael@0:     {{ false, true }, { true, true }},    // union
michael@0:     {{ false, true }, { true, false }},   // xor
michael@0:     {{ false, true }, { false, false }},  // rev diff
michael@0: };
michael@0: 
michael@0: bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
michael@0: #if DEBUG_SHOW_TEST_NAME
michael@0:     char* debugName = DEBUG_FILENAME_STRING;
michael@0:     if (debugName && debugName[0]) {
michael@0:         SkPathOpsDebug::BumpTestName(debugName);
michael@0:         SkPathOpsDebug::ShowPath(one, two, op, debugName);
michael@0:     }
michael@0: #endif
michael@0:     op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
michael@0:     SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
michael@0:             ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
michael@0:     const SkPath* minuend = &one;
michael@0:     const SkPath* subtrahend = &two;
michael@0:     if (op == kReverseDifference_PathOp) {
michael@0:         minuend = &two;
michael@0:         subtrahend = &one;
michael@0:         op = kDifference_PathOp;
michael@0:     }
michael@0: #if DEBUG_SORT || DEBUG_SWAP_TOP
michael@0:     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
michael@0: #endif
michael@0:     // turn path into list of segments
michael@0:     SkTArray<SkOpContour> contours;
michael@0:     // FIXME: add self-intersecting cubics' T values to segment
michael@0:     SkOpEdgeBuilder builder(*minuend, contours);
michael@0:     const int xorMask = builder.xorMask();
michael@0:     builder.addOperand(*subtrahend);
michael@0:     if (!builder.finish()) {
michael@0:         return false;
michael@0:     }
michael@0:     result->reset();
michael@0:     result->setFillType(fillType);
michael@0:     const int xorOpMask = builder.xorMask();
michael@0:     SkTArray<SkOpContour*, true> contourList;
michael@0:     MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
michael@0:             xorOpMask == kEvenOdd_PathOpsMask);
michael@0:     SkOpContour** currentPtr = contourList.begin();
michael@0:     if (!currentPtr) {
michael@0:         return true;
michael@0:     }
michael@0:     SkOpContour** listEnd = contourList.end();
michael@0:     // find all intersections between segments
michael@0:     do {
michael@0:         SkOpContour** nextPtr = currentPtr;
michael@0:         SkOpContour* current = *currentPtr++;
michael@0:         if (current->containsCubics()) {
michael@0:             AddSelfIntersectTs(current);
michael@0:         }
michael@0:         SkOpContour* next;
michael@0:         do {
michael@0:             next = *nextPtr++;
michael@0:         } while (AddIntersectTs(current, next) && nextPtr != listEnd);
michael@0:     } while (currentPtr != listEnd);
michael@0:     // eat through coincident edges
michael@0: 
michael@0:     int total = 0;
michael@0:     int index;
michael@0:     for (index = 0; index < contourList.count(); ++index) {
michael@0:         total += contourList[index]->segments().count();
michael@0:     }
michael@0:     HandleCoincidence(&contourList, total);
michael@0:     // construct closed contours
michael@0:     SkPathWriter wrapper(*result);
michael@0:     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
michael@0:     {  // if some edges could not be resolved, assemble remaining fragments
michael@0:         SkPath temp;
michael@0:         temp.setFillType(fillType);
michael@0:         SkPathWriter assembled(temp);
michael@0:         Assemble(wrapper, &assembled);
michael@0:         *result = *assembled.nativePath();
michael@0:         result->setFillType(fillType);
michael@0:     }
michael@0:     return true;
michael@0: }