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