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: static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, 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 topDone;
michael@0:         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
michael@0:                 &index, &endIndex, &topLeft, &topUnsortable, &topDone);
michael@0:         if (!current) {
michael@0:             if (topUnsortable || !topDone) {
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->activeWinding(index, endIndex)) {
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:                             break;
michael@0:                         }
michael@0:                     }
michael@0:                     SkASSERT(unsortable || !current->done());
michael@0:                     int nextStart = index;
michael@0:                     int nextEnd = endIndex;
michael@0:                     SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
michael@0:                             &unsortable);
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:                     SkASSERT(unsortable || simple->isEmpty());
michael@0:                     int min = SkMin32(index, endIndex);
michael@0:                     if (!current->done(min)) {
michael@0:                         current->addCurveTo(index, endIndex, simple, true);
michael@0:                         current->markDoneUnary(min);
michael@0:                     }
michael@0:                 }
michael@0:                 simple->close();
michael@0:             } else {
michael@0:                 SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
michael@0:                 if (last && !last->fLoop) {
michael@0:                     *chaseArray.append() = last;
michael@0:                 }
michael@0:             }
michael@0:             current = FindChase(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: // returns true if all edges were processed
michael@0: static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
michael@0:     SkOpSegment* current;
michael@0:     int start, end;
michael@0:     bool unsortable = false;
michael@0:     bool closable = true;
michael@0:     while ((current = FindUndone(contourList, &start, &end))) {
michael@0:         do {
michael@0:     #if DEBUG_ACTIVE_SPANS
michael@0:             if (!unsortable && current->done()) {
michael@0:                 DebugShowActiveSpans(contourList);
michael@0:             }
michael@0:     #endif
michael@0:             SkASSERT(unsortable || !current->done());
michael@0:             int nextStart = start;
michael@0:             int nextEnd = end;
michael@0:             SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
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(start, end, 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(start).fX, current->xyAtT(start).fY,
michael@0:                     current->xyAtT(end).fX, current->xyAtT(end).fY);
michael@0:         #endif
michael@0:             current->addCurveTo(start, end, simple, true);
michael@0:             current = next;
michael@0:             start = nextStart;
michael@0:             end = nextEnd;
michael@0:         } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
michael@0:         if (!simple->isClosed()) {
michael@0:             SkASSERT(unsortable);
michael@0:             int min = SkMin32(start, end);
michael@0:             if (!current->done(min)) {
michael@0:                 current->addCurveTo(start, end, simple, true);
michael@0:                 current->markDone(min, 1);
michael@0:             }
michael@0:             closable = false;
michael@0:         }
michael@0:         simple->close();
michael@0:     #if DEBUG_ACTIVE_SPANS
michael@0:         DebugShowActiveSpans(contourList);
michael@0:     #endif
michael@0:     }
michael@0:     return closable;
michael@0: }
michael@0: 
michael@0: // FIXME : add this as a member of SkPath
michael@0: bool Simplify(const SkPath& path, SkPath* result) {
michael@0: #if DEBUG_SORT || DEBUG_SWAP_TOP
michael@0:     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
michael@0: #endif
michael@0:     // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
michael@0:     SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
michael@0:             : SkPath::kEvenOdd_FillType;
michael@0: 
michael@0:     // turn path into list of segments
michael@0:     SkTArray<SkOpContour> contours;
michael@0:     SkOpEdgeBuilder builder(path, contours);
michael@0:     if (!builder.finish()) {
michael@0:         return false;
michael@0:     }
michael@0:     SkTArray<SkOpContour*, true> contourList;
michael@0:     MakeContourList(contours, contourList, false, false);
michael@0:     SkOpContour** currentPtr = contourList.begin();
michael@0:     result->reset();
michael@0:     result->setFillType(fillType);
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:     HandleCoincidence(&contourList, 0);
michael@0:     // construct closed contours
michael@0:     SkPathWriter simple(*result);
michael@0:     if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
michael@0:                 : !bridgeXor(contourList, &simple))
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(simple, &assembled);
michael@0:         *result = *assembled.nativePath();
michael@0:         result->setFillType(fillType);
michael@0:     }
michael@0:     return true;
michael@0: }