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