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    fCurrentContour = fContoursHead;
13    fOperand = false;
14    fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
15            : kWinding_PathOpsMask;
16    fUnparseable = false;
17    fSecondHalf = preFetch();
18}
19
20void SkOpEdgeBuilder::addOperand(const SkPath& path) {
21    SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
22    fPathVerbs.pop();
23    fPath = &path;
24    fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
25            : kWinding_PathOpsMask;
26    preFetch();
27}
28
29int SkOpEdgeBuilder::count() const {
30    SkOpContour* contour = fContoursHead;
31    int count = 0;
32    while (contour) {
33        count += contour->count() > 0;
34        contour = contour->next();
35    }
36    return count;
37}
38
39bool SkOpEdgeBuilder::finish(SkChunkAlloc* allocator) {
40    fOperand = false;
41    if (fUnparseable || !walk(allocator)) {
42        return false;
43    }
44    complete();
45    if (fCurrentContour && !fCurrentContour->count()) {
46        fContoursHead->remove(fCurrentContour);
47    }
48    return true;
49}
50
51void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
52    if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
53        *fPathVerbs.append() = SkPath::kLine_Verb;
54        *fPathPts.append() = curveStart;
55    } else {
56        fPathPts[fPathPts.count() - 1] = curveStart;
57    }
58    *fPathVerbs.append() = SkPath::kClose_Verb;
59}
60
61// very tiny points cause numerical instability : don't allow them
62static void force_small_to_zero(SkPoint* pt) {
63    if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
64        pt->fX = 0;
65    }
66    if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
67        pt->fY = 0;
68    }
69}
70
71int SkOpEdgeBuilder::preFetch() {
72    if (!fPath->isFinite()) {
73        fUnparseable = true;
74        return 0;
75    }
76    SkPath::RawIter iter(*fPath);
77    SkPoint curveStart;
78    SkPoint curve[4];
79    SkPoint pts[4];
80    SkPath::Verb verb;
81    bool lastCurve = false;
82    do {
83        verb = iter.next(pts);
84        switch (verb) {
85            case SkPath::kMove_Verb:
86                if (!fAllowOpenContours && lastCurve) {
87                    closeContour(curve[0], curveStart);
88                }
89                *fPathVerbs.append() = verb;
90                force_small_to_zero(&pts[0]);
91                *fPathPts.append() = pts[0];
92                curveStart = curve[0] = pts[0];
93                lastCurve = false;
94                continue;
95            case SkPath::kLine_Verb:
96                force_small_to_zero(&pts[1]);
97                if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
98                    uint8_t lastVerb = fPathVerbs.top();
99                    if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
100                        fPathPts.top() = pts[1];
101                    }
102                    continue;  // skip degenerate points
103                }
104                break;
105            case SkPath::kQuad_Verb:
106                force_small_to_zero(&pts[1]);
107                force_small_to_zero(&pts[2]);
108                curve[1] = pts[1];
109                curve[2] = pts[2];
110                verb = SkReduceOrder::Quad(curve, pts);
111                if (verb == SkPath::kMove_Verb) {
112                    continue;  // skip degenerate points
113                }
114                break;
115            case SkPath::kConic_Verb:
116                force_small_to_zero(&pts[1]);
117                force_small_to_zero(&pts[2]);
118                curve[1] = pts[1];
119                curve[2] = pts[2];
120                verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts);
121                if (verb == SkPath::kMove_Verb) {
122                    continue;  // skip degenerate points
123                }
124                break;
125            case SkPath::kCubic_Verb:
126                force_small_to_zero(&pts[1]);
127                force_small_to_zero(&pts[2]);
128                force_small_to_zero(&pts[3]);
129                curve[1] = pts[1];
130                curve[2] = pts[2];
131                curve[3] = pts[3];
132                verb = SkReduceOrder::Cubic(curve, pts);
133                if (verb == SkPath::kMove_Verb) {
134                    continue;  // skip degenerate points
135                }
136                break;
137            case SkPath::kClose_Verb:
138                closeContour(curve[0], curveStart);
139                lastCurve = false;
140                continue;
141            case SkPath::kDone_Verb:
142                continue;
143        }
144        *fPathVerbs.append() = verb;
145        int ptCount = SkPathOpsVerbToPoints(verb);
146        fPathPts.append(ptCount, &pts[1]);
147        if (verb == SkPath::kConic_Verb) {
148            *fWeights.append() = iter.conicWeight();
149        }
150        curve[0] = pts[ptCount];
151        lastCurve = true;
152    } while (verb != SkPath::kDone_Verb);
153    if (!fAllowOpenContours && lastCurve) {
154        closeContour(curve[0], curveStart);
155    }
156    *fPathVerbs.append() = SkPath::kDone_Verb;
157    return fPathVerbs.count() - 1;
158}
159
160bool SkOpEdgeBuilder::close() {
161    complete();
162    return true;
163}
164
165bool SkOpEdgeBuilder::walk(SkChunkAlloc* allocator) {
166    uint8_t* verbPtr = fPathVerbs.begin();
167    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
168    SkPoint* pointsPtr = fPathPts.begin() - 1;
169    SkScalar* weightPtr = fWeights.begin();
170    SkPath::Verb verb;
171    while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
172        if (verbPtr == endOfFirstHalf) {
173            fOperand = true;
174        }
175        verbPtr++;
176        switch (verb) {
177            case SkPath::kMove_Verb:
178                if (fCurrentContour && fCurrentContour->count()) {
179                    if (fAllowOpenContours) {
180                        complete();
181                    } else if (!close()) {
182                        return false;
183                    }
184                }
185                if (!fCurrentContour) {
186                    fCurrentContour = fContoursHead->appendContour(allocator);
187                }
188                fCurrentContour->init(fGlobalState, fOperand,
189                    fXorMask[fOperand] == kEvenOdd_PathOpsMask);
190                pointsPtr += 1;
191                continue;
192            case SkPath::kLine_Verb:
193                fCurrentContour->addLine(pointsPtr, fAllocator);
194                break;
195            case SkPath::kQuad_Verb:
196                fCurrentContour->addQuad(pointsPtr, fAllocator);
197                break;
198            case SkPath::kConic_Verb:
199                fCurrentContour->addConic(pointsPtr, *weightPtr++, fAllocator);
200                break;
201            case SkPath::kCubic_Verb: {
202                // split self-intersecting cubics in two before proceeding
203                // if the cubic is convex, it doesn't self intersect.
204                SkScalar loopT;
205                if (SkDCubic::ComplexBreak(pointsPtr, &loopT)) {
206                    SkPoint cubicPair[7];
207                    SkChopCubicAt(pointsPtr, cubicPair, loopT);
208                    if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cubicPair) * 2)) {
209                        return false;
210                    }
211                    SkPoint cStorage[2][4];
212                    SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]);
213                    SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]);
214                    if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) {
215                        SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair[0] : cStorage[0];
216                        SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair[3] : cStorage[1];
217                        for (int index = 0; index < SkPathOpsVerbToPoints(v1); ++index) {
218                            force_small_to_zero(&curve1[index]);
219                        }
220                        for (int index = 0; index < SkPathOpsVerbToPoints(v2); ++index) {
221                            force_small_to_zero(&curve2[index]);
222                        }
223                        fCurrentContour->addCurve(v1, curve1, fAllocator);
224                        fCurrentContour->addCurve(v2, curve2, fAllocator);
225                    } else {
226                        fCurrentContour->addCubic(pointsPtr, fAllocator);
227                    }
228                } else {
229                    fCurrentContour->addCubic(pointsPtr, fAllocator);
230                }
231                } break;
232            case SkPath::kClose_Verb:
233                SkASSERT(fCurrentContour);
234                if (!close()) {
235                    return false;
236                }
237                continue;
238            default:
239                SkDEBUGFAIL("bad verb");
240                return false;
241        }
242        SkASSERT(fCurrentContour);
243        fCurrentContour->debugValidate();
244        pointsPtr += SkPathOpsVerbToPoints(verb);
245    }
246   if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !close()) {
247       return false;
248   }
249   return true;
250}
251