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 SkPathFillType fillType = path->getFillType();
40 if (fillType == SkPathFillType::kInverseEvenOdd) {
41 fillType = SkPathFillType::kInverseWinding;
42 } else if (fillType == SkPathFillType::kEvenOdd) {
43 fillType = SkPathFillType::kWinding;
44 }
45 if (one_contour(*path)) {
46 SkPathFirstDirection dir = SkPathPriv::ComputeFirstDirection(*path);
47 if (dir != SkPathFirstDirection::kUnknown) {
48 if (dir == SkPathFirstDirection::kCW) {
49 ReversePath(path);
50 }
51 path->setFillType(fillType);
52 return true;
53 }
54 }
55 SkSTArenaAlloc<4096> allocator;
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
add(const SkPath & path,SkPathOp op)111 void 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
reset()120 void 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. */
resolve(SkPath * result)128 bool SkOpBuilder::resolve(SkPath* result) {
129 SkPath original = *result;
130 int count = fOps.count();
131 bool allUnion = true;
132 SkPathFirstDirection firstDir = SkPathFirstDirection::kUnknown;
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 SkPathFirstDirection dir = SkPathPriv::ComputeFirstDirection(*test);
142 if (dir == SkPathFirstDirection::kUnknown) {
143 allUnion = false;
144 break;
145 }
146 if (firstDir == SkPathFirstDirection::kUnknown) {
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