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