Home | History | Annotate | Download | only in pathops 
      1 /*
      2  * Copyright 2014 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 
      8 #include "SkArenaAlloc.h"
      9 #include "SkMatrix.h"
     10 #include "SkOpEdgeBuilder.h"
     11 #include "SkPathPriv.h"
     12 #include "SkPathOps.h"
     13 #include "SkPathOpsCommon.h"
     14 
     15 static bool one_contour(const SkPath& path) {
     16     char storage[256];
     17     SkArenaAlloc allocator(storage);
     18     int verbCount = path.countVerbs();
     19     uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
     20     (void) path.getVerbs(verbs, verbCount);
     21     for (int index = 1; index < verbCount; ++index) {
     22         if (verbs[index] == SkPath::kMove_Verb) {
     23             return false;
     24         }
     25     }
     26     return true;
     27 }
     28 
     29 void SkOpBuilder::ReversePath(SkPath* path) {
     30     SkPath temp;
     31     SkPoint lastPt;
     32     SkAssertResult(path->getLastPt(&lastPt));
     33     temp.moveTo(lastPt);
     34     temp.reversePathTo(*path);
     35     temp.close();
     36     *path = temp;
     37 }
     38 
     39 bool SkOpBuilder::FixWinding(SkPath* path) {
     40     SkPath::FillType fillType = path->getFillType();
     41     if (fillType == SkPath::kInverseEvenOdd_FillType) {
     42         fillType = SkPath::kInverseWinding_FillType;
     43     } else if (fillType == SkPath::kEvenOdd_FillType) {
     44         fillType = SkPath::kWinding_FillType;
     45     }
     46     SkPathPriv::FirstDirection dir;
     47     if (one_contour(*path) && SkPathPriv::CheapComputeFirstDirection(*path, &dir)) {
     48         if (dir != SkPathPriv::kCCW_FirstDirection) {
     49             ReversePath(path);
     50         }
     51         path->setFillType(fillType);
     52         return true;
     53     }
     54     char storage[4096];
     55     SkArenaAlloc allocator(storage);
     56     SkOpContourHead contourHead;
     57     SkOpGlobalState globalState(&contourHead, &allocator  SkDEBUGPARAMS(false)
     58             SkDEBUGPARAMS(nullptr));
     59     SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
     60     if (builder.unparseable() || !builder.finish()) {
     61         return false;
     62     }
     63     if (!contourHead.count()) {
     64         return true;
     65     }
     66     if (!contourHead.next()) {
     67         return false;
     68     }
     69     contourHead.joinAllSegments();
     70     contourHead.resetReverse();
     71     bool writePath = false;
     72     SkOpSpan* topSpan;
     73     globalState.setPhase(SkOpPhase::kFixWinding);
     74     while ((topSpan = FindSortableTop(&contourHead))) {
     75         SkOpSegment* topSegment = topSpan->segment();
     76         SkOpContour* topContour = topSegment->contour();
     77         SkASSERT(topContour->isCcw() >= 0);
     78 #if DEBUG_WINDING
     79         SkDebugf("%s id=%d nested=%d ccw=%d\n",  __FUNCTION__,
     80                 topSegment->debugID(), globalState.nested(), topContour->isCcw());
     81 #endif
     82         if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
     83             topContour->setReverse();
     84             writePath = true;
     85         }
     86         topContour->markAllDone();
     87         globalState.clearNested();
     88     }
     89     if (!writePath) {
     90         path->setFillType(fillType);
     91         return true;
     92     }
     93     SkPath empty;
     94     SkPathWriter woundPath(empty);
     95     SkOpContour* test = &contourHead;
     96     do {
     97         if (!test->count()) {
     98             continue;
     99         }
    100         if (test->reversed()) {
    101             test->toReversePath(&woundPath);
    102         } else {
    103             test->toPath(&woundPath);
    104         }
    105     } while ((test = test->next()));
    106     *path = *woundPath.nativePath();
    107     path->setFillType(fillType);
    108     return true;
    109 }
    110 
    111 void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
    112     if (0 == fOps.count() && op != kUnion_SkPathOp) {
    113         fPathRefs.push_back() = SkPath();
    114         *fOps.append() = kUnion_SkPathOp;
    115     }
    116     fPathRefs.push_back() = path;
    117     *fOps.append() = op;
    118 }
    119 
    120 void SkOpBuilder::reset() {
    121     fPathRefs.reset();
    122     fOps.reset();
    123 }
    124 
    125 /* OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
    126    paths with union ops could be locally resolved and still improve over doing the
    127    ops one at a time. */
    128 bool SkOpBuilder::resolve(SkPath* result) {
    129     SkPath original = *result;
    130     int count = fOps.count();
    131     bool allUnion = true;
    132     SkPathPriv::FirstDirection firstDir = SkPathPriv::kUnknown_FirstDirection;
    133     for (int index = 0; index < count; ++index) {
    134         SkPath* test = &fPathRefs[index];
    135         if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
    136             allUnion = false;
    137             break;
    138         }
    139         // If all paths are convex, track direction, reversing as needed.
    140         if (test->isConvex()) {
    141             SkPathPriv::FirstDirection dir;
    142             if (!SkPathPriv::CheapComputeFirstDirection(*test, &dir)) {
    143                 allUnion = false;
    144                 break;
    145             }
    146             if (firstDir == SkPathPriv::kUnknown_FirstDirection) {
    147                 firstDir = dir;
    148             } else if (firstDir != dir) {
    149                 ReversePath(test);
    150             }
    151             continue;
    152         }
    153         // If the path is not convex but its bounds do not intersect the others, simplify is enough.
    154         const SkRect& testBounds = test->getBounds();
    155         for (int inner = 0; inner < index; ++inner) {
    156             // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
    157             if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
    158                 allUnion = false;
    159                 break;
    160             }
    161         }
    162     }
    163     if (!allUnion) {
    164         *result = fPathRefs[0];
    165         for (int index = 1; index < count; ++index) {
    166             if (!Op(*result, fPathRefs[index], fOps[index], result)) {
    167                 reset();
    168                 *result = original;
    169                 return false;
    170             }
    171         }
    172         reset();
    173         return true;
    174     }
    175     SkPath sum;
    176     for (int index = 0; index < count; ++index) {
    177         if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
    178             reset();
    179             *result = original;
    180             return false;
    181         }
    182         if (!fPathRefs[index].isEmpty()) {
    183             // convert the even odd result back to winding form before accumulating it
    184             if (!FixWinding(&fPathRefs[index])) {
    185                 *result = original;
    186                 return false;
    187             }
    188             sum.addPath(fPathRefs[index]);
    189         }
    190     }
    191     reset();
    192     bool success = Simplify(sum, result);
    193     if (!success) {
    194         *result = original;
    195     }
    196     return success;
    197 }
    198