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