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 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 
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 
38 bool SkOpBuilder::FixWinding(SkPath* path) {
39     SkPath::FillType fillType = path->getFillType();
40     if (fillType == SkPath::kInverseEvenOdd_FillType) {
41         fillType = SkPath::kInverseWinding_FillType;
42     } else if (fillType == SkPath::kEvenOdd_FillType) {
43         fillType = SkPath::kWinding_FillType;
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 
109 void 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 
118 void 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. */
126 bool 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