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 #ifdef SK_DEBUG
17 SkPathOpsDebug::gContourID = 0;
18 SkPathOpsDebug::gSegmentID = 0;
19 #endif
20 fUnparseable = false;
21 fSecondHalf = preFetch();
22 }
23
addOperand(const SkPath & path)24 void 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
finish()33 bool 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
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)44 void 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
preFetch()54 int 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
close()137 bool SkOpEdgeBuilder::close() {
138 complete();
139 return true;
140 }
141
walk()142 bool 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