OLD | NEW |
| (Empty) |
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 "CubicIntersection_TestData.h" | |
8 #include <limits> | |
9 | |
10 const Cubic pointDegenerates[] = { | |
11 {{0, 0}, {0, 0}, {0, 0}, {0, 0}}, | |
12 {{1, 1}, {1, 1}, {1, 1}, {1, 1}}, | |
13 {{1 + PointEpsilon - std::numeric_limits<double>::epsilon(), 1}, | |
14 {1, 1 + PointEpsilon - std::numeric_limits<double>::epsilon()}, {1, 1}, {1,
1}}, | |
15 {{1 + PointEpsilon/2 - std::numeric_limits<double>::epsilon(), 1}, | |
16 {1 - (PointEpsilon/2 - std::numeric_limits<double>::epsilon()), 1}, {1, 1},
{1, 1}} | |
17 }; | |
18 | |
19 const size_t pointDegenerates_count = sizeof(pointDegenerates) / sizeof(pointDeg
enerates[0]); | |
20 | |
21 const Cubic notPointDegenerates[] = { | |
22 {{1 + PointEpsilon + std::numeric_limits<double>::epsilon(), 1}, {1, 1 + Poi
ntEpsilon}, {1, 1}, {1, 1}}, | |
23 {{1 + PointEpsilon/2 + std::numeric_limits<double>::epsilon(), 1}, {1 - Poin
tEpsilon/2, 1}, {1, 1}, {1, 1}} | |
24 }; | |
25 | |
26 const size_t notPointDegenerates_count = sizeof(notPointDegenerates) / sizeof(no
tPointDegenerates[0]); | |
27 | |
28 // from http://www.truetex.com/bezint.htm | |
29 const Cubic tests[][2] = { | |
30 { // intersects in one place (data gives bezier clip fits | |
31 {{0, 45}, | |
32 {6.0094158284751593, 51.610357411322688}, | |
33 {12.741093228940867, 55.981703949474607}, | |
34 {20.021417396476362, 58.652245509710262}}, | |
35 {{2.2070737699246674, 52.703494107327209}, | |
36 {31.591482272629477, 23.811002295222025}, | |
37 {76.824588616426425, 44.049473790502674}, | |
38 {119.25488947221436, 55.599248272955073}} | |
39 }, | |
40 { // intersects in three places | |
41 {{0, 45}, {50, 100}, {150, 0}, {200, 55}}, | |
42 {{0, 55}, {50, 0}, {150, 100}, {200, 45}} | |
43 }, | |
44 { // intersects in one place, cross over is nearly parallel | |
45 {{0, 0}, {0, 100}, {200, 0}, {200, 100}}, | |
46 {{0, 100}, {0, 0}, {200, 100}, {200, 0}} | |
47 }, | |
48 { // intersects in two places | |
49 {{0, 0}, {0, 100}, {200, 100}, {200, 0}}, | |
50 {{0, 100}, {0, 0}, {200, 0}, {200, 100}} | |
51 }, | |
52 { | |
53 {{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}}, | |
54 {{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}} | |
55 }, | |
56 { // single intersection around 168,185 | |
57 {{200, 100}, {150, 100}, {150, 150}, {200, 150}}, | |
58 {{250, 150}, {250, 100}, {100, 100}, {100, 150}} | |
59 }, | |
60 { | |
61 {{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}}, | |
62 {{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}} | |
63 }, | |
64 { | |
65 {{664.00168, 0}, {726.11545, 124.22757}, {736.89069, 267.89743}, {
694.0017, 400.0002}}, | |
66 {{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309}, {
694.0017, 400.0002}} | |
67 }, | |
68 { | |
69 {{1, 1}, {12.5, 6.5}, {-4, 6.5}, {7.5, 1}}, | |
70 {{1, 6.5}, {12.5, 1}, {-4, 1}, {.5, 6}} | |
71 }, | |
72 { | |
73 {{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 31
6.804}}, | |
74 {{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19}, {304.332, 31
8.179}} | |
75 }, | |
76 { | |
77 {{1046.604051, 172.937967}, {1046.604051, 178.9763059}, {1041.76745, 1
83.9279165}, {1035.703842, 184.0432409}}, | |
78 {{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 1
84.0469882}, {1035.505925, 184.0469882}} | |
79 }, | |
80 { | |
81 {{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494, 16.67848}, {16
7.29361, 16.67848}}, | |
82 {{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {12
5.7942, 199.57309}} | |
83 } | |
84 }; | |
85 | |
86 const size_t tests_count = sizeof(tests) / sizeof(tests[0]); | |
87 | |
88 Cubic hexTests[][2] = { | |
89 { | |
90 {{0}} // placeholder for hex converted below | |
91 } | |
92 }; | |
93 | |
94 const size_t hexTests_count = sizeof(hexTests) / sizeof(hexTests[0]); | |
95 | |
96 static const uint64_t testx[2][8] = { | |
97 { | |
98 0xf0d0d1ca63075a40LLU, 0x9408ce996a237740LLU, 0x6d5675460fbe5e40LLU, 0x6
ef501e1b7487940LLU, | |
99 0x9a71d2f8143d6540LLU, 0x6bc18bbe02907a40LLU, 0x5b94d92093aa6b40LLU, 0x6
ac18bbe02907a40LLU | |
100 }, | |
101 { | |
102 0x92c56ed7b6145d40LLU, 0xede4f1255edb7740LLU, 0x1138c1101af75940LLU, 0x4
2e4f1255edb7740LLU, | |
103 0x408e51603ad95640LLU, 0x1e2e8fe9dd927740LLU, 0x1cb4777cd3a75440LLU, 0x2
12e1390de017740LLU | |
104 } | |
105 }; | |
106 | |
107 void convert_testx() { | |
108 const uint64_t* inPtr = testx[0]; | |
109 double* outPtr = &hexTests[sizeof(tests) / sizeof(tests[0]) - 1][0][0].x; | |
110 for (unsigned index = 0; index < sizeof(testx) / sizeof(testx[0][0]); ++inde
x) { | |
111 uint64_t input = *inPtr++; | |
112 unsigned char* output = (unsigned char*) outPtr++; | |
113 for (unsigned byte = 0; byte < sizeof(input); ++byte) { | |
114 output[byte] = input >> (7 - byte) * 8; | |
115 } | |
116 } | |
117 } | |
118 | |
119 const Cubic lines[] = { | |
120 {{0, 0}, {0, 0}, {0, 0}, {1, 0}}, // 0: horizontal | |
121 {{0, 0}, {0, 0}, {1, 0}, {0, 0}}, | |
122 {{0, 0}, {1, 0}, {0, 0}, {0, 0}}, | |
123 {{1, 0}, {0, 0}, {0, 0}, {0, 0}}, | |
124 {{1, 0}, {2, 0}, {3, 0}, {4, 0}}, | |
125 {{0, 0}, {0, 0}, {0, 0}, {0, 1}}, // 5: vertical | |
126 {{0, 0}, {0, 0}, {0, 1}, {0, 0}}, | |
127 {{0, 0}, {0, 1}, {0, 0}, {0, 0}}, | |
128 {{0, 1}, {0, 0}, {0, 0}, {0, 0}}, | |
129 {{0, 1}, {0, 2}, {0, 3}, {0, 4}}, | |
130 {{0, 0}, {0, 0}, {0, 0}, {1, 1}}, // 10: 3 coincident | |
131 {{0, 0}, {0, 0}, {1, 1}, {0, 0}}, | |
132 {{0, 0}, {1, 1}, {0, 0}, {0, 0}}, | |
133 {{1, 1}, {0, 0}, {0, 0}, {0, 0}}, | |
134 {{0, 0}, {0, 0}, {1, 1}, {2, 2}}, // 14: 2 coincident | |
135 {{0, 0}, {1, 1}, {0, 0}, {2, 2}}, | |
136 {{0, 0}, {1, 1}, {2, 2}, {0, 0}}, | |
137 {{1, 1}, {0, 0}, {0, 0}, {2, 2}}, // 17: | |
138 {{1, 1}, {0, 0}, {2, 2}, {0, 0}}, | |
139 {{1, 1}, {2, 2}, {0, 0}, {0, 0}}, | |
140 {{1, 1}, {2, 2}, {3, 3}, {2, 2}}, // middle-last coincident | |
141 {{1, 1}, {2, 2}, {3, 3}, {3, 3}}, // middle-last coincident | |
142 {{1, 1}, {1, 1}, {2, 2}, {2, 2}}, // 2 pairs coincident | |
143 {{1, 1}, {2, 2}, {1, 1}, {2, 2}}, | |
144 {{1, 1}, {2, 2}, {2, 2}, {1, 1}}, | |
145 {{1, 1}, {1, 1}, {3, 3}, {3, 3}}, // first-middle middle-last coincident | |
146 {{1, 1}, {2, 2}, {3, 3}, {4, 4}}, // no coincident | |
147 {{1, 1}, {3, 3}, {2, 2}, {4, 4}}, | |
148 {{1, 1}, {2, 2}, {4, 4}, {3, 3}}, | |
149 {{1, 1}, {3, 3}, {4, 4}, {2, 2}}, | |
150 {{1, 1}, {4, 4}, {2, 2}, {3, 3}}, | |
151 {{1, 1}, {4, 4}, {3, 3}, {2, 2}}, | |
152 {{2, 2}, {1, 1}, {3, 3}, {4, 4}}, | |
153 {{2, 2}, {1, 1}, {4, 4}, {3, 3}}, | |
154 {{2, 2}, {3, 3}, {1, 1}, {4, 4}}, | |
155 {{2, 2}, {3, 3}, {4, 4}, {1, 1}}, | |
156 {{2, 2}, {4, 4}, {1, 1}, {3, 3}}, | |
157 {{2, 2}, {4, 4}, {3, 3}, {1, 1}}, | |
158 }; | |
159 | |
160 const size_t lines_count = sizeof(lines) / sizeof(lines[0]); | |
161 | |
162 // 'not a line' tries to fool the line detection code | |
163 const Cubic notLines[] = { | |
164 {{0, 0}, {0, 0}, {0, 1}, {1, 0}}, | |
165 {{0, 0}, {0, 1}, {0, 0}, {1, 0}}, | |
166 {{0, 0}, {0, 1}, {1, 0}, {0, 0}}, | |
167 {{0, 1}, {0, 0}, {0, 0}, {1, 0}}, | |
168 {{0, 1}, {0, 0}, {1, 0}, {0, 0}}, | |
169 {{0, 1}, {1, 0}, {0, 0}, {0, 0}}, | |
170 }; | |
171 | |
172 const size_t notLines_count = sizeof(notLines) / sizeof(notLines[0]); | |
173 | |
174 static const double E = PointEpsilon * 2; | |
175 static const double F = PointEpsilon * 3; | |
176 | |
177 const Cubic modEpsilonLines[] = { | |
178 {{0, E}, {0, 0}, {0, 0}, {1, 0}}, // horizontal | |
179 {{0, 0}, {0, E}, {1, 0}, {0, 0}}, | |
180 {{0, 0}, {1, 0}, {0, E}, {0, 0}}, | |
181 {{1, 0}, {0, 0}, {0, 0}, {0, E}}, | |
182 {{1, E}, {2, 0}, {3, 0}, {4, 0}}, | |
183 {{E, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical | |
184 {{0, 0}, {E, 0}, {0, 1}, {0, 0}}, | |
185 {{0, 0}, {0, 1}, {E, 0}, {0, 0}}, | |
186 {{0, 1}, {0, 0}, {0, 0}, {E, 0}}, | |
187 {{E, 1}, {0, 2}, {0, 3}, {0, 4}}, | |
188 {{E, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident | |
189 {{0, 0}, {E, 0}, {1, 1}, {0, 0}}, | |
190 {{0, 0}, {1, 1}, {E, 0}, {0, 0}}, | |
191 {{1, 1}, {0, 0}, {0, 0}, {E, 0}}, | |
192 {{0, E}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident | |
193 {{0, 0}, {1, 1}, {0, E}, {2, 2}}, | |
194 {{0, 0}, {1, 1}, {2, 2}, {0, E}}, | |
195 {{1, 1}, {0, E}, {0, 0}, {2, 2}}, | |
196 {{1, 1}, {0, E}, {2, 2}, {0, 0}}, | |
197 {{1, 1}, {2, 2}, {E, 0}, {0, 0}}, | |
198 {{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}, // middle-last coincident | |
199 {{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}, // middle-last coincident | |
200 {{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}, // 2 pairs coincident | |
201 {{1, 1}, {2, 2}, {1, 1}, {2+E, 2}}, | |
202 {{1, 1}, {2, 2}, {2, 2+E}, {1, 1}}, | |
203 {{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}, // first-middle middle-last coincident | |
204 {{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}, // no coincident | |
205 {{1, 1}, {3, 3}, {2, 2}, {4, 4+F}}, // INVESTIGATE: why the epsilon is bigge
r | |
206 {{1, 1+F}, {2, 2}, {4, 4}, {3, 3}}, // INVESTIGATE: why the epsilon is bigge
r | |
207 {{1, 1}, {3, 3}, {4, 4+E}, {2, 2}}, | |
208 {{1, 1}, {4, 4}, {2, 2}, {3, 3+E}}, | |
209 {{1, 1}, {4, 4}, {3, 3}, {2+E, 2}}, | |
210 {{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}, | |
211 {{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}, | |
212 {{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}, | |
213 {{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}, | |
214 {{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}, | |
215 {{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}, | |
216 }; | |
217 | |
218 const size_t modEpsilonLines_count = sizeof(modEpsilonLines) / sizeof(modEpsilon
Lines[0]); | |
219 | |
220 static const double D = PointEpsilon / 2; | |
221 static const double G = PointEpsilon / 3; | |
222 | |
223 const Cubic lessEpsilonLines[] = { | |
224 {{0, D}, {0, 0}, {0, 0}, {1, 0}}, // horizontal | |
225 {{0, 0}, {0, D}, {1, 0}, {0, 0}}, | |
226 {{0, 0}, {1, 0}, {0, D}, {0, 0}}, | |
227 {{1, 0}, {0, 0}, {0, 0}, {0, D}}, | |
228 {{1, D}, {2, 0}, {3, 0}, {4, 0}}, | |
229 {{D, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical | |
230 {{0, 0}, {D, 0}, {0, 1}, {0, 0}}, | |
231 {{0, 0}, {0, 1}, {D, 0}, {0, 0}}, | |
232 {{0, 1}, {0, 0}, {0, 0}, {D, 0}}, | |
233 {{D, 1}, {0, 2}, {0, 3}, {0, 4}}, | |
234 {{D, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident | |
235 {{0, 0}, {D, 0}, {1, 1}, {0, 0}}, | |
236 {{0, 0}, {1, 1}, {D, 0}, {0, 0}}, | |
237 {{1, 1}, {0, 0}, {0, 0}, {D, 0}}, | |
238 {{0, D}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident | |
239 {{0, 0}, {1, 1}, {0, D}, {2, 2}}, | |
240 {{0, 0}, {1, 1}, {2, 2}, {0, D}}, | |
241 {{1, 1}, {0, D}, {0, 0}, {2, 2}}, | |
242 {{1, 1}, {0, D}, {2, 2}, {0, 0}}, | |
243 {{1, 1}, {2, 2}, {D, 0}, {0, 0}}, | |
244 {{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}, // middle-last coincident | |
245 {{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}, // middle-last coincident | |
246 {{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}, // 2 pairs coincident | |
247 {{1, 1}, {2, 2}, {1, 1}, {2+D, 2}}, | |
248 {{1, 1}, {2, 2}, {2, 2+D}, {1, 1}}, | |
249 {{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}, // first-middle middle-last coincident | |
250 {{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}, // no coincident (FIXME: N as opposed
to N/2 failed) | |
251 {{1, 1}, {3, 3}, {2, 2}, {4, 4+D}}, | |
252 {{1, 1+D}, {2, 2}, {4, 4}, {3, 3}}, | |
253 {{1, 1}, {3, 3}, {4, 4+D}, {2, 2}}, | |
254 {{1, 1}, {4, 4}, {2, 2}, {3, 3+D}}, | |
255 {{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}, // INVESTIGATE: why the epsilon is small
er | |
256 {{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}, | |
257 {{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}, | |
258 {{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}, | |
259 {{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}, // INVESTIGATE: why the epsilon is small
er | |
260 {{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}, | |
261 {{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}, | |
262 }; | |
263 | |
264 const size_t lessEpsilonLines_count = sizeof(lessEpsilonLines) / sizeof(lessEpsi
lonLines[0]); | |
265 | |
266 static const double N = -PointEpsilon / 2; | |
267 static const double M = -PointEpsilon / 3; | |
268 | |
269 const Cubic negEpsilonLines[] = { | |
270 {{0, N}, {0, 0}, {0, 0}, {1, 0}}, // horizontal | |
271 {{0, 0}, {0, N}, {1, 0}, {0, 0}}, | |
272 {{0, 0}, {1, 0}, {0, N}, {0, 0}}, | |
273 {{1, 0}, {0, 0}, {0, 0}, {0, N}}, | |
274 {{1, N}, {2, 0}, {3, 0}, {4, 0}}, | |
275 {{N, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical | |
276 {{0, 0}, {N, 0}, {0, 1}, {0, 0}}, | |
277 {{0, 0}, {0, 1}, {N, 0}, {0, 0}}, | |
278 {{0, 1}, {0, 0}, {0, 0}, {N, 0}}, | |
279 {{N, 1}, {0, 2}, {0, 3}, {0, 4}}, | |
280 {{N, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident | |
281 {{0, 0}, {N, 0}, {1, 1}, {0, 0}}, | |
282 {{0, 0}, {1, 1}, {N, 0}, {0, 0}}, | |
283 {{1, 1}, {0, 0}, {0, 0}, {N, 0}}, | |
284 {{0, N}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident | |
285 {{0, 0}, {1, 1}, {0, N}, {2, 2}}, | |
286 {{0, 0}, {1, 1}, {2, 2}, {0, N}}, | |
287 {{1, 1}, {0, N}, {0, 0}, {2, 2}}, | |
288 {{1, 1}, {0, N}, {2, 2}, {0, 0}}, | |
289 {{1, 1}, {2, 2}, {N, 0}, {0, 0}}, | |
290 {{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}, // middle-last coincident | |
291 {{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}, // middle-last coincident | |
292 {{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}, // 2 pairs coincident | |
293 {{1, 1}, {2, 2}, {1, 1}, {2+N, 2}}, | |
294 {{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}, | |
295 {{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}, // first-middle middle-last coincident | |
296 {{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}, // no coincident (FIXME: N as opposed
to N/2 failed) | |
297 {{1, 1}, {3, 3}, {2, 2}, {4, 4+N}}, | |
298 {{1, 1+N}, {2, 2}, {4, 4}, {3, 3}}, | |
299 {{1, 1}, {3, 3}, {4, 4+N}, {2, 2}}, | |
300 {{1, 1}, {4, 4}, {2, 2}, {3, 3+N}}, | |
301 {{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}, // INVESTIGATE: why the epsilon is small
er | |
302 {{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}, | |
303 {{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}, | |
304 {{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}, | |
305 {{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}, // INVESTIGATE: why the epsilon is small
er | |
306 {{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}, | |
307 {{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}, | |
308 }; | |
309 | |
310 const size_t negEpsilonLines_count = sizeof(negEpsilonLines) / sizeof(negEpsilon
Lines[0]); | |
OLD | NEW |