107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkIntersections.h" 855888e44171ffd48b591d19256884a969fe4da17caryclark#include "SkPathOpsCurve.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comFind the interection of a line and quadratic by solving for valid t values. 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comFrom http://stackoverflow.com/questions/1853637/how-to-find-the-mathematical-function-defining-a-bezier-curve 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com"A Bezier curve is a parametric function. A quadratic Bezier curve (i.e. three 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comcontrol points) can be expressed as: F(t) = A(1 - t)^2 + B(1 - t)t + Ct^2 where 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comA, B and C are points and t goes from zero to one. 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comThis will give you two equations: 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com x = a(1 - t)^2 + b(1 - t)t + ct^2 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com y = d(1 - t)^2 + e(1 - t)t + ft^2 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comIf you add for instance the line equation (y = kx + m) to that, you'll end up 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comwith three equations and three unknowns (x, y and t)." 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comSimilar to above, the quadratic is represented as 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com x = a(1-t)^2 + 2b(1-t)t + ct^2 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com y = d(1-t)^2 + 2e(1-t)t + ft^2 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comand the line as 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com y = g*x + h 3407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comUsing Mathematica, solve for the values of t where the quadratic intersects the 3607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comline: 3707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (in) t1 = Resultant[a*(1 - t)^2 + 2*b*(1 - t)*t + c*t^2 - x, 3907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com d*(1 - t)^2 + 2*e*(1 - t)*t + f*t^2 - g*x - h, x] 4007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (out) -d + h + 2 d t - 2 e t - d t^2 + 2 e t^2 - f t^2 + 4107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com g (a - 2 a t + 2 b t + a t^2 - 2 b t^2 + c t^2) 4207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (in) Solve[t1 == 0, t] 4307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (out) { 4407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {t -> (-2 d + 2 e + 2 a g - 2 b g - 4507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Sqrt[(2 d - 2 e - 2 a g + 2 b g)^2 - 4607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4 (-d + 2 e - f + a g - 2 b g + c g) (-d + a g + h)]) / 4707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (2 (-d + 2 e - f + a g - 2 b g + c g)) 4807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com }, 4907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {t -> (-2 d + 2 e + 2 a g - 2 b g + 5007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Sqrt[(2 d - 2 e - 2 a g + 2 b g)^2 - 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4 (-d + 2 e - f + a g - 2 b g + c g) (-d + a g + h)]) / 5207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (2 (-d + 2 e - f + a g - 2 b g + c g)) 5307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 5507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 5607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comUsing the results above (when the line tends towards horizontal) 5707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A = (-(d - 2*e + f) + g*(a - 2*b + c) ) 5807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com B = 2*( (d - e ) - g*(a - b ) ) 5907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com C = (-(d ) + g*(a ) + h ) 6007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comIf g goes to infinity, we can rewrite the line in terms of x. 6207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com x = g'*y + h' 6307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comAnd solve accordingly in Mathematica: 6507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 6607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (in) t2 = Resultant[a*(1 - t)^2 + 2*b*(1 - t)*t + c*t^2 - g'*y - h', 6707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com d*(1 - t)^2 + 2*e*(1 - t)*t + f*t^2 - y, y] 6807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (out) a - h' - 2 a t + 2 b t + a t^2 - 2 b t^2 + c t^2 - 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com g' (d - 2 d t + 2 e t + d t^2 - 2 e t^2 + f t^2) 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (in) Solve[t2 == 0, t] 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (out) { 7207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {t -> (2 a - 2 b - 2 d g' + 2 e g' - 7307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Sqrt[(-2 a + 2 b + 2 d g' - 2 e g')^2 - 7407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4 (a - 2 b + c - d g' + 2 e g' - f g') (a - d g' - h')]) / 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (2 (a - 2 b + c - d g' + 2 e g' - f g')) 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com }, 7707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com {t -> (2 a - 2 b - 2 d g' + 2 e g' + 7807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com Sqrt[(-2 a + 2 b + 2 d g' - 2 e g')^2 - 7907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 4 (a - 2 b + c - d g' + 2 e g' - f g') (a - d g' - h')])/ 8007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com (2 (a - 2 b + c - d g' + 2 e g' - f g')) 8107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 8307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 8407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comThus, if the slope of the line tends towards vertical, we use: 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A = ( (a - 2*b + c) - g'*(d - 2*e + f) ) 8607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com B = 2*(-(a - b ) + g'*(d - e ) ) 8707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com C = ( (a ) - g'*(d ) - h' ) 8807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comclass LineQuadraticIntersections { 9107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.compublic: 924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com enum PinTPoint { 934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com kPointUninitialized, 944fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com kPointInitialized 954fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com }; 964fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com 9707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i) 984fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com : fQuad(q) 99624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark , fLine(&l) 1004fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com , fIntersections(i) 101fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com , fAllowNear(true) { 10245f04b8ea8256476d87c677e23d9efbcb0ab937ecaryclark i->setMax(5); // allow short partial coincidence plus discrete intersections 103fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 104fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 105624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark LineQuadraticIntersections(const SkDQuad& q) 10655888e44171ffd48b591d19256884a969fe4da17caryclark : fQuad(q) 10796fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGPARAMS(fLine(nullptr)) 10896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGPARAMS(fIntersections(nullptr)) 109624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark SkDEBUGPARAMS(fAllowNear(false)) { 110624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } 111624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 112fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void allowNear(bool allow) { 113fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com fAllowNear = allow; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11654359294a7c9dc54802d512a5d891a35c1663392caryclark void checkCoincident() { 11754359294a7c9dc54802d512a5d891a35c1663392caryclark int last = fIntersections->used() - 1; 11854359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < last; ) { 11954359294a7c9dc54802d512a5d891a35c1663392caryclark double quadMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; 12054359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint quadMidPt = fQuad.ptAtT(quadMidT); 12196fcdcc219d2a0d3579719b84b28bede76efba64halcanary double t = fLine->nearPoint(quadMidPt, nullptr); 12254359294a7c9dc54802d512a5d891a35c1663392caryclark if (t < 0) { 12354359294a7c9dc54802d512a5d891a35c1663392caryclark ++index; 12454359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 12554359294a7c9dc54802d512a5d891a35c1663392caryclark } 12654359294a7c9dc54802d512a5d891a35c1663392caryclark if (fIntersections->isCoincident(index)) { 12754359294a7c9dc54802d512a5d891a35c1663392caryclark fIntersections->removeOne(index); 12854359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 12954359294a7c9dc54802d512a5d891a35c1663392caryclark } else if (fIntersections->isCoincident(index + 1)) { 13054359294a7c9dc54802d512a5d891a35c1663392caryclark fIntersections->removeOne(index + 1); 13154359294a7c9dc54802d512a5d891a35c1663392caryclark --last; 13254359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 13354359294a7c9dc54802d512a5d891a35c1663392caryclark fIntersections->setCoincident(index++); 13454359294a7c9dc54802d512a5d891a35c1663392caryclark } 13554359294a7c9dc54802d512a5d891a35c1663392caryclark fIntersections->setCoincident(index); 13654359294a7c9dc54802d512a5d891a35c1663392caryclark } 13754359294a7c9dc54802d512a5d891a35c1663392caryclark } 13854359294a7c9dc54802d512a5d891a35c1663392caryclark 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersectRay(double roots[2]) { 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com /* 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com solve by rotating line+quad so line is horizontal, then finding the roots 14207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com set up matrix to rotate quad to x-axis 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com |cos(a) -sin(a)| 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com |sin(a) cos(a)| 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com note that cos(a) = A(djacent) / Hypoteneuse 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com sin(a) = O(pposite) / Hypoteneuse 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com since we are computing Ts, we can ignore hypoteneuse, the scale factor: 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com | A -O | 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com | O A | 15007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A = line[1].fX - line[0].fX (adjacent side of the right triangle) 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com O = line[1].fY - line[0].fY (opposite side of the right triangle) 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for each of the three points (e.g. n = 0 to 2) 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com quad[n].fY' = (quad[n].fY - line[0].fY) * A - (quad[n].fX - line[0].fX) * O 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 155624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double adj = (*fLine)[1].fX - (*fLine)[0].fX; 156624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double opp = (*fLine)[1].fY - (*fLine)[0].fY; 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double r[3]; 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int n = 0; n < 3; ++n) { 159624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark r[n] = (fQuad[n].fY - (*fLine)[0].fY) * adj - (fQuad[n].fX - (*fLine)[0].fX) * opp; 16007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double A = r[2]; 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double B = r[1]; 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double C = r[0]; 16407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com A += C - 2 * B; // A = a - 2*b + c 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com B -= C; // B = -(b - c) 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return SkDQuad::RootsValidT(A, 2 * B, C, roots); 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int intersect() { 170fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com addExactEndPoints(); 171570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (fAllowNear) { 172570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com addNearEndPoints(); 173570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 17454359294a7c9dc54802d512a5d891a35c1663392caryclark double rootVals[2]; 17554359294a7c9dc54802d512a5d891a35c1663392caryclark int roots = intersectRay(rootVals); 17654359294a7c9dc54802d512a5d891a35c1663392caryclark for (int index = 0; index < roots; ++index) { 17754359294a7c9dc54802d512a5d891a35c1663392caryclark double quadT = rootVals[index]; 17854359294a7c9dc54802d512a5d891a35c1663392caryclark double lineT = findLineT(quadT); 17954359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint pt; 18054359294a7c9dc54802d512a5d891a35c1663392caryclark if (pinTs(&quadT, &lineT, &pt, kPointUninitialized) && uniqueAnswer(quadT, pt)) { 18154359294a7c9dc54802d512a5d891a35c1663392caryclark fIntersections->insert(quadT, lineT, pt); 18207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18454359294a7c9dc54802d512a5d891a35c1663392caryclark checkCoincident(); 1854fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fIntersections->used(); 18607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 18707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 18807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontalIntersect(double axisIntercept, double roots[2]) { 1894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double D = fQuad[2].fY; // f 1904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double E = fQuad[1].fY; // e 1914fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double F = fQuad[0].fY; // d 19207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com D += F - 2 * E; // D = d - 2*e + f 19307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com E -= F; // E = -(d - e) 19407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com F -= axisIntercept; 19507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return SkDQuad::RootsValidT(D, 2 * E, F, roots); 19607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 19707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 19807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 199fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com addExactHorizontalEndPoints(left, right, axisIntercept); 200570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (fAllowNear) { 201570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com addNearHorizontalEndPoints(left, right, axisIntercept); 202570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 20307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double rootVals[2]; 20407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots = horizontalIntersect(axisIntercept, rootVals); 20507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < roots; ++index) { 20607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double quadT = rootVals[index]; 2074fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint pt = fQuad.ptAtT(quadT); 20807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double lineT = (pt.fX - left) / (right - left); 20954359294a7c9dc54802d512a5d891a35c1663392caryclark if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) { 2104fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, pt); 21107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (flipped) { 2144fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->flip(); 21507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21654359294a7c9dc54802d512a5d891a35c1663392caryclark checkCoincident(); 2174fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fIntersections->used(); 21807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 21907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 22054359294a7c9dc54802d512a5d891a35c1663392caryclark bool uniqueAnswer(double quadT, const SkDPoint& pt) { 22154359294a7c9dc54802d512a5d891a35c1663392caryclark for (int inner = 0; inner < fIntersections->used(); ++inner) { 22254359294a7c9dc54802d512a5d891a35c1663392caryclark if (fIntersections->pt(inner) != pt) { 22354359294a7c9dc54802d512a5d891a35c1663392caryclark continue; 22454359294a7c9dc54802d512a5d891a35c1663392caryclark } 22554359294a7c9dc54802d512a5d891a35c1663392caryclark double existingQuadT = (*fIntersections)[0][inner]; 22654359294a7c9dc54802d512a5d891a35c1663392caryclark if (quadT == existingQuadT) { 22754359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 22854359294a7c9dc54802d512a5d891a35c1663392caryclark } 22954359294a7c9dc54802d512a5d891a35c1663392caryclark // check if midway on quad is also same point. If so, discard this 23054359294a7c9dc54802d512a5d891a35c1663392caryclark double quadMidT = (existingQuadT + quadT) / 2; 23154359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint quadMidPt = fQuad.ptAtT(quadMidT); 23254359294a7c9dc54802d512a5d891a35c1663392caryclark if (quadMidPt.approximatelyEqual(pt)) { 23354359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 23454359294a7c9dc54802d512a5d891a35c1663392caryclark } 23554359294a7c9dc54802d512a5d891a35c1663392caryclark } 23654359294a7c9dc54802d512a5d891a35c1663392caryclark#if ONE_OFF_DEBUG 23754359294a7c9dc54802d512a5d891a35c1663392caryclark SkDPoint qPt = fQuad.ptAtT(quadT); 23854359294a7c9dc54802d512a5d891a35c1663392caryclark SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, 23954359294a7c9dc54802d512a5d891a35c1663392caryclark qPt.fX, qPt.fY); 24054359294a7c9dc54802d512a5d891a35c1663392caryclark#endif 24154359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 24254359294a7c9dc54802d512a5d891a35c1663392caryclark } 24354359294a7c9dc54802d512a5d891a35c1663392caryclark 24407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int verticalIntersect(double axisIntercept, double roots[2]) { 2454fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double D = fQuad[2].fX; // f 2464fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double E = fQuad[1].fX; // e 2474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double F = fQuad[0].fX; // d 24807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com D += F - 2 * E; // D = d - 2*e + f 24907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com E -= F; // E = -(d - e) 25007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com F -= axisIntercept; 25107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return SkDQuad::RootsValidT(D, 2 * E, F, roots); 25207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 25307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 25407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 255fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com addExactVerticalEndPoints(top, bottom, axisIntercept); 256570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (fAllowNear) { 257570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com addNearVerticalEndPoints(top, bottom, axisIntercept); 258570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 25907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double rootVals[2]; 26007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com int roots = verticalIntersect(axisIntercept, rootVals); 26107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < roots; ++index) { 26207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double quadT = rootVals[index]; 2634fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint pt = fQuad.ptAtT(quadT); 26407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double lineT = (pt.fY - top) / (bottom - top); 26554359294a7c9dc54802d512a5d891a35c1663392caryclark if (pinTs(&quadT, &lineT, &pt, kPointInitialized) && uniqueAnswer(quadT, pt)) { 2664fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, pt); 26707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 26807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 26907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (flipped) { 2704fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->flip(); 27107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 27254359294a7c9dc54802d512a5d891a35c1663392caryclark checkCoincident(); 2734fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com return fIntersections->used(); 27407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 27507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 27607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comprotected: 27707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com // add endpoints first to get zero and one t values exactly 278fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addExactEndPoints() { 27907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 280624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double lineT = fLine->exactPoint(fQuad[qIndex]); 281fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 28207e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com continue; 28307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 284fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 2854fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 286fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 287fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 288fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 289fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addNearEndPoints() { 290fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 291fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 2924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (fIntersections->hasT(quadT)) { 29307e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com continue; 29407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 29596fcdcc219d2a0d3579719b84b28bede76efba64halcanary double lineT = fLine->nearPoint(fQuad[qIndex], nullptr); 296fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 29707e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com continue; 29807e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 2994fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 300fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 30155888e44171ffd48b591d19256884a969fe4da17caryclark this->addLineNearEndPoints(); 30255888e44171ffd48b591d19256884a969fe4da17caryclark } 30355888e44171ffd48b591d19256884a969fe4da17caryclark 30455888e44171ffd48b591d19256884a969fe4da17caryclark void addLineNearEndPoints() { 30555888e44171ffd48b591d19256884a969fe4da17caryclark for (int lIndex = 0; lIndex < 2; ++lIndex) { 30655888e44171ffd48b591d19256884a969fe4da17caryclark double lineT = (double) lIndex; 30755888e44171ffd48b591d19256884a969fe4da17caryclark if (fIntersections->hasOppT(lineT)) { 30855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 30955888e44171ffd48b591d19256884a969fe4da17caryclark } 31055888e44171ffd48b591d19256884a969fe4da17caryclark double quadT = ((SkDCurve*) &fQuad)->nearPoint(SkPath::kQuad_Verb, 31155888e44171ffd48b591d19256884a969fe4da17caryclark (*fLine)[lIndex], (*fLine)[!lIndex]); 31255888e44171ffd48b591d19256884a969fe4da17caryclark if (quadT < 0) { 31355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 31455888e44171ffd48b591d19256884a969fe4da17caryclark } 31555888e44171ffd48b591d19256884a969fe4da17caryclark fIntersections->insert(quadT, lineT, (*fLine)[lIndex]); 31655888e44171ffd48b591d19256884a969fe4da17caryclark } 317fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 318fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 319fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addExactHorizontalEndPoints(double left, double right, double y) { 320fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 3214fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double lineT = SkDLine::ExactPointH(fQuad[qIndex], left, right, y); 322fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 323fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com continue; 32407e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 325fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 3264fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 32707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 32807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 32907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 330fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addNearHorizontalEndPoints(double left, double right, double y) { 33107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 332fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 3334fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (fIntersections->hasT(quadT)) { 33407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 33507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3364fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double lineT = SkDLine::NearPointH(fQuad[qIndex], left, right, y); 337fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 338fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com continue; 33907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3404fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 34107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 34255888e44171ffd48b591d19256884a969fe4da17caryclark this->addLineNearEndPoints(); 34307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 34407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 345fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addExactVerticalEndPoints(double top, double bottom, double x) { 34607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 3474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double lineT = SkDLine::ExactPointV(fQuad[qIndex], top, bottom, x); 348fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 34907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com continue; 35007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 351fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 3524fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 353fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 354fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 355fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com 356fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com void addNearVerticalEndPoints(double top, double bottom, double x) { 357fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com for (int qIndex = 0; qIndex < 3; qIndex += 2) { 358fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com double quadT = (double) (qIndex >> 1); 3594fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (fIntersections->hasT(quadT)) { 360fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com continue; 361fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com } 3624fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double lineT = SkDLine::NearPointV(fQuad[qIndex], top, bottom, x); 363fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com if (lineT < 0) { 364fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com continue; 36507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3664fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fIntersections->insert(quadT, lineT, fQuad[qIndex]); 36707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 36855888e44171ffd48b591d19256884a969fe4da17caryclark this->addLineNearEndPoints(); 36907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 37007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 37107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double findLineT(double t) { 3724fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDPoint xy = fQuad.ptAtT(t); 373624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double dx = (*fLine)[1].fX - (*fLine)[0].fX; 374624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark double dy = (*fLine)[1].fY - (*fLine)[0].fY; 37528d219c5682af6dfacea2460b5ba2f9e98702de6caryclark@google.com if (fabs(dx) > fabs(dy)) { 376624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (xy.fX - (*fLine)[0].fX) / dx; 37707e97fccd2d85076cd22ef411b0773ab92a18abecaryclark@google.com } 378624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return (xy.fY - (*fLine)[0].fY) / dy; 37907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 38007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3814fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com bool pinTs(double* quadT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { 3824431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!approximately_one_or_less_double(*lineT)) { 38307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 38407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3854431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org if (!approximately_zero_or_more_double(*lineT)) { 38607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 38707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 3884fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double qT = *quadT = SkPinT(*quadT); 3894fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com double lT = *lineT = SkPinT(*lineT); 3904fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { 391624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark *pt = (*fLine).ptAtT(lT); 3924fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } else if (ptSet == kPointUninitialized) { 3934fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com *pt = fQuad.ptAtT(qT); 3944fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com } 395570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com SkPoint gridPt = pt->asSkPoint(); 396624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { 397624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark *pt = (*fLine)[0]; 398570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com *lineT = 0; 399624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { 400624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark *pt = (*fLine)[1]; 401570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com *lineT = 1; 402570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 4038cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { 4048cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org return false; 4058cb1daaa1e4343eb60a7c4f21c12e33de30dad64commit-bot@chromium.org } 406570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (gridPt == fQuad[0].asSkPoint()) { 4074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *pt = fQuad[0]; 408570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com *quadT = 0; 409570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } else if (gridPt == fQuad[2].asSkPoint()) { 4104431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org *pt = fQuad[2]; 411570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com *quadT = 1; 412570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 41307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 41407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 41507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 41607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comprivate: 4174fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com const SkDQuad& fQuad; 418624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark const SkDLine* fLine; 4194fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkIntersections* fIntersections; 420fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com bool fAllowNear; 42107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 42207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 42307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::horizontal(const SkDQuad& quad, double left, double right, double y, 42407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flipped) { 4254fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDLine line = {{{ left, y }, { right, y }}}; 4264fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com LineQuadraticIntersections q(quad, line, this); 42707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return q.horizontalIntersect(y, left, right, flipped); 42807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 42907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 43007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, double x, 43107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool flipped) { 4324fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com SkDLine line = {{{ x, top }, { x, bottom }}}; 4334fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com LineQuadraticIntersections q(quad, line, this); 43407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return q.verticalIntersect(x, top, bottom, flipped); 43507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 43607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 43707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersect(const SkDQuad& quad, const SkDLine& line) { 43807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com LineQuadraticIntersections q(quad, line, this); 439fa2aeee27af27f2934ee52a9732148f66481fb03caryclark@google.com q.allowNear(fAllowNear); 44007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return q.intersect(); 44107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 44207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 44307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comint SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) { 44407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com LineQuadraticIntersections q(quad, line, this); 445a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com fUsed = q.intersectRay(fT[0]); 446a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com for (int index = 0; index < fUsed; ++index) { 4474fdbb229649caf74e5c1b55a1823926df903af34caryclark@google.com fPt[index] = quad.ptAtT(fT[0][index]); 448a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com } 449a5e55925ea03e76885804bda77408a1d6f04c335caryclark@google.com return fUsed; 45007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 451624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 452624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkIntersections::HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots) { 453624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark LineQuadraticIntersections q(quad); 454624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return q.horizontalIntersect(y, roots); 455624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 456624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark 457624637cc8ec22c000409704d0b403ac1b81ad4b0caryclarkint SkIntersections::VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots) { 458624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark LineQuadraticIntersections q(quad); 459624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark return q.verticalIntersect(x, roots); 460624637cc8ec22c000409704d0b403ac1b81ad4b0caryclark} 4610449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark 4620449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark// SkDQuad accessors to Intersection utilities 4630449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark 4640449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclarkint SkDQuad::horizontalIntersect(double yIntercept, double roots[2]) const { 4650449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark return SkIntersections::HorizontalIntercept(*this, yIntercept, roots); 4660449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark} 4670449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark 4680449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclarkint SkDQuad::verticalIntersect(double xIntercept, double roots[2]) const { 4690449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark return SkIntersections::VerticalIntercept(*this, xIntercept, roots); 4700449bcfb2fa1dd33cb3a4c0c8b17960d17edf01acaryclark} 471