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 = NULL;
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_back();
23    fPath = &path;
24    fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
25            : kWinding_PathOpsMask;
26    preFetch();
27}
28
29bool SkOpEdgeBuilder::finish() {
30    if (fUnparseable || !walk()) {
31        return false;
32    }
33    complete();
34    if (fCurrentContour && !fCurrentContour->segments().count()) {
35        fContours.pop_back();
36    }
37    return true;
38}
39
40void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
41    if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
42        fPathVerbs.push_back(SkPath::kLine_Verb);
43        fPathPts.push_back_n(1, &curveStart);
44    } else {
45        fPathPts[fPathPts.count() - 1] = curveStart;
46    }
47    fPathVerbs.push_back(SkPath::kClose_Verb);
48}
49
50// very tiny points cause numerical instability : don't allow them
51static void force_small_to_zero(SkPoint* pt) {
52    if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
53        pt->fX = 0;
54    }
55    if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
56        pt->fY = 0;
57    }
58}
59
60
61int SkOpEdgeBuilder::preFetch() {
62    if (!fPath->isFinite()) {
63        fUnparseable = true;
64        return 0;
65    }
66    SkAutoConicToQuads quadder;
67    const SkScalar quadderTol = SK_Scalar1 / 16;
68    SkPath::RawIter iter(*fPath);
69    SkPoint curveStart;
70    SkPoint curve[4];
71    SkPoint pts[4];
72    SkPath::Verb verb;
73    bool lastCurve = false;
74    do {
75        verb = iter.next(pts);
76        switch (verb) {
77            case SkPath::kMove_Verb:
78                if (!fAllowOpenContours && lastCurve) {
79                    closeContour(curve[0], curveStart);
80                }
81                fPathVerbs.push_back(verb);
82                force_small_to_zero(&pts[0]);
83                fPathPts.push_back(pts[0]);
84                curveStart = curve[0] = pts[0];
85                lastCurve = false;
86                continue;
87            case SkPath::kLine_Verb:
88                force_small_to_zero(&pts[1]);
89                if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
90                    uint8_t lastVerb = fPathVerbs.back();
91                    if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
92                        fPathPts.back() = pts[1];
93                    }
94                    continue;  // skip degenerate points
95                }
96                break;
97            case SkPath::kQuad_Verb:
98                force_small_to_zero(&pts[1]);
99                force_small_to_zero(&pts[2]);
100                curve[1] = pts[1];
101                curve[2] = pts[2];
102                verb = SkReduceOrder::Quad(curve, pts);
103                if (verb == SkPath::kMove_Verb) {
104                    continue;  // skip degenerate points
105                }
106                break;
107            case SkPath::kConic_Verb: {
108                    const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
109                            quadderTol);
110                    const int nQuads = quadder.countQuads();
111                    for (int i = 0; i < nQuads; ++i) {
112                       fPathVerbs.push_back(SkPath::kQuad_Verb);
113                    }
114                    fPathPts.push_back_n(nQuads * 2, quadPts);
115                    curve[0] = quadPts[nQuads * 2 - 1];
116                    lastCurve = true;
117                }
118                continue;
119            case SkPath::kCubic_Verb:
120                force_small_to_zero(&pts[1]);
121                force_small_to_zero(&pts[2]);
122                force_small_to_zero(&pts[3]);
123                curve[1] = pts[1];
124                curve[2] = pts[2];
125                curve[3] = pts[3];
126                verb = SkReduceOrder::Cubic(curve, pts);
127                if (verb == SkPath::kMove_Verb) {
128                    continue;  // skip degenerate points
129                }
130                break;
131            case SkPath::kClose_Verb:
132                closeContour(curve[0], curveStart);
133                lastCurve = false;
134                continue;
135            case SkPath::kDone_Verb:
136                continue;
137        }
138        fPathVerbs.push_back(verb);
139        int ptCount = SkPathOpsVerbToPoints(verb);
140        fPathPts.push_back_n(ptCount, &pts[1]);
141        curve[0] = pts[ptCount];
142        lastCurve = true;
143    } while (verb != SkPath::kDone_Verb);
144    if (!fAllowOpenContours && lastCurve) {
145        closeContour(curve[0], curveStart);
146    }
147    fPathVerbs.push_back(SkPath::kDone_Verb);
148    return fPathVerbs.count() - 1;
149}
150
151bool SkOpEdgeBuilder::close() {
152    complete();
153    return true;
154}
155
156bool SkOpEdgeBuilder::walk() {
157    uint8_t* verbPtr = fPathVerbs.begin();
158    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
159    const SkPoint* pointsPtr = fPathPts.begin() - 1;
160    SkPath::Verb verb;
161    while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
162        if (verbPtr == endOfFirstHalf) {
163            fOperand = true;
164        }
165        verbPtr++;
166        switch (verb) {
167            case SkPath::kMove_Verb:
168                if (fCurrentContour) {
169                    if (fAllowOpenContours) {
170                        complete();
171                    } else if (!close()) {
172                        return false;
173                    }
174                }
175                if (!fCurrentContour) {
176                    fCurrentContour = fContours.push_back_n(1);
177                    fCurrentContour->setOperand(fOperand);
178                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
179                }
180                pointsPtr += 1;
181                continue;
182            case SkPath::kLine_Verb:
183                fCurrentContour->addLine(pointsPtr);
184                break;
185            case SkPath::kQuad_Verb:
186                fCurrentContour->addQuad(pointsPtr);
187                break;
188            case SkPath::kCubic_Verb:
189                fCurrentContour->addCubic(pointsPtr);
190                break;
191            case SkPath::kClose_Verb:
192                SkASSERT(fCurrentContour);
193                if (!close()) {
194                    return false;
195                }
196                continue;
197            default:
198                SkDEBUGFAIL("bad verb");
199                return false;
200        }
201        pointsPtr += SkPathOpsVerbToPoints(verb);
202        SkASSERT(fCurrentContour);
203    }
204   if (fCurrentContour && !fAllowOpenContours && !close()) {
205       return false;
206   }
207   return true;
208}
209