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
init()11 void 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
addOperand(const SkPath & path)20 void 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
finish()29 bool 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
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)40 void 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
preFetch()50 int 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
close()133 bool SkOpEdgeBuilder::close() {
134 complete();
135 return true;
136 }
137
walk()138 bool 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