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