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