1 /*
2 * Copyright 2018 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 #include "include/core/SkPath.h"
8 #include "include/core/SkPathBuilder.h"
9 #include "include/core/SkPathTypes.h"
10 #include "include/core/SkPoint.h"
11 #include "include/core/SkRect.h"
12 #include "include/core/SkScalar.h"
13 #include "include/core/SkTypes.h"
14 #include "include/pathops/SkPathOps.h"
15 #include "include/private/base/SkMacros.h"
16 #include "src/core/SkPathPriv.h"
17 #include "src/pathops/SkPathOpsConic.h"
18 #include "src/pathops/SkPathOpsCubic.h"
19 #include "src/pathops/SkPathOpsCurve.h"
20 #include "src/pathops/SkPathOpsPoint.h"
21 #include "src/pathops/SkPathOpsQuad.h"
22 #include "src/pathops/SkPathOpsTypes.h"
23
24 #include <algorithm>
25 #include <vector>
26
27 using std::vector;
28
29 struct Contour {
30 enum class Direction { // SkPathDirection doesn't have 'none' state
31 kCCW = -1,
32 kNone,
33 kCW,
34 };
35
ContourContour36 Contour(const SkRect& bounds, int lastStart, int verbStart)
37 : fBounds(bounds)
38 , fVerbStart(lastStart)
39 , fVerbEnd(verbStart) {
40 }
41
42 vector<Contour*> fChildren;
43 const SkRect fBounds;
44 SkPoint fMinXY{SK_ScalarMax, SK_ScalarMax};
45 const int fVerbStart;
46 const int fVerbEnd;
47 Direction fDirection{Direction::kNone};
48 bool fContained{false};
49 bool fReverse{false};
50 };
51
52 static const int kPtCount[] = { 1, 1, 2, 2, 3, 0 };
53 static const int kPtIndex[] = { 0, 1, 1, 1, 1, 0 };
54
to_direction(SkScalar dy)55 static Contour::Direction to_direction(SkScalar dy) {
56 return dy > 0 ? Contour::Direction::kCCW : dy < 0 ? Contour::Direction::kCW :
57 Contour::Direction::kNone;
58 }
59
contains_edge(SkPoint pts[4],SkPath::Verb verb,SkScalar weight,const SkPoint & edge)60 static int contains_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight, const SkPoint& edge) {
61 SkRect bounds;
62 bounds.setBounds(pts, kPtCount[verb] + 1);
63 if (bounds.fTop > edge.fY) {
64 return 0;
65 }
66 if (bounds.fBottom <= edge.fY) { // check to see if y is at line end to avoid double counting
67 return 0;
68 }
69 if (bounds.fLeft >= edge.fX) {
70 return 0;
71 }
72 int winding = 0;
73 double tVals[3];
74 Contour::Direction directions[3];
75 // must intersect horz ray with curve in case it intersects more than once
76 int count = (*CurveIntercept[verb * 2])(pts, weight, edge.fY, tVals);
77 SkASSERT(between(0, count, 3));
78 // remove results to the right of edge
79 for (int index = 0; index < count; ) {
80 SkScalar intersectX = (*CurvePointAtT[verb])(pts, weight, tVals[index]).fX;
81 if (intersectX < edge.fX) {
82 ++index;
83 continue;
84 }
85 if (intersectX > edge.fX) {
86 tVals[index] = tVals[--count];
87 continue;
88 }
89 // if intersect x equals edge x, we need to determine if pts is to the left or right of edge
90 if (pts[0].fX < edge.fX && pts[kPtCount[verb]].fX < edge.fX) {
91 ++index;
92 continue;
93 }
94 // TODO : other cases need discriminating. need op angle code to figure it out
95 // example: edge ends 45 degree diagonal going up. If pts is to the left of edge, keep.
96 // if pts is to the right of edge, discard. With code as is, can't distiguish the two cases.
97 tVals[index] = tVals[--count];
98 }
99 // use first derivative to determine if intersection is contributing +1 or -1 to winding
100 for (int index = 0; index < count; ++index) {
101 directions[index] = to_direction((*CurveSlopeAtT[verb])(pts, weight, tVals[index]).fY);
102 }
103 for (int index = 0; index < count; ++index) {
104 // skip intersections that end at edge and go up
105 if (zero_or_one(tVals[index]) && Contour::Direction::kCCW != directions[index]) {
106 continue;
107 }
108 winding += (int) directions[index];
109 }
110 return winding; // note winding indicates containership, not contour direction
111 }
112
conic_weight(const SkPath::Iter & iter,SkPath::Verb verb)113 static SkScalar conic_weight(const SkPath::Iter& iter, SkPath::Verb verb) {
114 return SkPath::kConic_Verb == verb ? iter.conicWeight() : 1;
115 }
116
left_edge(SkPoint pts[4],SkPath::Verb verb,SkScalar weight)117 static SkPoint left_edge(SkPoint pts[4], SkPath::Verb verb, SkScalar weight) {
118 SkASSERT(SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb);
119 SkPoint result;
120 double t SK_INIT_TO_AVOID_WARNING;
121 int roots = 0;
122 if (SkPath::kLine_Verb == verb) {
123 result = pts[0].fX < pts[1].fX ? pts[0] : pts[1];
124 } else if (SkPath::kQuad_Verb == verb) {
125 SkDQuad quad;
126 quad.set(pts);
127 if (!quad.monotonicInX()) {
128 roots = SkDQuad::FindExtrema(&quad[0].fX, &t);
129 }
130 if (roots) {
131 result = quad.ptAtT(t).asSkPoint();
132 } else {
133 result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
134 }
135 } else if (SkPath::kConic_Verb == verb) {
136 SkDConic conic;
137 conic.set(pts, weight);
138 if (!conic.monotonicInX()) {
139 roots = SkDConic::FindExtrema(&conic[0].fX, weight, &t);
140 }
141 if (roots) {
142 result = conic.ptAtT(t).asSkPoint();
143 } else {
144 result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
145 }
146 } else {
147 SkASSERT(SkPath::kCubic_Verb == verb);
148 SkDCubic cubic;
149 cubic.set(pts);
150 if (!cubic.monotonicInX()) {
151 double tValues[2];
152 roots = SkDCubic::FindExtrema(&cubic[0].fX, tValues);
153 SkASSERT(roots <= 2);
154 for (int index = 0; index < roots; ++index) {
155 SkPoint temp = cubic.ptAtT(tValues[index]).asSkPoint();
156 if (0 == index || result.fX > temp.fX) {
157 result = temp;
158 }
159 }
160 }
161 if (roots) {
162 result = cubic.ptAtT(t).asSkPoint();
163 } else {
164 result = pts[0].fX < pts[3].fX ? pts[0] : pts[3];
165 }
166 }
167 return result;
168 }
169
170 class OpAsWinding {
171 public:
172 enum class Edge {
173 kInitial,
174 kCompare,
175 };
176
OpAsWinding(const SkPath & path)177 OpAsWinding(const SkPath& path)
178 : fPath(path) {
179 }
180
contourBounds(vector<Contour> * containers)181 void contourBounds(vector<Contour>* containers) {
182 SkRect bounds;
183 bounds.setEmpty();
184 int lastStart = 0;
185 int verbStart = 0;
186 for (auto [verb, pts, w] : SkPathPriv::Iterate(fPath)) {
187 if (SkPathVerb::kMove == verb) {
188 if (!bounds.isEmpty()) {
189 containers->emplace_back(bounds, lastStart, verbStart);
190 lastStart = verbStart;
191 }
192 bounds.setBounds(&pts[kPtIndex[SkPath::kMove_Verb]], kPtCount[SkPath::kMove_Verb]);
193 }
194 if (SkPathVerb::kLine <= verb && verb <= SkPathVerb::kCubic) {
195 SkRect verbBounds;
196 verbBounds.setBounds(&pts[kPtIndex[(int)verb]], kPtCount[(int)verb]);
197 bounds.joinPossiblyEmptyRect(verbBounds);
198 }
199 ++verbStart;
200 }
201 if (!bounds.isEmpty()) {
202 containers->emplace_back(bounds, lastStart, ++verbStart);
203 }
204 }
205
getDirection(Contour & contour)206 Contour::Direction getDirection(Contour& contour) {
207 SkPath::Iter iter(fPath, true);
208 int verbCount = -1;
209 SkPath::Verb verb;
210 SkPoint pts[4];
211
212 SkScalar total_signed_area = 0;
213 do {
214 verb = iter.next(pts);
215 if (++verbCount < contour.fVerbStart) {
216 continue;
217 }
218 if (verbCount >= contour.fVerbEnd) {
219 continue;
220 }
221 if (SkPath::kLine_Verb > verb || verb > SkPath::kCubic_Verb) {
222 continue;
223 }
224
225 switch (verb)
226 {
227 case SkPath::kLine_Verb:
228 total_signed_area += (pts[0].fY - pts[1].fY) * (pts[0].fX + pts[1].fX);
229 break;
230 case SkPath::kQuad_Verb:
231 case SkPath::kConic_Verb:
232 total_signed_area += (pts[0].fY - pts[2].fY) * (pts[0].fX + pts[2].fX);
233 break;
234 case SkPath::kCubic_Verb:
235 total_signed_area += (pts[0].fY - pts[3].fY) * (pts[0].fX + pts[3].fX);
236 break;
237 default:
238 break;
239 }
240 } while (SkPath::kDone_Verb != verb);
241
242 return total_signed_area < 0 ? Contour::Direction::kCCW: Contour::Direction::kCW;
243 }
244
nextEdge(Contour & contour,Edge edge)245 int nextEdge(Contour& contour, Edge edge) {
246 SkPath::Iter iter(fPath, true);
247 SkPoint pts[4];
248 SkPath::Verb verb;
249 int verbCount = -1;
250 int winding = 0;
251 do {
252 verb = iter.next(pts);
253 if (++verbCount < contour.fVerbStart) {
254 continue;
255 }
256 if (verbCount >= contour.fVerbEnd) {
257 continue;
258 }
259 if (SkPath::kLine_Verb > verb || verb > SkPath::kCubic_Verb) {
260 continue;
261 }
262 bool horizontal = true;
263 for (int index = 1; index <= kPtCount[verb]; ++index) {
264 if (pts[0].fY != pts[index].fY) {
265 horizontal = false;
266 break;
267 }
268 }
269 if (horizontal) {
270 continue;
271 }
272 if (edge == Edge::kCompare) {
273 winding += contains_edge(pts, verb, conic_weight(iter, verb), contour.fMinXY);
274 continue;
275 }
276 SkASSERT(edge == Edge::kInitial);
277 SkPoint minXY = left_edge(pts, verb, conic_weight(iter, verb));
278 if (minXY.fX > contour.fMinXY.fX) {
279 continue;
280 }
281 if (minXY.fX == contour.fMinXY.fX) {
282 if (minXY.fY != contour.fMinXY.fY) {
283 continue;
284 }
285 }
286 contour.fMinXY = minXY;
287 } while (SkPath::kDone_Verb != verb);
288 return winding;
289 }
290
containerContains(Contour & contour,Contour & test)291 bool containerContains(Contour& contour, Contour& test) {
292 // find outside point on lesser contour
293 // arbitrarily, choose non-horizontal edge where point <= bounds left
294 // note that if leftmost point is control point, may need tight bounds
295 // to find edge with minimum-x
296 if (SK_ScalarMax == test.fMinXY.fX) {
297 this->nextEdge(test, Edge::kInitial);
298 }
299 // find all edges on greater equal or to the left of one on lesser
300 contour.fMinXY = test.fMinXY;
301 int winding = this->nextEdge(contour, Edge::kCompare);
302 // if edge is up, mark contour cw, otherwise, ccw
303 // sum of greater edges direction should be cw, 0, ccw
304 test.fContained = winding != 0;
305 return -1 <= winding && winding <= 1;
306 }
307
inParent(Contour & contour,Contour & parent)308 void inParent(Contour& contour, Contour& parent) {
309 // move contour into sibling list contained by parent
310 for (auto test : parent.fChildren) {
311 if (test->fBounds.contains(contour.fBounds)) {
312 inParent(contour, *test);
313 return;
314 }
315 }
316 // move parent's children into contour's children if contained by contour
317 for (auto iter = parent.fChildren.begin(); iter != parent.fChildren.end(); ) {
318 if (contour.fBounds.contains((*iter)->fBounds)) {
319 contour.fChildren.push_back(*iter);
320 iter = parent.fChildren.erase(iter);
321 continue;
322 }
323 ++iter;
324 }
325 parent.fChildren.push_back(&contour);
326 }
327
checkContainerChildren(Contour * parent,Contour * child)328 bool checkContainerChildren(Contour* parent, Contour* child) {
329 for (auto grandChild : child->fChildren) {
330 if (!checkContainerChildren(child, grandChild)) {
331 return false;
332 }
333 }
334 if (parent) {
335 if (!containerContains(*parent, *child)) {
336 return false;
337 }
338 }
339 return true;
340 }
341
markReverse(Contour * parent,Contour * child)342 bool markReverse(Contour* parent, Contour* child) {
343 bool reversed = false;
344 for (auto grandChild : child->fChildren) {
345 reversed |= markReverse(grandChild->fContained ? child : parent, grandChild);
346 }
347
348 child->fDirection = getDirection(*child);
349 if (parent && parent->fDirection == child->fDirection) {
350 child->fReverse = true;
351 child->fDirection = (Contour::Direction) -(int) child->fDirection;
352 return true;
353 }
354 return reversed;
355 }
356
reverseMarkedContours(vector<Contour> & contours,SkPathFillType fillType)357 SkPath reverseMarkedContours(vector<Contour>& contours, SkPathFillType fillType) {
358 SkPathPriv::Iterate iterate(fPath);
359 auto iter = iterate.begin();
360 int verbCount = 0;
361
362 SkPathBuilder result;
363 result.setFillType(fillType);
364 for (const Contour& contour : contours) {
365 SkPathBuilder reverse;
366 SkPathBuilder* temp = contour.fReverse ? &reverse : &result;
367 for (; iter != iterate.end() && verbCount < contour.fVerbEnd; ++iter, ++verbCount) {
368 auto [verb, pts, w] = *iter;
369 switch (verb) {
370 case SkPathVerb::kMove:
371 temp->moveTo(pts[0]);
372 break;
373 case SkPathVerb::kLine:
374 temp->lineTo(pts[1]);
375 break;
376 case SkPathVerb::kQuad:
377 temp->quadTo(pts[1], pts[2]);
378 break;
379 case SkPathVerb::kConic:
380 temp->conicTo(pts[1], pts[2], *w);
381 break;
382 case SkPathVerb::kCubic:
383 temp->cubicTo(pts[1], pts[2], pts[3]);
384 break;
385 case SkPathVerb::kClose:
386 temp->close();
387 break;
388 }
389 }
390 if (contour.fReverse) {
391 SkASSERT(temp == &reverse);
392 SkPathPriv::ReverseAddPath(&result, reverse.detach());
393 }
394 }
395 return result.detach();
396 }
397
398 private:
399 const SkPath& fPath;
400 };
401
set_result_path(SkPath * result,const SkPath & path,SkPathFillType fillType)402 static bool set_result_path(SkPath* result, const SkPath& path, SkPathFillType fillType) {
403 *result = path;
404 result->setFillType(fillType);
405 return true;
406 }
407
AsWinding(const SkPath & path,SkPath * result)408 bool AsWinding(const SkPath& path, SkPath* result) {
409 if (!path.isFinite()) {
410 return false;
411 }
412 SkPathFillType fillType = path.getFillType();
413 if (fillType == SkPathFillType::kWinding
414 || fillType == SkPathFillType::kInverseWinding ) {
415 return set_result_path(result, path, fillType);
416 }
417 fillType = path.isInverseFillType() ? SkPathFillType::kInverseWinding :
418 SkPathFillType::kWinding;
419 if (path.isEmpty() || path.isConvex()) {
420 return set_result_path(result, path, fillType);
421 }
422 // count contours
423 vector<Contour> contours; // one per contour
424 OpAsWinding winder(path);
425 winder.contourBounds(&contours);
426 if (contours.size() <= 1) {
427 return set_result_path(result, path, fillType);
428 }
429 // create contour bounding box tree
430 Contour sorted(SkRect(), 0, 0);
431 for (auto& contour : contours) {
432 winder.inParent(contour, sorted);
433 }
434 // if sorted has no grandchildren, no child has to fix its children's winding
435 if (std::all_of(sorted.fChildren.begin(), sorted.fChildren.end(),
436 [](const Contour* contour) -> bool { return contour->fChildren.empty(); } )) {
437 return set_result_path(result, path, fillType);
438 }
439 // starting with outermost and moving inward, see if one path contains another
440 for (auto contour : sorted.fChildren) {
441 winder.nextEdge(*contour, OpAsWinding::Edge::kInitial);
442 contour->fDirection = winder.getDirection(*contour);
443 if (!winder.checkContainerChildren(nullptr, contour)) {
444 return false;
445 }
446 }
447 // starting with outermost and moving inward, mark paths to reverse
448 bool reversed = false;
449 for (auto contour : sorted.fChildren) {
450 reversed |= winder.markReverse(nullptr, contour);
451 }
452 if (!reversed) {
453 return set_result_path(result, path, fillType);
454 }
455 *result = winder.reverseMarkedContours(contours, fillType);
456 return true;
457 }
458