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