src/third_party/skia/src/pathops/SkPathOpsOp.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 SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
  13     while (chase.count()) {
  14         SkOpSpan* span;
  15         chase.pop(&span);
  16         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
  17         SkOpSegment* segment = backPtr.fOther;
  18         *tIndex = backPtr.fOtherIndex;
  19         bool sortable = true;
  20         bool done = true;
  21         *endIndex = -1;
  22         if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
  23                 &sortable)) {
  24             if (last->unorderable()) {
  25                 continue;
  26             }
  27             *tIndex = last->start();
  28             *endIndex = last->end();
  29    #if TRY_ROTATE
  30             *chase.insert(0) = span;
  31    #else
  32             *chase.append() = span;
  33    #endif
  34             return last->segment();
  35         }
  36         if (done) {
  37             continue;
  38         }
  39         if (!sortable) {
  40             continue;
  41         }
  42         // find first angle, initialize winding to computed fWindSum
  43         const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
  44         if (!angle) {
  45             continue;
  46         }
  47         const SkOpAngle* firstAngle = angle;
  48         SkDEBUGCODE(bool loop = false);
  49         int winding;
  50         do {
  51             angle = angle->next();
  52             SkASSERT(angle != firstAngle || !loop);
  53             SkDEBUGCODE(loop |= angle == firstAngle);
  54             segment = angle->segment();
  55             winding = segment->windSum(angle);
  56         } while (winding == SK_MinS32);
  57         int sumMiWinding = segment->updateWindingReverse(angle);
  58         int sumSuWinding = segment->updateOppWindingReverse(angle);
  59         if (segment->operand()) {
  60             SkTSwap<int>(sumMiWinding, sumSuWinding);
  61         }
  62         SkOpSegment* first = NULL;
  63         while ((angle = angle->next()) != firstAngle) {
  64             segment = angle->segment();
  65             int start = angle->start();
  66             int end = angle->end();
  67             int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
  68             segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
  69                     &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
  70             if (!segment->done(angle)) {
  71                 if (!first) {
  72                     first = segment;
  73                     *tIndex = start;
  74                     *endIndex = end;
  75                 }
  76                 // OPTIMIZATION: should this also add to the chase?
  77                 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
  78                     oppSumWinding, angle);
  79             }
  80         }
  81         if (first) {
  82        #if TRY_ROTATE
  83             *chase.insert(0) = span;
  84        #else
  85             *chase.append() = span;
  86        #endif
  87             return first;
  88         }
  89     }
  90     return NULL;
  91 }
  92
  93 /*
  94 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
  95         bool windingIsOp, PathOp op) {
  96     bool active = windingIsActive(winding, spanWinding);
  97     if (!active) {
  98         return false;
  99     }
 100     if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
 101         switch (op) {
 102             case kIntersect_Op:
 103             case kUnion_Op:
 104                 return true;
 105             case kDifference_Op: {
 106                 int absSpan = abs(spanWinding);
 107                 int absOpp = abs(oppSpanWinding);
 108                 return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
 109             }
 110             case kXor_Op:
 111                 return spanWinding != oppSpanWinding;
 112             default:
 113                 SkASSERT(0);
 114         }
 115     }
 116     bool opActive = oppWinding != 0;
 117     return gOpLookup[op][opActive][windingIsOp];
 118 }
 119 */
 120
 121 static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
 122         const int xorMask, const int xorOpMask, SkPathWriter* simple) {
 123     bool firstContour = true;
 124     bool unsortable = false;
 125     bool topUnsortable = false;
 126     bool firstPass = true;
 127     SkPoint lastTopLeft;
 128     SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
 129     do {
 130         int index, endIndex;
 131         bool topDone;
 132         bool onlyVertical = false;
 133         lastTopLeft = topLeft;
 134         SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
 135                 &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
 136         if (!current) {
 137             if ((!topUnsortable || firstPass) && !topDone) {
 138                 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
 139                 if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
 140                     if (firstPass) {
 141                         firstPass = false;
 142                     } else {
 143                         break;
 144                     }
 145                 }
 146                 topLeft.fX = topLeft.fY = SK_ScalarMin;
 147                 continue;
 148             }
 149             break;
 150         } else if (onlyVertical) {
 151             break;
 152         }
 153         firstPass = !topUnsortable || lastTopLeft != topLeft;
 154         SkTDArray<SkOpSpan*> chase;
 155         do {
 156             if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
 157                 do {
 158                     if (!unsortable && current->done()) {
 159                         break;
 160                     }
 161                     SkASSERT(unsortable || !current->done());
 162                     int nextStart = index;
 163                     int nextEnd = endIndex;
 164                     SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
 165                             &unsortable, op, xorMask, xorOpMask);
 166                     if (!next) {
 167                         if (!unsortable && simple->hasMove()
 168                                 && current->verb() != SkPath::kLine_Verb
 169                                 && !simple->isClosed()) {
 170                             current->addCurveTo(index, endIndex, simple, true);
 171                     #if DEBUG_ACTIVE_SPANS
 172                             if (!simple->isClosed()) {
 173                                 DebugShowActiveSpans(contourList);
 174                             }
 175                     #endif
 176 //                            SkASSERT(simple->isClosed());
 177                         }
 178                         break;
 179                     }
 180         #if DEBUG_FLOW
 181             SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
 182                     current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
 183                     current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
 184         #endif
 185                     current->addCurveTo(index, endIndex, simple, true);
 186                     current = next;
 187                     index = nextStart;
 188                     endIndex = nextEnd;
 189                 } while (!simple->isClosed() && (!unsortable
 190                         || !current->done(SkMin32(index, endIndex))));
 191                 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
 192                     // FIXME : add to simplify, xor cpaths
 193                     int min = SkMin32(index, endIndex);
 194                     if (!unsortable && !simple->isEmpty()) {
 195                         unsortable = current->checkSmall(min);
 196                     }
 197                     if (!current->done(min)) {
 198                         current->addCurveTo(index, endIndex, simple, true);
 199                         current->markDoneBinary(min);
 200                     }
 201                 }
 202                 simple->close();
 203             } else {
 204                 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
 205                 if (last && !last->fChased && !last->fLoop) {
 206                     last->fChased = true;
 207                     SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
 208                     *chase.append() = last;
 209 #if DEBUG_WINDING
 210                     SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
 211                             last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
 212                             last->fSmall);
 213 #endif
 214                 }
 215             }
 216             current = findChaseOp(chase, &index, &endIndex);
 217         #if DEBUG_ACTIVE_SPANS
 218             DebugShowActiveSpans(contourList);
 219         #endif
 220             if (!current) {
 221                 break;
 222             }
 223         } while (true);
 224     } while (true);
 225     return simple->someAssemblyRequired();
 226 }
 227
 228 // pretty picture:
 229 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
 230 static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
 231 //                  inside minuend                               outside minuend
 232 //     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
 233     {{ kDifference_PathOp,    kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
 234     {{ kIntersect_PathOp,    kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
 235     {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp,    kIntersect_PathOp }},
 236     {{ kXOR_PathOp,                 kXOR_PathOp }, { kXOR_PathOp,                 kXOR_PathOp }},
 237     {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp,    kDifference_PathOp }},
 238 };
 239
 240 static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
 241     {{ false, false }, { true, false }},  // diff
 242     {{ false, false }, { false, true }},  // sect
 243     {{ false, true }, { true, true }},    // union
 244     {{ false, true }, { true, false }},   // xor
 245     {{ false, true }, { false, false }},  // rev diff
 246 };
 247
 248 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
 249 #if DEBUG_SHOW_TEST_NAME
 250     char* debugName = DEBUG_FILENAME_STRING;
 251     if (debugName && debugName[0]) {
 252         SkPathOpsDebug::BumpTestName(debugName);
 253         SkPathOpsDebug::ShowPath(one, two, op, debugName);
 254     }
 255 #endif
 256     op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
 257     SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
 258             ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
 259     const SkPath* minuend = &one;
 260     const SkPath* subtrahend = &two;
 261     if (op == kReverseDifference_PathOp) {
 262         minuend = &two;
 263         subtrahend = &one;
 264         op = kDifference_PathOp;
 265     }
 266 #if DEBUG_SORT || DEBUG_SWAP_TOP
 267     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 268 #endif
 269     // turn path into list of segments
 270     SkTArray<SkOpContour> contours;
 271     // FIXME: add self-intersecting cubics' T values to segment
 272     SkOpEdgeBuilder builder(*minuend, contours);
 273     const int xorMask = builder.xorMask();
 274     builder.addOperand(*subtrahend);
 275     if (!builder.finish()) {
 276         return false;
 277     }
 278     result->reset();
 279     result->setFillType(fillType);
 280     const int xorOpMask = builder.xorMask();
 281     SkTArray<SkOpContour*, true> contourList;
 282     MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
 283             xorOpMask == kEvenOdd_PathOpsMask);
 284     SkOpContour** currentPtr = contourList.begin();
 285     if (!currentPtr) {
 286         return true;
 287     }
 288     SkOpContour** listEnd = contourList.end();
 289     // find all intersections between segments
 290     do {
 291         SkOpContour** nextPtr = currentPtr;
 292         SkOpContour* current = *currentPtr++;
 293         if (current->containsCubics()) {
 294             AddSelfIntersectTs(current);
 295         }
 296         SkOpContour* next;
 297         do {
 298             next = *nextPtr++;
 299         } while (AddIntersectTs(current, next) && nextPtr != listEnd);
 300     } while (currentPtr != listEnd);
 301     // eat through coincident edges
 302
 303     int total = 0;
 304     int index;
 305     for (index = 0; index < contourList.count(); ++index) {
 306         total += contourList[index]->segments().count();
 307     }
 308     if (!HandleCoincidence(&contourList, total)) {
 309         return false;
 310     }
 311     // construct closed contours
 312     SkPathWriter wrapper(*result);
 313     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
 314     {  // if some edges could not be resolved, assemble remaining fragments
 315         SkPath temp;
 316         temp.setFillType(fillType);
 317         SkPathWriter assembled(temp);
 318         Assemble(wrapper, &assembled);
 319         *result = *assembled.nativePath();
 320         result->setFillType(fillType);
 321     }
 322     return true;
 323 }