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/SkPathPriv.h"
8 #include "src/core/SkTSort.h"
9 #include "src/pathops/SkPathOpsBounds.h"
10 #include "src/pathops/SkPathOpsConic.h"
11 #include "src/pathops/SkPathOpsCubic.h"
12 #include "src/pathops/SkPathOpsLine.h"
13 #include "src/pathops/SkPathOpsQuad.h"
14 #include "src/pathops/SkPathOpsTSect.h"
15 #include "src/pathops/SkReduceOrder.h"
16 #include "tests/PathOpsTestCommon.h"
17
18 #include <utility>
19
calc_t_div(const SkDCubic & cubic,double precision,double start)20 static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
21 const double adjust = sqrt(3.) / 36;
22 SkDCubic sub;
23 const SkDCubic* cPtr;
24 if (start == 0) {
25 cPtr = &cubic;
26 } else {
27 // OPTIMIZE: special-case half-split ?
28 sub = cubic.subDivide(start, 1);
29 cPtr = ⊂
30 }
31 const SkDCubic& c = *cPtr;
32 double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
33 double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
34 double dist = sqrt(dx * dx + dy * dy);
35 double tDiv3 = precision / (adjust * dist);
36 double t = SkDCubeRoot(tDiv3);
37 if (start > 0) {
38 t = start + (1 - start) * t;
39 }
40 return t;
41 }
42
add_simple_ts(const SkDCubic & cubic,double precision,SkTArray<double,true> * ts)43 static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
44 double tDiv = calc_t_div(cubic, precision, 0);
45 if (tDiv >= 1) {
46 return true;
47 }
48 if (tDiv >= 0.5) {
49 ts->push_back(0.5);
50 return true;
51 }
52 return false;
53 }
54
addTs(const SkDCubic & cubic,double precision,double start,double end,SkTArray<double,true> * ts)55 static void addTs(const SkDCubic& cubic, double precision, double start, double end,
56 SkTArray<double, true>* ts) {
57 double tDiv = calc_t_div(cubic, precision, 0);
58 double parts = ceil(1.0 / tDiv);
59 for (double index = 0; index < parts; ++index) {
60 double newT = start + (index / parts) * (end - start);
61 if (newT > 0 && newT < 1) {
62 ts->push_back(newT);
63 }
64 }
65 }
66
toQuadraticTs(const SkDCubic * cubic,double precision,SkTArray<double,true> * ts)67 static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) {
68 SkReduceOrder reducer;
69 int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics);
70 if (order < 3) {
71 return;
72 }
73 double inflectT[5];
74 int inflections = cubic->findInflections(inflectT);
75 SkASSERT(inflections <= 2);
76 if (!cubic->endsAreExtremaInXOrY()) {
77 inflections += cubic->findMaxCurvature(&inflectT[inflections]);
78 SkASSERT(inflections <= 5);
79 }
80 SkTQSort<double>(inflectT, inflectT + inflections);
81 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
82 // own subroutine?
83 while (inflections && approximately_less_than_zero(inflectT[0])) {
84 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
85 }
86 int start = 0;
87 int next = 1;
88 while (next < inflections) {
89 if (!approximately_equal(inflectT[start], inflectT[next])) {
90 ++start;
91 ++next;
92 continue;
93 }
94 memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
95 }
96
97 while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
98 --inflections;
99 }
100 SkDCubicPair pair;
101 if (inflections == 1) {
102 pair = cubic->chopAt(inflectT[0]);
103 int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
104 if (orderP1 < 2) {
105 --inflections;
106 } else {
107 int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
108 if (orderP2 < 2) {
109 --inflections;
110 }
111 }
112 }
113 if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) {
114 return;
115 }
116 if (inflections == 1) {
117 pair = cubic->chopAt(inflectT[0]);
118 addTs(pair.first(), precision, 0, inflectT[0], ts);
119 addTs(pair.second(), precision, inflectT[0], 1, ts);
120 return;
121 }
122 if (inflections > 1) {
123 SkDCubic part = cubic->subDivide(0, inflectT[0]);
124 addTs(part, precision, 0, inflectT[0], ts);
125 int last = inflections - 1;
126 for (int idx = 0; idx < last; ++idx) {
127 part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]);
128 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
129 }
130 part = cubic->subDivide(inflectT[last], 1);
131 addTs(part, precision, inflectT[last], 1, ts);
132 return;
133 }
134 addTs(*cubic, precision, 0, 1, ts);
135 }
136
CubicToQuads(const SkDCubic & cubic,double precision,SkTArray<SkDQuad,true> & quads)137 void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) {
138 SkTArray<double, true> ts;
139 toQuadraticTs(&cubic, precision, &ts);
140 if (ts.count() <= 0) {
141 SkDQuad quad = cubic.toQuad();
142 quads.push_back(quad);
143 return;
144 }
145 double tStart = 0;
146 for (int i1 = 0; i1 <= ts.count(); ++i1) {
147 const double tEnd = i1 < ts.count() ? ts[i1] : 1;
148 SkDRect bounds;
149 bounds.setBounds(cubic);
150 SkDCubic part = cubic.subDivide(tStart, tEnd);
151 SkDQuad quad = part.toQuad();
152 if (quad[1].fX < bounds.fLeft) {
153 quad[1].fX = bounds.fLeft;
154 } else if (quad[1].fX > bounds.fRight) {
155 quad[1].fX = bounds.fRight;
156 }
157 if (quad[1].fY < bounds.fTop) {
158 quad[1].fY = bounds.fTop;
159 } else if (quad[1].fY > bounds.fBottom) {
160 quad[1].fY = bounds.fBottom;
161 }
162 quads.push_back(quad);
163 tStart = tEnd;
164 }
165 }
166
CubicPathToQuads(const SkPath & cubicPath,SkPath * quadPath)167 void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
168 quadPath->reset();
169 SkDCubic cubic;
170 SkTArray<SkDQuad, true> quads;
171 for (auto [verb, pts, w] : SkPathPriv::Iterate(cubicPath)) {
172 switch (verb) {
173 case SkPathVerb::kMove:
174 quadPath->moveTo(pts[0].fX, pts[0].fY);
175 continue;
176 case SkPathVerb::kLine:
177 quadPath->lineTo(pts[1].fX, pts[1].fY);
178 break;
179 case SkPathVerb::kQuad:
180 quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
181 break;
182 case SkPathVerb::kCubic:
183 quads.reset();
184 cubic.set(pts);
185 CubicToQuads(cubic, cubic.calcPrecision(), quads);
186 for (int index = 0; index < quads.count(); ++index) {
187 SkPoint qPts[2] = {
188 quads[index][1].asSkPoint(),
189 quads[index][2].asSkPoint()
190 };
191 quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY);
192 }
193 break;
194 case SkPathVerb::kClose:
195 quadPath->close();
196 break;
197 default:
198 SkDEBUGFAIL("bad verb");
199 return;
200 }
201 }
202 }
203
CubicPathToSimple(const SkPath & cubicPath,SkPath * simplePath)204 void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) {
205 simplePath->reset();
206 SkDCubic cubic;
207 for (auto [verb, pts, w] : SkPathPriv::Iterate(cubicPath)) {
208 switch (verb) {
209 case SkPathVerb::kMove:
210 simplePath->moveTo(pts[0].fX, pts[0].fY);
211 continue;
212 case SkPathVerb::kLine:
213 simplePath->lineTo(pts[1].fX, pts[1].fY);
214 break;
215 case SkPathVerb::kQuad:
216 simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
217 break;
218 case SkPathVerb::kCubic: {
219 cubic.set(pts);
220 double tInflects[2];
221 int inflections = cubic.findInflections(tInflects);
222 if (inflections > 1 && tInflects[0] > tInflects[1]) {
223 using std::swap;
224 swap(tInflects[0], tInflects[1]);
225 }
226 double lo = 0;
227 for (int index = 0; index <= inflections; ++index) {
228 double hi = index < inflections ? tInflects[index] : 1;
229 SkDCubic part = cubic.subDivide(lo, hi);
230 SkPoint cPts[3];
231 cPts[0] = part[1].asSkPoint();
232 cPts[1] = part[2].asSkPoint();
233 cPts[2] = part[3].asSkPoint();
234 simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY,
235 cPts[2].fX, cPts[2].fY);
236 lo = hi;
237 }
238 break;
239 }
240 case SkPathVerb::kClose:
241 simplePath->close();
242 break;
243 default:
244 SkDEBUGFAIL("bad verb");
245 return;
246 }
247 }
248 }
249
ValidBounds(const SkPathOpsBounds & bounds)250 bool ValidBounds(const SkPathOpsBounds& bounds) {
251 if (SkScalarIsNaN(bounds.fLeft)) {
252 return false;
253 }
254 if (SkScalarIsNaN(bounds.fTop)) {
255 return false;
256 }
257 if (SkScalarIsNaN(bounds.fRight)) {
258 return false;
259 }
260 return !SkScalarIsNaN(bounds.fBottom);
261 }
262
ValidConic(const SkDConic & conic)263 bool ValidConic(const SkDConic& conic) {
264 for (int index = 0; index < SkDConic::kPointCount; ++index) {
265 if (!ValidPoint(conic[index])) {
266 return false;
267 }
268 }
269 if (SkDoubleIsNaN(conic.fWeight)) {
270 return false;
271 }
272 return true;
273 }
274
ValidCubic(const SkDCubic & cubic)275 bool ValidCubic(const SkDCubic& cubic) {
276 for (int index = 0; index < 4; ++index) {
277 if (!ValidPoint(cubic[index])) {
278 return false;
279 }
280 }
281 return true;
282 }
283
ValidLine(const SkDLine & line)284 bool ValidLine(const SkDLine& line) {
285 for (int index = 0; index < 2; ++index) {
286 if (!ValidPoint(line[index])) {
287 return false;
288 }
289 }
290 return true;
291 }
292
ValidPoint(const SkDPoint & pt)293 bool ValidPoint(const SkDPoint& pt) {
294 if (SkDoubleIsNaN(pt.fX)) {
295 return false;
296 }
297 return !SkDoubleIsNaN(pt.fY);
298 }
299
ValidPoints(const SkPoint * pts,int count)300 bool ValidPoints(const SkPoint* pts, int count) {
301 for (int index = 0; index < count; ++index) {
302 if (SkScalarIsNaN(pts[index].fX)) {
303 return false;
304 }
305 if (SkScalarIsNaN(pts[index].fY)) {
306 return false;
307 }
308 }
309 return true;
310 }
311
ValidQuad(const SkDQuad & quad)312 bool ValidQuad(const SkDQuad& quad) {
313 for (int index = 0; index < 3; ++index) {
314 if (!ValidPoint(quad[index])) {
315 return false;
316 }
317 }
318 return true;
319 }
320
ValidVector(const SkDVector & v)321 bool ValidVector(const SkDVector& v) {
322 if (SkDoubleIsNaN(v.fX)) {
323 return false;
324 }
325 return !SkDoubleIsNaN(v.fY);
326 }
327