Flutter Engine
The Flutter Engine
Classes | Functions | Variables
PathOpsCubicLineIntersectionIdeas.cpp File Reference
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "src/base/SkRandom.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "tests/PathOpsTestCommon.h"
#include "tests/Test.h"
#include <algorithm>
#include <array>
#include <cmath>

Go to the source code of this file.

Classes

struct  CubicLineFailures
 

Functions

static double binary_search (const SkDCubic &cubic, double step, const SkDPoint &pt, double t, int *iters)
 
 DEF_TEST (PathOpsCubicLineRoots, reporter)
 
static double testOneFailure (const CubicLineFailures &failure)
 
 DEF_TEST (PathOpsCubicLineFailures, reporter)
 
 DEF_TEST (PathOpsCubicLineOneFailure, reporter)
 

Variables

static bool gPathOpsCubicLineIntersectionIdeasVerbose = false
 
static struct CubicLineFailures cubicLineFailures []
 
int cubicLineFailuresCount = (int) std::size(cubicLineFailures)
 
double measuredSteps []
 

Function Documentation

◆ binary_search()

static double binary_search ( const SkDCubic &  cubic,
double  step,
const SkDPoint &  pt,
double  t,
int *  iters 
)
static

Definition at line 58 of file PathOpsCubicLineIntersectionIdeas.cpp.

