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 "PathOpsTestCommon.h"
8#include "SkIntersections.h"
9#include "SkPathOpsLine.h"
10#include "Test.h"
11
12// FIXME: add tests for intersecting, non-intersecting, degenerate, coincident
13static const SkDLine tests[][2] = {
14{{{{0.00010360032320022583, 1.0172703415155411}, {0.00014114845544099808, 1.0200891587883234}}},
15 {{{0.00010259449481964111, 1.017270140349865}, {0.00018215179443359375, 1.022890567779541}}}},
16
17#if 0
18    // these do intersect at a pair of points, but not close enough for check results liking
19    {{{{365.848175,5081.15186}, {368,5103}}}, {{{367.967712,5102.61084}, {368.278717,5105.71045}}}},
20#endif
21    {{{{30,20}, {30,50}}}, {{{24,30}, {36,30}}}},
22    {{{{323,193}, {-317,193}}}, {{{0,994}, {0,0}}}},
23    {{{{90,230}, {160,60}}}, {{{60,120}, {260,120}}}},
24    {{{{90,230}, {160,60}}}, {{{181.176468,120}, {135.294128,120}}}},
25    {{{{181.1764678955078125f, 120}, {186.3661956787109375f, 134.7042236328125f}}},
26     {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}},
27#if 0  // FIXME: these fail because one line is too short and appears quasi-coincident
28    {{{{158.000000, 926.000000}, {1108.00000, 926.000000}}},
29            {{{1108.00000, 926.000000}, {1108.00000, 925.999634}}}},
30    {{{{1108,926}, {1108,925.9996337890625}}}, {{{158,926}, {1108,926}}}},
31#endif
32    {{{{192, 4}, {243, 4}}}, {{{246, 4}, {189, 4}}}},
33    {{{{246, 4}, {189, 4}}}, {{{192, 4}, {243, 4}}}},
34    {{{{5, 0}, {0, 5}}}, {{{5, 4}, {1, 4}}}},
35    {{{{0, 0}, {1, 0}}}, {{{1, 0}, {0, 0}}}},
36    {{{{0, 0}, {0, 0}}}, {{{0, 0}, {1, 0}}}},
37    {{{{0, 1}, {0, 1}}}, {{{0, 0}, {0, 2}}}},
38    {{{{0, 0}, {1, 0}}}, {{{0, 0}, {2, 0}}}},
39    {{{{1, 1}, {2, 2}}}, {{{0, 0}, {3, 3}}}},
40    {{{{166.86950047022856, 112.69654129527828}, {166.86948801592692, 112.69655741235339}}},
41     {{{166.86960700313026, 112.6965477747386}, {166.86925794355412, 112.69656471103423}}}}
42};
43
44static const size_t tests_count = SK_ARRAY_COUNT(tests);
45
46static const SkDLine noIntersect[][2] = {
47   {{{{(double) (2 - 1e-6f),2}, {(double) (2 - 1e-6f),4}}},
48    {{{2,1}, {2,3}}}},
49
50    {{{{0, 0}, {1, 0}}}, {{{3, 0}, {2, 0}}}},
51    {{{{0, 0}, {0, 0}}}, {{{1, 0}, {2, 0}}}},
52    {{{{0, 1}, {0, 1}}}, {{{0, 3}, {0, 2}}}},
53    {{{{0, 0}, {1, 0}}}, {{{2, 0}, {3, 0}}}},
54    {{{{1, 1}, {2, 2}}}, {{{4, 4}, {3, 3}}}},
55};
56
57static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect);
58
59static const SkDLine coincidentTests[][2] = {
60   {{{ {-1.48383003e-006,-83}, {4.2268899e-014,-60} }},
61    {{ {9.5359502e-007,-60}, {5.08227985e-015,-83} }}},
62
63   {{{ { 10105, 2510 }, { 10123, 2509.98999f } }},
64    {{{10105, 2509.98999f}, { 10123, 2510 } }}},
65
66   {{ { { 0, 482.5 }, { -4.4408921e-016, 682.5 } } },
67    {{{0,683}, {0,482}}}},
68
69   {{{{1.77635684e-015,312}, {-1.24344979e-014,348}}},
70    {{{0,348}, {0,312}}}},
71
72   {{{{979.304871, 561}, {1036.69507, 291}}},
73    {{{985.681519, 531}, {982.159790, 547.568542}}}},
74
75   {{{{232.159805, 547.568542}, {235.681549, 531}}},
76    {{{286.695129,291}, {229.304855,561}}}},
77
78    {{{{186.3661956787109375f, 134.7042236328125f}, {187.8782806396484375f, 133.7258148193359375f}}},
79     {{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}},
80
81    {{{{235.681549, 531.000000}, {280.318420, 321.000000}}},
82     {{{286.695129, 291.000000}, {229.304855, 561.000000}}}},
83};
84
85static const size_t coincidentTests_count = SK_ARRAY_COUNT(coincidentTests);
86
87static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2,
88                          const SkIntersections& ts, bool nearAllowed) {
89    for (int i = 0; i < ts.used(); ++i) {
90        SkDPoint result1 = line1.ptAtT(ts[0][i]);
91        SkDPoint result2 = line2.ptAtT(ts[1][i]);
92        if (nearAllowed && result1.roughlyEqual(result2)) {
93            continue;
94        }
95        if (!result1.approximatelyEqual(result2) && !ts.nearlySame(i)) {
96            REPORTER_ASSERT(reporter, ts.used() != 1);
97            result2 = line2.ptAtT(ts[1][i ^ 1]);
98            if (!result1.approximatelyEqual(result2)) {
99                SkDebugf(".");
100            }
101            REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2));
102            REPORTER_ASSERT(reporter, result1.approximatelyEqual(ts.pt(i).asSkPoint()));
103        }
104    }
105}
106
107static void testOne(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2,
108        bool nearAllowed) {
109    SkASSERT(ValidLine(line1));
110    SkASSERT(ValidLine(line2));
111    SkIntersections i;
112    i.allowNear(nearAllowed);
113    int pts = i.intersect(line1, line2);
114    REPORTER_ASSERT(reporter, pts);
115    REPORTER_ASSERT(reporter, pts == i.used());
116    check_results(reporter, line1, line2, i, nearAllowed);
117    if (line1[0] == line1[1] || line2[0] == line2[1]) {
118        return;
119    }
120    if (line1[0].fY == line1[1].fY) {
121        double left = SkTMin(line1[0].fX, line1[1].fX);
122        double right = SkTMax(line1[0].fX, line1[1].fX);
123        SkIntersections ts;
124        ts.horizontal(line2, left, right, line1[0].fY, line1[0].fX != left);
125        check_results(reporter, line2, line1, ts, nearAllowed);
126    }
127    if (line2[0].fY == line2[1].fY) {
128        double left = SkTMin(line2[0].fX, line2[1].fX);
129        double right = SkTMax(line2[0].fX, line2[1].fX);
130        SkIntersections ts;
131        ts.horizontal(line1, left, right, line2[0].fY, line2[0].fX != left);
132        check_results(reporter, line1, line2, ts, nearAllowed);
133    }
134    if (line1[0].fX == line1[1].fX) {
135        double top = SkTMin(line1[0].fY, line1[1].fY);
136        double bottom = SkTMax(line1[0].fY, line1[1].fY);
137        SkIntersections ts;
138        ts.vertical(line2, top, bottom, line1[0].fX, line1[0].fY != top);
139        check_results(reporter, line2, line1, ts, nearAllowed);
140    }
141    if (line2[0].fX == line2[1].fX) {
142        double top = SkTMin(line2[0].fY, line2[1].fY);
143        double bottom = SkTMax(line2[0].fY, line2[1].fY);
144        SkIntersections ts;
145        ts.vertical(line1, top, bottom, line2[0].fX, line2[0].fY != top);
146        check_results(reporter, line1, line2, ts, nearAllowed);
147    }
148    reporter->bumpTestCount();
149}
150
151static void testOneCoincident(skiatest::Reporter* reporter, const SkDLine& line1,
152                              const SkDLine& line2) {
153    SkASSERT(ValidLine(line1));
154    SkASSERT(ValidLine(line2));
155    SkIntersections ts;
156    int pts = ts.intersect(line1, line2);
157    REPORTER_ASSERT(reporter, pts == 2);
158    REPORTER_ASSERT(reporter, pts == ts.used());
159    check_results(reporter, line1, line2, ts, false);
160    if (line1[0] == line1[1] || line2[0] == line2[1]) {
161        return;
162    }
163    if (line1[0].fY == line1[1].fY) {
164        double left = SkTMin(line1[0].fX, line1[1].fX);
165        double right = SkTMax(line1[0].fX, line1[1].fX);
166        SkIntersections ts;
167        ts.horizontal(line2, left, right, line1[0].fY, line1[0].fX != left);
168        REPORTER_ASSERT(reporter, pts == 2);
169        REPORTER_ASSERT(reporter, pts == ts.used());
170        check_results(reporter, line2, line1, ts, false);
171    }
172    if (line2[0].fY == line2[1].fY) {
173        double left = SkTMin(line2[0].fX, line2[1].fX);
174        double right = SkTMax(line2[0].fX, line2[1].fX);
175        SkIntersections ts;
176        ts.horizontal(line1, left, right, line2[0].fY, line2[0].fX != left);
177        REPORTER_ASSERT(reporter, pts == 2);
178        REPORTER_ASSERT(reporter, pts == ts.used());
179        check_results(reporter, line1, line2, ts, false);
180    }
181    if (line1[0].fX == line1[1].fX) {
182        double top = SkTMin(line1[0].fY, line1[1].fY);
183        double bottom = SkTMax(line1[0].fY, line1[1].fY);
184        SkIntersections ts;
185        ts.vertical(line2, top, bottom, line1[0].fX, line1[0].fY != top);
186        REPORTER_ASSERT(reporter, pts == 2);
187        REPORTER_ASSERT(reporter, pts == ts.used());
188        check_results(reporter, line2, line1, ts, false);
189    }
190    if (line2[0].fX == line2[1].fX) {
191        double top = SkTMin(line2[0].fY, line2[1].fY);
192        double bottom = SkTMax(line2[0].fY, line2[1].fY);
193        SkIntersections ts;
194        ts.vertical(line1, top, bottom, line2[0].fX, line2[0].fY != top);
195        REPORTER_ASSERT(reporter, pts == 2);
196        REPORTER_ASSERT(reporter, pts == ts.used());
197        check_results(reporter, line1, line2, ts, false);
198    }
199    reporter->bumpTestCount();
200}
201
202DEF_TEST(PathOpsLineIntersection, reporter) {
203    size_t index;
204    for (index = 0; index < coincidentTests_count; ++index) {
205        const SkDLine& line1 = coincidentTests[index][0];
206        const SkDLine& line2 = coincidentTests[index][1];
207        testOneCoincident(reporter, line1, line2);
208    }
209    for (index = 0; index < tests_count; ++index) {
210        const SkDLine& line1 = tests[index][0];
211        const SkDLine& line2 = tests[index][1];
212        testOne(reporter, line1, line2, true);
213    }
214    for (index = 0; index < noIntersect_count; ++index) {
215        const SkDLine& line1 = noIntersect[index][0];
216        const SkDLine& line2 = noIntersect[index][1];
217        SkIntersections ts;
218        int pts = ts.intersect(line1, line2);
219        REPORTER_ASSERT(reporter, !pts);
220        REPORTER_ASSERT(reporter, pts == ts.used());
221        reporter->bumpTestCount();
222    }
223}
224
225DEF_TEST(PathOpsLineIntersectionOneOff, reporter) {
226    int index = 0;
227    SkASSERT(index < (int) tests_count);
228    testOne(reporter, tests[index][0], tests[index][1], true);
229}
230
231DEF_TEST(PathOpsLineIntersectionExactOneOff, reporter) {
232    int index = 0;
233    SkASSERT(index < (int) tests_count);
234    testOne(reporter, tests[index][0], tests[index][1], false);
235}
236
237DEF_TEST(PathOpsLineIntersectionOneCoincident, reporter) {
238    int index = 0;
239    SkASSERT(index < (int) coincidentTests_count);
240    const SkDLine& line1 = coincidentTests[index][0];
241    const SkDLine& line2 = coincidentTests[index][1];
242    testOneCoincident(reporter, line1, line2);
243}
244