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 "src/core/SkGeometry.h"
8#include "src/pathops/SkOpEdgeBuilder.h"
9#include "src/pathops/SkReduceOrder.h"
10
11void SkOpEdgeBuilder::init() {
12 fOperand = false;
13 fXorMask[0] = fXorMask[1] = ((int)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
20static 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
29static 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
39void 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] = ((int)fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
44 : kWinding_PathOpsMask;
45 preFetch();
46}
47
48bool 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
61void 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
79int 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
170bool SkOpEdgeBuilder::close() {
171 complete();
172 return true;
173}
174
175bool SkOpEdgeBuilder::walk() {
176 uint8_t* verbPtr = fPathVerbs.begin();
177 uint8_t* endOfFirstHalf = &verbPtr[fSecondHalf];
178 SkPoint* pointsPtr = fPathPts.begin();
179 SkScalar* weightPtr = fWeights.begin();
180 SkPath::Verb verb;
181 SkOpContour* contour = fContourBuilder.contour();
182 int moveToPtrBump = 0;
183 while ((verb = (SkPath::Verb) *verbPtr) != SkPath::kDone_Verb) {
184 if (verbPtr == endOfFirstHalf) {
185 fOperand = true;
186 }
187 verbPtr++;
188 switch (verb) {
189 case SkPath::kMove_Verb:
190 if (contour && contour->count()) {
191 if (fAllowOpenContours) {
192 complete();
193 } else if (!close()) {
194 return false;
195 }
196 }
197 if (!contour) {
198 fContourBuilder.setContour(contour = fContoursHead->appendContour());
199 }
200 contour->init(fGlobalState, fOperand,
201 fXorMask[fOperand] == kEvenOdd_PathOpsMask);
202 pointsPtr += moveToPtrBump;
203 moveToPtrBump = 1;
204 continue;
205 case SkPath::kLine_Verb:
206 fContourBuilder.addLine(pointsPtr);
207 break;
208 case SkPath::kQuad_Verb:
209 {
210 SkVector v1 = pointsPtr[1] - pointsPtr[0];
211 SkVector v2 = pointsPtr[2] - pointsPtr[1];
212 if (v1.dot(v2) < 0) {
213 SkPoint pair[5];
214 if (SkChopQuadAtMaxCurvature(pointsPtr, pair) == 1) {
215 goto addOneQuad;
216 }
217 if (!SkScalarsAreFinite(&pair[0].fX, SK_ARRAY_COUNT(pair) * 2)) {
218 return false;
219 }
220 for (unsigned index = 0; index < SK_ARRAY_COUNT(pair); ++index) {
221 force_small_to_zero(&pair[index]);
222 }
223 SkPoint cStorage[2][2];
224 SkPath::Verb v1 = SkReduceOrder::Quad(&pair[0], cStorage[0]);
225 SkPath::Verb v2 = SkReduceOrder::Quad(&pair[2], cStorage[1]);
226 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? &pair[0] : cStorage[0];
227 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? &pair[2] : cStorage[1];
228 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
229 fContourBuilder.addCurve(v1, curve1);
230 fContourBuilder.addCurve(v2, curve2);
231 break;
232 }
233 }
234 }
235 addOneQuad:
236 fContourBuilder.addQuad(pointsPtr);
237 break;
238 case SkPath::kConic_Verb: {
239 SkVector v1 = pointsPtr[1] - pointsPtr[0];
240 SkVector v2 = pointsPtr[2] - pointsPtr[1];
241 SkScalar weight = *weightPtr++;
242 if (v1.dot(v2) < 0) {
243 // FIXME: max curvature for conics hasn't been implemented; use placeholder
244 SkScalar maxCurvature = SkFindQuadMaxCurvature(pointsPtr);
245 if (0 < maxCurvature && maxCurvature < 1) {
246 SkConic conic(pointsPtr, weight);
247 SkConic pair[2];
248 if (!conic.chopAt(maxCurvature, pair)) {
249 // if result can't be computed, use original
250 fContourBuilder.addConic(pointsPtr, weight);
251 break;
252 }
253 SkPoint cStorage[2][3];
254 SkPath::Verb v1 = SkReduceOrder::Conic(pair[0], cStorage[0]);
255 SkPath::Verb v2 = SkReduceOrder::Conic(pair[1], cStorage[1]);
256 SkPoint* curve1 = v1 != SkPath::kLine_Verb ? pair[0].fPts : cStorage[0];
257 SkPoint* curve2 = v2 != SkPath::kLine_Verb ? pair[1].fPts : cStorage[1];
258 if (can_add_curve(v1, curve1) && can_add_curve(v2, curve2)) {
259 fContourBuilder.addCurve(v1, curve1, pair[0].fW);
260 fContourBuilder.addCurve(v2, curve2, pair[1].fW);
261 break;
262 }
263 }
264 }
265 fContourBuilder.addConic(pointsPtr, weight);
266 } break;
267 case SkPath::kCubic_Verb:
268 {
269 // Split complex cubics (such as self-intersecting curves or
270 // ones with difficult curvature) in two before proceeding.
271 // This can be required for intersection to succeed.
272 SkScalar splitT[3];
273 int breaks = SkDCubic::ComplexBreak(pointsPtr, splitT);
274 if (!breaks) {
275 fContourBuilder.addCubic(pointsPtr);
276 break;
277 }
278 SkASSERT(breaks <= (int) SK_ARRAY_COUNT(splitT));
279 struct Splitsville {
280 double fT[2];
281 SkPoint fPts[4];
282 SkPoint fReduced[4];
283 SkPath::Verb fVerb;
284 bool fCanAdd;
285 } splits[4];
286 SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
287 SkTQSort(splitT, &splitT[breaks - 1]);
288 for (int index = 0; index <= breaks; ++index) {
289 Splitsville* split = &splits[index];
290 split->fT[0] = index ? splitT[index - 1] : 0;
291 split->fT[1] = index < breaks ? splitT[index] : 1;
292 SkDCubic part = SkDCubic::SubDivide(pointsPtr, split->fT[0], split->fT[1]);
293 if (!part.toFloatPoints(split->fPts)) {
294 return false;
295 }
296 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
297 SkPoint* curve = SkPath::kCubic_Verb == verb
298 ? split->fPts : split->fReduced;
299 split->fCanAdd = can_add_curve(split->fVerb, curve);
300 }
301 for (int index = 0; index <= breaks; ++index) {
302 Splitsville* split = &splits[index];
303 if (!split->fCanAdd) {
304 continue;
305 }
306 int prior = index;
307 while (prior > 0 && !splits[prior - 1].fCanAdd) {
308 --prior;
309 }
310 if (prior < index) {
311 split->fT[0] = splits[prior].fT[0];
312 split->fPts[0] = splits[prior].fPts[0];
313 }
314 int next = index;
315 int breakLimit = std::min(breaks, (int) SK_ARRAY_COUNT(splits) - 1);
316 while (next < breakLimit && !splits[next + 1].fCanAdd) {
317 ++next;
318 }
319 if (next > index) {
320 split->fT[1] = splits[next].fT[1];
321 split->fPts[3] = splits[next].fPts[3];
322 }
323 if (prior < index || next > index) {
324 split->fVerb = SkReduceOrder::Cubic(split->fPts, split->fReduced);
325 }
326 SkPoint* curve = SkPath::kCubic_Verb == split->fVerb
327 ? split->fPts : split->fReduced;
328 if (!can_add_curve(split->fVerb, curve)) {
329 return false;
330 }
331 fContourBuilder.addCurve(split->fVerb, curve);
332 }
333 }
334 break;
335 case SkPath::kClose_Verb:
336 SkASSERT(contour);
337 if (!close()) {
338 return false;
339 }
340 contour = nullptr;
341 continue;
342 default:
343 SkDEBUGFAIL("bad verb");
344 return false;
345 }
346 SkASSERT(contour);
347 if (contour->count()) {
348 contour->debugValidate();
349 }
350 pointsPtr += SkPathOpsVerbToPoints(verb);
351 }
352 fContourBuilder.flush();
353 if (contour && contour->count() &&!fAllowOpenContours && !close()) {
354 return false;
355 }
356 return true;
357}
358