Line data Source code
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 :
15 0 : static bool one_contour(const SkPath& path) {
16 : char storage[256];
17 0 : SkArenaAlloc allocator(storage);
18 0 : int verbCount = path.countVerbs();
19 0 : uint8_t* verbs = (uint8_t*) allocator.makeArrayDefault<uint8_t>(verbCount);
20 0 : (void) path.getVerbs(verbs, verbCount);
21 0 : for (int index = 1; index < verbCount; ++index) {
22 0 : if (verbs[index] == SkPath::kMove_Verb) {
23 0 : return false;
24 : }
25 : }
26 0 : return true;
27 : }
28 :
29 0 : void SkOpBuilder::ReversePath(SkPath* path) {
30 0 : SkPath temp;
31 : SkPoint lastPt;
32 0 : SkAssertResult(path->getLastPt(&lastPt));
33 0 : temp.moveTo(lastPt);
34 0 : temp.reversePathTo(*path);
35 0 : temp.close();
36 0 : *path = temp;
37 0 : }
38 :
39 0 : bool SkOpBuilder::FixWinding(SkPath* path) {
40 0 : SkPath::FillType fillType = path->getFillType();
41 0 : if (fillType == SkPath::kInverseEvenOdd_FillType) {
42 0 : fillType = SkPath::kInverseWinding_FillType;
43 0 : } else if (fillType == SkPath::kEvenOdd_FillType) {
44 0 : fillType = SkPath::kWinding_FillType;
45 : }
46 : SkPathPriv::FirstDirection dir;
47 0 : if (one_contour(*path) && SkPathPriv::CheapComputeFirstDirection(*path, &dir)) {
48 0 : if (dir != SkPathPriv::kCCW_FirstDirection) {
49 0 : ReversePath(path);
50 : }
51 0 : path->setFillType(fillType);
52 0 : return true;
53 : }
54 : char storage[4096];
55 0 : SkArenaAlloc allocator(storage);
56 0 : SkOpContourHead contourHead;
57 : SkOpGlobalState globalState(&contourHead, &allocator SkDEBUGPARAMS(false)
58 0 : SkDEBUGPARAMS(nullptr));
59 0 : SkOpEdgeBuilder builder(*path, &contourHead, &globalState);
60 0 : if (builder.unparseable() || !builder.finish()) {
61 0 : return false;
62 : }
63 0 : if (!contourHead.count()) {
64 0 : return true;
65 : }
66 0 : if (!contourHead.next()) {
67 0 : return false;
68 : }
69 0 : contourHead.joinAllSegments();
70 0 : contourHead.resetReverse();
71 0 : bool writePath = false;
72 : SkOpSpan* topSpan;
73 0 : globalState.setPhase(SkOpPhase::kFixWinding);
74 0 : while ((topSpan = FindSortableTop(&contourHead))) {
75 0 : SkOpSegment* topSegment = topSpan->segment();
76 0 : SkOpContour* topContour = topSegment->contour();
77 0 : 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 0 : if ((globalState.nested() & 1) != SkToBool(topContour->isCcw())) {
83 0 : topContour->setReverse();
84 0 : writePath = true;
85 : }
86 0 : topContour->markAllDone();
87 0 : globalState.clearNested();
88 : }
89 0 : if (!writePath) {
90 0 : path->setFillType(fillType);
91 0 : return true;
92 : }
93 0 : SkPath empty;
94 0 : SkPathWriter woundPath(empty);
95 0 : SkOpContour* test = &contourHead;
96 0 : do {
97 0 : if (!test->count()) {
98 0 : continue;
99 : }
100 0 : if (test->reversed()) {
101 0 : test->toReversePath(&woundPath);
102 : } else {
103 0 : test->toPath(&woundPath);
104 : }
105 : } while ((test = test->next()));
106 0 : *path = *woundPath.nativePath();
107 0 : path->setFillType(fillType);
108 0 : return true;
109 : }
110 :
111 0 : void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
112 0 : if (0 == fOps.count() && op != kUnion_SkPathOp) {
113 0 : fPathRefs.push_back() = SkPath();
114 0 : *fOps.append() = kUnion_SkPathOp;
115 : }
116 0 : fPathRefs.push_back() = path;
117 0 : *fOps.append() = op;
118 0 : }
119 :
120 0 : void SkOpBuilder::reset() {
121 0 : fPathRefs.reset();
122 0 : fOps.reset();
123 0 : }
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. */
128 0 : bool SkOpBuilder::resolve(SkPath* result) {
129 0 : SkPath original = *result;
130 0 : int count = fOps.count();
131 0 : bool allUnion = true;
132 0 : SkPathPriv::FirstDirection firstDir = SkPathPriv::kUnknown_FirstDirection;
133 0 : for (int index = 0; index < count; ++index) {
134 0 : SkPath* test = &fPathRefs[index];
135 0 : if (kUnion_SkPathOp != fOps[index] || test->isInverseFillType()) {
136 0 : allUnion = false;
137 0 : break;
138 : }
139 : // If all paths are convex, track direction, reversing as needed.
140 0 : if (test->isConvex()) {
141 : SkPathPriv::FirstDirection dir;
142 0 : if (!SkPathPriv::CheapComputeFirstDirection(*test, &dir)) {
143 0 : allUnion = false;
144 0 : break;
145 : }
146 0 : if (firstDir == SkPathPriv::kUnknown_FirstDirection) {
147 0 : firstDir = dir;
148 0 : } else if (firstDir != dir) {
149 0 : ReversePath(test);
150 : }
151 0 : continue;
152 : }
153 : // If the path is not convex but its bounds do not intersect the others, simplify is enough.
154 0 : const SkRect& testBounds = test->getBounds();
155 0 : for (int inner = 0; inner < index; ++inner) {
156 : // OPTIMIZE: check to see if the contour bounds do not intersect other contour bounds?
157 0 : if (SkRect::Intersects(fPathRefs[inner].getBounds(), testBounds)) {
158 0 : allUnion = false;
159 0 : break;
160 : }
161 : }
162 : }
163 0 : if (!allUnion) {
164 0 : *result = fPathRefs[0];
165 0 : for (int index = 1; index < count; ++index) {
166 0 : if (!Op(*result, fPathRefs[index], fOps[index], result)) {
167 0 : reset();
168 0 : *result = original;
169 0 : return false;
170 : }
171 : }
172 0 : reset();
173 0 : return true;
174 : }
175 0 : SkPath sum;
176 0 : for (int index = 0; index < count; ++index) {
177 0 : if (!Simplify(fPathRefs[index], &fPathRefs[index])) {
178 0 : reset();
179 0 : *result = original;
180 0 : return false;
181 : }
182 0 : if (!fPathRefs[index].isEmpty()) {
183 : // convert the even odd result back to winding form before accumulating it
184 0 : if (!FixWinding(&fPathRefs[index])) {
185 0 : *result = original;
186 0 : return false;
187 : }
188 0 : sum.addPath(fPathRefs[index]);
189 : }
190 : }
191 0 : reset();
192 0 : bool success = Simplify(sum, result);
193 0 : if (!success) {
194 0 : *result = original;
195 : }
196 0 : return success;
197 : }
|
