Flutter Engine
The Flutter Engine
Loading...
Searching...
No Matches
PathOpsCubicIntersectionTestData.cpp
Go to the documentation of this file.
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 "src/pathops/SkPathOpsTypes.h"
9#include "tests/PathOpsCubicIntersectionTestData.h"
10
11#include <array>
12#include <cfloat>
13
14namespace PathOpsCubicIntersectionTestData {
15
16static const double D = FLT_EPSILON / 2;
17static const double G = FLT_EPSILON / 3;
18static const double N = -FLT_EPSILON / 2;
19static const double M = -FLT_EPSILON / 3;
20
21const CubicPts pointDegenerates[] = {
22 {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}},
23 {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}},
24 {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}},
25 {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}},
26 {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}},
27 {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}},
28 {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}},
29 {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}},
30 {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}},
31 {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}},
32 {{{0, 0}, {1, 1}, {2, 2}, {0, 0}}},
33 {{{1, 1}, {2, 2}, {2, 2}, {1, 1}}},
34 {{{0, 0}, {0, D}, {1, 0}, {0, 0}}},
35 {{{0, 0}, {1, 0}, {0, D}, {0, 0}}},
36 {{{0, 0}, {D, 0}, {0, 1}, {0, 0}}},
37 {{{0, 0}, {0, 1}, {D, 0}, {0, 0}}},
38 {{{1, 1}, {2, 2}, {2, 2+D}, {1, 1}}},
39 {{{0, 0}, {0, N}, {1, 0}, {0, 0}}},
40 {{{0, 0}, {1, 0}, {0, N}, {0, 0}}},
41 {{{0, 0}, {N, 0}, {0, 1}, {0, 0}}},
42 {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}},
43 {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}},
44 {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}},
45 {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}},
46 {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}},
47 {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}},
48};
49
50const size_t pointDegenerates_count = std::size(pointDegenerates);
51
52const CubicPts notPointDegenerates[] = {
53 {{{1 + FLT_EPSILON * 8, 1}, {1, FLT_EPSILON * 8}, {1, 1}, {1, 1}}},
54 {{{1 + FLT_EPSILON * 8, 1}, {1 - FLT_EPSILON * 8, 1}, {1, 1}, {1, 1}}}
55};
56
57const size_t notPointDegenerates_count =
58 std::size(notPointDegenerates);
59
60// from http://www.truetex.com/bezint.htm
61const CubicPts tests[][2] = {
62 { // intersects in one place (data gives bezier clip fits
63 {{{0, 45},
64 {6.0094158284751593, 51.610357411322688},
65 {12.741093228940867, 55.981703949474607},
66 {20.021417396476362, 58.652245509710262}}},
67 {{{2.2070737699246674, 52.703494107327209},
68 {31.591482272629477, 23.811002295222025},
69 {76.824588616426425, 44.049473790502674},
70 {119.25488947221436, 55.599248272955073}}}
71 }, { // intersects in three places
72 {{{0, 45}, {50, 100}, {150, 0}, {200, 55}}},
73 {{{0, 55}, {50, 0}, {150, 100}, {200, 45}}}
74 }, { // intersects in one place, cross over is nearly parallel
75 {{{0, 0}, {0, 100}, {200, 0}, {200, 100}}},
76 {{{0, 100}, {0, 0}, {200, 100}, {200, 0}}}
77 }, { // intersects in two places
78 {{{0, 0}, {0, 100}, {200, 100}, {200, 0}}},
79 {{{0, 100}, {0, 0}, {200, 0}, {200, 100}}}
80 }, {
81 {{{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}}},
82 {{{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}}}
83 }, { // single intersection around 168,185
84 {{{200, 100}, {150, 100}, {150, 150}, {200, 150}}},
85 {{{250, 150}, {250, 100}, {100, 100}, {100, 150}}}
86 }, {
87 {{{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}}},
88 {{{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}}}
89 }, {
90 {{{664.00168, 0}, {726.11545, 124.22757}, {736.89069, 267.89743},
91 {694.0017, 400.0002}}},
92 {{{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309},
93 {694.0017, 400.0002}}}
94 }, {
95 {{{1, 1}, {12.5, 6.5}, {-4, 6.5}, {7.5, 1}}},
96 {{{1, 6.5}, {12.5, 1}, {-4, 1}, {.5, 6}}}
97 }, {
98 {{{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 316.804}}},
99 {{{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19}, {304.332, 318.179}}}
100 }, {
101 {{{1046.604051, 172.937967}, {1046.604051, 178.9763059}, {1041.76745, 183.9279165}, {1035.703842, 184.0432409}}},
102 {{{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}}
103 }, {
104 {{{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494, 16.67848}, {167.29361, 16.67848}}},
105 {{{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}}
106 }, {
107 {{{104.11546583642826, 370.21352558595504}, {122.96968232592344, 404.54489231839295},
108 {169.90881005384728, 425.00067000000007}, {221.33045999999999, 425.00067000000001}}},
109 {{{116.32365976159625, 381.71048540582598}, {103.86096590870899, 381.71048540581626},
110 {91.394188003200725, 377.17917781762833}, {82.622283093355179, 368.11683661930334}}}
111 }
112};
113
114const size_t tests_count = std::size(tests);
115
116const CubicPts lines[] = {
117 {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}}, // 0: horizontal
118 {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}},
119 {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}},
120 {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}}, // 5: vertical
121 {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}},
122 {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}},
123 {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 10: 3 coincident
124 {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}},
125 {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}}, // 14: 2 coincident
126 {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}},
127 {{{1, 1}, {0, 0}, {0, 0}, {2, 2}}}, // 17:
128 {{{1, 1}, {0, 0}, {2, 2}, {0, 0}}},
129 {{{1, 1}, {2, 2}, {0, 0}, {0, 0}}},
130 {{{1, 1}, {2, 2}, {3, 3}, {2, 2}}}, // middle-last coincident
131 {{{1, 1}, {2, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
132 {{{1, 1}, {1, 1}, {2, 2}, {2, 2}}}, // 2 pairs coincident
133 {{{1, 1}, {2, 2}, {1, 1}, {2, 2}}},
134 {{{1, 1}, {1, 1}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
135 {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}}, // no coincident
136 {{{1, 1}, {3, 3}, {2, 2}, {4, 4}}},
137 {{{1, 1}, {2, 2}, {4, 4}, {3, 3}}},
138 {{{1, 1}, {3, 3}, {4, 4}, {2, 2}}},
139 {{{1, 1}, {4, 4}, {2, 2}, {3, 3}}},
140 {{{1, 1}, {4, 4}, {3, 3}, {2, 2}}},
141 {{{2, 2}, {1, 1}, {3, 3}, {4, 4}}},
142 {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}},
143 {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}},
144 {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}},
145 {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}},
146 {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}},
147};
148
149const size_t lines_count = std::size(lines);
150
151// 'not a line' tries to fool the line detection code
152const CubicPts notLines[] = {
153 {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}},
154 {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}},
155 {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}},
156 {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}},
157 {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}},
158 {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}},
159};
160
161const size_t notLines_count = std::size(notLines);
162
163static const double E = FLT_EPSILON * 8;
164static const double F = FLT_EPSILON * 8;
165
166const CubicPts modEpsilonLines[] = {
167 {{{0, E}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
168 {{{0, 0}, {0, E}, {1, 0}, {0, 0}}},
169 {{{0, 0}, {1, 0}, {0, E}, {0, 0}}},
170 {{{1, 0}, {0, 0}, {0, 0}, {0, E}}},
171 {{{1, E}, {2, 0}, {3, 0}, {4, 0}}},
172 {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
173 {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}},
174 {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}},
175 {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}},
176 {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}},
177 {{{E, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
178 {{{0, 0}, {E, 0}, {1, 1}, {0, 0}}},
179 {{{0, 0}, {1, 1}, {E, 0}, {0, 0}}},
180 {{{1, 1}, {0, 0}, {0, 0}, {E, 0}}},
181 {{{0, E}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
182 {{{0, 0}, {1, 1}, {0, E}, {2, 2}}},
183 {{{0, 0}, {1, 1}, {2, 2}, {0, E}}},
184 {{{1, 1}, {0, E}, {0, 0}, {2, 2}}},
185 {{{1, 1}, {0, E}, {2, 2}, {0, 0}}},
186 {{{1, 1}, {2, 2}, {E, 0}, {0, 0}}},
187 {{{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}}, // middle-last coincident
188 {{{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
189 {{{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}}, // 2 pairs coincident
190 {{{1, 1}, {2, 2}, {1, 1}, {2+E, 2}}},
191 {{{1, 1}, {2, 2}, {2, 2+E}, {1, 1}}},
192 {{{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
193 {{{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}}, // no coincident
194 {{{1, 1}, {3, 3}, {2, 2}, {4, 4+F+F}}}, // INVESTIGATE: why the epsilon is bigger
195 {{{1, 1+F+F}, {2, 2}, {4, 4}, {3, 3}}}, // INVESTIGATE: why the epsilon is bigger
196 {{{1, 1}, {3, 3}, {4, 4+E}, {2, 2}}},
197 {{{1, 1}, {4, 4}, {2, 2}, {3, 3+E}}},
198 {{{1, 1}, {4, 4}, {3, 3}, {2+E, 2}}},
199 {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}},
200 {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}},
201 {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}},
202 {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}},
203 {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}},
204 {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}},
205};
206
207const size_t modEpsilonLines_count = std::size(modEpsilonLines);
208
209const CubicPts lessEpsilonLines[] = {
210 {{{0, D}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
211 {{{1, 0}, {0, 0}, {0, 0}, {0, D}}},
212 {{{1, D}, {2, 0}, {3, 0}, {4, 0}}},
213 {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
214 {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}},
215 {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}},
216 {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
217 {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}},
218 {{{0, D}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
219 {{{0, 0}, {1, 1}, {0, D}, {2, 2}}},
220 {{{0, 0}, {1, 1}, {2, 2}, {1, 1+D}}},
221 {{{1, 1}, {0, D}, {0, 0}, {2, 2}}},
222 {{{1, 1}, {0, D}, {2, 2}, {0, 0}}},
223 {{{1, 1}, {2, 2}, {D, 0}, {0, 0}}},
224 {{{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}}, // middle-last coincident
225 {{{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
226 {{{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}}, // 2 pairs coincident
227 {{{1, 1}, {2, 2}, {1, 1}, {2+D, 2}}},
228 {{{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
229 {{{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}}, // no coincident (FIXME: N as opposed to N/2 failed)
230 {{{1, 1}, {3, 3}, {2, 2}, {4, 4+D}}},
231 {{{1, 1+D}, {2, 2}, {4, 4}, {3, 3}}},
232 {{{1, 1}, {3, 3}, {4, 4+D}, {2, 2}}},
233 {{{1, 1}, {4, 4}, {2, 2}, {3, 3+D}}},
234 {{{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}}, // INVESTIGATE: why the epsilon is smaller
235 {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}},
236 {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}},
237 {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}},
238 {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}}, // INVESTIGATE: why the epsilon is smaller
239 {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}},
240 {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}},
241};
242
243const size_t lessEpsilonLines_count = std::size(lessEpsilonLines);
244
245const CubicPts negEpsilonLines[] = {
246 {{{0, N}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
247 {{{1, 0}, {0, 0}, {0, 0}, {0, N}}},
248 {{{1, N}, {2, 0}, {3, 0}, {4, 0}}},
249 {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
250 {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}},
251 {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}},
252 {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
253 {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}},
254 {{{0, N}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
255 {{{0, 0}, {1, 1}, {0, N}, {2, 2}}},
256 {{{0, 0}, {1, 1}, {2, 2}, {1, 1+N}}},
257 {{{1, 1}, {0, N}, {0, 0}, {2, 2}}},
258 {{{1, 1}, {0, N}, {2, 2}, {0, 0}}},
259 {{{1, 1}, {2, 2}, {N, 0}, {0, 0}}},
260 {{{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}}, // middle-last coincident
261 {{{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
262 {{{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}}, // 2 pairs coincident
263 {{{1, 1}, {2, 2}, {1, 1}, {2+N, 2}}},
264 {{{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
265 {{{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}}, // no coincident (FIXME: N as opposed to N/2 failed)
266 {{{1, 1}, {3, 3}, {2, 2}, {4, 4+N}}},
267 {{{1, 1+N}, {2, 2}, {4, 4}, {3, 3}}},
268 {{{1, 1}, {3, 3}, {4, 4+N}, {2, 2}}},
269 {{{1, 1}, {4, 4}, {2, 2}, {3, 3+N}}},
270 {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}}, // INVESTIGATE: why the epsilon is smaller
271 {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}},
272 {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}},
273 {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}},
274 {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}}, // INVESTIGATE: why the epsilon is smaller
275 {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}},
276 {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}},
277};
278
279const size_t negEpsilonLines_count = std::size(negEpsilonLines);
280
281} // namespace PathOpsCubicIntersectionTestData
FLT_EPSILON_HALF
const double FLT_EPSILON_HALF
Definition SkPathOpsTypes.h:306
F
Definition SkMD5.cpp:120
G
Definition SkMD5.cpp:125
Generated on Fri Apr 26 2024 06:17:51 for Flutter Engine by doxygen 1.9.8