59 {
60 double firstStep = step;
61 do {
62 *iters += 1;
63 SkDPoint cubicAtT = cubic.ptAtT(t);
64 if (cubicAtT.approximatelyEqual(pt)) {
65 break;
66 }
67 double calcX = cubicAtT.fX - pt.fX;
68 double calcY = cubicAtT.fY - pt.fY;
69 double calcDist = calcX * calcX + calcY * calcY;
70 if (step == 0) {
71 SkDebugf("binary search failed: step=%1.9g cubic=", firstStep);
72 cubic.dump();
73 SkDebugf(" t=%1.9g ", t);
74 pt.dump();
75 SkDebugf("\n");
76 return -1;
77 }
78 double lastStep = step;
79 step /= 2;
80 SkDPoint lessPt = cubic.ptAtT(t - lastStep);
81 double lessX = lessPt.fX - pt.fX;
82 double lessY = lessPt.fY - pt.fY;
83 double lessDist = lessX * lessX + lessY * lessY;
84 // use larger x/y difference to choose step
85 if (calcDist > lessDist) {
86 t -= step;
87 t = std::max(0., t);
88 } else {
89 SkDPoint morePt = cubic.ptAtT(t + lastStep);
90 double moreX = morePt.fX - pt.fX;
91 double moreY = morePt.fY - pt.fY;
92 double moreDist = moreX * moreX + moreY * moreY;
93 if (calcDist <= moreDist) {
94 continue;
95 }
96 t += step;
97 t = std::min(1., t);
98 }
99 } while (true);
100 return t;
101}
step
static int step(int x, SkScalar min, SkScalar max)
Definition: BlurTest.cpp:215
SkDebugf
void SK_SPI SkDebugf(const char format[],...) SK_PRINTF_LIKE(1
max
static float max(float r, float g, float b)
Definition: hsl.cpp:49
min
static float min(float r, float g, float b)
Definition: hsl.cpp:48
skgpu::wangs_formula::cubic
AI float cubic(float precision, const SkPoint pts[], const VectorXform &vectorXform=VectorXform())
Definition: WangsFormula.h:195
SkDPoint::approximatelyEqual
bool approximatelyEqual(const SkDPoint &a) const
Definition: SkPathOpsPoint.h:177
SkDPoint::dump
void dump() const
Definition: PathOpsDebug.cpp:181

◆ DEF_TEST() [1/3]

DEF_TEST ( PathOpsCubicLineFailures  ,
reporter   
)

Definition at line 277 of file PathOpsCubicLineIntersectionIdeas.cpp.

277 {
278 if ((false)) { // disable for now
279 for (int index = 0; index < cubicLineFailuresCount; ++index) {
280 const CubicLineFailures& failure = cubicLineFailures[index];
281 double newT = testOneFailure(failure);
282 SkASSERT_RELEASE(newT >= 0);
283 }
284 }
285}
testOneFailure
static double testOneFailure(const CubicLineFailures &failure)
Definition: PathOpsCubicLineIntersectionIdeas.cpp:256
cubicLineFailures
static struct CubicLineFailures cubicLineFailures[]
SkASSERT_RELEASE
#define SkASSERT_RELEASE(cond)
Definition: SkAssert.h:100

◆ DEF_TEST() [2/3]

DEF_TEST ( PathOpsCubicLineOneFailure  ,
reporter   
)

Definition at line 287 of file PathOpsCubicLineIntersectionIdeas.cpp.

287 {
288 if ((false)) { // disable for now
289 const CubicLineFailures& failure = cubicLineFailures[1];
290 double newT = testOneFailure(failure);
291 SkASSERT_RELEASE(newT >= 0);
292 }
293}

◆ DEF_TEST() [3/3]

DEF_TEST ( PathOpsCubicLineRoots  ,
reporter   
)

Definition at line 140 of file PathOpsCubicLineIntersectionIdeas.cpp.

140 {
141 if (!gPathOpsCubicLineIntersectionIdeasVerbose) { // slow; exclude it by default
142 return;
143 }
144 SkRandom ran;
145 double worstStep[256] = {0};
146 int errors = 0;
147 int iters = 0;
148 double smallestR2 = 0;
149 double largestR2 = 0;
150 for (int index = 0; index < 1000000000; ++index) {
151 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)};
152 CubicPts cuPts = {{origin,
153 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
154 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)},
155 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}
156 }};
157 // construct a line at a known intersection
158 double t = ran.nextRangeF(0, 1);
159 SkDCubic cubic;
160 cubic.debugSet(cuPts.fPts);
161 SkDPoint pt = cubic.ptAtT(t);
162 // skip answers with no intersections (although note the bug!) or two, or more
163 // see if the line / cubic has a fun range of roots
164 double A, B, C, D;
165 SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D);
166 D -= pt.fY;
167 double allRoots[3] = {0}, validRoots[3] = {0};
168 int realRoots = SkDCubic::RootsReal(A, B, C, D, allRoots);
169 int valid = SkDQuad::AddValidTs(allRoots, realRoots, validRoots);
170 if (valid != 1) {
171 continue;
172 }
173 if (realRoots == 1) {
174 continue;
175 }
176 t = validRoots[0];
177 SkDPoint calcPt = cubic.ptAtT(t);
178 if (calcPt.approximatelyEqual(pt)) {
179 continue;
180 }
181#if 0
182 double R2MinusQ3;
183 if (r2check(A, B, C, D, &R2MinusQ3)) {
184 smallestR2 = std::min(smallestR2, R2MinusQ3);
185 largestR2 = std::max(largestR2, R2MinusQ3);
186 }
187#endif
188 double largest = std::max(fabs(allRoots[0]), fabs(allRoots[1]));
189 if (realRoots == 3) {
190 largest = std::max(largest, fabs(allRoots[2]));
191 }
192 int largeBits;
193 if (largest <= 1) {
194#if 0
195 SkDebugf("realRoots=%d (%1.9g, %1.9g, %1.9g) valid=%d (%1.9g, %1.9g, %1.9g)\n",
196 realRoots, allRoots[0], allRoots[1], allRoots[2], valid, validRoots[0],
197 validRoots[1], validRoots[2]);
198#endif
199 double smallest = std::min(allRoots[0], allRoots[1]);
200 if (realRoots == 3) {
201 smallest = std::min(smallest, allRoots[2]);
202 }
203 SkASSERT_RELEASE(smallest < 0);
204 SkASSERT_RELEASE(smallest >= -1);
205 largeBits = 0;
206 } else {
207 frexp(largest, &largeBits);
208 SkASSERT_RELEASE(largeBits >= 0);
209 SkASSERT_RELEASE(largeBits < 256);
210 }
211 double step = 1e-6;
212 if (largeBits > 21) {
213 step = 1e-1;
214 } else if (largeBits > 18) {
215 step = 1e-2;
216 } else if (largeBits > 15) {
217 step = 1e-3;
218 } else if (largeBits > 12) {
219 step = 1e-4;
220 } else if (largeBits > 9) {
221 step = 1e-5;
222 }
223 double diff;
224 do {
225 double newT = binary_search(cubic, step, pt, t, &iters);
226 if (newT >= 0) {
227 diff = fabs(t - newT);
228 break;
229 }
230 step *= 1.5;
231 SkASSERT_RELEASE(step < 1);
232 } while (true);
233 worstStep[largeBits] = std::max(worstStep[largeBits], diff);
234#if 0
235 {
236 cubic.dump();
237 SkDebugf("\n");
238 SkDLine line = {{{pt.fX - 1, pt.fY}, {pt.fX + 1, pt.fY}}};
239 line.dump();
240 SkDebugf("\n");
241 }
242#endif
243 ++errors;
244 }
245 SkDebugf("errors=%d avgIter=%1.9g", errors, (double) iters / errors);
246 SkDebugf(" steps: ");
247 int worstLimit = std::size(worstStep);
248 while (worstStep[--worstLimit] == 0) ;
249 for (int idx2 = 0; idx2 <= worstLimit; ++idx2) {
250 SkDebugf("%1.9g ", worstStep[idx2]);
251 }
252 SkDebugf("\n");
253 SkDebugf("smallestR2=%1.9g largestR2=%1.9g\n", smallestR2, largestR2);
254}
gPathOpsCubicLineIntersectionIdeasVerbose
static bool gPathOpsCubicLineIntersectionIdeasVerbose
Definition: PathOpsCubicLineIntersectionIdeas.cpp:20
binary_search
static double binary_search(const SkDCubic &cubic, double step, const SkDPoint &pt, double t, int *iters)
Definition: PathOpsCubicLineIntersectionIdeas.cpp:58
SkRandom::nextRangeF
float nextRangeF(float min, float max)
Definition: SkRandom.h:64
C
#define C(TEST_CATEGORY)
Definition: colrv1.cpp:248
B
#define B
Definition: kernel_binary_flowgraph.cc:27
compiler_layering_check.errors
def errors
Definition: compiler_layering_check.py:128
flutter::size
it will be possible to load the file into Perfetto s trace viewer disable asset Prevents usage of any non test fonts unless they were explicitly Loaded via prefetched default font Indicates whether the embedding started a prefetch of the default font manager before creating the engine run In non interactive keep the shell running after the Dart script has completed enable serial On low power devices with low core running concurrent GC tasks on threads can cause them to contend with the UI thread which could potentially lead to jank This option turns off all concurrent GC activities domain network JSON encoded network policy per domain This overrides the DisallowInsecureConnections switch Embedder can specify whether to allow or disallow insecure connections at a domain level old gen heap size
Definition: switches.h:259
gn.gn_meta_sln.line
line
Definition: gn_meta_sln.py:144
protoc_wrapper.e
e
Definition: protoc_wrapper.py:226
CubicPts::fPts
SkDPoint fPts[kPointCount]
Definition: PathOpsTestCommon.h:34
SkDCubic::RootsReal
static int RootsReal(double A, double B, double C, double D, double t[3])
Definition: SkPathOpsCubic.cpp:412
SkDCubic::Coefficients
static void Coefficients(const double *cubic, double *A, double *B, double *C, double *D)
Definition: SkPathOpsCubic.cpp:134
SkDQuad::AddValidTs
static int AddValidTs(double s[], int realRoots, double *t)
Definition: SkPathOpsQuad.cpp:116

