19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.com#include "CurveIntersection.h" 8fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com#include "Intersections.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "LineIntersection.h" 1045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com#include "LineUtilities.h" 11639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 1273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com/* Determine the intersection point of two lines. This assumes the lines are not parallel, 1373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com and that that the lines are infinite. 1473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com From http://en.wikipedia.org/wiki/Line-line_intersection 1573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com */ 1673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid lineIntersect(const _Line& a, const _Line& b, _Point& p) { 1773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double axLen = a[1].x - a[0].x; 1873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double ayLen = a[1].y - a[0].y; 1973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double bxLen = b[1].x - b[0].x; 2073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double byLen = b[1].y - b[0].y; 2173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double denom = byLen * axLen - ayLen * bxLen; 22aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(denom); 2373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double term1 = a[1].x * a[0].y - a[1].y * a[0].x; 2473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double term2 = b[1].x * b[0].y - b[1].y * b[0].x; 2573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com p.x = (term1 * bxLen - axLen * term2) / denom; 2673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com p.y = (term1 * byLen - ayLen * term2) / denom; 2773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 2945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comstatic int computePoints(const _Line& a, int used, Intersections& i) { 3045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fPt[0] = xy_at_t(a, i.fT[0][0]); 3145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com if ((i.fUsed = used) == 2) { 3245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fPt[1] = xy_at_t(a, i.fT[0][1]); 3345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com } 3445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return i.fUsed; 3545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com} 3645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com/* 38639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Determine the intersection point of two line segments 39639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Return FALSE if the lines don't intersect 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com from: http://paulbourke.net/geometry/lineline2d/ 4173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com */ 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 4345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.comint intersect(const _Line& a, const _Line& b, Intersections& i) { 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double axLen = a[1].x - a[0].x; 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ayLen = a[1].y - a[0].y; 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double bxLen = b[1].x - b[0].x; 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double byLen = b[1].y - b[0].y; 48d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com /* Slopes match when denom goes to zero: 49c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com axLen / ayLen == bxLen / byLen 50c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 51c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com byLen * axLen == ayLen * bxLen 52c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com byLen * axLen - ayLen * bxLen == 0 ( == denom ) 53c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */ 5473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double denom = byLen * axLen - ayLen * bxLen; 55639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab0y = a[0].y - b[0].y; 56639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double ab0x = a[0].x - b[0].x; 57639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double numerA = ab0y * bxLen - byLen * ab0x; 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double numerB = ab0y * axLen - ayLen * ab0x; 59f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com bool mayNotOverlap = (numerA < 0 && denom > numerA) || (numerA > 0 && denom < numerA) 60f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com || (numerB < 0 && denom > numerB) || (numerB > 0 && denom < numerB); 61f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com numerA /= denom; 62f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com numerB /= denom; 63beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com if ((!approximately_zero(denom) || (!approximately_zero_inverse(numerA) 64beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com && !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA) 65beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com && !sk_double_isnan(numerB)) { 66f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (mayNotOverlap) { 67f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com return 0; 68f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 6945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[0][0] = numerA; 7045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[1][0] = numerB; 7145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fPt[0] = xy_at_t(a, numerA); 7245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(a, 1, i); 73f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 74f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com /* See if the axis intercepts match: 75f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com ay - ax * ayLen / axLen == by - bx * ayLen / axLen 76f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) 77f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com axLen * ay - ax * ayLen == axLen * by - bx * ayLen 78f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com */ 79f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com // FIXME: need to use AlmostEqualUlps variant instead 80f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (!approximately_equal_squared(axLen * a[0].y - ayLen * a[0].x, 81f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com axLen * b[0].y - ayLen * b[0].x)) { 82c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 0; 83639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 84f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com const double* aPtr; 85f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com const double* bPtr; 86f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (fabs(axLen) > fabs(ayLen) || fabs(bxLen) > fabs(byLen)) { 87f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com aPtr = &a[0].x; 88f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com bPtr = &b[0].x; 89f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else { 90f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com aPtr = &a[0].y; 91f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com bPtr = &b[0].y; 92f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 93f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double a0 = aPtr[0]; 94f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double a1 = aPtr[2]; 95f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double b0 = bPtr[0]; 96f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double b1 = bPtr[2]; 97f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com // OPTIMIZATION: restructure to reject before the divide 98f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com // e.g., if ((a0 - b0) * (a0 - a1) < 0 || abs(a0 - b0) > abs(a0 - a1)) 99f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com // (except efficient) 100f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double aDenom = a0 - a1; 101f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (approximately_zero(aDenom)) { 102f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (!between(b0, a0, b1)) { 103f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com return 0; 104f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 10545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[0][0] = i.fT[0][1] = 0; 106f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else { 107f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double at0 = (a0 - b0) / aDenom; 108f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double at1 = (a0 - b1) / aDenom; 109f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { 110f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com return 0; 111f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } 11245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); 11345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); 114c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 115f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com double bDenom = b0 - b1; 116f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com if (approximately_zero(bDenom)) { 11745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[1][0] = i.fT[1][1] = 0; 118f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com } else { 119f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com int bIn = aDenom * bDenom < 0; 12045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / bDenom, 1.0), 0.0); 12145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com i.fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / bDenom, 1.0), 0.0); 122c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 12345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com bool second = fabs(i.fT[0][0] - i.fT[0][1]) > FLT_EPSILON; 12445a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com SkASSERT((fabs(i.fT[1][0] - i.fT[1][1]) <= FLT_EPSILON) ^ second); 12545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(a, 1 + second, i); 126639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 127639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 128c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint horizontalIntersect(const _Line& line, double y, double tRange[2]) { 129c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double min = line[0].y; 130c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double max = line[1].y; 131c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (min > max) { 132aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(min, max); 133c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 134c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (min > y || max < y) { 135c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 0; 136c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1376d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (AlmostEqualUlps(min, max)) { 138c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com tRange[0] = 0; 139c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com tRange[1] = 1; 140c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 2; 141c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 142c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com tRange[0] = (y - line[0].y) / (line[1].y - line[0].y); 143c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 1; 144c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 145639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 1462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZATION Given: dy = line[1].y - line[0].y 1472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// and: xIntercept / (y - line[0].y) == (line[1].x - line[0].x) / dy 1482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// then: xIntercept * dy == (line[1].x - line[0].x) * (y - line[0].y) 1492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// Assuming that dy is always > 0, the line segment intercepts if: 1502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// left * dy <= xIntercept * dy <= right * dy 1512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// thus: left * dy <= (line[1].x - line[0].x) * (y - line[0].y) <= right * dy 1522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// (clever as this is, it does not give us the t value, so may be useful only 1532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// as a quick reject -- and maybe not then; it takes 3 muls, 3 adds, 2 cmps) 1542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comint horizontalLineIntersect(const _Line& line, double left, double right, 1552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double y, double tRange[2]) { 1562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int result = horizontalIntersect(line, y, tRange); 1572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (result != 1) { 158fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com // FIXME: this is incorrect if result == 2 1592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return result; 1602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double xIntercept = line[0].x + tRange[0] * (line[1].x - line[0].x); 1622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (xIntercept > right || xIntercept < left) { 1632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return 0; 1642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return result; 1662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 1672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 168fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint horizontalIntersect(const _Line& line, double left, double right, 169fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double y, bool flipped, Intersections& intersections) { 170fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int result = horizontalIntersect(line, y, intersections.fT[0]); 171fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com switch (result) { 172fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 0: 173fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 174fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 1: { 175fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double xIntercept = line[0].x + intersections.fT[0][0] 176fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com * (line[1].x - line[0].x); 177fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (xIntercept > right || xIntercept < left) { 178fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 0; 179fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 180fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][0] = (xIntercept - left) / (right - left); 181fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 182fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 183fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 2: 1848dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #if 0 // sorting edges fails to preserve original direction 185fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double lineL = line[0].x; 186fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double lineR = line[1].x; 187fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (lineL > lineR) { 188aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(lineL, lineR); 189fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 190aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com double overlapL = SkTMax(left, lineL); 191aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com double overlapR = SkTMin(right, lineR); 192fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (overlapL > overlapR) { 193fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 0; 194fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 195fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (overlapL == overlapR) { 196fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com result = 1; 197fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 198fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[0][0] = (overlapL - line[0].x) / (line[1].x - line[0].x); 199fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][0] = (overlapL - left) / (right - left); 200fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (result > 1) { 201fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[0][1] = (overlapR - line[0].x) / (line[1].x - line[0].x); 202fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][1] = (overlapR - left) / (right - left); 203fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 2048dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #else 2058dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a0 = line[0].x; 2068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a1 = line[1].x; 2078dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b0 = flipped ? right : left; 2088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b1 = flipped ? left : right; 2098dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // FIXME: share common code below 2108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double at0 = (a0 - b0) / (a0 - a1); 2118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double at1 = (a0 - b1) / (a0 - a1); 2128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { 2138dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return 0; 2148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 215aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); 216aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); 2178dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int bIn = (a0 - a1) * (b0 - b1) < 0; 218aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 2198dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1.0), 0.0); 220aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 2218dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1.0), 0.0); 2228dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool second = fabs(intersections.fT[0][0] - intersections.fT[0][1]) 2238dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com > FLT_EPSILON; 224aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT((fabs(intersections.fT[1][0] - intersections.fT[1][1]) 2258dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com <= FLT_EPSILON) ^ second); 22645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(line, 1 + second, intersections); 2278dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #endif 228fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 229fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 230fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (flipped) { 231fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com // OPTIMIZATION: instead of swapping, pass original line, use [1].x - [0].x 232fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com for (int index = 0; index < result; ++index) { 233fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][index] = 1 - intersections.fT[1][index]; 234fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 235fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 23645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(line, result, intersections); 237fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 238fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 239a3f05facab01712a1b58e60a70b0dbdb90a39830caryclark@google.comstatic int verticalIntersect(const _Line& line, double x, double tRange[2]) { 240fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double min = line[0].x; 241fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double max = line[1].x; 242fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (min > max) { 243aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(min, max); 244fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 245fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (min > x || max < x) { 246fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 0; 247fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 2486d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (AlmostEqualUlps(min, max)) { 249fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com tRange[0] = 0; 250fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com tRange[1] = 1; 251fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 2; 252fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 253fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com tRange[0] = (x - line[0].x) / (line[1].x - line[0].x); 254fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 1; 255fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 256fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 257fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint verticalIntersect(const _Line& line, double top, double bottom, 258fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double x, bool flipped, Intersections& intersections) { 259fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com int result = verticalIntersect(line, x, intersections.fT[0]); 260fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com switch (result) { 261fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 0: 262fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 263fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 1: { 264fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double yIntercept = line[0].y + intersections.fT[0][0] 265fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com * (line[1].y - line[0].y); 266fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (yIntercept > bottom || yIntercept < top) { 267fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 0; 268fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 269fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][0] = (yIntercept - top) / (bottom - top); 270fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 271fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 272fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com case 2: 2738dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #if 0 // sorting edges fails to preserve original direction 274fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double lineT = line[0].y; 275fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double lineB = line[1].y; 276fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (lineT > lineB) { 277aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(lineT, lineB); 278fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 279aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com double overlapT = SkTMax(top, lineT); 280aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com double overlapB = SkTMin(bottom, lineB); 281fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (overlapT > overlapB) { 282fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com return 0; 283fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 284fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (overlapT == overlapB) { 285fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com result = 1; 286fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 287fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[0][0] = (overlapT - line[0].y) / (line[1].y - line[0].y); 288fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][0] = (overlapT - top) / (bottom - top); 289fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (result > 1) { 290fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[0][1] = (overlapB - line[0].y) / (line[1].y - line[0].y); 291fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][1] = (overlapB - top) / (bottom - top); 292fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 2938dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #else 2948dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a0 = line[0].y; 2958dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double a1 = line[1].y; 2968dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b0 = flipped ? bottom : top; 2978dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double b1 = flipped ? top : bottom; 2988dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com // FIXME: share common code above 2998dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double at0 = (a0 - b0) / (a0 - a1); 3008dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com double at1 = (a0 - b1) / (a0 - a1); 3018dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com if ((at0 < 0 && at1 < 0) || (at0 > 1 && at1 > 1)) { 3028dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com return 0; 3038dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com } 304aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[0][0] = SkTMax(SkTMin(at0, 1.0), 0.0); 305aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[0][1] = SkTMax(SkTMin(at1, 1.0), 0.0); 3068dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com int bIn = (a0 - a1) * (b0 - b1) < 0; 307aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[1][bIn] = SkTMax(SkTMin((b0 - a0) / (b0 - b1), 3088dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1.0), 0.0); 309aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com intersections.fT[1][!bIn] = SkTMax(SkTMin((b0 - a1) / (b0 - b1), 3108dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com 1.0), 0.0); 3118dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com bool second = fabs(intersections.fT[0][0] - intersections.fT[0][1]) 3128dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com > FLT_EPSILON; 313aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT((fabs(intersections.fT[1][0] - intersections.fT[1][1]) 3148dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com <= FLT_EPSILON) ^ second); 31545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(line, 1 + second, intersections); 3168dcf114db9762c02d217beba6e29dffa4e92d298caryclark@google.com #endif 317fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com break; 318fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 319fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (flipped) { 320fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y 321fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com for (int index = 0; index < result; ++index) { 322fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com intersections.fT[1][index] = 1 - intersections.fT[1][index]; 323fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 324fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 32545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com return computePoints(line, result, intersections); 326fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 327fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 328639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py 329639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// 4 subs, 2 muls, 1 cmp 330639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comstatic bool ccw(const _Point& A, const _Point& B, const _Point& C) { 331d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x); 332639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 333639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 334639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com// 16 subs, 8 muls, 6 cmps 335639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool testIntersect(const _Line& a, const _Line& b) { 336d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) 337639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); 338639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 339