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
10const 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
19const size_t pointDegenerates_count = sizeof(pointDegenerates) / sizeof(pointDegenerates[0]);
20
21const Cubic notPointDegenerates[] = {
22    {{1 + PointEpsilon + std::numeric_limits<double>::epsilon(), 1}, {1, 1 + PointEpsilon}, {1, 1}, {1, 1}},
23    {{1 + PointEpsilon/2 + std::numeric_limits<double>::epsilon(), 1}, {1 - PointEpsilon/2, 1}, {1, 1}, {1, 1}}
24};
25
26const size_t notPointDegenerates_count = sizeof(notPointDegenerates) / sizeof(notPointDegenerates[0]);
27
28// from http://www.truetex.com/bezint.htm
29const 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, 316.804}},
74        {{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19},  {304.332, 318.179}}
75    },
76    {
77        {{1046.604051, 172.937967},  {1046.604051, 178.9763059}, {1041.76745,  183.9279165}, {1035.703842, 184.0432409}},
78        {{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}
79    },
80    {
81        {{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494,  16.67848}, {167.29361, 16.67848}},
82        {{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}
83    }
84};
85
86const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
87
88Cubic hexTests[][2] = {
89    {
90        {{0}} // placeholder for hex converted below
91    }
92};
93
94const size_t hexTests_count = sizeof(hexTests) / sizeof(hexTests[0]);
95
96static const uint64_t testx[2][8] = {
97    {
98        0xf0d0d1ca63075a40LLU, 0x9408ce996a237740LLU, 0x6d5675460fbe5e40LLU, 0x6ef501e1b7487940LLU,
99        0x9a71d2f8143d6540LLU, 0x6bc18bbe02907a40LLU, 0x5b94d92093aa6b40LLU, 0x6ac18bbe02907a40LLU
100    },
101    {
102        0x92c56ed7b6145d40LLU, 0xede4f1255edb7740LLU, 0x1138c1101af75940LLU, 0x42e4f1255edb7740LLU,
103        0x408e51603ad95640LLU, 0x1e2e8fe9dd927740LLU, 0x1cb4777cd3a75440LLU, 0x212e1390de017740LLU
104    }
105};
106
107void 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]); ++index) {
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
119const 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
160const size_t lines_count = sizeof(lines) / sizeof(lines[0]);
161
162// 'not a line' tries to fool the line detection code
163const 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
172const size_t notLines_count = sizeof(notLines) / sizeof(notLines[0]);
173
174static const double E = PointEpsilon * 2;
175static const double F = PointEpsilon * 3;
176
177const 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 bigger
206    {{1, 1+F}, {2, 2}, {4, 4}, {3, 3}}, // INVESTIGATE: why the epsilon is bigger
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
218const size_t modEpsilonLines_count = sizeof(modEpsilonLines) / sizeof(modEpsilonLines[0]);
219
220static const double D = PointEpsilon / 2;
221static const double G = PointEpsilon / 3;
222
223const 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 smaller
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 smaller
260    {{2, 2}, {4+D, 4}, {1, 1}, {3, 3}},
261    {{2, 2}, {4, 4}, {3, 3}, {1, 1+D}},
262};
263
264const size_t lessEpsilonLines_count = sizeof(lessEpsilonLines) / sizeof(lessEpsilonLines[0]);
265
266static const double N = -PointEpsilon / 2;
267static const double M = -PointEpsilon / 3;
268
269const 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 smaller
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 smaller
306    {{2, 2}, {4+N, 4}, {1, 1}, {3, 3}},
307    {{2, 2}, {4, 4}, {3, 3}, {1, 1+N}},
308};
309
310const size_t negEpsilonLines_count = sizeof(negEpsilonLines) / sizeof(negEpsilonLines[0]);
311