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 "SkReduceOrder.h"
14 #include "SkTSort.h"
15
calc_t_div(const SkDCubic & cubic,double precision,double start)16 static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
17 const double adjust = sqrt(3.) / 36;
18 SkDCubic sub;
19 const SkDCubic* cPtr;
20 if (start == 0) {
21 cPtr = &cubic;
22 } else {
23 // OPTIMIZE: special-case half-split ?
24 sub = cubic.subDivide(start, 1);
25 cPtr = ⊂
26 }
27 const SkDCubic& c = *cPtr;
28 double dx = c[3].fX - 3 * (c[2].fX - c[1].fX) - c[0].fX;
29 double dy = c[3].fY - 3 * (c[2].fY - c[1].fY) - c[0].fY;
30 double dist = sqrt(dx * dx + dy * dy);
31 double tDiv3 = precision / (adjust * dist);
32 double t = SkDCubeRoot(tDiv3);
33 if (start > 0) {
34 t = start + (1 - start) * t;
35 }
36 return t;
37 }
38
add_simple_ts(const SkDCubic & cubic,double precision,SkTArray<double,true> * ts)39 static bool add_simple_ts(const SkDCubic& cubic, double precision, SkTArray<double, true>* ts) {
40 double tDiv = calc_t_div(cubic, precision, 0);
41 if (tDiv >= 1) {
42 return true;
43 }
44 if (tDiv >= 0.5) {
45 ts->push_back(0.5);
46 return true;
47 }
48 return false;
49 }
50
addTs(const SkDCubic & cubic,double precision,double start,double end,SkTArray<double,true> * ts)51 static void addTs(const SkDCubic& cubic, double precision, double start, double end,
52 SkTArray<double, true>* ts) {
53 double tDiv = calc_t_div(cubic, precision, 0);
54 double parts = ceil(1.0 / tDiv);
55 for (double index = 0; index < parts; ++index) {
56 double newT = start + (index / parts) * (end - start);
57 if (newT > 0 && newT < 1) {
58 ts->push_back(newT);
59 }
60 }
61 }
62
toQuadraticTs(const SkDCubic * cubic,double precision,SkTArray<double,true> * ts)63 static void toQuadraticTs(const SkDCubic* cubic, double precision, SkTArray<double, true>* ts) {
64 SkReduceOrder reducer;
65 int order = reducer.reduce(*cubic, SkReduceOrder::kAllow_Quadratics);
66 if (order < 3) {
67 return;
68 }
69 double inflectT[5];
70 int inflections = cubic->findInflections(inflectT);
71 SkASSERT(inflections <= 2);
72 if (!cubic->endsAreExtremaInXOrY()) {
73 inflections += cubic->findMaxCurvature(&inflectT[inflections]);
74 SkASSERT(inflections <= 5);
75 }
76 SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
77 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
78 // own subroutine?
79 while (inflections && approximately_less_than_zero(inflectT[0])) {
80 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
81 }
82 int start = 0;
83 int next = 1;
84 while (next < inflections) {
85 if (!approximately_equal(inflectT[start], inflectT[next])) {
86 ++start;
87 ++next;
88 continue;
89 }
90 memmove(&inflectT[start], &inflectT[next], sizeof(inflectT[0]) * (--inflections - start));
91 }
92
93 while (inflections && approximately_greater_than_one(inflectT[inflections - 1])) {
94 --inflections;
95 }
96 SkDCubicPair pair;
97 if (inflections == 1) {
98 pair = cubic->chopAt(inflectT[0]);
99 int orderP1 = reducer.reduce(pair.first(), SkReduceOrder::kNo_Quadratics);
100 if (orderP1 < 2) {
101 --inflections;
102 } else {
103 int orderP2 = reducer.reduce(pair.second(), SkReduceOrder::kNo_Quadratics);
104 if (orderP2 < 2) {
105 --inflections;
106 }
107 }
108 }
109 if (inflections == 0 && add_simple_ts(*cubic, precision, ts)) {
110 return;
111 }
112 if (inflections == 1) {
113 pair = cubic->chopAt(inflectT[0]);
114 addTs(pair.first(), precision, 0, inflectT[0], ts);
115 addTs(pair.second(), precision, inflectT[0], 1, ts);
116 return;
117 }
118 if (inflections > 1) {
119 SkDCubic part = cubic->subDivide(0, inflectT[0]);
120 addTs(part, precision, 0, inflectT[0], ts);
121 int last = inflections - 1;
122 for (int idx = 0; idx < last; ++idx) {
123 part = cubic->subDivide(inflectT[idx], inflectT[idx + 1]);
124 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
125 }
126 part = cubic->subDivide(inflectT[last], 1);
127 addTs(part, precision, inflectT[last], 1, ts);
128 return;
129 }
130 addTs(*cubic, precision, 0, 1, ts);
131 }
132
CubicToQuads(const SkDCubic & cubic,double precision,SkTArray<SkDQuad,true> & quads)133 void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, true>& quads) {
134 SkTArray<double, true> ts;
135 toQuadraticTs(&cubic, precision, &ts);
136 if (ts.count() <= 0) {
137 SkDQuad quad = cubic.toQuad();
138 quads.push_back(quad);
139 return;
140 }
141 double tStart = 0;
142 for (int i1 = 0; i1 <= ts.count(); ++i1) {
143 const double tEnd = i1 < ts.count() ? ts[i1] : 1;
144 SkDRect bounds;
145 bounds.setBounds(cubic);
146 SkDCubic part = cubic.subDivide(tStart, tEnd);
147 SkDQuad quad = part.toQuad();
148 if (quad[1].fX < bounds.fLeft) {
149 quad[1].fX = bounds.fLeft;
150 } else if (quad[1].fX > bounds.fRight) {
151 quad[1].fX = bounds.fRight;
152 }
153 if (quad[1].fY < bounds.fTop) {
154 quad[1].fY = bounds.fTop;
155 } else if (quad[1].fY > bounds.fBottom) {
156 quad[1].fY = bounds.fBottom;
157 }
158 quads.push_back(quad);
159 tStart = tEnd;
160 }
161 }
162
CubicPathToQuads(const SkPath & cubicPath,SkPath * quadPath)163 void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
164 quadPath->reset();
165 SkDCubic cubic;
166 SkTArray<SkDQuad, true> quads;
167 SkPath::RawIter iter(cubicPath);
168 uint8_t verb;
169 SkPoint pts[4];
170 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
171 switch (verb) {
172 case SkPath::kMove_Verb:
173 quadPath->moveTo(pts[0].fX, pts[0].fY);
174 continue;
175 case SkPath::kLine_Verb:
176 quadPath->lineTo(pts[1].fX, pts[1].fY);
177 break;
178 case SkPath::kQuad_Verb:
179 quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
180 break;
181 case SkPath::kCubic_Verb:
182 quads.reset();
183 cubic.set(pts);
184 CubicToQuads(cubic, cubic.calcPrecision(), quads);
185 for (int index = 0; index < quads.count(); ++index) {
186 SkPoint qPts[2] = {
187 quads[index][1].asSkPoint(),
188 quads[index][2].asSkPoint()
189 };
190 quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY);
191 }
192 break;
193 case SkPath::kClose_Verb:
194 quadPath->close();
195 break;
196 default:
197 SkDEBUGFAIL("bad verb");
198 return;
199 }
200 }
201 }
202
CubicPathToSimple(const SkPath & cubicPath,SkPath * simplePath)203 void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) {
204 simplePath->reset();
205 SkDCubic cubic;
206 SkPath::RawIter iter(cubicPath);
207 uint8_t verb;
208 SkPoint pts[4];
209 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
210 switch (verb) {
211 case SkPath::kMove_Verb:
212 simplePath->moveTo(pts[0].fX, pts[0].fY);
213 continue;
214 case SkPath::kLine_Verb:
215 simplePath->lineTo(pts[1].fX, pts[1].fY);
216 break;
217 case SkPath::kQuad_Verb:
218 simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
219 break;
220 case SkPath::kCubic_Verb: {
221 cubic.set(pts);
222 double tInflects[2];
223 int inflections = cubic.findInflections(tInflects);
224 if (inflections > 1 && tInflects[0] > tInflects[1]) {
225 SkTSwap(tInflects[0], tInflects[1]);
226 }
227 double lo = 0;
228 for (int index = 0; index <= inflections; ++index) {
229 double hi = index < inflections ? tInflects[index] : 1;
230 SkDCubic part = cubic.subDivide(lo, hi);
231 SkPoint cPts[3];
232 cPts[0] = part[1].asSkPoint();
233 cPts[1] = part[2].asSkPoint();
234 cPts[2] = part[3].asSkPoint();
235 simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY,
236 cPts[2].fX, cPts[2].fY);
237 lo = hi;
238 }
239 break;
240 }
241 case SkPath::kClose_Verb:
242 simplePath->close();
243 break;
244 default:
245 SkDEBUGFAIL("bad verb");
246 return;
247 }
248 }
249 }
250
SkDoubleIsNaN(double x)251 static bool SkDoubleIsNaN(double x) {
252 return x != x;
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