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
15static 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
28void 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
38bool 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 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
109void 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
118void 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. */
126bool 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