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