1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkDLineIntersection.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,354 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkIntersections.h"
1.11 +#include "SkPathOpsLine.h"
1.12 +
1.13 +/* Determine the intersection point of two lines. This assumes the lines are not parallel,
1.14 + and that that the lines are infinite.
1.15 + From http://en.wikipedia.org/wiki/Line-line_intersection
1.16 + */
1.17 +SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) {
1.18 + double axLen = a[1].fX - a[0].fX;
1.19 + double ayLen = a[1].fY - a[0].fY;
1.20 + double bxLen = b[1].fX - b[0].fX;
1.21 + double byLen = b[1].fY - b[0].fY;
1.22 + double denom = byLen * axLen - ayLen * bxLen;
1.23 + SkASSERT(denom);
1.24 + double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX;
1.25 + double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX;
1.26 + SkDPoint p;
1.27 + p.fX = (term1 * bxLen - axLen * term2) / denom;
1.28 + p.fY = (term1 * byLen - ayLen * term2) / denom;
1.29 + return p;
1.30 +}
1.31 +
1.32 +void SkIntersections::cleanUpCoincidence() {
1.33 + SkASSERT(fUsed == 2);
1.34 + // both t values are good
1.35 + bool startMatch = fT[0][0] == 0 && (fT[1][0] == 0 || fT[1][0] == 1);
1.36 + bool endMatch = fT[0][1] == 1 && (fT[1][1] == 0 || fT[1][1] == 1);
1.37 + if (startMatch || endMatch) {
1.38 + removeOne(startMatch);
1.39 + return;
1.40 + }
1.41 + // either t value is good
1.42 + bool pStartMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1;
1.43 + bool pEndMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1;
1.44 + removeOne(pStartMatch || !pEndMatch);
1.45 +}
1.46 +
1.47 +void SkIntersections::cleanUpParallelLines(bool parallel) {
1.48 + while (fUsed > 2) {
1.49 + removeOne(1);
1.50 + }
1.51 + if (fUsed == 2 && !parallel) {
1.52 + bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1;
1.53 + bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1;
1.54 + if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) {
1.55 + SkASSERT(startMatch || endMatch);
1.56 + removeOne(endMatch);
1.57 + }
1.58 + }
1.59 +}
1.60 +
1.61 +void SkIntersections::computePoints(const SkDLine& line, int used) {
1.62 + fPt[0] = line.ptAtT(fT[0][0]);
1.63 + if ((fUsed = used) == 2) {
1.64 + fPt[1] = line.ptAtT(fT[0][1]);
1.65 + }
1.66 +}
1.67 +
1.68 +int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
1.69 + fMax = 2;
1.70 + SkDVector aLen = a[1] - a[0];
1.71 + SkDVector bLen = b[1] - b[0];
1.72 + /* Slopes match when denom goes to zero:
1.73 + axLen / ayLen == bxLen / byLen
1.74 + (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
1.75 + byLen * axLen == ayLen * bxLen
1.76 + byLen * axLen - ayLen * bxLen == 0 ( == denom )
1.77 + */
1.78 + double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
1.79 + SkDVector ab0 = a[0] - b[0];
1.80 + double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
1.81 + double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
1.82 + numerA /= denom;
1.83 + numerB /= denom;
1.84 + int used;
1.85 + if (!approximately_zero(denom)) {
1.86 + fT[0][0] = numerA;
1.87 + fT[1][0] = numerB;
1.88 + used = 1;
1.89 + } else {
1.90 + /* See if the axis intercepts match:
1.91 + ay - ax * ayLen / axLen == by - bx * ayLen / axLen
1.92 + axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
1.93 + axLen * ay - ax * ayLen == axLen * by - bx * ayLen
1.94 + */
1.95 + if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
1.96 + aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
1.97 + return fUsed = 0;
1.98 + }
1.99 + // there's no great answer for intersection points for coincident rays, but return something
1.100 + fT[0][0] = fT[1][0] = 0;
1.101 + fT[1][0] = fT[1][1] = 1;
1.102 + used = 2;
1.103 + }
1.104 + computePoints(a, used);
1.105 + return fUsed;
1.106 +}
1.107 +
1.108 +// note that this only works if both lines are neither horizontal nor vertical
1.109 +int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
1.110 + fMax = 3; // note that we clean up so that there is no more than two in the end
1.111 + // see if end points intersect the opposite line
1.112 + double t;
1.113 + for (int iA = 0; iA < 2; ++iA) {
1.114 + if ((t = b.exactPoint(a[iA])) >= 0) {
1.115 + insert(iA, t, a[iA]);
1.116 + }
1.117 + }
1.118 + for (int iB = 0; iB < 2; ++iB) {
1.119 + if ((t = a.exactPoint(b[iB])) >= 0) {
1.120 + insert(t, iB, b[iB]);
1.121 + }
1.122 + }
1.123 + /* Determine the intersection point of two line segments
1.124 + Return FALSE if the lines don't intersect
1.125 + from: http://paulbourke.net/geometry/lineline2d/ */
1.126 + double axLen = a[1].fX - a[0].fX;
1.127 + double ayLen = a[1].fY - a[0].fY;
1.128 + double bxLen = b[1].fX - b[0].fX;
1.129 + double byLen = b[1].fY - b[0].fY;
1.130 + /* Slopes match when denom goes to zero:
1.131 + axLen / ayLen == bxLen / byLen
1.132 + (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
1.133 + byLen * axLen == ayLen * bxLen
1.134 + byLen * axLen - ayLen * bxLen == 0 ( == denom )
1.135 + */
1.136 + double axByLen = axLen * byLen;
1.137 + double ayBxLen = ayLen * bxLen;
1.138 + // detect parallel lines the same way here and in SkOpAngle operator <
1.139 + // so that non-parallel means they are also sortable
1.140 + bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen)
1.141 + : NotAlmostDequalUlps(axByLen, ayBxLen);
1.142 + if (unparallel && fUsed == 0) {
1.143 + double ab0y = a[0].fY - b[0].fY;
1.144 + double ab0x = a[0].fX - b[0].fX;
1.145 + double numerA = ab0y * bxLen - byLen * ab0x;
1.146 + double numerB = ab0y * axLen - ayLen * ab0x;
1.147 + double denom = axByLen - ayBxLen;
1.148 + if (between(0, numerA, denom) && between(0, numerB, denom)) {
1.149 + fT[0][0] = numerA / denom;
1.150 + fT[1][0] = numerB / denom;
1.151 + computePoints(a, 1);
1.152 + }
1.153 + }
1.154 + if (fAllowNear || !unparallel) {
1.155 + for (int iA = 0; iA < 2; ++iA) {
1.156 + if ((t = b.nearPoint(a[iA])) >= 0) {
1.157 + insert(iA, t, a[iA]);
1.158 + }
1.159 + }
1.160 + for (int iB = 0; iB < 2; ++iB) {
1.161 + if ((t = a.nearPoint(b[iB])) >= 0) {
1.162 + insert(t, iB, b[iB]);
1.163 + }
1.164 + }
1.165 + }
1.166 + cleanUpParallelLines(!unparallel);
1.167 + SkASSERT(fUsed <= 2);
1.168 + return fUsed;
1.169 +}
1.170 +
1.171 +static int horizontal_coincident(const SkDLine& line, double y) {
1.172 + double min = line[0].fY;
1.173 + double max = line[1].fY;
1.174 + if (min > max) {
1.175 + SkTSwap(min, max);
1.176 + }
1.177 + if (min > y || max < y) {
1.178 + return 0;
1.179 + }
1.180 + if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
1.181 + return 2;
1.182 + }
1.183 + return 1;
1.184 +}
1.185 +
1.186 +static double horizontal_intercept(const SkDLine& line, double y) {
1.187 + return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
1.188 +}
1.189 +
1.190 +int SkIntersections::horizontal(const SkDLine& line, double y) {
1.191 + fMax = 2;
1.192 + int horizontalType = horizontal_coincident(line, y);
1.193 + if (horizontalType == 1) {
1.194 + fT[0][0] = horizontal_intercept(line, y);
1.195 + } else if (horizontalType == 2) {
1.196 + fT[0][0] = 0;
1.197 + fT[0][1] = 1;
1.198 + }
1.199 + return fUsed = horizontalType;
1.200 +}
1.201 +
1.202 +int SkIntersections::horizontal(const SkDLine& line, double left, double right,
1.203 + double y, bool flipped) {
1.204 + fMax = 2;
1.205 + // see if end points intersect the opposite line
1.206 + double t;
1.207 + const SkDPoint leftPt = { left, y };
1.208 + if ((t = line.exactPoint(leftPt)) >= 0) {
1.209 + insert(t, (double) flipped, leftPt);
1.210 + }
1.211 + if (left != right) {
1.212 + const SkDPoint rightPt = { right, y };
1.213 + if ((t = line.exactPoint(rightPt)) >= 0) {
1.214 + insert(t, (double) !flipped, rightPt);
1.215 + }
1.216 + for (int index = 0; index < 2; ++index) {
1.217 + if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
1.218 + insert((double) index, flipped ? 1 - t : t, line[index]);
1.219 + }
1.220 + }
1.221 + }
1.222 + int result = horizontal_coincident(line, y);
1.223 + if (result == 1 && fUsed == 0) {
1.224 + fT[0][0] = horizontal_intercept(line, y);
1.225 + double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
1.226 + if (between(left, xIntercept, right)) {
1.227 + fT[1][0] = (xIntercept - left) / (right - left);
1.228 + if (flipped) {
1.229 + // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
1.230 + for (int index = 0; index < result; ++index) {
1.231 + fT[1][index] = 1 - fT[1][index];
1.232 + }
1.233 + }
1.234 + fPt[0].fX = xIntercept;
1.235 + fPt[0].fY = y;
1.236 + fUsed = 1;
1.237 + }
1.238 + }
1.239 + if (fAllowNear || result == 2) {
1.240 + if ((t = line.nearPoint(leftPt)) >= 0) {
1.241 + insert(t, (double) flipped, leftPt);
1.242 + }
1.243 + if (left != right) {
1.244 + const SkDPoint rightPt = { right, y };
1.245 + if ((t = line.nearPoint(rightPt)) >= 0) {
1.246 + insert(t, (double) !flipped, rightPt);
1.247 + }
1.248 + for (int index = 0; index < 2; ++index) {
1.249 + if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
1.250 + insert((double) index, flipped ? 1 - t : t, line[index]);
1.251 + }
1.252 + }
1.253 + }
1.254 + }
1.255 + cleanUpParallelLines(result == 2);
1.256 + return fUsed;
1.257 +}
1.258 +
1.259 +static int vertical_coincident(const SkDLine& line, double x) {
1.260 + double min = line[0].fX;
1.261 + double max = line[1].fX;
1.262 + if (min > max) {
1.263 + SkTSwap(min, max);
1.264 + }
1.265 + if (!precisely_between(min, x, max)) {
1.266 + return 0;
1.267 + }
1.268 + if (AlmostEqualUlps(min, max)) {
1.269 + return 2;
1.270 + }
1.271 + return 1;
1.272 +}
1.273 +
1.274 +static double vertical_intercept(const SkDLine& line, double x) {
1.275 + return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
1.276 +}
1.277 +
1.278 +int SkIntersections::vertical(const SkDLine& line, double x) {
1.279 + fMax = 2;
1.280 + int verticalType = vertical_coincident(line, x);
1.281 + if (verticalType == 1) {
1.282 + fT[0][0] = vertical_intercept(line, x);
1.283 + } else if (verticalType == 2) {
1.284 + fT[0][0] = 0;
1.285 + fT[0][1] = 1;
1.286 + }
1.287 + return fUsed = verticalType;
1.288 +}
1.289 +
1.290 +int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
1.291 + double x, bool flipped) {
1.292 + fMax = 2;
1.293 + // see if end points intersect the opposite line
1.294 + double t;
1.295 + SkDPoint topPt = { x, top };
1.296 + if ((t = line.exactPoint(topPt)) >= 0) {
1.297 + insert(t, (double) flipped, topPt);
1.298 + }
1.299 + if (top != bottom) {
1.300 + SkDPoint bottomPt = { x, bottom };
1.301 + if ((t = line.exactPoint(bottomPt)) >= 0) {
1.302 + insert(t, (double) !flipped, bottomPt);
1.303 + }
1.304 + for (int index = 0; index < 2; ++index) {
1.305 + if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
1.306 + insert((double) index, flipped ? 1 - t : t, line[index]);
1.307 + }
1.308 + }
1.309 + }
1.310 + int result = vertical_coincident(line, x);
1.311 + if (result == 1 && fUsed == 0) {
1.312 + fT[0][0] = vertical_intercept(line, x);
1.313 + double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
1.314 + if (between(top, yIntercept, bottom)) {
1.315 + fT[1][0] = (yIntercept - top) / (bottom - top);
1.316 + if (flipped) {
1.317 + // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
1.318 + for (int index = 0; index < result; ++index) {
1.319 + fT[1][index] = 1 - fT[1][index];
1.320 + }
1.321 + }
1.322 + fPt[0].fX = x;
1.323 + fPt[0].fY = yIntercept;
1.324 + fUsed = 1;
1.325 + }
1.326 + }
1.327 + if (fAllowNear || result == 2) {
1.328 + if ((t = line.nearPoint(topPt)) >= 0) {
1.329 + insert(t, (double) flipped, topPt);
1.330 + }
1.331 + if (top != bottom) {
1.332 + SkDPoint bottomPt = { x, bottom };
1.333 + if ((t = line.nearPoint(bottomPt)) >= 0) {
1.334 + insert(t, (double) !flipped, bottomPt);
1.335 + }
1.336 + for (int index = 0; index < 2; ++index) {
1.337 + if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
1.338 + insert((double) index, flipped ? 1 - t : t, line[index]);
1.339 + }
1.340 + }
1.341 + }
1.342 + }
1.343 + cleanUpParallelLines(result == 2);
1.344 + return fUsed;
1.345 +}
1.346 +
1.347 +// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
1.348 +// 4 subs, 2 muls, 1 cmp
1.349 +static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) {
1.350 + return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX);
1.351 +}
1.352 +
1.353 +// 16 subs, 8 muls, 6 cmps
1.354 +bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) {
1.355 + return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1])
1.356 + && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]);
1.357 +}
