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