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