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 "include/core/SkMatrix.h" 9 #include "include/pathops/SkPathOps.h" 10 #include "src/core/SkArenaAlloc.h" 11 #include "src/core/SkPathPriv.h" 12 #include "src/pathops/SkOpEdgeBuilder.h" 13 #include "src/pathops/SkPathOpsCommon.h" 14 one_contour(const SkPath & path)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 ReversePath(SkPath * path)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 FixWinding(SkPath * path)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 add(const SkPath & path,SkPathOp op)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 reset()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. */ resolve(SkPath * result)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