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