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
11const 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
19size_t convex_count = sizeof(convex) / sizeof(convex[0]);
20
21const 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
28size_t bowtie_count = sizeof(bowtie) / sizeof(bowtie[0]);
29
30const 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
37size_t arrow_count = sizeof(arrow) / sizeof(arrow[0]);
38
39const 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
48size_t three_count = sizeof(three) / sizeof(three[0]);
49
50const 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
72size_t triangle_count = sizeof(triangle) / sizeof(triangle[0]);
73
74const 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
85size_t cubicDataSet_count = sizeof(cubicDataSet) / sizeof(cubicDataSet[0]);
86
87typedef double Matrix3x2[3][2];
88
89static 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
106static void transform(const Cubic& cubic, const Matrix3x2& matrix, Cubic& rotPath) {
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
120static 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], sides[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] zeroes < 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] zeroes < 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] zeroes < 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] zeroes > 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] too many rays from one point\n",
196                        __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner);
197                }
198                outsidePtSet[inner] = outer;
199            }
200skipInner:
201            ;
202        }
203skip:
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
225int firstIndex = 0;
226int firstInner = 0;
227
228void 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], cmpOrder[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
331const double a = 1.0/3;
332const double b = 2.0/3;
333
334const 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
353size_t x_cubic_count = sizeof(x_cubic) / sizeof(x_cubic[0]);
354
355static int first_x_test = 0;
356
357void 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        }
465nextTest:
466        ;
467    }
468}
469