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