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" 8639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "Intersections.h" 9639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "IntersectionUtilities.h" 10639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com#include "LineIntersection.h" 11a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com#include "LineUtilities.h" 12a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com#include "QuadraticLineSegments.h" 13a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com#include "QuadraticUtilities.h" 14a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com#include <algorithm> // for swap 15639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 16235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comstatic const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections 17235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 18235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comclass QuadraticIntersections { 19639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.compublic: 20639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 21d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.comQuadraticIntersections(const Quadratic& q1, const Quadratic& q2, Intersections& i) 22639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com : quad1(q1) 23639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com , quad2(q2) 24639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com , intersections(i) 25d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com , depth(0) 26235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com , splits(0) 27235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com , coinMinT1(-1) { 28639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 29639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 30639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool intersect() { 31639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double minT1, minT2, maxT1, maxT2; 32639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!bezier_clip(quad2, quad1, minT1, maxT1)) { 33639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return false; 34639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 35639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!bezier_clip(quad1, quad2, minT2, maxT2)) { 36639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return false; 37639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 38a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com quad1Divisions = 1 / subDivisions(quad1); 39a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com quad2Divisions = 1 / subDivisions(quad2); 40639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int split; 41639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (maxT1 - minT1 < maxT2 - minT2) { 42639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersections.swap(); 43639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT2 = 0; 44639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT2 = 1; 45639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com split = maxT1 - minT1 > tClipLimit; 46639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 47639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT1 = 0; 48639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT1 = 1; 49639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com split = (maxT2 - minT2 > tClipLimit) << 1; 50639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 51639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return chop(minT1, maxT1, minT2, maxT2, split); 52639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 53639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 54639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comprotected: 55d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com 56639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool intersect(double minT1, double maxT1, double minT2, double maxT2) { 57a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com bool t1IsLine = maxT1 - minT1 <= quad1Divisions; 58a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com bool t2IsLine = maxT2 - minT2 <= quad2Divisions; 59a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (t1IsLine | t2IsLine) { 60a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com return intersectAsLine(minT1, maxT1, minT2, maxT2, t1IsLine, t2IsLine); 61a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 62639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com Quadratic smaller, larger; 63d6176b0dcacb124539e0cfd051e6d93a9782f020rmistry@google.com // FIXME: carry last subdivide and reduceOrder result with quad 64639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sub_divide(quad1, minT1, maxT1, intersections.swapped() ? larger : smaller); 65639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com sub_divide(quad2, minT2, maxT2, intersections.swapped() ? smaller : larger); 66639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double minT, maxT; 67639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (!bezier_clip(smaller, larger, minT, maxT)) { 68a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (approximately_equal(minT, maxT)) { 69a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com double smallT, largeT; 70a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com _Point q2pt, q1pt; 71639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (intersections.swapped()) { 72a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com largeT = interp(minT2, maxT2, minT); 73a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad2, largeT, q2pt.x, q2pt.y); 74a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad1, minT1, q1pt.x, q1pt.y); 756d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)) { 76a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com smallT = minT1; 77a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else { 78a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad1, maxT1, q1pt.x, q1pt.y); // FIXME: debug code 79aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)); 80a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com smallT = maxT1; 81a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 82639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 83a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com smallT = interp(minT1, maxT1, minT); 84a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad1, smallT, q1pt.x, q1pt.y); 85a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad2, minT2, q2pt.x, q2pt.y); 866d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)) { 87a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com largeT = minT2; 88a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else { 89a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad2, maxT2, q2pt.x, q2pt.y); // FIXME: debug code 90aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)); 91a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com largeT = maxT2; 92a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 93639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 94a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com intersections.add(smallT, largeT); 95639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return true; 96639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 97639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return false; 98639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 99639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com int split; 100639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (intersections.swapped()) { 101639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double newMinT1 = interp(minT1, maxT1, minT); 102639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double newMaxT1 = interp(minT1, maxT1, maxT); 103639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1; 104198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#define VERBOSE 0 105198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#if VERBOSE 106639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n", __FUNCTION__, depth, 107639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com splits, newMinT1, newMaxT1, minT1, maxT1, split); 108198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#endif 109639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT1 = newMinT1; 110639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT1 = newMaxT1; 111639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 112639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double newMinT2 = interp(minT2, maxT2, minT); 113639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double newMaxT2 = interp(minT2, maxT2, maxT); 114639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit; 115198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#if VERBOSE 116639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n", __FUNCTION__, depth, 117639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com splits, newMinT2, newMaxT2, minT2, maxT2, split); 118198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com#endif 119639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com minT2 = newMinT2; 120639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com maxT2 = newMaxT2; 121639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 122639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return chop(minT1, maxT1, minT2, maxT2, split); 123639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 124639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 125a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.combool intersectAsLine(double minT1, double maxT1, double minT2, double maxT2, 126a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com bool treat1AsLine, bool treat2AsLine) 127a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com{ 128a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com _Line line1, line2; 129a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (intersections.swapped()) { 130aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(treat1AsLine, treat2AsLine); 131aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(minT1, minT2); 132aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkTSwap(maxT1, maxT2); 133a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 134235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (coinMinT1 >= 0) { 135235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bool earlyExit; 136235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if ((earlyExit = coinMaxT1 == minT1)) { 137235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMaxT1 = maxT1; 138235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 139235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (coinMaxT2 == minT2) { 140235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMaxT2 = maxT2; 141235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return true; 142235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 143235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (earlyExit) { 144235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return true; 145235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 146235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMinT1 = -1; 147235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 148a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com // do line/quadratic or even line/line intersection instead 149a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (treat1AsLine) { 150a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad1, minT1, line1[0].x, line1[0].y); 151a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad1, maxT1, line1[1].x, line1[1].y); 152a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 153a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (treat2AsLine) { 154a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad2, minT2, line2[0].x, line2[0].y); 155a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(quad2, maxT2, line2[1].x, line2[1].y); 156a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 157a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com int pts; 158235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double smallT1, largeT1, smallT2, largeT2; 159a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (treat1AsLine & treat2AsLine) { 160a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com double t1[2], t2[2]; 161a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com pts = ::intersect(line1, line2, t1, t2); 162235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (pts == 2) { 163235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = interp(minT1, maxT1, t1[0]); 164235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = interp(minT2, maxT2, t2[0]); 165235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT2 = interp(minT1, maxT1, t1[1]); 166235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT2 = interp(minT2, maxT2, t2[1]); 167235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com intersections.addCoincident(smallT1, smallT2, largeT1, largeT2); 168235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else { 169235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = interp(minT1, maxT1, t1[0]); 170235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = interp(minT2, maxT2, t2[0]); 171235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com intersections.add(smallT1, largeT1); 172a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 173a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else { 174a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com Intersections lq; 175a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com pts = ::intersect(treat1AsLine ? quad2 : quad1, 176a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com treat1AsLine ? line1 : line2, lq); 177a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com if (pts == 2) { // if the line and edge are coincident treat differently 178a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com _Point midQuad, midLine; 179a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com double midQuadT = (lq.fT[0][0] + lq.fT[0][1]) / 2; 180a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(treat1AsLine ? quad2 : quad1, midQuadT, midQuad.x, midQuad.y); 181a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com double lineT = t_at(treat1AsLine ? line1 : line2, midQuad); 182a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com xy_at_t(treat1AsLine ? line1 : line2, lineT, midLine.x, midLine.y); 1836d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (AlmostEqualUlps(midQuad.x, midLine.x) 1846d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com && AlmostEqualUlps(midQuad.y, midLine.y)) { 185235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = lq.fT[0][0]; 186235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = lq.fT[1][0]; 187235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT2 = lq.fT[0][1]; 188235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT2 = lq.fT[1][1]; 189235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (treat2AsLine) { 190235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = interp(minT1, maxT1, smallT1); 191235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT2 = interp(minT1, maxT1, smallT2); 192235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else { 193235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = interp(minT2, maxT2, largeT1); 194235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT2 = interp(minT2, maxT2, largeT2); 195235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 196235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com intersections.addCoincident(smallT1, smallT2, largeT1, largeT2); 197235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com goto setCoinMinMax; 198235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 199a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 200a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com for (int index = 0; index < pts; ++index) { 201235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = lq.fT[0][index]; 202235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = lq.fT[1][index]; 203235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (treat2AsLine) { 204235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com smallT1 = interp(minT1, maxT1, smallT1); 205a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } else { 206235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com largeT1 = interp(minT2, maxT2, largeT1); 207a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 208235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com intersections.add(smallT1, largeT1); 209a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 210a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com } 211235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (pts > 0) { 212235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comsetCoinMinMax: 213235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMinT1 = minT1; 214235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMaxT1 = maxT1; 215235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMinT2 = minT2; 216235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com coinMaxT2 = maxT2; 217235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 218a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com return pts > 0; 219a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com} 220a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.com 221639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.combool chop(double minT1, double maxT1, double minT2, double maxT2, int split) { 222639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com ++depth; 223639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersections.swap(); 224639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (split) { 225639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com ++splits; 226639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com if (split & 2) { 227639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double middle1 = (maxT1 + minT1) / 2; 228639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersect(minT1, middle1, minT2, maxT2); 229639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersect(middle1, maxT1, minT2, maxT2); 230639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } else { 231639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com double middle2 = (maxT2 + minT2) / 2; 232639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersect(minT1, maxT1, minT2, middle2); 233639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersect(minT1, maxT1, middle2, maxT2); 234639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 235639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com --splits; 236639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersections.swap(); 237639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com --depth; 238639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return intersections.intersected(); 239639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com } 240639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com bool result = intersect(minT1, maxT1, minT2, maxT2); 241639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com intersections.swap(); 242639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com --depth; 243639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com return result; 244639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 245639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 246639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comprivate: 247639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 248639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comconst Quadratic& quad1; 249639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comconst Quadratic& quad2; 250639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comIntersections& intersections; 251639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comint depth; 252639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.comint splits; 253a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.comdouble quad1Divisions; // line segments to approximate original within error 254a7e483d130a65833e4c0d4abb4c2f13a9ce7703bcaryclark@google.comdouble quad2Divisions; 255235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comdouble coinMinT1; // range of Ts where approximate line intersected curve 256235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comdouble coinMaxT1; 257235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comdouble coinMinT2; 258235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comdouble coinMaxT2; 259639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com}; 260639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com 261235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com#include "LineParameters.h" 262235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 263235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comstatic void hackToFixPartialCoincidence(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 264235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // look to see if non-coincident data basically has unsortable tangents 265055c7c299cb47eebd360b809ad58a0006e2e55f7skia.committer@gmail.com 266235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // look to see if a point between non-coincident data is on the curve 267235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int cIndex; 268235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com for (int uIndex = 0; uIndex < i.fUsed; ) { 269235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double bestDist1 = 1; 270235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double bestDist2 = 1; 271235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int closest1 = -1; 272235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int closest2 = -1; 273235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com for (cIndex = 0; cIndex < i.fCoincidentUsed; ++cIndex) { 274235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double dist = fabs(i.fT[0][uIndex] - i.fCoincidentT[0][cIndex]); 275235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (bestDist1 > dist) { 276235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bestDist1 = dist; 277235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com closest1 = cIndex; 278235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 279235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com dist = fabs(i.fT[1][uIndex] - i.fCoincidentT[1][cIndex]); 280235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (bestDist2 > dist) { 281235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bestDist2 = dist; 282235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com closest2 = cIndex; 283235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 284235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 285235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com _Line ends; 286235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com _Point mid; 287235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double t1 = i.fT[0][uIndex]; 288235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q1, t1, ends[0].x, ends[0].y); 289235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q1, i.fCoincidentT[0][closest1], ends[1].x, ends[1].y); 290235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double midT = (t1 + i.fCoincidentT[0][closest1]) / 2; 291235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q1, midT, mid.x, mid.y); 292235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com LineParameters params; 293235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com params.lineEndPoints(ends); 294235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double midDist = params.pointDistance(mid); 295235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // Note that we prefer to always measure t error, which does not scale, 296235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // instead of point error, which is scale dependent. FIXME 297235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!approximately_zero(midDist)) { 298235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com ++uIndex; 299235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 300235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 301235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double t2 = i.fT[1][uIndex]; 302235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q2, t2, ends[0].x, ends[0].y); 303235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q2, i.fCoincidentT[1][closest2], ends[1].x, ends[1].y); 304235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com midT = (t2 + i.fCoincidentT[1][closest2]) / 2; 305235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q2, midT, mid.x, mid.y); 306235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com params.lineEndPoints(ends); 307235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com midDist = params.pointDistance(mid); 308235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!approximately_zero(midDist)) { 309235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com ++uIndex; 310235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 311235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 312235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // if both midpoints are close to the line, lengthen coincident span 313235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int cEnd = closest1 ^ 1; // assume coincidence always travels in pairs 314235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!between(i.fCoincidentT[0][cEnd], t1, i.fCoincidentT[0][closest1])) { 315235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.fCoincidentT[0][closest1] = t1; 316235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 317235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com cEnd = closest2 ^ 1; 318235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (!between(i.fCoincidentT[0][cEnd], t2, i.fCoincidentT[0][closest2])) { 319235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.fCoincidentT[0][closest2] = t2; 320235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 321235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int remaining = --i.fUsed - uIndex; 322235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (remaining > 0) { 323235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com memmove(&i.fT[0][uIndex], &i.fT[0][uIndex + 1], sizeof(i.fT[0][0]) * remaining); 324235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com memmove(&i.fT[1][uIndex], &i.fT[1][uIndex + 1], sizeof(i.fT[1][0]) * remaining); 325235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 326235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 327235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // if coincident data is subjectively a tiny span, replace it with a single point 328235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com for (cIndex = 0; cIndex < i.fCoincidentUsed; ) { 329235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double start1 = i.fCoincidentT[0][cIndex]; 330235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double end1 = i.fCoincidentT[0][cIndex + 1]; 331235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com _Line ends1; 332235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q1, start1, ends1[0].x, ends1[0].y); 333235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q1, end1, ends1[1].x, ends1[1].y); 3346d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(ends1[0].x, ends1[1].x) || AlmostEqualUlps(ends1[0].y, ends1[1].y)) { 335235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com cIndex += 2; 336235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 337235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 338235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double start2 = i.fCoincidentT[1][cIndex]; 339235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com double end2 = i.fCoincidentT[1][cIndex + 1]; 340235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com _Line ends2; 341235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q2, start2, ends2[0].x, ends2[0].y); 342235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com xy_at_t(q2, end2, ends2[1].x, ends2[1].y); 343235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // again, approximately should be used with T values, not points FIXME 3446d0032a8ec680221c2a704cac2391f2a2d77546fcaryclark@google.com if (!AlmostEqualUlps(ends2[0].x, ends2[1].x) || AlmostEqualUlps(ends2[0].y, ends2[1].y)) { 345235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com cIndex += 2; 346235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com continue; 347235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 348235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (approximately_less_than_zero(start1) || approximately_less_than_zero(end1)) { 349235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start1 = 0; 350235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else if (approximately_greater_than_one(start1) || approximately_greater_than_one(end1)) { 351235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start1 = 1; 352235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else { 353235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start1 = (start1 + end1) / 2; 354235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 355235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (approximately_less_than_zero(start2) || approximately_less_than_zero(end2)) { 356235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start2 = 0; 357235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else if (approximately_greater_than_one(start2) || approximately_greater_than_one(end2)) { 358235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start2 = 1; 359235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } else { 360235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com start2 = (start2 + end2) / 2; 361235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 362235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.insert(start1, start2); 363235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.fCoincidentUsed -= 2; 364235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com int remaining = i.fCoincidentUsed - cIndex; 365235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (remaining > 0) { 366235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com memmove(&i.fCoincidentT[0][cIndex], &i.fCoincidentT[0][cIndex + 2], sizeof(i.fCoincidentT[0][0]) * remaining); 367235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com memmove(&i.fCoincidentT[1][cIndex], &i.fCoincidentT[1][cIndex + 2], sizeof(i.fCoincidentT[1][0]) * remaining); 368235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 369235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 370235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com} 371235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 372c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& i) { 373fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if (implicit_matches(q1, q2)) { 374fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com // FIXME: compute T values 375fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com // compute the intersections of the ends to find the coincident span 376fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool useVertical = fabs(q1[0].x - q1[2].x) < fabs(q1[0].y - q1[2].y); 377fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double t; 378fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if ((t = axialIntersect(q1, q2[0], useVertical)) >= 0) { 379235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.addCoincident(t, 0); 380fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 381fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if ((t = axialIntersect(q1, q2[2], useVertical)) >= 0) { 382235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.addCoincident(t, 1); 383fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 384fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com useVertical = fabs(q2[0].x - q2[2].x) < fabs(q2[0].y - q2[2].y); 385fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if ((t = axialIntersect(q2, q1[0], useVertical)) >= 0) { 386235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.addCoincident(0, t); 387fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 388fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com if ((t = axialIntersect(q2, q1[2], useVertical)) >= 0) { 389235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com i.addCoincident(1, t); 390fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 391aa35831d1d0e4c798a63fe772430adc4f3a038cdcaryclark@google.com SkASSERT(i.fCoincidentUsed <= 2); 39232546db1494a6c6433a7919844133a6ff5b5c7b2caryclark@google.com return i.fCoincidentUsed > 0; 393fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com } 394639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com QuadraticIntersections q(q1, q2, i); 395235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com bool result = q.intersect(); 396235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // FIXME: partial coincidence detection is currently poor. For now, try 397235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // to fix up the data after the fact. In the future, revisit the error 398235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com // term to try to avoid this kind of result in the first place. 399235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com if (i.fUsed && i.fCoincidentUsed) { 400235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com hackToFixPartialCoincidence(q1, q2, i); 401235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com } 402235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com return result; 403639df891487e40925a4f8d9a34fd3dc0c18b40a7caryclark@google.com} 404