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
11void 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
20static 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
29static 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
39void 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
48bool 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
61void 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
79int 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
170bool SkOpEdgeBuilder::close() {
171    complete();
172    return true;
173}
174
175bool SkOpEdgeBuilder::walk() {
176    uint8_t* verbPtr = fPathVerbs.begin();
177    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
178    SkPoint* pointsPtr = fPathPts.begin() - 1;
179    SkScalar* weightPtr = fWeights.begin();
180    SkPath::Verb verb;
181    SkOpContour* contour = fContourBuilder.contour();
182    while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
183        if (verbPtr == endOfFirstHalf) {
184            fOperand = true;
185        }
186        verbPtr++;
187        switch (verb) {
188            case SkPath::kMove_Verb:
189                if (contour && contour->count()) {
190                    if (fAllowOpenContours) {
191                        complete();
192                    } else if (!close()) {
193                        return false;
194                    }
195                }
196                if (!contour) {
197                    fContourBuilder.setContour(contour = fContoursHead->appendContour());
198                }
199                contour->init(fGlobalState, fOperand,
200                    fXorMask[fOperand] == kEvenOdd_PathOpsMask);
201                pointsPtr += 1;
202                continue;
203            case SkPath::kLine_Verb:
204                fContourBuilder.addLine(pointsPtr);
205                break;
206            case SkPath::kQuad_Verb:
207                {
208                    SkVector v1 = pointsPtr[1] - pointsPtr[0];
209                    SkVector v2 = pointsPtr[2] - pointsPtr[1];
210                    if (v1.dot(v2) < 0) {
211                        SkPoint pair[5];
212                        if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
213                            goto addOneQuad;
214                        }
215                        if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
216                            return false;
217                        }
218                        SkPoint cStorage[2][2];
219                        SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
220                        SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
221                        SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
222                        SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
223                        if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
224                            fContourBuilder.addCurve(v1, curve1);
225                            fContourBuilder.addCurve(v2, curve2);
226                            break;
227                        }
228                    }
229                }
230            addOneQuad:
231                fContourBuilder.addQuad(pointsPtr);
232                break;
233            case SkPath::kConic_Verb: {
234                SkVector v1 = pointsPtr[1] - pointsPtr[0];
235                SkVector v2 = pointsPtr[2] - pointsPtr[1];
236                SkScalar weight = *weightPtr++;
237                if (v1.dot(v2) < 0) {
238                    // FIXME: max curvature for conics hasn't been implemented; use placeholder
239                    SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
240                    if (maxCurvature > 0) {
241                        SkConic conic(pointsPtr, weight);
242                        SkConic pair[2];
243                        if (!conic.chopAt(maxCurvature, pair)) {
244                            // if result can't be computed, use original
245                            fContourBuilder.addConic(pointsPtr, weight);
246                            break;
247                        }
248                        SkPoint cStorage[2][3];
249                        SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
250                        SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
251                        SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
252                        SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
253                        if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
254                            fContourBuilder.addCurve(v1, curve1, pair[0].fW);
255                            fContourBuilder.addCurve(v2, curve2, pair[1].fW);
256                            break;
257                        }
258                    }
259                }
260                fContourBuilder.addConic(pointsPtr, weight);
261                } break;
262            case SkPath::kCubic_Verb:
263                {
264                    // Split complex cubics (such as self-intersecting curves or
265                    // ones with difficult curvature) in two before proceeding.
266                    // This can be required for intersection to succeed.
267                    SkScalar splitT[3];
268                    int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
269                    if (!breaks) {
270                        fContourBuilder.addCubic(pointsPtr);
271                        break;
272                    }
273                    SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
274                    struct Splitsville {
275                        double fT[2];
276                        SkPoint fPts[4];
277                        SkPoint fReduced[4];
278                        SkPath::Verb fVerb;
279                        bool fCanAdd;
280                    } splits[4];
281                    SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
282                    SkTQSort(splitT, &splitT[breaks - 1]);
283                    for (int index = 0; index <= breaks; ++index) {
284                        Splitsville* split = &splits[index];
285                        split->fT[0] = index ? splitT[index - 1] : 0;
286                        split->fT[1] = index < breaks ? splitT[index] : 1;
287                        SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
288                        if (!part.toFloatPoints(split->fPts)) {
289                            return false;
290                        }
291                        split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
292                        SkPoint* curve = SkPath::kCubic_Verb == verb
293                                ? split->fPts : split->fReduced;
294                        split->fCanAdd = can_add_curve(split->fVerb, curve);
295                    }
296                    for (int index = 0; index <= breaks; ++index) {
297                        Splitsville* split = &splits[index];
298                        if (!split->fCanAdd) {
299                            continue;
300                        }
301                        int prior = index;
302                        while (prior > 0 && !splits[prior - 1].fCanAdd) {
303                            --prior;
304                        }
305                        if (prior < index) {
306                            split->fT[0] = splits[prior].fT[0];
307                        }
308                        int next = index;
309                        while (next < breaks && !splits[next + 1].fCanAdd) {
310                            ++next;
311                        }
312                        if (next > index) {
313                            split->fT[1] = splits[next].fT[1];
314                        }
315                        if (prior < index || next > index) {
316                            if (0 == split->fT[0] && 1 == split->fT[1]) {
317                                fContourBuilder.addCubic(pointsPtr);
318                                break;
319                            }
320                            SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0],
321                                    split->fT[1]);
322                            if (!part.toFloatPoints(split->fPts)) {
323                                return false;
324                            }
325                            split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
326                        }
327                        SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
328                                ? split->fPts : split->fReduced;
329                        SkAssertResult(can_add_curve(split->fVerb, curve));
330                        fContourBuilder.addCurve(split->fVerb, curve);
331                    }
332                }
333                break;
334            case SkPath::kClose_Verb:
335                SkASSERT(contour);
336                if (!close()) {
337                    return false;
338                }
339                contour = nullptr;
340                continue;
341            default:
342                SkDEBUGFAIL("bad verb");
343                return false;
344        }
345        SkASSERT(contour);
346        if (contour->count()) {
347            contour->debugValidate();
348        }
349        pointsPtr += SkPathOpsVerbToPoints(verb);
350    }
351    fContourBuilder.flush();
352    if (contour && contour->count() &&!fAllowOpenContours && !close()) {
353        return false;
354    }
355    return true;
356}
357