src/third_party/skia/src/pathops/SkPathOpsSimplify.cpp

   1 /*
   2  * Copyright 2012 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7 #include "SkAddIntersections.h"
   8 #include "SkOpEdgeBuilder.h"
   9 #include "SkPathOpsCommon.h"
  10 #include "SkPathWriter.h"
  11
  12 static bool bridgeWinding(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
  13     bool firstContour = true;
  14     bool unsortable = false;
  15     bool topUnsortable = false;
  16     bool firstPass = true;
  17     SkPoint lastTopLeft;
  18     SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
  19     do {
  20         int index, endIndex;
  21         bool topDone;
  22         lastTopLeft = topLeft;
  23         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
  24                 &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
  25         if (!current) {
  26             if ((!topUnsortable || firstPass) && !topDone) {
  27                 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
  28                 topLeft.fX = topLeft.fY = SK_ScalarMin;
  29                 continue;
  30             }
  31             break;
  32         }
  33         firstPass = !topUnsortable || lastTopLeft != topLeft;
  34         SkTDArray<SkOpSpan*> chaseArray;
  35         do {
  36             if (current->activeWinding(index, endIndex)) {
  37                 do {
  38                     if (!unsortable && current->done()) {
  39                         if (simple->isEmpty()) {
  40                             simple->init();
  41                             break;
  42                         }
  43                     }
  44                     SkASSERT(unsortable || !current->done());
  45                     int nextStart = index;
  46                     int nextEnd = endIndex;
  47                     SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
  48                             &unsortable);
  49                     if (!next) {
  50                         if (!unsortable && simple->hasMove()
  51                                 && current->verb() != SkPath::kLine_Verb
  52                                 && !simple->isClosed()) {
  53                             current->addCurveTo(index, endIndex, simple, true);
  54                             SkASSERT(simple->isClosed());
  55                         }
  56                         break;
  57                     }
  58         #if DEBUG_FLOW
  59             SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
  60                     current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
  61                     current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
  62         #endif
  63                     current->addCurveTo(index, endIndex, simple, true);
  64                     current = next;
  65                     index = nextStart;
  66                     endIndex = nextEnd;
  67                 } while (!simple->isClosed() && (!unsortable
  68                         || !current->done(SkMin32(index, endIndex))));
  69                 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
  70                     SkASSERT(unsortable || simple->isEmpty());
  71                     int min = SkMin32(index, endIndex);
  72                     if (!current->done(min)) {
  73                         current->addCurveTo(index, endIndex, simple, true);
  74                         current->markDoneUnary(min);
  75                     }
  76                 }
  77                 simple->close();
  78             } else {
  79                 SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
  80                 if (last && !last->fChased && !last->fLoop) {
  81                     last->fChased = true;
  82                     SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last));
  83                     // assert that last isn't already in array
  84                     *chaseArray.append() = last;
  85                 }
  86             }
  87             SkTDArray<SkOpSpan *>* chaseArrayPtr = &chaseArray;
  88             current = FindChase(chaseArrayPtr, &index, &endIndex);
  89         #if DEBUG_ACTIVE_SPANS
  90             DebugShowActiveSpans(contourList);
  91         #endif
  92             if (!current) {
  93                 break;
  94             }
  95         } while (true);
  96     } while (true);
  97     return simple->someAssemblyRequired();
  98 }
  99
 100 // returns true if all edges were processed
 101 static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
 102     SkOpSegment* current;
 103     int start, end;
 104     bool unsortable = false;
 105     bool closable = true;
 106     while ((current = FindUndone(contourList, &start, &end))) {
 107         do {
 108     #if DEBUG_ACTIVE_SPANS
 109             if (!unsortable && current->done()) {
 110                 DebugShowActiveSpans(contourList);
 111             }
 112     #endif
 113             SkASSERT(unsortable || !current->done());
 114             int nextStart = start;
 115             int nextEnd = end;
 116             SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
 117             if (!next) {
 118                 if (!unsortable && simple->hasMove()
 119                         && current->verb() != SkPath::kLine_Verb
 120                         && !simple->isClosed()) {
 121                     current->addCurveTo(start, end, simple, true);
 122                     SkASSERT(simple->isClosed());
 123                 }
 124                 break;
 125             }
 126         #if DEBUG_FLOW
 127             SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
 128                     current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
 129                     current->xyAtT(end).fX, current->xyAtT(end).fY);
 130         #endif
 131             current->addCurveTo(start, end, simple, true);
 132             current = next;
 133             start = nextStart;
 134             end = nextEnd;
 135         } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
 136         if (!simple->isClosed()) {
 137             SkASSERT(unsortable);
 138             int min = SkMin32(start, end);
 139             if (!current->done(min)) {
 140                 current->addCurveTo(start, end, simple, true);
 141                 current->markDone(min, 1);
 142             }
 143             closable = false;
 144         }
 145         simple->close();
 146     #if DEBUG_ACTIVE_SPANS
 147         DebugShowActiveSpans(contourList);
 148     #endif
 149     }
 150     return closable;
 151 }
 152
 153 // FIXME : add this as a member of SkPath
 154 bool Simplify(const SkPath& path, SkPath* result) {
 155 #if DEBUG_SORT || DEBUG_SWAP_TOP
 156     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 157 #endif
 158     // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
 159     SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
 160             : SkPath::kEvenOdd_FillType;
 161
 162     // turn path into list of segments
 163     SkTArray<SkOpContour> contours;
 164     SkOpEdgeBuilder builder(path, contours);
 165     if (!builder.finish()) {
 166         return false;
 167     }
 168     SkTArray<SkOpContour*, true> contourList;
 169     MakeContourList(contours, contourList, false, false);
 170     SkOpContour** currentPtr = contourList.begin();
 171     result->reset();
 172     result->setFillType(fillType);
 173     if (!currentPtr) {
 174         return true;
 175     }
 176     SkOpContour** listEnd = contourList.end();
 177     // find all intersections between segments
 178     do {
 179         SkOpContour** nextPtr = currentPtr;
 180         SkOpContour* current = *currentPtr++;
 181         if (current->containsCubics()) {
 182             AddSelfIntersectTs(current);
 183         }
 184         SkOpContour* next;
 185         do {
 186             next = *nextPtr++;
 187         } while (AddIntersectTs(current, next) && nextPtr != listEnd);
 188     } while (currentPtr != listEnd);
 189     if (!HandleCoincidence(&contourList, 0)) {
 190         return false;
 191     }
 192     // construct closed contours
 193     SkPathWriter simple(*result);
 194     if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
 195                 : !bridgeXor(contourList, &simple))
 196     {  // if some edges could not be resolved, assemble remaining fragments
 197         SkPath temp;
 198         temp.setFillType(fillType);
 199         SkPathWriter assembled(temp);
 200         Assemble(simple, &assembled);
 201         *result = *assembled.nativePath();
 202         result->setFillType(fillType);
 203     }
 204     return true;
 205 }