Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
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
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:247
B
#define B
Definition kernel_binary_flowgraph.cc:27
compiler_layering_check.errors
errors
Definition compiler_layering_check.py:128
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.

40 {
41 9.15910731e-007, 8.6600277e-007, 7.4122059e-007, 6.92087618e-007, 8.35290245e-007,
42 3.29763199e-007, 5.07547773e-007, 4.41294224e-007, 0, 0,
43 3.76879167e-006, 1.06126249e-006, 2.36873967e-006, 1.62421134e-005, 3.09103599e-005,
44 4.38917976e-005, 0.000112348938, 0.000243149242, 0.000433174114, 0.00170880232,
45 0.00272619724, 0.00518844604, 0.000352621078, 0.00175960064, 0.027875185,
46 0.0351329803, 0.103964925,
47};
Generated on Fri Apr 26 2024 06:18:56 for Flutter Engine by doxygen 1.9.8