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