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