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