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 = fContoursHead;
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();
23 fPath = &path;
24 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
25 : kWinding_PathOpsMask;
26 preFetch();
27 }
28
count() const29 int SkOpEdgeBuilder::count() const {
30 SkOpContour* contour = fContoursHead;
31 int count = 0;
32 while (contour) {
33 count += contour->count() > 0;
34 contour = contour->next();
35 }
36 return count;
37 }
38
finish(SkChunkAlloc * allocator)39 bool SkOpEdgeBuilder::finish(SkChunkAlloc* allocator) {
40 fOperand = false;
41 if (fUnparseable || !walk(allocator)) {
42 return false;
43 }
44 complete();
45 if (fCurrentContour && !fCurrentContour->count()) {
46 fContoursHead->remove(fCurrentContour);
47 }
48 return true;
49 }
50
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)51 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
52 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
53 *fPathVerbs.append() = SkPath::kLine_Verb;
54 *fPathPts.append() = curveStart;
55 } else {
56 fPathPts[fPathPts.count() - 1] = curveStart;
57 }
58 *fPathVerbs.append() = SkPath::kClose_Verb;
59 }
60
61 // very tiny points cause numerical instability : don't allow them
force_small_to_zero(SkPoint * pt)62 static void force_small_to_zero(SkPoint* pt) {
63 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
64 pt->fX = 0;
65 }
66 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
67 pt->fY = 0;
68 }
69 }
70
preFetch()71 int SkOpEdgeBuilder::preFetch() {
72 if (!fPath->isFinite()) {
73 fUnparseable = true;
74 return 0;
75 }
76 SkPath::RawIter iter(*fPath);
77 SkPoint curveStart;
78 SkPoint curve[4];
79 SkPoint pts[4];
80 SkPath::Verb verb;
81 bool lastCurve = false;
82 do {
83 verb = iter.next(pts);
84 switch (verb) {
85 case SkPath::kMove_Verb:
86 if (!fAllowOpenContours && lastCurve) {
87 closeContour(curve[0], curveStart);
88 }
89 *fPathVerbs.append() = verb;
90 force_small_to_zero(&pts[0]);
91 *fPathPts.append() = pts[0];
92 curveStart = curve[0] = pts[0];
93 lastCurve = false;
94 continue;
95 case SkPath::kLine_Verb:
96 force_small_to_zero(&pts[1]);
97 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
98 uint8_t lastVerb = fPathVerbs.top();
99 if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
100 fPathPts.top() = pts[1];
101 }
102 continue; // skip degenerate points
103 }
104 break;
105 case SkPath::kQuad_Verb:
106 force_small_to_zero(&pts[1]);
107 force_small_to_zero(&pts[2]);
108 curve[1] = pts[1];
109 curve[2] = pts[2];
110 verb = SkReduceOrder::Quad(curve, pts);
111 if (verb == SkPath::kMove_Verb) {
112 continue; // skip degenerate points
113 }
114 break;
115 case SkPath::kConic_Verb:
116 force_small_to_zero(&pts[1]);
117 force_small_to_zero(&pts[2]);
118 curve[1] = pts[1];
119 curve[2] = pts[2];
120 verb = SkReduceOrder::Conic(curve, iter.conicWeight(), pts);
121 if (verb == SkPath::kMove_Verb) {
122 continue; // skip degenerate points
123 }
124 break;
125 case SkPath::kCubic_Verb:
126 force_small_to_zero(&pts[1]);
127 force_small_to_zero(&pts[2]);
128 force_small_to_zero(&pts[3]);
129 curve[1] = pts[1];
130 curve[2] = pts[2];
131 curve[3] = pts[3];
132 verb = SkReduceOrder::Cubic(curve, pts);
133 if (verb == SkPath::kMove_Verb) {
134 continue; // skip degenerate points
135 }
136 break;
137 case SkPath::kClose_Verb:
138 closeContour(curve[0], curveStart);
139 lastCurve = false;
140 continue;
141 case SkPath::kDone_Verb:
142 continue;
143 }
144 *fPathVerbs.append() = verb;
145 int ptCount = SkPathOpsVerbToPoints(verb);
146 fPathPts.append(ptCount, &pts[1]);
147 if (verb == SkPath::kConic_Verb) {
148 *fWeights.append() = iter.conicWeight();
149 }
150 curve[0] = pts[ptCount];
151 lastCurve = true;
152 } while (verb != SkPath::kDone_Verb);
153 if (!fAllowOpenContours && lastCurve) {
154 closeContour(curve[0], curveStart);
155 }
156 *fPathVerbs.append() = SkPath::kDone_Verb;
157 return fPathVerbs.count() - 1;
158 }
159
close()160 bool SkOpEdgeBuilder::close() {
161 complete();
162 return true;
163 }
164
walk(SkChunkAlloc * allocator)165 bool SkOpEdgeBuilder::walk(SkChunkAlloc* allocator) {
166 uint8_t* verbPtr = fPathVerbs.begin();
167 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
168 SkPoint* pointsPtr = fPathPts.begin() - 1;
169 SkScalar* weightPtr = fWeights.begin();
170 SkPath::Verb verb;
171 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
172 if (verbPtr == endOfFirstHalf) {
173 fOperand = true;
174 }
175 verbPtr++;
176 switch (verb) {
177 case SkPath::kMove_Verb:
178 if (fCurrentContour && fCurrentContour->count()) {
179 if (fAllowOpenContours) {
180 complete();
181 } else if (!close()) {
182 return false;
183 }
184 }
185 if (!fCurrentContour) {
186 fCurrentContour = fContoursHead->appendContour(allocator);
187 }
188 fCurrentContour->init(fGlobalState, fOperand,
189 fXorMask[fOperand] == kEvenOdd_PathOpsMask);
190 pointsPtr += 1;
191 continue;
192 case SkPath::kLine_Verb:
193 fCurrentContour->addLine(pointsPtr, fAllocator);
194 break;
195 case SkPath::kQuad_Verb:
196 fCurrentContour->addQuad(pointsPtr, fAllocator);
197 break;
198 case SkPath::kConic_Verb:
199 fCurrentContour->addConic(pointsPtr, *weightPtr++, fAllocator);
200 break;
201 case SkPath::kCubic_Verb: {
202 // split self-intersecting cubics in two before proceeding
203 // if the cubic is convex, it doesn't self intersect.
204 SkScalar loopT;
205 if (SkDCubic::ComplexBreak(pointsPtr, &loopT)) {
206 SkPoint cubicPair[7];
207 SkChopCubicAt(pointsPtr, cubicPair, loopT);
208 if (!SkScalarsAreFinite(&cubicPair[0].fX, SK_ARRAY_COUNT(cubicPair) * 2)) {
209 return false;
210 }
211 SkPoint cStorage[2][4];
212 SkPath::Verb v1 = SkReduceOrder::Cubic(&cubicPair[0], cStorage[0]);
213 SkPath::Verb v2 = SkReduceOrder::Cubic(&cubicPair[3], cStorage[1]);
214 if (v1 != SkPath::kMove_Verb && v2 != SkPath::kMove_Verb) {
215 SkPoint* curve1 = v1 == SkPath::kCubic_Verb ? &cubicPair[0] : cStorage[0];
216 SkPoint* curve2 = v2 == SkPath::kCubic_Verb ? &cubicPair[3] : cStorage[1];
217 for (int index = 0; index < SkPathOpsVerbToPoints(v1); ++index) {
218 force_small_to_zero(&curve1[index]);
219 }
220 for (int index = 0; index < SkPathOpsVerbToPoints(v2); ++index) {
221 force_small_to_zero(&curve2[index]);
222 }
223 fCurrentContour->addCurve(v1, curve1, fAllocator);
224 fCurrentContour->addCurve(v2, curve2, fAllocator);
225 } else {
226 fCurrentContour->addCubic(pointsPtr, fAllocator);
227 }
228 } else {
229 fCurrentContour->addCubic(pointsPtr, fAllocator);
230 }
231 } break;
232 case SkPath::kClose_Verb:
233 SkASSERT(fCurrentContour);
234 if (!close()) {
235 return false;
236 }
237 continue;
238 default:
239 SkDEBUGFAIL("bad verb");
240 return false;
241 }
242 SkASSERT(fCurrentContour);
243 fCurrentContour->debugValidate();
244 pointsPtr += SkPathOpsVerbToPoints(verb);
245 }
246 if (fCurrentContour && fCurrentContour->count() &&!fAllowOpenContours && !close()) {
247 return false;
248 }
249 return true;
250 }
251