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