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/SkPath.h"
9 #include "include/core/SkPathTypes.h"
10 #include "include/core/SkPoint.h"
11 #include "include/core/SkRect.h"
12 #include "include/core/SkTypes.h"
13 #include "include/pathops/SkPathOps.h"
14 #include "include/private/base/SkTArray.h"
15 #include "include/private/base/SkTDArray.h"
16 #include "include/private/base/SkTo.h"
17 #include "src/base/SkArenaAlloc.h"
18 #include "src/core/SkPathEnums.h"
19 #include "src/core/SkPathPriv.h"
20 #include "src/pathops/SkOpContour.h"
21 #include "src/pathops/SkOpEdgeBuilder.h"
22 #include "src/pathops/SkOpSegment.h"
23 #include "src/pathops/SkOpSpan.h"
24 #include "src/pathops/SkPathOpsCommon.h"
25 #include "src/pathops/SkPathOpsTypes.h"
26 #include "src/pathops/SkPathWriter.h"
27
28 #include <cstdint>
29
one_contour(const SkPath & path)30 static bool one_contour(const SkPath& path) {
31 SkSTArenaAlloc<256> allocator;
32 int verbCount = path.countVerbs();
33 uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
34 (void) path.getVerbs(verbs, verbCount);
35 for (int index = 1; index < verbCount; ++index) {
36 if (verbs[index] == SkPath::kMove_Verb) {
37 return false;
38 }
39 }
40 return true;
41 }
42
ReversePath(SkPath * path)43 void SkOpBuilder::ReversePath(SkPath* path) {
44 SkPath temp;
45 SkPoint lastPt;
46 SkAssertResult(path->getLastPt(&lastPt));
47 temp.moveTo(lastPt);
48 temp.reversePathTo(*path);
49 temp.close();
50 *path = temp;
51 }
52
FixWinding(SkPath * path)53 bool SkOpBuilder::FixWinding(SkPath* path) {
54 SkPathFillType fillType = path->getFillType();
55 if (fillType == SkPathFillType::kInverseEvenOdd) {
56 fillType = SkPathFillType::kInverseWinding;
57 } else if (fillType == SkPathFillType::kEvenOdd) {
58 fillType = SkPathFillType::kWinding;
59 }
60 if (one_contour(*path)) {
61 SkPathFirstDirection dir = SkPathPriv::ComputeFirstDirection(*path);
62 if (dir != SkPathFirstDirection::kUnknown) {
63 if (dir == SkPathFirstDirection::kCW) {
64 ReversePath(path);
65 }
66 path->setFillType(fillType);
67 return true;
68 }
69 }
70 SkSTArenaAlloc<4096> allocator;
71 SkOpContourHead contourHead;
72 SkOpGlobalState globalState(&contourHead, &allocator SkDEBUGPARAMS(false)
73 SkDEBUGPARAMS(nullptr));
74 SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
75 if (builder.unparseable() || !builder.finish()) {
76 return false;
77 }
78 if (!contourHead.count()) {
79 return true;
80 }
81 if (!contourHead.next()) {
82 return false;
83 }
84 contourHead.joinAllSegments();
85 contourHead.resetReverse();
86 bool writePath = false;
87 SkOpSpan* topSpan;
88 globalState.setPhase(SkOpPhase::kFixWinding);
89 while ((topSpan = FindSortableTop(&contourHead))) {
90 SkOpSegment* topSegment = topSpan->segment();
91 SkOpContour* topContour = topSegment->contour();
92 SkASSERT(topContour->isCcw() >= 0);
93 #if DEBUG_WINDING
94 SkDebugf("%s id=%d nested=%d ccw=%d\n", __FUNCTION__,
95 topSegment->debugID(), globalState.nested(), topContour->isCcw());
96 #endif
97 if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
98 topContour->setReverse();
99 writePath = true;
100 }
101 topContour->markAllDone();
102 globalState.clearNested();
103 }
104 if (!writePath) {
105 path->setFillType(fillType);
106 return true;
107 }
108 SkPath empty;
109 SkPathWriter woundPath(empty);
110 SkOpContour* test = &contourHead;
111 do {
112 if (!test->count()) {
113 continue;
114 }
115 if (test->reversed()) {
116 test->toReversePath(&woundPath);
117 } else {
118 test->toPath(&woundPath);
119 }
120 } while ((test = test->next()));
121 *path = *woundPath.nativePath();
122 path->setFillType(fillType);
123 return true;
124 }
125
add(const SkPath & path,SkPathOp op)126 void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
127 if (fOps.empty() && op != kUnion_SkPathOp) {
128 fPathRefs.push_back() = SkPath();
129 *fOps.append() = kUnion_SkPathOp;
130 }
131 fPathRefs.push_back() = path;
132 *fOps.append() = op;
133 }
134
reset()135 void SkOpBuilder::reset() {
136 fPathRefs.clear();
137 fOps.reset();
138 }
139
140 /* OPTIMIZATION: Union doesn't need to be all-or-nothing. A run of three or more convex
141 paths with union ops could be locally resolved and still improve over doing the
142 ops one at a time. */
resolve(SkPath * result)143 bool SkOpBuilder::resolve(SkPath* result) {
144 SkPath original = *result;
145 int count = fOps.size();
146 bool allUnion = true;
147 SkPathFirstDirection firstDir = SkPathFirstDirection::kUnknown;
148 for (int index = 0; index < count; ++index) {
149 SkPath* test = &fPathRefs[index];
150 if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
151 allUnion = false;
152 break;
153 }
154 // If all paths are convex, track direction, reversing as needed.
155 if (test->isConvex()) {
156 SkPathFirstDirection dir = SkPathPriv::ComputeFirstDirection(*test);
157 if (dir == SkPathFirstDirection::kUnknown) {
158 allUnion = false;
159 break;
160 }
161 if (firstDir == SkPathFirstDirection::kUnknown) {
162 firstDir = dir;
163 } else if (firstDir != dir) {
164 ReversePath(test);
165 }
166 continue;
167 }
168 // If the path is not convex but its bounds do not intersect the others, simplify is enough.
169 const SkRect& testBounds = test->getBounds();
170 for (int inner = 0; inner < index; ++inner) {
171 // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
172 if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
173 allUnion = false;
174 break;
175 }
176 }
177 }
178 if (!allUnion) {
179 *result = fPathRefs[0];
180 for (int index = 1; index < count; ++index) {
181 if (!Op(*result, fPathRefs[index], fOps[index], result)) {
182 reset();
183 *result = original;
184 return false;
185 }
186 }
187 reset();
188 return true;
189 }
190 SkPath sum;
191 for (int index = 0; index < count; ++index) {
192 if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
193 reset();
194 *result = original;
195 return false;
196 }
197 if (!fPathRefs[index].isEmpty()) {
198 // convert the even odd result back to winding form before accumulating it
199 if (!FixWinding(&fPathRefs[index])) {
200 *result = original;
201 return false;
202 }
203 sum.addPath(fPathRefs[index]);
204 }
205 }
206 reset();
207 bool success = Simplify(sum, result);
208 if (!success) {
209 *result = original;
210 }
211 return success;
212 }
213