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