1 /*
2  * Copyright 2012 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 "src/core/SkGeometry.h"
8 #include "src/core/SkPathPriv.h"
9 #include "src/core/SkTSort.h"
10 #include "src/pathops/SkOpEdgeBuilder.h"
11 #include "src/pathops/SkReduceOrder.h"
12 
init()13 void SkOpEdgeBuilder::init() {
14     fOperand = false;
15     fXorMask[0] = fXorMask[1] = ((int)fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
16             : kWinding_PathOpsMask;
17     fUnparseable = false;
18     fSecondHalf = preFetch();
19 }
20 
21 // very tiny points cause numerical instability : don't allow them
force_small_to_zero(const SkPoint & pt)22 static SkPoint force_small_to_zero(const SkPoint& pt) {
23     SkPoint ret = pt;
24     if (SkScalarAbs(ret.fX) < FLT_EPSILON_ORDERABLE_ERR) {
25         ret.fX = 0;
26     }
27     if (SkScalarAbs(ret.fY) < FLT_EPSILON_ORDERABLE_ERR) {
28         ret.fY = 0;
29     }
30     return ret;
31 }
32 
can_add_curve(SkPath::Verb verb,SkPoint * curve)33 static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
34     if (SkPath::kMove_Verb == verb) {
35         return false;
36     }
37     for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
38         curve[index] = force_small_to_zero(curve[index]);
39     }
40     return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
41 }
42 
addOperand(const SkPath & path)43 void SkOpEdgeBuilder::addOperand(const SkPath& path) {
44     SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
45     fPathVerbs.pop();
46     fPath = &path;
47     fXorMask[1] = ((int)fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
48             : kWinding_PathOpsMask;
49     preFetch();
50 }
51 
finish()52 bool SkOpEdgeBuilder::finish() {
53     fOperand = false;
54     if (fUnparseable || !walk()) {
55         return false;
56     }
57     complete();
58     SkOpContour* contour = fContourBuilder.contour();
59     if (contour && !contour->count()) {
60         fContoursHead->remove(contour);
61     }
62     return true;
63 }
64 
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)65 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
66     if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
67         *fPathVerbs.append() = SkPath::kLine_Verb;
68         *fPathPts.append() = curveStart;
69     } else {
70         int verbCount = fPathVerbs.count();
71         int ptsCount = fPathPts.count();
72         if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1]
73                 && fPathPts[ptsCount - 2] == curveStart) {
74             fPathVerbs.pop();
75             fPathPts.pop();
76         } else {
77             fPathPts[ptsCount - 1] = curveStart;
78         }
79     }
80     *fPathVerbs.append() = SkPath::kClose_Verb;
81 }
82 
preFetch()83 int SkOpEdgeBuilder::preFetch() {
84     if (!fPath->isFinite()) {
85         fUnparseable = true;
86         return 0;
87     }
88     SkPoint curveStart;
89     SkPoint curve[4];
90     bool lastCurve = false;
91     for (auto [pathVerb, pts, w] : SkPathPriv::Iterate(*fPath)) {
92         auto verb = static_cast<SkPath::Verb>(pathVerb);
93         switch (verb) {
94             case SkPath::kMove_Verb:
95                 if (!fAllowOpenContours && lastCurve) {
96                     closeContour(curve[0], curveStart);
97                 }
98                 *fPathVerbs.append() = verb;
99                 curve[0] = force_small_to_zero(pts[0]);
100                 *fPathPts.append() = curve[0];
101                 curveStart = curve[0];
102                 lastCurve = false;
103                 continue;
104             case SkPath::kLine_Verb:
105                 curve[1] = force_small_to_zero(pts[1]);
106                 if (SkDPoint::ApproximatelyEqual(curve[0], curve[1])) {
107                     uint8_t lastVerb = fPathVerbs.top();
108                     if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
109                         fPathPts.top() = curve[0] = curve[1];
110                     }
111                     continue;  // skip degenerate points
112                 }
113                 break;
114             case SkPath::kQuad_Verb:
115                 curve[1] = force_small_to_zero(pts[1]);
116                 curve[2] = force_small_to_zero(pts[2]);
117                 verb = SkReduceOrder::Quad(curve, curve);
118                 if (verb == SkPath::kMove_Verb) {
119                     continue;  // skip degenerate points
120                 }
121                 break;
122             case SkPath::kConic_Verb:
123                 curve[1] = force_small_to_zero(pts[1]);
124                 curve[2] = force_small_to_zero(pts[2]);
125                 verb = SkReduceOrder::Quad(curve, curve);
126                 if (SkPath::kQuad_Verb == verb && 1 != *w) {
127                   verb = SkPath::kConic_Verb;
128                 } else if (verb == SkPath::kMove_Verb) {
129                     continue;  // skip degenerate points
130                 }
131                 break;
132             case SkPath::kCubic_Verb:
133                 curve[1] = force_small_to_zero(pts[1]);
134                 curve[2] = force_small_to_zero(pts[2]);
135                 curve[3] = force_small_to_zero(pts[3]);
136                 verb = SkReduceOrder::Cubic(curve, curve);
137                 if (verb == SkPath::kMove_Verb) {
138                     continue;  // skip degenerate points
139                 }
140                 break;
141             case SkPath::kClose_Verb:
142                 closeContour(curve[0], curveStart);
143                 lastCurve = false;
144                 continue;
145             case SkPath::kDone_Verb:
146                 continue;
147         }
148         *fPathVerbs.append() = verb;
149         int ptCount = SkPathOpsVerbToPoints(verb);
150         fPathPts.append(ptCount, &curve[1]);
151         if (verb == SkPath::kConic_Verb) {
152             *fWeights.append() = *w;
153         }
154         curve[0] = curve[ptCount];
155         lastCurve = true;
156     }
157     if (!fAllowOpenContours && lastCurve) {
158         closeContour(curve[0], curveStart);
159     }
160     *fPathVerbs.append() = SkPath::kDone_Verb;
161     return fPathVerbs.count() - 1;
162 }
163 
close()164 bool SkOpEdgeBuilder::close() {
165     complete();
166     return true;
167 }
168 
walk()169 bool SkOpEdgeBuilder::walk() {
170     uint8_t* verbPtr = fPathVerbs.begin();
171     uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
172     SkPoint* pointsPtr = fPathPts.begin();
173     SkScalar* weightPtr = fWeights.begin();
174     SkPath::Verb verb;
175     SkOpContour* contour = fContourBuilder.contour();
176     int moveToPtrBump = 0;
177     while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
178         if (verbPtr == endOfFirstHalf) {
179             fOperand = true;
180         }
181         verbPtr++;
182         switch (verb) {
183             case SkPath::kMove_Verb:
184                 if (contour && contour->count()) {
185                     if (fAllowOpenContours) {
186                         complete();
187                     } else if (!close()) {
188                         return false;
189                     }
190                 }
191                 if (!contour) {
192                     fContourBuilder.setContour(contour = fContoursHead->appendContour());
193                 }
194                 contour->init(fGlobalState, fOperand,
195                     fXorMask[fOperand] == kEvenOdd_PathOpsMask);
196                 pointsPtr += moveToPtrBump;
197                 moveToPtrBump = 1;
198                 continue;
199             case SkPath::kLine_Verb:
200                 fContourBuilder.addLine(pointsPtr);
201                 break;
202             case SkPath::kQuad_Verb:
203                 {
204                     SkVector v1 = pointsPtr[1] - pointsPtr[0];
205                     SkVector v2 = pointsPtr[2] - pointsPtr[1];
206                     if (v1.dot(v2) < 0) {
207                         SkPoint pair[5];
208                         if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
209                             goto addOneQuad;
210                         }
211                         if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
212                             return false;
213                         }
214                         for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) {
215                             pair[index] = force_small_to_zero(pair[index]);
216                         }
217                         SkPoint cStorage[2][2];
218                         SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
219                         SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
220                         SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
221                         SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
222                         if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
223                             fContourBuilder.addCurve(v1, curve1);
224                             fContourBuilder.addCurve(v2, curve2);
225                             break;
226                         }
227                     }
228                 }
229             addOneQuad:
230                 fContourBuilder.addQuad(pointsPtr);
231                 break;
232             case SkPath::kConic_Verb: {
233                 SkVector v1 = pointsPtr[1] - pointsPtr[0];
234                 SkVector v2 = pointsPtr[2] - pointsPtr[1];
235                 SkScalar weight = *weightPtr++;
236                 if (v1.dot(v2) < 0) {
237                     // FIXME: max curvature for conics hasn't been implemented; use placeholder
238                     SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
239                     if (0 < maxCurvature && maxCurvature < 1) {
240                         SkConic conic(pointsPtr, weight);
241                         SkConic pair[2];
242                         if (!conic.chopAt(maxCurvature, pair)) {
243                             // if result can't be computed, use original
244                             fContourBuilder.addConic(pointsPtr, weight);
245                             break;
246                         }
247                         SkPoint cStorage[2][3];
248                         SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
249                         SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
250                         SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
251                         SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
252                         if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
253                             fContourBuilder.addCurve(v1, curve1, pair[0].fW);
254                             fContourBuilder.addCurve(v2, curve2, pair[1].fW);
255                             break;
256                         }
257                     }
258                 }
259                 fContourBuilder.addConic(pointsPtr, weight);
260                 } break;
261             case SkPath::kCubic_Verb:
262                 {
263                     // Split complex cubics (such as self-intersecting curves or
264                     // ones with difficult curvature) in two before proceeding.
265                     // This can be required for intersection to succeed.
266                     SkScalar splitT[3];
267                     int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
268                     if (!breaks) {
269                         fContourBuilder.addCubic(pointsPtr);
270                         break;
271                     }
272                     SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
273                     struct Splitsville {
274                         double fT[2];
275                         SkPoint fPts[4];
276                         SkPoint fReduced[4];
277                         SkPath::Verb fVerb;
278                         bool fCanAdd;
279                     } splits[4];
280                     SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
281                     SkTQSort(splitT, splitT + breaks);
282                     for (int index = 0; index <= breaks; ++index) {
283                         Splitsville* split = &splits[index];
284                         split->fT[0] = index ? splitT[index - 1] : 0;
285                         split->fT[1] = index < breaks ? splitT[index] : 1;
286                         SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
287                         if (!part.toFloatPoints(split->fPts)) {
288                             return false;
289                         }
290                         split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
291                         SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
292                                 ? split->fPts : split->fReduced;
293                         split->fCanAdd = can_add_curve(split->fVerb, curve);
294                     }
295                     for (int index = 0; index <= breaks; ++index) {
296                         Splitsville* split = &splits[index];
297                         if (!split->fCanAdd) {
298                             continue;
299                         }
300                         int prior = index;
301                         while (prior > 0 && !splits[prior - 1].fCanAdd) {
302                             --prior;
303                         }
304                         if (prior < index) {
305                             split->fT[0] = splits[prior].fT[0];
306                             split->fPts[0] = splits[prior].fPts[0];
307                         }
308                         int next = index;
309                         int breakLimit = std::min(breaks, (int) SK_ARRAY_COUNT(splits) - 1);
310                         while (next < breakLimit && !splits[next + 1].fCanAdd) {
311                             ++next;
312                         }
313                         if (next > index) {
314                             split->fT[1] = splits[next].fT[1];
315                             split->fPts[3] = splits[next].fPts[3];
316                         }
317                         if (prior < index || next > index) {
318                             split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
319                         }
320                         SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
321                                 ? split->fPts : split->fReduced;
322                         if (!can_add_curve(split->fVerb, curve)) {
323                             return false;
324                         }
325                         fContourBuilder.addCurve(split->fVerb, curve);
326                     }
327                 }
328                 break;
329             case SkPath::kClose_Verb:
330                 SkASSERT(contour);
331                 if (!close()) {
332                     return false;
333                 }
334                 contour = nullptr;
335                 continue;
336             default:
337                 SkDEBUGFAIL("bad verb");
338                 return false;
339         }
340         SkASSERT(contour);
341         if (contour->count()) {
342             contour->debugValidate();
343         }
344         pointsPtr += SkPathOpsVerbToPoints(verb);
345     }
346     fContourBuilder.flush();
347     if (contour && contour->count() &&!fAllowOpenContours && !close()) {
348         return false;
349     }
350     return true;
351 }
352