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
50int SkOpEdgeBuilder::preFetch() {
51    if (!fPath->isFinite()) {
52        fUnparseable = true;
53        return 0;
54    }
55    SkAutoConicToQuads quadder;
56    const SkScalar quadderTol = SK_Scalar1 / 16;
57    SkPath::RawIter iter(*fPath);
58    SkPoint curveStart;
59    SkPoint curve[4];
60    SkPoint pts[4];
61    SkPath::Verb verb;
62    bool lastCurve = false;
63    do {
64        verb = iter.next(pts);
65        switch (verb) {
66            case SkPath::kMove_Verb:
67                if (!fAllowOpenContours && lastCurve) {
68                    closeContour(curve[0], curveStart);
69                }
70                fPathVerbs.push_back(verb);
71                fPathPts.push_back(pts[0]);
72                curveStart = curve[0] = pts[0];
73                lastCurve = false;
74                continue;
75            case SkPath::kLine_Verb:
76                if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
77                    uint8_t lastVerb = fPathVerbs.back();
78                    if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
79                        fPathPts.back() = pts[1];
80                    }
81                    continue;  // skip degenerate points
82                }
83                break;
84            case SkPath::kQuad_Verb:
85                curve[1] = pts[1];
86                curve[2] = pts[2];
87                verb = SkReduceOrder::Quad(curve, pts);
88                if (verb == SkPath::kMove_Verb) {
89                    continue;  // skip degenerate points
90                }
91                break;
92            case SkPath::kConic_Verb: {
93                    const SkPoint* quadPts = quadder.computeQuads(pts, iter.conicWeight(),
94                            quadderTol);
95                    const int nQuads = quadder.countQuads();
96                    for (int i = 0; i < nQuads; ++i) {
97                       fPathVerbs.push_back(SkPath::kQuad_Verb);
98                    }
99                    fPathPts.push_back_n(nQuads * 2, quadPts);
100                    curve[0] = quadPts[nQuads * 2 - 1];
101                    lastCurve = true;
102                }
103                continue;
104            case SkPath::kCubic_Verb:
105                curve[1] = pts[1];
106                curve[2] = pts[2];
107                curve[3] = pts[3];
108                verb = SkReduceOrder::Cubic(curve, pts);
109                if (verb == SkPath::kMove_Verb) {
110                    continue;  // skip degenerate points
111                }
112                break;
113            case SkPath::kClose_Verb:
114                closeContour(curve[0], curveStart);
115                lastCurve = false;
116                continue;
117            case SkPath::kDone_Verb:
118                continue;
119        }
120        fPathVerbs.push_back(verb);
121        int ptCount = SkPathOpsVerbToPoints(verb);
122        fPathPts.push_back_n(ptCount, &pts[1]);
123        curve[0] = pts[ptCount];
124        lastCurve = true;
125    } while (verb != SkPath::kDone_Verb);
126    if (!fAllowOpenContours && lastCurve) {
127        closeContour(curve[0], curveStart);
128    }
129    fPathVerbs.push_back(SkPath::kDone_Verb);
130    return fPathVerbs.count() - 1;
131}
132
133bool SkOpEdgeBuilder::close() {
134    complete();
135    return true;
136}
137
138bool SkOpEdgeBuilder::walk() {
139    uint8_t* verbPtr = fPathVerbs.begin();
140    uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
141    const SkPoint* pointsPtr = fPathPts.begin() - 1;
142    SkPath::Verb verb;
143    while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
144        if (verbPtr == endOfFirstHalf) {
145            fOperand = true;
146        }
147        verbPtr++;
148        switch (verb) {
149            case SkPath::kMove_Verb:
150                if (fCurrentContour) {
151                    if (fAllowOpenContours) {
152                        complete();
153                    } else if (!close()) {
154                        return false;
155                    }
156                }
157                if (!fCurrentContour) {
158                    fCurrentContour = fContours.push_back_n(1);
159                    fCurrentContour->setOperand(fOperand);
160                    fCurrentContour->setXor(fXorMask[fOperand] == kEvenOdd_PathOpsMask);
161                }
162                pointsPtr += 1;
163                continue;
164            case SkPath::kLine_Verb:
165                fCurrentContour->addLine(pointsPtr);
166                break;
167            case SkPath::kQuad_Verb:
168                fCurrentContour->addQuad(pointsPtr);
169                break;
170            case SkPath::kCubic_Verb:
171                fCurrentContour->addCubic(pointsPtr);
172                break;
173            case SkPath::kClose_Verb:
174                SkASSERT(fCurrentContour);
175                if (!close()) {
176                    return false;
177                }
178                continue;
179            default:
180                SkDEBUGFAIL("bad verb");
181                return false;
182        }
183        pointsPtr += SkPathOpsVerbToPoints(verb);
184        SkASSERT(fCurrentContour);
185    }
186   if (fCurrentContour && !fAllowOpenContours && !close()) {
187       return false;
188   }
189   return true;
190}
191