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 */ 7c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "CurveIntersection.h" 827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "CubicUtilities.h" 927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "Intersections.h" 1027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com#include "LineUtilities.h" 1127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 1227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com/* 1327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comFind the interection of a line and cubic by solving for valid t values. 1427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 1527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comAnalogous to line-quadratic intersection, solve line-cubic intersection by 1627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comrepresenting the cubic as: 1727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com x = a(1-t)^3 + 2b(1-t)^2t + c(1-t)t^2 + dt^3 1827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com y = e(1-t)^3 + 2f(1-t)^2t + g(1-t)t^2 + ht^3 1927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comand the line as: 2027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com y = i*x + j (if the line is more horizontal) 2127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comor: 2227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com x = i*y + j (if the line is more vertical) 2327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 2427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comThen using Mathematica, solve for the values of t where the cubic intersects the 2527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comline: 2627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 2727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com (in) Resultant[ 28d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - x, 29c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - i*x - j, x] 3027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com (out) -e + j + 3127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 e t - 3 f t - 3227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 e t^2 + 6 f t^2 - 3 g t^2 + 33d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com e t^3 - 3 f t^3 + 3 g t^3 - h t^3 + 3427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com i ( a - 3527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 a t + 3 b t + 3627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 a t^2 - 6 b t^2 + 3 c t^2 - 3727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com a t^3 + 3 b t^3 - 3 c t^3 + d t^3 ) 3827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comif i goes to infinity, we can rewrite the line in terms of x. Mathematica: 4027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 4127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com (in) Resultant[ 42d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - i*y - j, 43c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] 44d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com (out) a - j - 45d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 3 a t + 3 b t + 4627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 a t^2 - 6 b t^2 + 3 c t^2 - 47d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com a t^3 + 3 b t^3 - 3 c t^3 + d t^3 - 48d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com i ( e - 49d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 3 e t + 3 f t + 5027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 3 e t^2 - 6 f t^2 + 3 g t^2 - 5127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com e t^3 + 3 f t^3 - 3 g t^3 + h t^3 ) 5227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 5327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comSolving this with Mathematica produces an expression with hundreds of terms; 5427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.cominstead, use Numeric Solutions recipe to solve the cubic. 5527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 5627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comThe near-horizontal case, in terms of: Ax^3 + Bx^2 + Cx + D == 0 5727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com A = (-(-e + 3*f - 3*g + h) + i*(-a + 3*b - 3*c + d) ) 5827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com B = 3*(-( e - 2*f + g ) + i*( a - 2*b + c ) ) 5927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com C = 3*(-(-e + f ) + i*(-a + b ) ) 6027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com D = (-( e ) + i*( a ) + j ) 6127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 6227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comThe near-vertical case, in terms of: Ax^3 + Bx^2 + Cx + D == 0 6327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com A = ( (-a + 3*b - 3*c + d) - i*(-e + 3*f - 3*g + h) ) 6427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com B = 3*( ( a - 2*b + c ) - i*( e - 2*f + g ) ) 6527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com C = 3*( (-a + b ) - i*(-e + f ) ) 6627accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com D = ( ( a ) - i*( e ) - j ) 67d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 68c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comFor horizontal lines: 69c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com(in) Resultant[ 70d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j, 71c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y] 72c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com(out) e - j - 73d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 3 e t + 3 f t + 74c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 3 e t^2 - 6 f t^2 + 3 g t^2 - 75c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com e t^3 + 3 f t^3 - 3 g t^3 + h t^3 76c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comSo the cubic coefficients are: 77c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com */ 7927accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 8073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comclass LineCubicIntersections { 8127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.compublic: 8227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 8373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comLineCubicIntersections(const Cubic& c, const _Line& l, Intersections& i) 8427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com : cubic(c) 8527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com , line(l) 8673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com , intersections(i) { 8727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 8827accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 8973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com// see parallel routine in line quadratic intersections 9073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint intersectRay(double roots[3]) { 9173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double adj = line[1].x - line[0].x; 9273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double opp = line[1].y - line[0].y; 9373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com Cubic r; 9473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int n = 0; n < 4; ++n) { 9573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com r[n].x = (cubic[n].y - line[0].y) * adj - (cubic[n].x - line[0].x) * opp; 9673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 97c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double A, B, C, D; 9873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com coefficients(&r[0].x, A, B, C, D); 999f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return cubicRootsValidT(A, B, C, D, roots); 10073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 10173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 10273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint intersect() { 10373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com addEndPoints(); 10473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double rootVals[3]; 10573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = intersectRay(rootVals); 10673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 0; index < roots; ++index) { 10773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double cubicT = rootVals[index]; 10873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double lineT = findLineT(cubicT); 10973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (pinTs(cubicT, lineT)) { 11045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point pt; 11145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(line, lineT, pt.x, pt.y); 11245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cubicT, lineT, pt); 11373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 11473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 11573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return intersections.fUsed; 11673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 11773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 11873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint horizontalIntersect(double axisIntercept, double roots[3]) { 119c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double A, B, C, D; 120c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com coefficients(&cubic[0].y, A, B, C, D); 121c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com D -= axisIntercept; 1229f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return cubicRootsValidT(A, B, C, D, roots); 12327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 12427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 12573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 12673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com addHorizontalEndPoints(left, right, axisIntercept); 12773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double rootVals[3]; 12873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = horizontalIntersect(axisIntercept, rootVals); 12973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 0; index < roots; ++index) { 13045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point pt; 13173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double cubicT = rootVals[index]; 13245a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic, cubicT, pt.x, pt.y); 13345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double lineT = (pt.x - left) / (right - left); 13473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (pinTs(cubicT, lineT)) { 13545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cubicT, lineT, pt); 13673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 13773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 13873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (flipped) { 13973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com flip(); 14073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 14173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return intersections.fUsed; 14273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 14373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 14473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint verticalIntersect(double axisIntercept, double roots[3]) { 145fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double A, B, C, D; 146fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com coefficients(&cubic[0].x, A, B, C, D); 147fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com D -= axisIntercept; 1489f60291c5375457f8adf228dbe6e8ff1186b13e1caryclark@google.com return cubicRootsValidT(A, B, C, D, roots); 14973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 15073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 15173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 15273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com addVerticalEndPoints(top, bottom, axisIntercept); 15373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double rootVals[3]; 15473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = verticalIntersect(axisIntercept, rootVals); 15573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 0; index < roots; ++index) { 15645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com _Point pt; 15773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double cubicT = rootVals[index]; 15845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com xy_at_t(cubic, cubicT, pt.x, pt.y); 15945a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com double lineT = (pt.y - top) / (bottom - top); 16073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (pinTs(cubicT, lineT)) { 16145a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cubicT, lineT, pt); 16273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 16373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 16473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (flipped) { 16573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com flip(); 16673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 16773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return intersections.fUsed; 16873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 16973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 17073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comprotected: 17173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 17273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid addEndPoints() 17373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{ 17473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int cIndex = 0; cIndex < 4; cIndex += 3) { 17573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int lIndex = 0; lIndex < 2; lIndex++) { 17673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex] == line[lIndex]) { 17745a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cIndex >> 1, lIndex, line[lIndex]); 17873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 17973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 18273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 18373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid addHorizontalEndPoints(double left, double right, double y) 18473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{ 18573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int cIndex = 0; cIndex < 4; cIndex += 3) { 18673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].y != y) { 18773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 18873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 18973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].x == left) { 19045a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cIndex >> 1, 0, cubic[cIndex]); 19173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 19273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].x == right) { 19345a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cIndex >> 1, 1, cubic[cIndex]); 19473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 19573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 19673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 19773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 19873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid addVerticalEndPoints(double top, double bottom, double x) 19973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{ 20073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int cIndex = 0; cIndex < 4; cIndex += 3) { 20173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].x != x) { 20273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com continue; 20373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 20473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].y == top) { 20545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cIndex >> 1, 0, cubic[cIndex]); 20673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 20773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (cubic[cIndex].y == bottom) { 20845a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com intersections.insert(cIndex >> 1, 1, cubic[cIndex]); 20973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 21073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 211fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 212fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 21327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comdouble findLineT(double t) { 21473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double x, y; 21573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(cubic, t, x, y); 21673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double dx = line[1].x - line[0].x; 21773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double dy = line[1].y - line[0].y; 21873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (fabs(dx) > fabs(dy)) { 21973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return (x - line[0].x) / dx; 22073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 22173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return (y - line[0].y) / dy; 22273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 22373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 22473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid flip() { 22573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com // OPTIMIZATION: instead of swapping, pass original line, use [1].y - [0].y 22673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int roots = intersections.fUsed; 22773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 0; index < roots; ++index) { 22873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com intersections.fT[1][index] = 1 - intersections.fT[1][index]; 22973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 23073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 23173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 2321304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.comstatic bool pinTs(double& cubicT, double& lineT) { 23373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!approximately_one_or_less(lineT)) { 23473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 23573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 23673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (!approximately_zero_or_more(lineT)) { 23773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return false; 23873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 2391304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com if (precisely_less_than_zero(cubicT)) { 24073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubicT = 0; 2411304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } else if (precisely_greater_than_one(cubicT)) { 24273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com cubicT = 1; 24373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 2441304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com if (precisely_less_than_zero(lineT)) { 24573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com lineT = 0; 2461304bb25aa3b0baa61fc2e2900fabcef88801b59caryclark@google.com } else if (precisely_greater_than_one(lineT)) { 24773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com lineT = 1; 24873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 24973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return true; 25027accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 25127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 25227accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comprivate: 25327accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com 25427accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comconst Cubic& cubic; 25527accef223a27fba437f5e825d99edbae20a045bcaryclark@google.comconst _Line& line; 25673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comIntersections& intersections; 25727accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com}; 258c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 259198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comint horizontalIntersect(const Cubic& cubic, double left, double right, double y, 260198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com double tRange[3]) { 26173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com LineCubicIntersections c(cubic, *((_Line*) 0), *((Intersections*) 0)); 26273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com double rootVals[3]; 26373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int result = c.horizontalIntersect(y, rootVals); 26473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com int tCount = 0; 26573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com for (int index = 0; index < result; ++index) { 266198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com double x, y; 26773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com xy_at_t(cubic, rootVals[index], x, y); 268198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com if (x < left || x > right) { 269198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com continue; 270198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com } 27173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com tRange[tCount++] = rootVals[index]; 272198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com } 273198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com return result; 274198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com} 275198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com 276fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint horizontalIntersect(const Cubic& cubic, double left, double right, double y, 277fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool flipped, Intersections& intersections) { 27873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com LineCubicIntersections c(cubic, *((_Line*) 0), intersections); 27973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return c.horizontalIntersect(y, left, right, flipped); 280fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 281fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 282fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint verticalIntersect(const Cubic& cubic, double top, double bottom, double x, 283fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool flipped, Intersections& intersections) { 28473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com LineCubicIntersections c(cubic, *((_Line*) 0), intersections); 28573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return c.verticalIntersect(x, top, bottom, flipped); 286fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com} 287fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com 28873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint intersect(const Cubic& cubic, const _Line& line, Intersections& i) { 28973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com LineCubicIntersections c(cubic, line, i); 29073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return c.intersect(); 29127accef223a27fba437f5e825d99edbae20a045bcaryclark@google.com} 292f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com 293f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comint intersectRay(const Cubic& cubic, const _Line& line, Intersections& i) { 294f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com LineCubicIntersections c(cubic, line, i); 295f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com return c.intersectRay(i.fT[0]); 296f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.com} 297