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
one_contour(const SkPath & path)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
FixWinding(SkPath * path)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
add(const SkPath & path,SkPathOp op)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
reset()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. */
resolve(SkPath * result)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