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 15static 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 29void 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 39bool 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 111void 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 120void 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. */ 128bool 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