◆ testOneFailure()

static double testOneFailure ( const CubicLineFailures &  failure)
static

Definition at line 256 of file PathOpsCubicLineIntersectionIdeas.cpp.

256 {
257 const CubicPts& c = failure.c;
258 SkDCubic cubic;
259 cubic.debugSet(c.fPts);
260 const SkDPoint& pt = failure.p;
261 double A, B, C, D;
262 SkDCubic::Coefficients(&cubic[0].fY, &A, &B, &C, &D);
263 D -= pt.fY;
264 double allRoots[3] = {0}, validRoots[3] = {0};
265 int realRoots = SkDCubic::RootsReal(A, B, C, D, allRoots);
266 int valid = SkDQuad::AddValidTs(allRoots, realRoots, validRoots);
267 SkASSERT_RELEASE(valid == 1);
268 SkASSERT_RELEASE(realRoots != 1);
269 double t = validRoots[0];
270 SkDPoint calcPt = cubic.ptAtT(t);
271 SkASSERT_RELEASE(!calcPt.approximatelyEqual(pt));
272 int iters = 0;
273 double newT = binary_search(cubic, 0.1, pt, t, &iters);
274 return newT;
275}

Variable Documentation

◆ cubicLineFailures

struct CubicLineFailures cubicLineFailures[]
static
Initial value:
= {
{{{{-164.3726806640625, 36.826904296875}, {-189.045166015625, -953.2220458984375},
{926.505859375, -897.36175537109375}, {-139.33489990234375, 204.40771484375}}},
0.37329583, {107.54935269006289, -632.13736293162208}},
{{{{784.056884765625, -554.8350830078125}, {67.5489501953125, 509.0224609375},
{-447.713134765625, 751.375}, {415.7784423828125, 172.22265625}}},
0.660005242, {-32.973148967736151, 478.01341797403569}},
{{{{-580.6834716796875, -127.044921875}, {-872.8983154296875, -945.54302978515625},
{260.8092041015625, -909.34991455078125}, {-976.2125244140625, -18.46551513671875}}},
0.578826774, {-390.17910153915489, -687.21144412296007}},
}

◆ cubicLineFailuresCount

int cubicLineFailuresCount = (int) std::size(cubicLineFailures)

Definition at line 38 of file PathOpsCubicLineIntersectionIdeas.cpp.

◆ gPathOpsCubicLineIntersectionIdeasVerbose

bool gPathOpsCubicLineIntersectionIdeasVerbose = false
static

Definition at line 20 of file PathOpsCubicLineIntersectionIdeas.cpp.

◆ measuredSteps

double measuredSteps[]
Initial value:
= {
9.15910731e-007, 8.6600277e-007, 7.4122059e-007, 6.92087618e-007, 8.35290245e-007,
3.29763199e-007, 5.07547773e-007, 4.41294224e-007, 0, 0,
3.76879167e-006, 1.06126249e-006, 2.36873967e-006, 1.62421134e-005, 3.09103599e-005,
4.38917976e-005, 0.000112348938, 0.000243149242, 0.000433174114, 0.00170880232,
0.00272619724, 0.00518844604, 0.000352621078, 0.00175960064, 0.027875185,
0.0351329803, 0.103964925,
}

Definition at line 40 of file PathOpsCubicLineIntersectionIdeas.cpp.

Generated on Sun Jun 23 2024 21:57:32 for Flutter Engine by doxygen 1.9.4