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 = &sub;
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