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 "CurveIntersection.h" | |
8 #include "Intersection_Tests.h" | |
9 #include "IntersectionUtilities.h" | |
10 | |
11 const Cubic convex[] = { | |
12 {{0, 0}, {2, 0}, {2, 1}, {0, 1}}, | |
13 {{1, 0}, {1, 1}, {0, 1}, {0, 0}}, | |
14 {{1, 1}, {0, 1}, {0, 0}, {1, 0}}, | |
15 {{0, 1}, {0, 0}, {1, 0}, {1, 1}}, | |
16 {{0, 0}, {10, 0}, {10, 10}, {5, 6}}, | |
17 }; | |
18 | |
19 size_t convex_count = sizeof(convex) / sizeof(convex[0]); | |
20 | |
21 const Cubic bowtie[] = { | |
22 {{0, 0}, {1, 1}, {1, 0}, {0, 1}}, | |
23 {{1, 0}, {0, 1}, {1, 1}, {0, 0}}, | |
24 {{1, 1}, {0, 0}, {0, 1}, {1, 0}}, | |
25 {{0, 1}, {1, 0}, {0, 0}, {1, 1}}, | |
26 }; | |
27 | |
28 size_t bowtie_count = sizeof(bowtie) / sizeof(bowtie[0]); | |
29 | |
30 const Cubic arrow[] = { | |
31 {{0, 0}, {10, 0}, {10, 10}, {5, 4}}, | |
32 {{10, 0}, {10, 10}, {5, 4}, {0, 0}}, | |
33 {{10, 10}, {5, 4}, {0, 0}, {10, 0}}, | |
34 {{5, 4}, {0, 0}, {10, 0}, {10, 10}}, | |
35 }; | |
36 | |
37 size_t arrow_count = sizeof(arrow) / sizeof(arrow[0]); | |
38 | |
39 const Cubic three[] = { | |
40 {{1, 0}, {1, 0}, {1, 1}, {0, 1}}, // 0 == 1 | |
41 {{0, 0}, {1, 1}, {1, 1}, {0, 1}}, // 1 == 2 | |
42 {{0, 0}, {1, 0}, {0, 1}, {0, 1}}, // 2 == 3 | |
43 {{1, 0}, {1, 1}, {1, 0}, {0, 1}}, // 0 == 2 | |
44 {{1, 0}, {1, 1}, {0, 1}, {1, 0}}, // 0 == 3 | |
45 {{0, 0}, {1, 0}, {1, 1}, {1, 0}}, // 1 == 3 | |
46 }; | |
47 | |
48 size_t three_count = sizeof(three) / sizeof(three[0]); | |
49 | |
50 const Cubic triangle[] = { | |
51 {{0, 0}, {1, 0}, {2, 0}, {0, 1}}, // extra point on horz | |
52 {{1, 0}, {2, 0}, {0, 1}, {0, 0}}, | |
53 {{2, 0}, {0, 1}, {0, 0}, {1, 0}}, | |
54 {{0, 1}, {0, 0}, {1, 0}, {2, 0}}, | |
55 | |
56 {{0, 0}, {0, 1}, {0, 2}, {1, 1}}, // extra point on vert | |
57 {{0, 1}, {0, 2}, {1, 1}, {0, 0}}, | |
58 {{0, 2}, {1, 1}, {0, 0}, {0, 1}}, | |
59 {{1, 1}, {0, 0}, {0, 1}, {0, 2}}, | |
60 | |
61 {{0, 0}, {1, 1}, {2, 2}, {2, 0}}, // extra point on diag | |
62 {{1, 1}, {2, 2}, {2, 0}, {0, 0}}, | |
63 {{2, 2}, {2, 0}, {0, 0}, {1, 1}}, | |
64 {{2, 0}, {0, 0}, {1, 1}, {2, 2}}, | |
65 | |
66 {{0, 0}, {2, 0}, {2, 2}, {1, 1}}, // extra point on diag | |
67 {{2, 0}, {2, 2}, {1, 1}, {0, 0}}, | |
68 {{2, 2}, {1, 1}, {0, 0}, {2, 0}}, | |
69 {{1, 1}, {0, 0}, {2, 0}, {2, 2}}, | |
70 }; | |
71 | |
72 size_t triangle_count = sizeof(triangle) / sizeof(triangle[0]); | |
73 | |
74 const struct CubicDataSet { | |
75 const Cubic* data; | |
76 size_t size; | |
77 } cubicDataSet[] = { | |
78 { three, three_count }, | |
79 { convex, convex_count }, | |
80 { bowtie, bowtie_count }, | |
81 { arrow, arrow_count }, | |
82 { triangle, triangle_count }, | |
83 }; | |
84 | |
85 size_t cubicDataSet_count = sizeof(cubicDataSet) / sizeof(cubicDataSet[0]); | |
86 | |
87 typedef double Matrix3x2[3][2]; | |
88 | |
89 static bool rotateToAxis(const _Point& a, const _Point& b, Matrix3x2& matrix) { | |
90 double dx = b.x - a.x; | |
91 double dy = b.y - a.y; | |
92 double length = sqrt(dx * dx + dy * dy); | |
93 if (length == 0) { | |
94 return false; | |
95 } | |
96 double invLength = 1 / length; | |
97 matrix[0][0] = dx * invLength; | |
98 matrix[1][0] = dy * invLength; | |
99 matrix[2][0] = 0; | |
100 matrix[0][1] = -dy * invLength; | |
101 matrix[1][1] = dx * invLength; | |
102 matrix[2][1] = 0; | |
103 return true; | |
104 } | |
105 | |
106 static void transform(const Cubic& cubic, const Matrix3x2& matrix, Cubic& rotPat
h) { | |
107 for (int index = 0; index < 4; ++index) { | |
108 rotPath[index].x = cubic[index].x * matrix[0][0] | |
109 + cubic[index].y * matrix[1][0] + matrix[2][0]; | |
110 rotPath[index].y = cubic[index].x * matrix[0][1] | |
111 + cubic[index].y * matrix[1][1] + matrix[2][1]; | |
112 } | |
113 } | |
114 | |
115 // brute force way to find convex hull: | |
116 // pick two points | |
117 // rotate all four until the two points are horizontal | |
118 // are the remaining two points both above or below the horizontal line? | |
119 // if so, the two points must be an edge of the convex hull | |
120 static int rotate_to_hull(const Cubic& cubic, char order[4], size_t idx, size_t
inr) { | |
121 bool debug_rotate_to_hull = false; | |
122 int outsidePtSet[4]; | |
123 memset(outsidePtSet, -1, sizeof(outsidePtSet)); | |
124 for (int outer = 0; outer < 3; ++outer) { | |
125 for (int priorOuter = 0; priorOuter < outer; ++priorOuter) { | |
126 if (cubic[outer].approximatelyEqual(cubic[priorOuter])) { | |
127 goto skip; | |
128 } | |
129 } | |
130 for (int inner = outer + 1; inner < 4; ++inner) { | |
131 for (int priorInner = outer + 1; priorInner < inner; ++priorInner) { | |
132 if (cubic[inner].approximatelyEqual(cubic[priorInner])) { | |
133 goto skipInner; | |
134 } | |
135 } | |
136 if (cubic[outer].approximatelyEqual(cubic[inner])) { | |
137 continue; | |
138 } | |
139 Matrix3x2 matrix; | |
140 if (!rotateToAxis(cubic[outer], cubic[inner], matrix)) { | |
141 continue; | |
142 } | |
143 Cubic rotPath; | |
144 transform(cubic, matrix, rotPath); | |
145 int sides[3]; | |
146 int zeroes; | |
147 zeroes = -1; | |
148 bzero(sides, sizeof(sides)); | |
149 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] src=(%g,%
g) rot=", __FUNCTION__, | |
150 (int)idx, (int)inr, (int)outer, (int)inner, | |
151 cubic[inner].x, cubic[inner].y); | |
152 for (int index = 0; index < 4; ++index) { | |
153 if (debug_rotate_to_hull) SkDebugf("(%g,%g) ", rotPath[index].x,
rotPath[index].y); | |
154 sides[side(rotPath[index].y - rotPath[inner].y)]++; | |
155 if (index != outer && index != inner | |
156 && side(rotPath[index].y - rotPath[inner].y) == 1) | |
157 zeroes = index; | |
158 } | |
159 if (debug_rotate_to_hull) SkDebugf("sides=(%d,%d,%d)\n", sides[0], s
ides[1], sides[2]); | |
160 if (sides[0] && sides[2]) { | |
161 continue; | |
162 } | |
163 if (sides[1] == 3 && zeroes >= 0) { | |
164 // verify that third point is between outer, inner | |
165 // if either of remaining two equals outer or equal, pick lower | |
166 if (rotPath[zeroes].approximatelyEqual(rotPath[inner]) | |
167 && zeroes < inner) { | |
168 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] z
eroes < inner\n", | |
169 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner
); | |
170 continue; | |
171 } | |
172 if (rotPath[zeroes].approximatelyEqual(rotPath[outer]) | |
173 && zeroes < outer) { | |
174 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] z
eroes < outer\n", | |
175 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner
); | |
176 continue; | |
177 } | |
178 if (rotPath[zeroes].x < rotPath[inner].x | |
179 && rotPath[zeroes].x < rotPath[outer].x) { | |
180 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] z
eroes < inner && outer\n", | |
181 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner
); | |
182 continue; | |
183 } | |
184 if (rotPath[zeroes].x > rotPath[inner].x | |
185 && rotPath[zeroes].x > rotPath[outer].x) { | |
186 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] z
eroes > inner && outer\n", | |
187 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner
); | |
188 continue; | |
189 } | |
190 } | |
191 if (outsidePtSet[outer] < 0) { | |
192 outsidePtSet[outer] = inner; | |
193 } else { | |
194 if (outsidePtSet[inner] > 0) { | |
195 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] t
oo many rays from one point\n", | |
196 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner
); | |
197 } | |
198 outsidePtSet[inner] = outer; | |
199 } | |
200 skipInner: | |
201 ; | |
202 } | |
203 skip: | |
204 ; | |
205 } | |
206 int totalSides = 0; | |
207 int first = 0; | |
208 for (; first < 4; ++first) { | |
209 if (outsidePtSet[first] >= 0) { | |
210 break; | |
211 } | |
212 } | |
213 if (first > 3) { | |
214 order[0] = 0; | |
215 return 1; | |
216 } | |
217 int next = first; | |
218 do { | |
219 order[totalSides++] = next; | |
220 next = outsidePtSet[next]; | |
221 } while (next != -1 && next != first); | |
222 return totalSides; | |
223 } | |
224 | |
225 int firstIndex = 0; | |
226 int firstInner = 0; | |
227 | |
228 void ConvexHull_Test() { | |
229 for (size_t index = firstIndex; index < cubicDataSet_count; ++index) { | |
230 const CubicDataSet& set = cubicDataSet[index]; | |
231 for (size_t inner = firstInner; inner < set.size; ++inner) { | |
232 const Cubic& cubic = set.data[inner]; | |
233 char order[4], cmpOrder[4]; | |
234 int cmp = rotate_to_hull(cubic, cmpOrder, index, inner); | |
235 if (cmp < 3) { | |
236 continue; | |
237 } | |
238 int result = convex_hull(cubic, order); | |
239 if (cmp != result) { | |
240 SkDebugf("%s [%d,%d] result=%d cmp=%d\n", __FUNCTION__, | |
241 (int)index, (int)inner, result, cmp); | |
242 continue; | |
243 } | |
244 // check for same indices | |
245 char pts = 0; | |
246 char cmpPts = 0; | |
247 int pt, bit; | |
248 for (pt = 0; pt < cmp; ++pt) { | |
249 if (pts & 1 << order[pt]) { | |
250 SkDebugf("%s [%d,%d] duplicate index in order: %d,%d,%d", | |
251 __FUNCTION__, (int)index, (int)inner, | |
252 order[0], order[1], order[2]); | |
253 if (cmp == 4) { | |
254 SkDebugf(",%d", order[3]); | |
255 } | |
256 SkDebugf("\n"); | |
257 goto next; | |
258 } | |
259 if (cmpPts & 1 << cmpOrder[pt]) { | |
260 SkDebugf("%s [%d,%d] duplicate index in order: %d,%d,%d", | |
261 __FUNCTION__, (int)index, (int)inner, | |
262 cmpOrder[0], cmpOrder[1], cmpOrder[2]); | |
263 if (cmp == 4) { | |
264 SkDebugf(",%d", cmpOrder[3]); | |
265 } | |
266 SkDebugf("\n"); | |
267 goto next; | |
268 } | |
269 pts |= 1 << order[pt]; | |
270 cmpPts |= 1 << cmpOrder[pt]; | |
271 } | |
272 for (bit = 0; bit < 4; ++bit) { | |
273 if (pts & 1 << bit) { | |
274 continue; | |
275 } | |
276 for (pt = 0; pt < cmp; ++pt) { | |
277 if (order[pt] == bit) { | |
278 continue; | |
279 } | |
280 if (cubic[order[pt]] == cubic[bit]) { | |
281 pts |= 1 << bit; | |
282 } | |
283 } | |
284 } | |
285 for (bit = 0; bit < 4; ++bit) { | |
286 if (cmpPts & 1 << bit) { | |
287 continue; | |
288 } | |
289 for (pt = 0; pt < cmp; ++pt) { | |
290 if (cmpOrder[pt] == bit) { | |
291 continue; | |
292 } | |
293 if (cubic[cmpOrder[pt]] == cubic[bit]) { | |
294 cmpPts |= 1 << bit; | |
295 } | |
296 } | |
297 } | |
298 if (pts != cmpPts) { | |
299 SkDebugf("%s [%d,%d] mismatch indices: order=%d,%d,%d", | |
300 __FUNCTION__, (int)index, (int)inner, | |
301 order[0], order[1], order[2]); | |
302 if (cmp == 4) { | |
303 SkDebugf(",%d", order[3]); | |
304 } | |
305 SkDebugf(" cmpOrder=%d,%d,%d", cmpOrder[0], cmpOrder[1], cmpOrde
r[2]); | |
306 if (cmp == 4) { | |
307 SkDebugf(",%d", cmpOrder[3]); | |
308 } | |
309 SkDebugf("\n"); | |
310 continue; | |
311 } | |
312 if (cmp == 4) { // check for bow ties | |
313 int match = 0; | |
314 while (cmpOrder[match] != order[0]) { | |
315 ++match; | |
316 } | |
317 if (cmpOrder[match ^ 2] != order[2]) { | |
318 SkDebugf("%s [%d,%d] bowtie mismatch: order=%d,%d,%d,%d" | |
319 " cmpOrder=%d,%d,%d,%d\n", | |
320 __FUNCTION__, (int)index, (int)inner, | |
321 order[0], order[1], order[2], order[3], | |
322 cmpOrder[0], cmpOrder[1], cmpOrder[2], cmpOrder[3]); | |
323 } | |
324 } | |
325 next: | |
326 ; | |
327 } | |
328 } | |
329 } | |
330 | |
331 const double a = 1.0/3; | |
332 const double b = 2.0/3; | |
333 | |
334 const Cubic x_cubic[] = { | |
335 {{0, 0}, {a, 0}, {b, 0}, {1, 0}}, // 0 | |
336 {{0, 0}, {a, 0}, {b, 0}, {1, 1}}, // 1 | |
337 {{0, 0}, {a, 0}, {b, 1}, {1, 0}}, // 2 | |
338 {{0, 0}, {a, 0}, {b, 1}, {1, 1}}, // 3 | |
339 {{0, 0}, {a, 1}, {b, 0}, {1, 0}}, // 4 | |
340 {{0, 0}, {a, 1}, {b, 0}, {1, 1}}, // 5 | |
341 {{0, 0}, {a, 1}, {b, 1}, {1, 0}}, // 6 | |
342 {{0, 0}, {a, 1}, {b, 1}, {1, 1}}, // 7 | |
343 {{0, 1}, {a, 0}, {b, 0}, {1, 0}}, // 8 | |
344 {{0, 1}, {a, 0}, {b, 0}, {1, 1}}, // 9 | |
345 {{0, 1}, {a, 0}, {b, 1}, {1, 0}}, // 10 | |
346 {{0, 1}, {a, 0}, {b, 1}, {1, 1}}, // 11 | |
347 {{0, 1}, {a, 1}, {b, 0}, {1, 0}}, // 12 | |
348 {{0, 1}, {a, 1}, {b, 0}, {1, 1}}, // 13 | |
349 {{0, 1}, {a, 1}, {b, 1}, {1, 0}}, // 14 | |
350 {{0, 1}, {a, 1}, {b, 1}, {1, 1}}, // 15 | |
351 }; | |
352 | |
353 size_t x_cubic_count = sizeof(x_cubic) / sizeof(x_cubic[0]); | |
354 | |
355 static int first_x_test = 0; | |
356 | |
357 void ConvexHull_X_Test() { | |
358 for (size_t index = first_x_test; index < x_cubic_count; ++index) { | |
359 const Cubic& cubic = x_cubic[index]; | |
360 char connectTo0[2] = {-1, -1}; | |
361 char connectTo3[2] = {-1, -1}; | |
362 convex_x_hull(cubic, connectTo0, connectTo3); | |
363 int idx, cmp; | |
364 for (idx = 0; idx < 2; ++idx) { | |
365 if (connectTo0[idx] >= 1 && connectTo0[idx] < 4) { | |
366 continue; | |
367 } else { | |
368 SkDebugf("%s connectTo0[idx]=%d", __FUNCTION__, connectTo0[idx])
; | |
369 } | |
370 if (connectTo3[idx] >= 0 && connectTo3[idx] < 3) { | |
371 continue; | |
372 } else { | |
373 SkDebugf("%s connectTo3[idx]=%d", __FUNCTION__, connectTo3[idx])
; | |
374 } | |
375 goto nextTest; | |
376 } | |
377 char rOrder[4]; | |
378 char cmpOrder[4]; | |
379 cmp = rotate_to_hull(cubic, cmpOrder, index, 0); | |
380 if (index == 0 || index == 15) { | |
381 // FIXME: make rotate_to_hull work for degenerate 2 edge hull cases | |
382 cmpOrder[0] = 0; | |
383 cmpOrder[1] = 3; | |
384 cmp = 2; | |
385 } | |
386 if (cmp < 3) { | |
387 // FIXME: make rotate_to_hull work for index == 3 etc | |
388 continue; | |
389 } | |
390 for (idx = 0; idx < cmp; ++idx) { | |
391 if (cmpOrder[idx] == 0) { | |
392 rOrder[0] = cmpOrder[(idx + 1) % cmp]; | |
393 rOrder[1] = cmpOrder[(idx + cmp - 1) % cmp]; | |
394 } else if (cmpOrder[idx] == 3) { | |
395 rOrder[2] = cmpOrder[(idx + 1) % cmp]; | |
396 rOrder[3] = cmpOrder[(idx + cmp - 1) % cmp]; | |
397 } | |
398 } | |
399 if (connectTo0[0] != connectTo0[1]) { | |
400 if (rOrder[0] == rOrder[1]) { | |
401 SkDebugf("%s [%d] (1) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
402 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
403 connectTo3[0], connectTo3[1], | |
404 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
405 continue; | |
406 } | |
407 int unused = 6 - connectTo0[0] - connectTo0[1]; | |
408 int rUnused = 6 - rOrder[0] - rOrder[1]; | |
409 if (unused != rUnused) { | |
410 SkDebugf("%s [%d] (2) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
411 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
412 connectTo3[0], connectTo3[1], | |
413 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
414 continue; | |
415 } | |
416 } else { | |
417 if (rOrder[0] != rOrder[1]) { | |
418 SkDebugf("%s [%d] (3) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
419 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
420 connectTo3[0], connectTo3[1], | |
421 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
422 continue; | |
423 } | |
424 if (connectTo0[0] != rOrder[0]) { | |
425 SkDebugf("%s [%d] (4) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
426 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
427 connectTo3[0], connectTo3[1], | |
428 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
429 continue; | |
430 } | |
431 } | |
432 if (connectTo3[0] != connectTo3[1]) { | |
433 if (rOrder[2] == rOrder[3]) { | |
434 SkDebugf("%s [%d] (5) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
435 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
436 connectTo3[0], connectTo3[1], | |
437 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
438 continue; | |
439 } | |
440 int unused = 6 - connectTo3[0] - connectTo3[1]; | |
441 int rUnused = 6 - rOrder[2] - rOrder[3]; | |
442 if (unused != rUnused) { | |
443 SkDebugf("%s [%d] (6) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
444 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
445 connectTo3[0], connectTo3[1], | |
446 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
447 continue; | |
448 } | |
449 } else { | |
450 if (rOrder[2] != rOrder[3]) { | |
451 SkDebugf("%s [%d] (7) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
452 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
453 connectTo3[0], connectTo3[1], | |
454 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
455 continue; | |
456 } | |
457 if (connectTo3[1] != rOrder[3]) { | |
458 SkDebugf("%s [%d] (8) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\
n", | |
459 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], | |
460 connectTo3[0], connectTo3[1], | |
461 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); | |
462 continue; | |
463 } | |
464 } | |
465 nextTest: | |
466 ; | |
467 } | |
468 } | |
OLD | NEW |