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 fOperand = false;
13 fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
14 : kWinding_PathOpsMask;
15 fUnparseable = false;
16 fSecondHalf = preFetch();
17 }
18
19 // very tiny points cause numerical instability : don't allow them
force_small_to_zero(SkPoint * pt)20 static void force_small_to_zero(SkPoint* pt) {
21 if (SkScalarAbs(pt->fX) < FLT_EPSILON_ORDERABLE_ERR) {
22 pt->fX = 0;
23 }
24 if (SkScalarAbs(pt->fY) < FLT_EPSILON_ORDERABLE_ERR) {
25 pt->fY = 0;
26 }
27 }
28
can_add_curve(SkPath::Verb verb,SkPoint * curve)29 static bool can_add_curve(SkPath::Verb verb, SkPoint* curve) {
30 if (SkPath::kMove_Verb == verb) {
31 return false;
32 }
33 for (int index = 0; index <= SkPathOpsVerbToPoints(verb); ++index) {
34 force_small_to_zero(&curve[index]);
35 }
36 return SkPath::kLine_Verb != verb || !SkDPoint::ApproximatelyEqual(curve[0], curve[1]);
37 }
38
addOperand(const SkPath & path)39 void SkOpEdgeBuilder::addOperand(const SkPath& path) {
40 SkASSERT(fPathVerbs.count() > 0 && fPathVerbs.end()[-1] == SkPath::kDone_Verb);
41 fPathVerbs.pop();
42 fPath = &path;
43 fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
44 : kWinding_PathOpsMask;
45 preFetch();
46 }
47
finish()48 bool SkOpEdgeBuilder::finish() {
49 fOperand = false;
50 if (fUnparseable || !walk()) {
51 return false;
52 }
53 complete();
54 SkOpContour* contour = fContourBuilder.contour();
55 if (contour && !contour->count()) {
56 fContoursHead->remove(contour);
57 }
58 return true;
59 }
60
closeContour(const SkPoint & curveEnd,const SkPoint & curveStart)61 void SkOpEdgeBuilder::closeContour(const SkPoint& curveEnd, const SkPoint& curveStart) {
62 if (!SkDPoint::ApproximatelyEqual(curveEnd, curveStart)) {
63 *fPathVerbs.append() = SkPath::kLine_Verb;
64 *fPathPts.append() = curveStart;
65 } else {
66 int verbCount = fPathVerbs.count();
67 int ptsCount = fPathPts.count();
68 if (SkPath::kLine_Verb == fPathVerbs[verbCount - 1]
69 && fPathPts[ptsCount - 2] == curveStart) {
70 fPathVerbs.pop();
71 fPathPts.pop();
72 } else {
73 fPathPts[ptsCount - 1] = curveStart;
74 }
75 }
76 *fPathVerbs.append() = SkPath::kClose_Verb;
77 }
78
preFetch()79 int SkOpEdgeBuilder::preFetch() {
80 if (!fPath->isFinite()) {
81 fUnparseable = true;
82 return 0;
83 }
84 SkPath::RawIter iter(*fPath);
85 SkPoint curveStart;
86 SkPoint curve[4];
87 SkPoint pts[4];
88 SkPath::Verb verb;
89 bool lastCurve = false;
90 do {
91 verb = iter.next(pts);
92 switch (verb) {
93 case SkPath::kMove_Verb:
94 if (!fAllowOpenContours && lastCurve) {
95 closeContour(curve[0], curveStart);
96 }
97 *fPathVerbs.append() = verb;
98 force_small_to_zero(&pts[0]);
99 *fPathPts.append() = pts[0];
100 curveStart = curve[0] = pts[0];
101 lastCurve = false;
102 continue;
103 case SkPath::kLine_Verb:
104 force_small_to_zero(&pts[1]);
105 if (SkDPoint::ApproximatelyEqual(curve[0], pts[1])) {
106 uint8_t lastVerb = fPathVerbs.top();
107 if (lastVerb != SkPath::kLine_Verb && lastVerb != SkPath::kMove_Verb) {
108 fPathPts.top() = curve[0] = pts[1];
109 }
110 continue; // skip degenerate points
111 }
112 break;
113 case SkPath::kQuad_Verb:
114 force_small_to_zero(&pts[1]);
115 force_small_to_zero(&pts[2]);
116 curve[1] = pts[1];
117 curve[2] = pts[2];
118 verb = SkReduceOrder::Quad(curve, pts);
119 if (verb == SkPath::kMove_Verb) {
120 continue; // skip degenerate points
121 }
122 break;
123 case SkPath::kConic_Verb:
124 force_small_to_zero(&pts[1]);
125 force_small_to_zero(&pts[2]);
126 curve[1] = pts[1];
127 curve[2] = pts[2];
128 verb = SkReduceOrder::Quad(curve, pts);
129 if (SkPath::kQuad_Verb == verb && 1 != iter.conicWeight()) {
130 verb = SkPath::kConic_Verb;
131 } else if (verb == SkPath::kMove_Verb) {
132 continue; // skip degenerate points
133 }
134 break;
135 case SkPath::kCubic_Verb:
136 force_small_to_zero(&pts[1]);
137 force_small_to_zero(&pts[2]);
138 force_small_to_zero(&pts[3]);
139 curve[1] = pts[1];
140 curve[2] = pts[2];
141 curve[3] = pts[3];
142 verb = SkReduceOrder::Cubic(curve, pts);
143 if (verb == SkPath::kMove_Verb) {
144 continue; // skip degenerate points
145 }
146 break;
147 case SkPath::kClose_Verb:
148 closeContour(curve[0], curveStart);
149 lastCurve = false;
150 continue;
151 case SkPath::kDone_Verb:
152 continue;
153 }
154 *fPathVerbs.append() = verb;
155 int ptCount = SkPathOpsVerbToPoints(verb);
156 fPathPts.append(ptCount, &pts[1]);
157 if (verb == SkPath::kConic_Verb) {
158 *fWeights.append() = iter.conicWeight();
159 }
160 curve[0] = pts[ptCount];
161 lastCurve = true;
162 } while (verb != SkPath::kDone_Verb);
163 if (!fAllowOpenContours && lastCurve) {
164 closeContour(curve[0], curveStart);
165 }
166 *fPathVerbs.append() = SkPath::kDone_Verb;
167 return fPathVerbs.count() - 1;
168 }
169
close()170 bool SkOpEdgeBuilder::close() {
171 complete();
172 return true;
173 }
174
walk()175 bool SkOpEdgeBuilder::walk() {
176 uint8_t* verbPtr = fPathVerbs.begin();
177 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
178 SkPoint* pointsPtr = fPathPts.begin() - 1;
179 SkScalar* weightPtr = fWeights.begin();
180 SkPath::Verb verb;
181 SkOpContour* contour = fContourBuilder.contour();
182 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
183 if (verbPtr == endOfFirstHalf) {
184 fOperand = true;
185 }
186 verbPtr++;
187 switch (verb) {
188 case SkPath::kMove_Verb:
189 if (contour && contour->count()) {
190 if (fAllowOpenContours) {
191 complete();
192 } else if (!close()) {
193 return false;
194 }
195 }
196 if (!contour) {
197 fContourBuilder.setContour(contour = fContoursHead->appendContour());
198 }
199 contour->init(fGlobalState, fOperand,
200 fXorMask[fOperand] == kEvenOdd_PathOpsMask);
201 pointsPtr += 1;
202 continue;
203 case SkPath::kLine_Verb:
204 fContourBuilder.addLine(pointsPtr);
205 break;
206 case SkPath::kQuad_Verb:
207 {
208 SkVector v1 = pointsPtr[1] - pointsPtr[0];
209 SkVector v2 = pointsPtr[2] - pointsPtr[1];
210 if (v1.dot(v2) < 0) {
211 SkPoint pair[5];
212 if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
213 goto addOneQuad;
214 }
215 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
216 return false;
217 }
218 for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) {
219 force_small_to_zero(&pair[index]);
220 }
221 SkPoint cStorage[2][2];
222 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
223 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
224 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
225 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
226 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
227 fContourBuilder.addCurve(v1, curve1);
228 fContourBuilder.addCurve(v2, curve2);
229 break;
230 }
231 }
232 }
233 addOneQuad:
234 fContourBuilder.addQuad(pointsPtr);
235 break;
236 case SkPath::kConic_Verb: {
237 SkVector v1 = pointsPtr[1] - pointsPtr[0];
238 SkVector v2 = pointsPtr[2] - pointsPtr[1];
239 SkScalar weight = *weightPtr++;
240 if (v1.dot(v2) < 0) {
241 // FIXME: max curvature for conics hasn't been implemented; use placeholder
242 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
243 if (maxCurvature > 0) {
244 SkConic conic(pointsPtr, weight);
245 SkConic pair[2];
246 if (!conic.chopAt(maxCurvature, pair)) {
247 // if result can't be computed, use original
248 fContourBuilder.addConic(pointsPtr, weight);
249 break;
250 }
251 SkPoint cStorage[2][3];
252 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
253 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
254 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
255 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
256 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
257 fContourBuilder.addCurve(v1, curve1, pair[0].fW);
258 fContourBuilder.addCurve(v2, curve2, pair[1].fW);
259 break;
260 }
261 }
262 }
263 fContourBuilder.addConic(pointsPtr, weight);
264 } break;
265 case SkPath::kCubic_Verb:
266 {
267 // Split complex cubics (such as self-intersecting curves or
268 // ones with difficult curvature) in two before proceeding.
269 // This can be required for intersection to succeed.
270 SkScalar splitT[3];
271 int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
272 if (!breaks) {
273 fContourBuilder.addCubic(pointsPtr);
274 break;
275 }
276 SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
277 struct Splitsville {
278 double fT[2];
279 SkPoint fPts[4];
280 SkPoint fReduced[4];
281 SkPath::Verb fVerb;
282 bool fCanAdd;
283 } splits[4];
284 SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
285 SkTQSort(splitT, &splitT[breaks - 1]);
286 for (int index = 0; index <= breaks; ++index) {
287 Splitsville* split = &splits[index];
288 split->fT[0] = index ? splitT[index - 1] : 0;
289 split->fT[1] = index < breaks ? splitT[index] : 1;
290 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
291 if (!part.toFloatPoints(split->fPts)) {
292 return false;
293 }
294 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
295 SkPoint* curve = SkPath::kCubic_Verb == verb
296 ? split->fPts : split->fReduced;
297 split->fCanAdd = can_add_curve(split->fVerb, curve);
298 }
299 for (int index = 0; index <= breaks; ++index) {
300 Splitsville* split = &splits[index];
301 if (!split->fCanAdd) {
302 continue;
303 }
304 int prior = index;
305 while (prior > 0 && !splits[prior - 1].fCanAdd) {
306 --prior;
307 }
308 if (prior < index) {
309 split->fT[0] = splits[prior].fT[0];
310 split->fPts[0] = splits[prior].fPts[0];
311 }
312 int next = index;
313 int breakLimit = SkTMin(breaks, (int) SK_ARRAY_COUNT(splits) - 1);
314 while (next < breakLimit && !splits[next + 1].fCanAdd) {
315 ++next;
316 }
317 if (next > index) {
318 split->fT[1] = splits[next].fT[1];
319 split->fPts[3] = splits[next].fPts[3];
320 }
321 if (prior < index || next > index) {
322 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
323 }
324 SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
325 ? split->fPts : split->fReduced;
326 SkAssertResult(can_add_curve(split->fVerb, curve));
327 fContourBuilder.addCurve(split->fVerb, curve);
328 }
329 }
330 break;
331 case SkPath::kClose_Verb:
332 SkASSERT(contour);
333 if (!close()) {
334 return false;
335 }
336 contour = nullptr;
337 continue;
338 default:
339 SkDEBUGFAIL("bad verb");
340 return false;
341 }
342 SkASSERT(contour);
343 if (contour->count()) {
344 contour->debugValidate();
345 }
346 pointsPtr += SkPathOpsVerbToPoints(verb);
347 }
348 fContourBuilder.flush();
349 if (contour && contour->count() &&!fAllowOpenContours && !close()) {
350 return false;
351 }
352 return true;
353 }
354