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 "include/core/SkTypes.h"
8 #include "src/pathops/SkIntersections.h"
9 #include "src/pathops/SkPathOpsLine.h"
10 #include "src/pathops/SkPathOpsPoint.h"
11 #include "src/pathops/SkPathOpsTypes.h"
12
13 #include <cmath>
14 #include <cstdint>
15 #include <utility>
16
cleanUpParallelLines(bool parallel)17 void SkIntersections::cleanUpParallelLines(bool parallel) {
18 while (fUsed > 2) {
19 removeOne(1);
20 }
21 if (fUsed == 2 && !parallel) {
22 bool startMatch = fT[0][0] == 0 || zero_or_one(fT[1][0]);
23 bool endMatch = fT[0][1] == 1 || zero_or_one(fT[1][1]);
24 if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) {
25 SkASSERT(startMatch || endMatch);
26 if (startMatch && endMatch && (fT[0][0] != 0 || !zero_or_one(fT[1][0]))
27 && fT[0][1] == 1 && zero_or_one(fT[1][1])) {
28 removeOne(0);
29 } else {
30 removeOne(endMatch);
31 }
32 }
33 }
34 if (fUsed == 2) {
35 fIsCoincident[0] = fIsCoincident[1] = 0x03;
36 }
37 }
38
computePoints(const SkDLine & line,int used)39 void SkIntersections::computePoints(const SkDLine& line, int used) {
40 fPt[0] = line.ptAtT(fT[0][0]);
41 if ((fUsed = used) == 2) {
42 fPt[1] = line.ptAtT(fT[0][1]);
43 }
44 }
45
intersectRay(const SkDLine & a,const SkDLine & b)46 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
47 fMax = 2;
48 SkDVector aLen = a[1] - a[0];
49 SkDVector bLen = b[1] - b[0];
50 /* Slopes match when denom goes to zero:
51 axLen / ayLen == bxLen / byLen
52 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
53 byLen * axLen == ayLen * bxLen
54 byLen * axLen - ayLen * bxLen == 0 ( == denom )
55 */
56 double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
57 int used;
58 if (!approximately_zero(denom)) {
59 SkDVector ab0 = a[0] - b[0];
60 double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
61 double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
62 numerA /= denom;
63 numerB /= denom;
64 fT[0][0] = numerA;
65 fT[1][0] = numerB;
66 used = 1;
67 } else {
68 /* See if the axis intercepts match:
69 ay - ax * ayLen / axLen == by - bx * ayLen / axLen
70 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
71 axLen * ay - ax * ayLen == axLen * by - bx * ayLen
72 */
73 if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
74 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
75 return fUsed = 0;
76 }
77 // there's no great answer for intersection points for coincident rays, but return something
78 fT[0][0] = fT[1][0] = 0;
79 fT[1][0] = fT[1][1] = 1;
80 used = 2;
81 }
82 computePoints(a, used);
83 return fUsed;
84 }
85
86 // note that this only works if both lines are neither horizontal nor vertical
intersect(const SkDLine & a,const SkDLine & b)87 int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
88 fMax = 3; // note that we clean up so that there is no more than two in the end
89 // see if end points intersect the opposite line
90 double t;
91 for (int iA = 0; iA < 2; ++iA) {
92 if ((t = b.exactPoint(a[iA])) >= 0) {
93 insert(iA, t, a[iA]);
94 }
95 }
96 for (int iB = 0; iB < 2; ++iB) {
97 if ((t = a.exactPoint(b[iB])) >= 0) {
98 insert(t, iB, b[iB]);
99 }
100 }
101 /* Determine the intersection point of two line segments
102 Return FALSE if the lines don't intersect
103 from: http://paulbourke.net/geometry/lineline2d/ */
104 double axLen = a[1].fX - a[0].fX;
105 double ayLen = a[1].fY - a[0].fY;
106 double bxLen = b[1].fX - b[0].fX;
107 double byLen = b[1].fY - b[0].fY;
108 /* Slopes match when denom goes to zero:
109 axLen / ayLen == bxLen / byLen
110 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
111 byLen * axLen == ayLen * bxLen
112 byLen * axLen - ayLen * bxLen == 0 ( == denom )
113 */
114 double axByLen = axLen * byLen;
115 double ayBxLen = ayLen * bxLen;
116 // detect parallel lines the same way here and in SkOpAngle operator <
117 // so that non-parallel means they are also sortable
118 bool unparallel = fAllowNear ? NotAlmostEqualUlps_Pin(axByLen, ayBxLen)
119 : NotAlmostDequalUlps(axByLen, ayBxLen);
120 if (unparallel && fUsed == 0) {
121 double ab0y = a[0].fY - b[0].fY;
122 double ab0x = a[0].fX - b[0].fX;
123 double numerA = ab0y * bxLen - byLen * ab0x;
124 double numerB = ab0y * axLen - ayLen * ab0x;
125 double denom = axByLen - ayBxLen;
126 if (between(0, numerA, denom) && between(0, numerB, denom)) {
127 fT[0][0] = numerA / denom;
128 fT[1][0] = numerB / denom;
129 computePoints(a, 1);
130 }
131 }
132 /* Allow tracking that both sets of end points are near each other -- the lines are entirely
133 coincident -- even when the end points are not exactly the same.
134 Mark this as a 'wild card' for the end points, so that either point is considered totally
135 coincident. Then, avoid folding the lines over each other, but allow either end to mate
136 to the next set of lines.
137 */
138 if (fAllowNear || !unparallel) {
139 double aNearB[2];
140 double bNearA[2];
141 bool aNotB[2] = {false, false};
142 bool bNotA[2] = {false, false};
143 int nearCount = 0;
144 for (int index = 0; index < 2; ++index) {
145 aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
146 nearCount += t >= 0;
147 bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
148 nearCount += t >= 0;
149 }
150 if (nearCount > 0) {
151 // Skip if each segment contributes to one end point.
152 if (nearCount != 2 || aNotB[0] == aNotB[1]) {
153 for (int iA = 0; iA < 2; ++iA) {
154 if (!aNotB[iA]) {
155 continue;
156 }
157 int nearer = aNearB[iA] > 0.5;
158 if (!bNotA[nearer]) {
159 continue;
160 }
161 SkASSERT(a[iA] != b[nearer]);
162 SkOPASSERT(iA == (bNearA[nearer] > 0.5));
163 insertNear(iA, nearer, a[iA], b[nearer]);
164 aNearB[iA] = -1;
165 bNearA[nearer] = -1;
166 nearCount -= 2;
167 }
168 }
169 if (nearCount > 0) {
170 for (int iA = 0; iA < 2; ++iA) {
171 if (aNearB[iA] >= 0) {
172 insert(iA, aNearB[iA], a[iA]);
173 }
174 }
175 for (int iB = 0; iB < 2; ++iB) {
176 if (bNearA[iB] >= 0) {
177 insert(bNearA[iB], iB, b[iB]);
178 }
179 }
180 }
181 }
182 }
183 cleanUpParallelLines(!unparallel);
184 SkASSERT(fUsed <= 2);
185 return fUsed;
186 }
187
horizontal_coincident(const SkDLine & line,double y)188 static int horizontal_coincident(const SkDLine& line, double y) {
189 double min = line[0].fY;
190 double max = line[1].fY;
191 if (min > max) {
192 using std::swap;
193 swap(min, max);
194 }
195 if (min > y || max < y) {
196 return 0;
197 }
198 if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
199 return 2;
200 }
201 return 1;
202 }
203
HorizontalIntercept(const SkDLine & line,double y)204 double SkIntersections::HorizontalIntercept(const SkDLine& line, double y) {
205 SkASSERT(line[1].fY != line[0].fY);
206 return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
207 }
208
horizontal(const SkDLine & line,double left,double right,double y,bool flipped)209 int SkIntersections::horizontal(const SkDLine& line, double left, double right,
210 double y, bool flipped) {
211 fMax = 3; // clean up parallel at the end will limit the result to 2 at the most
212 // see if end points intersect the opposite line
213 double t;
214 const SkDPoint leftPt = { left, y };
215 if ((t = line.exactPoint(leftPt)) >= 0) {
216 insert(t, (double) flipped, leftPt);
217 }
218 if (left != right) {
219 const SkDPoint rightPt = { right, y };
220 if ((t = line.exactPoint(rightPt)) >= 0) {
221 insert(t, (double) !flipped, rightPt);
222 }
223 for (int index = 0; index < 2; ++index) {
224 if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
225 insert((double) index, flipped ? 1 - t : t, line[index]);
226 }
227 }
228 }
229 int result = horizontal_coincident(line, y);
230 if (result == 1 && fUsed == 0) {
231 fT[0][0] = HorizontalIntercept(line, y);
232 double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
233 if (between(left, xIntercept, right)) {
234 fT[1][0] = (xIntercept - left) / (right - left);
235 if (flipped) {
236 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
237 for (int index = 0; index < result; ++index) {
238 fT[1][index] = 1 - fT[1][index];
239 }
240 }
241 fPt[0].fX = xIntercept;
242 fPt[0].fY = y;
243 fUsed = 1;
244 }
245 }
246 if (fAllowNear || result == 2) {
247 if ((t = line.nearPoint(leftPt, nullptr)) >= 0) {
248 insert(t, (double) flipped, leftPt);
249 }
250 if (left != right) {
251 const SkDPoint rightPt = { right, y };
252 if ((t = line.nearPoint(rightPt, nullptr)) >= 0) {
253 insert(t, (double) !flipped, rightPt);
254 }
255 for (int index = 0; index < 2; ++index) {
256 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
257 insert((double) index, flipped ? 1 - t : t, line[index]);
258 }
259 }
260 }
261 }
262 cleanUpParallelLines(result == 2);
263 return fUsed;
264 }
265
vertical_coincident(const SkDLine & line,double x)266 static int vertical_coincident(const SkDLine& line, double x) {
267 double min = line[0].fX;
268 double max = line[1].fX;
269 if (min > max) {
270 using std::swap;
271 swap(min, max);
272 }
273 if (!precisely_between(min, x, max)) {
274 return 0;
275 }
276 if (AlmostEqualUlps(min, max)) {
277 return 2;
278 }
279 return 1;
280 }
281
VerticalIntercept(const SkDLine & line,double x)282 double SkIntersections::VerticalIntercept(const SkDLine& line, double x) {
283 SkASSERT(line[1].fX != line[0].fX);
284 return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
285 }
286
vertical(const SkDLine & line,double top,double bottom,double x,bool flipped)287 int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
288 double x, bool flipped) {
289 fMax = 3; // cleanup parallel lines will bring this back line
290 // see if end points intersect the opposite line
291 double t;
292 SkDPoint topPt = { x, top };
293 if ((t = line.exactPoint(topPt)) >= 0) {
294 insert(t, (double) flipped, topPt);
295 }
296 if (top != bottom) {
297 SkDPoint bottomPt = { x, bottom };
298 if ((t = line.exactPoint(bottomPt)) >= 0) {
299 insert(t, (double) !flipped, bottomPt);
300 }
301 for (int index = 0; index < 2; ++index) {
302 if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
303 insert((double) index, flipped ? 1 - t : t, line[index]);
304 }
305 }
306 }
307 int result = vertical_coincident(line, x);
308 if (result == 1 && fUsed == 0) {
309 fT[0][0] = VerticalIntercept(line, x);
310 double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
311 if (between(top, yIntercept, bottom)) {
312 fT[1][0] = (yIntercept - top) / (bottom - top);
313 if (flipped) {
314 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
315 for (int index = 0; index < result; ++index) {
316 fT[1][index] = 1 - fT[1][index];
317 }
318 }
319 fPt[0].fX = x;
320 fPt[0].fY = yIntercept;
321 fUsed = 1;
322 }
323 }
324 if (fAllowNear || result == 2) {
325 if ((t = line.nearPoint(topPt, nullptr)) >= 0) {
326 insert(t, (double) flipped, topPt);
327 }
328 if (top != bottom) {
329 SkDPoint bottomPt = { x, bottom };
330 if ((t = line.nearPoint(bottomPt, nullptr)) >= 0) {
331 insert(t, (double) !flipped, bottomPt);
332 }
333 for (int index = 0; index < 2; ++index) {
334 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
335 insert((double) index, flipped ? 1 - t : t, line[index]);
336 }
337 }
338 }
339 }
340 cleanUpParallelLines(result == 2);
341 SkASSERT(fUsed <= 2);
342 return fUsed;
343 }
344
345