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         bool onlyVertical = false;
  23         lastTopLeft = topLeft;
  24         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
  25                 &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
  26         if (!current) {
  27             if ((!topUnsortable || firstPass) && !topDone) {
  28                 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
  29                 topLeft.fX = topLeft.fY = SK_ScalarMin;
  30                 continue;
  31             }
  32             break;
  33         } else if (onlyVertical) {
  34             break;
  35         }
  36         firstPass = !topUnsortable || lastTopLeft != topLeft;
  37         SkTDArray<SkOpSpan*> chase;
  38         do {
  39             if (current->activeWinding(index, endIndex)) {
  40                 do {
  41                     if (!unsortable && current->done()) {
  42                           break;
  43                     }
  44                     SkASSERT(unsortable || !current->done());
  45                     int nextStart = index;
  46                     int nextEnd = endIndex;
  47                     SkOpSegment* next = current->findNextWinding(&chase, &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(chase, last));
  83                     // assert that last isn't already in array
  84                     *chase.append() = last;
  85 #if DEBUG_WINDING
  86                     SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
  87                             last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
  88                             last->fSmall);
  89 #endif
  90                 }
  91             }
  92             current = FindChase(&chase, &index, &endIndex);
  93         #if DEBUG_ACTIVE_SPANS
  94             DebugShowActiveSpans(contourList);
  95         #endif
  96             if (!current) {
  97                 break;
  98             }
  99         } while (true);
 100     } while (true);
 101     return simple->someAssemblyRequired();
 102 }
 103
 104 // returns true if all edges were processed
 105 static bool bridgeXor(SkTArray<SkOpContour*, true>& contourList, SkPathWriter* simple) {
 106     SkOpSegment* current;
 107     int start, end;
 108     bool unsortable = false;
 109     bool closable = true;
 110     while ((current = FindUndone(contourList, &start, &end))) {
 111         do {
 112     #if DEBUG_ACTIVE_SPANS
 113             if (!unsortable && current->done()) {
 114                 DebugShowActiveSpans(contourList);
 115             }
 116     #endif
 117             SkASSERT(unsortable || !current->done());
 118             int nextStart = start;
 119             int nextEnd = end;
 120             SkOpSegment* next = current->findNextXor(&nextStart, &nextEnd, &unsortable);
 121             if (!next) {
 122                 if (!unsortable && simple->hasMove()
 123                         && current->verb() != SkPath::kLine_Verb
 124                         && !simple->isClosed()) {
 125                     current->addCurveTo(start, end, simple, true);
 126                     SkASSERT(simple->isClosed());
 127                 }
 128                 break;
 129             }
 130         #if DEBUG_FLOW
 131             SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
 132                     current->debugID(), current->xyAtT(start).fX, current->xyAtT(start).fY,
 133                     current->xyAtT(end).fX, current->xyAtT(end).fY);
 134         #endif
 135             current->addCurveTo(start, end, simple, true);
 136             current = next;
 137             start = nextStart;
 138             end = nextEnd;
 139         } while (!simple->isClosed() && (!unsortable || !current->done(SkMin32(start, end))));
 140         if (!simple->isClosed()) {
 141             SkASSERT(unsortable);
 142             int min = SkMin32(start, end);
 143             if (!current->done(min)) {
 144                 current->addCurveTo(start, end, simple, true);
 145                 current->markDone(min, 1);
 146             }
 147             closable = false;
 148         }
 149         simple->close();
 150     #if DEBUG_ACTIVE_SPANS
 151         DebugShowActiveSpans(contourList);
 152     #endif
 153     }
 154     return closable;
 155 }
 156
 157 // FIXME : add this as a member of SkPath
 158 bool Simplify(const SkPath& path, SkPath* result) {
 159 #if DEBUG_SORT || DEBUG_SWAP_TOP
 160     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 161 #endif
 162     // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
 163     SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
 164             : SkPath::kEvenOdd_FillType;
 165
 166     // turn path into list of segments
 167     SkTArray<SkOpContour> contours;
 168     SkOpEdgeBuilder builder(path, contours);
 169     if (!builder.finish()) {
 170         return false;
 171     }
 172     SkTArray<SkOpContour*, true> contourList;
 173     MakeContourList(contours, contourList, false, false);
 174     SkOpContour** currentPtr = contourList.begin();
 175     result->reset();
 176     result->setFillType(fillType);
 177     if (!currentPtr) {
 178         return true;
 179     }
 180     SkOpContour** listEnd = contourList.end();
 181     // find all intersections between segments
 182     do {
 183         SkOpContour** nextPtr = currentPtr;
 184         SkOpContour* current = *currentPtr++;
 185         if (current->containsCubics()) {
 186             AddSelfIntersectTs(current);
 187         }
 188         SkOpContour* next;
 189         do {
 190             next = *nextPtr++;
 191         } while (AddIntersectTs(current, next) && nextPtr != listEnd);
 192     } while (currentPtr != listEnd);
 193     if (!HandleCoincidence(&contourList, 0)) {
 194         return false;
 195     }
 196     // construct closed contours
 197     SkPathWriter simple(*result);
 198     if (builder.xorMask() == kWinding_PathOpsMask ? bridgeWinding(contourList, &simple)
 199                 : !bridgeXor(contourList, &simple))
 200     {  // if some edges could not be resolved, assemble remaining fragments
 201         SkPath temp;
 202         temp.setFillType(fillType);
 203         SkPathWriter assembled(temp);
 204         Assemble(simple, &assembled);
 205         *result = *assembled.nativePath();
 206         result->setFillType(fillType);
 207     }
 208     return true;
 209 }