1/* 2 * Copyright 2015 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7#include "SkIntersections.h" 8#include "SkPathOpsConic.h" 9#include "SkPathOpsLine.h" 10 11class LineConicIntersections { 12public: 13 enum PinTPoint { 14 kPointUninitialized, 15 kPointInitialized 16 }; 17 18 LineConicIntersections(const SkDConic& c, const SkDLine& l, SkIntersections* i) 19 : fConic(c) 20 , fLine(&l) 21 , fIntersections(i) 22 , fAllowNear(true) { 23 i->setMax(3); // allow short partial coincidence plus discrete intersection 24 } 25 26 LineConicIntersections(const SkDConic& c) 27 : fConic(c) 28 SkDEBUGPARAMS(fLine(nullptr)) 29 SkDEBUGPARAMS(fIntersections(nullptr)) 30 SkDEBUGPARAMS(fAllowNear(false)) { 31 } 32 33 void allowNear(bool allow) { 34 fAllowNear = allow; 35 } 36 37 void checkCoincident() { 38 int last = fIntersections->used() - 1; 39 for (int index = 0; index < last; ) { 40 double conicMidT = ((*fIntersections)[0][index] + (*fIntersections)[0][index + 1]) / 2; 41 SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 42 double t = fLine->nearPoint(conicMidPt, nullptr); 43 if (t < 0) { 44 ++index; 45 continue; 46 } 47 if (fIntersections->isCoincident(index)) { 48 fIntersections->removeOne(index); 49 --last; 50 } else if (fIntersections->isCoincident(index + 1)) { 51 fIntersections->removeOne(index + 1); 52 --last; 53 } else { 54 fIntersections->setCoincident(index++); 55 } 56 fIntersections->setCoincident(index); 57 } 58 } 59 60#ifdef SK_DEBUG 61 static bool close_to(double a, double b, const double c[3]) { 62 double max = SkTMax(-SkTMin(SkTMin(c[0], c[1]), c[2]), SkTMax(SkTMax(c[0], c[1]), c[2])); 63 return approximately_zero_when_compared_to(a - b, max); 64 } 65#endif 66 int horizontalIntersect(double axisIntercept, double roots[2]) { 67 double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }; 68 return this->validT(conicVals, axisIntercept, roots); 69 } 70 71 int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { 72 this->addExactHorizontalEndPoints(left, right, axisIntercept); 73 if (fAllowNear) { 74 this->addNearHorizontalEndPoints(left, right, axisIntercept); 75 } 76 double roots[2]; 77 int count = this->horizontalIntersect(axisIntercept, roots); 78 for (int index = 0; index < count; ++index) { 79 double conicT = roots[index]; 80 SkDPoint pt = fConic.ptAtT(conicT); 81 SkDEBUGCODE_(double conicVals[] = { fConic[0].fY, fConic[1].fY, fConic[2].fY }); 82 SkASSERT(close_to(pt.fY, axisIntercept, conicVals)); 83 double lineT = (pt.fX - left) / (right - left); 84 if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 85 && this->uniqueAnswer(conicT, pt)) { 86 fIntersections->insert(conicT, lineT, pt); 87 } 88 } 89 if (flipped) { 90 fIntersections->flip(); 91 } 92 this->checkCoincident(); 93 return fIntersections->used(); 94 } 95 96 int intersect() { 97 this->addExactEndPoints(); 98 if (fAllowNear) { 99 this->addNearEndPoints(); 100 } 101 double rootVals[2]; 102 int roots = this->intersectRay(rootVals); 103 for (int index = 0; index < roots; ++index) { 104 double conicT = rootVals[index]; 105 double lineT = this->findLineT(conicT); 106 SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); 107 SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); 108 SkASSERT(conicPt.approximatelyEqual(linePt)); 109 SkDPoint pt; 110 if (this->pinTs(&conicT, &lineT, &pt, kPointUninitialized) 111 && this->uniqueAnswer(conicT, pt)) { 112 fIntersections->insert(conicT, lineT, pt); 113 } 114 } 115 this->checkCoincident(); 116 return fIntersections->used(); 117 } 118 119 int intersectRay(double roots[2]) { 120 double adj = (*fLine)[1].fX - (*fLine)[0].fX; 121 double opp = (*fLine)[1].fY - (*fLine)[0].fY; 122 double r[3]; 123 for (int n = 0; n < 3; ++n) { 124 r[n] = (fConic[n].fY - (*fLine)[0].fY) * adj - (fConic[n].fX - (*fLine)[0].fX) * opp; 125 } 126 return this->validT(r, 0, roots); 127 } 128 129 int validT(double r[3], double axisIntercept, double roots[2]) { 130 double A = r[2]; 131 double B = r[1] * fConic.fWeight - axisIntercept * fConic.fWeight + axisIntercept; 132 double C = r[0]; 133 A += C - 2 * B; // A = a + c - 2*(b*w - xCept*w + xCept) 134 B -= C; // B = b*w - w * xCept + xCept - a 135 C -= axisIntercept; 136 return SkDQuad::RootsValidT(A, 2 * B, C, roots); 137 } 138 139 int verticalIntersect(double axisIntercept, double roots[2]) { 140 double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }; 141 return this->validT(conicVals, axisIntercept, roots); 142 } 143 144 int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { 145 this->addExactVerticalEndPoints(top, bottom, axisIntercept); 146 if (fAllowNear) { 147 this->addNearVerticalEndPoints(top, bottom, axisIntercept); 148 } 149 double roots[2]; 150 int count = this->verticalIntersect(axisIntercept, roots); 151 for (int index = 0; index < count; ++index) { 152 double conicT = roots[index]; 153 SkDPoint pt = fConic.ptAtT(conicT); 154 SkDEBUGCODE_(double conicVals[] = { fConic[0].fX, fConic[1].fX, fConic[2].fX }); 155 SkASSERT(close_to(pt.fX, axisIntercept, conicVals)); 156 double lineT = (pt.fY - top) / (bottom - top); 157 if (this->pinTs(&conicT, &lineT, &pt, kPointInitialized) 158 && this->uniqueAnswer(conicT, pt)) { 159 fIntersections->insert(conicT, lineT, pt); 160 } 161 } 162 if (flipped) { 163 fIntersections->flip(); 164 } 165 this->checkCoincident(); 166 return fIntersections->used(); 167 } 168 169protected: 170// OPTIMIZE: Functions of the form add .. points are indentical to the conic routines. 171 // add endpoints first to get zero and one t values exactly 172 void addExactEndPoints() { 173 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 174 double lineT = fLine->exactPoint(fConic[cIndex]); 175 if (lineT < 0) { 176 continue; 177 } 178 double conicT = (double) (cIndex >> 1); 179 fIntersections->insert(conicT, lineT, fConic[cIndex]); 180 } 181 } 182 183 void addNearEndPoints() { 184 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 185 double conicT = (double) (cIndex >> 1); 186 if (fIntersections->hasT(conicT)) { 187 continue; 188 } 189 double lineT = fLine->nearPoint(fConic[cIndex], nullptr); 190 if (lineT < 0) { 191 continue; 192 } 193 fIntersections->insert(conicT, lineT, fConic[cIndex]); 194 } 195 // FIXME: see if line end is nearly on conic 196 } 197 198 void addExactHorizontalEndPoints(double left, double right, double y) { 199 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 200 double lineT = SkDLine::ExactPointH(fConic[cIndex], left, right, y); 201 if (lineT < 0) { 202 continue; 203 } 204 double conicT = (double) (cIndex >> 1); 205 fIntersections->insert(conicT, lineT, fConic[cIndex]); 206 } 207 } 208 209 void addNearHorizontalEndPoints(double left, double right, double y) { 210 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 211 double conicT = (double) (cIndex >> 1); 212 if (fIntersections->hasT(conicT)) { 213 continue; 214 } 215 double lineT = SkDLine::NearPointH(fConic[cIndex], left, right, y); 216 if (lineT < 0) { 217 continue; 218 } 219 fIntersections->insert(conicT, lineT, fConic[cIndex]); 220 } 221 // FIXME: see if line end is nearly on conic 222 } 223 224 void addExactVerticalEndPoints(double top, double bottom, double x) { 225 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 226 double lineT = SkDLine::ExactPointV(fConic[cIndex], top, bottom, x); 227 if (lineT < 0) { 228 continue; 229 } 230 double conicT = (double) (cIndex >> 1); 231 fIntersections->insert(conicT, lineT, fConic[cIndex]); 232 } 233 } 234 235 void addNearVerticalEndPoints(double top, double bottom, double x) { 236 for (int cIndex = 0; cIndex < SkDConic::kPointCount; cIndex += SkDConic::kPointLast) { 237 double conicT = (double) (cIndex >> 1); 238 if (fIntersections->hasT(conicT)) { 239 continue; 240 } 241 double lineT = SkDLine::NearPointV(fConic[cIndex], top, bottom, x); 242 if (lineT < 0) { 243 continue; 244 } 245 fIntersections->insert(conicT, lineT, fConic[cIndex]); 246 } 247 // FIXME: see if line end is nearly on conic 248 } 249 250 double findLineT(double t) { 251 SkDPoint xy = fConic.ptAtT(t); 252 double dx = (*fLine)[1].fX - (*fLine)[0].fX; 253 double dy = (*fLine)[1].fY - (*fLine)[0].fY; 254 if (fabs(dx) > fabs(dy)) { 255 return (xy.fX - (*fLine)[0].fX) / dx; 256 } 257 return (xy.fY - (*fLine)[0].fY) / dy; 258 } 259 260 bool pinTs(double* conicT, double* lineT, SkDPoint* pt, PinTPoint ptSet) { 261 if (!approximately_one_or_less_double(*lineT)) { 262 return false; 263 } 264 if (!approximately_zero_or_more_double(*lineT)) { 265 return false; 266 } 267 double qT = *conicT = SkPinT(*conicT); 268 double lT = *lineT = SkPinT(*lineT); 269 if (lT == 0 || lT == 1 || (ptSet == kPointUninitialized && qT != 0 && qT != 1)) { 270 *pt = (*fLine).ptAtT(lT); 271 } else if (ptSet == kPointUninitialized) { 272 *pt = fConic.ptAtT(qT); 273 } 274 SkPoint gridPt = pt->asSkPoint(); 275 if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[0].asSkPoint())) { 276 *pt = (*fLine)[0]; 277 *lineT = 0; 278 } else if (SkDPoint::ApproximatelyEqual(gridPt, (*fLine)[1].asSkPoint())) { 279 *pt = (*fLine)[1]; 280 *lineT = 1; 281 } 282 if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) { 283 return false; 284 } 285 if (gridPt == fConic[0].asSkPoint()) { 286 *pt = fConic[0]; 287 *conicT = 0; 288 } else if (gridPt == fConic[2].asSkPoint()) { 289 *pt = fConic[2]; 290 *conicT = 1; 291 } 292 return true; 293 } 294 295 bool uniqueAnswer(double conicT, const SkDPoint& pt) { 296 for (int inner = 0; inner < fIntersections->used(); ++inner) { 297 if (fIntersections->pt(inner) != pt) { 298 continue; 299 } 300 double existingConicT = (*fIntersections)[0][inner]; 301 if (conicT == existingConicT) { 302 return false; 303 } 304 // check if midway on conic is also same point. If so, discard this 305 double conicMidT = (existingConicT + conicT) / 2; 306 SkDPoint conicMidPt = fConic.ptAtT(conicMidT); 307 if (conicMidPt.approximatelyEqual(pt)) { 308 return false; 309 } 310 } 311#if ONE_OFF_DEBUG 312 SkDPoint qPt = fConic.ptAtT(conicT); 313 SkDebugf("%s pt=(%1.9g,%1.9g) cPt=(%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY, 314 qPt.fX, qPt.fY); 315#endif 316 return true; 317 } 318 319private: 320 const SkDConic& fConic; 321 const SkDLine* fLine; 322 SkIntersections* fIntersections; 323 bool fAllowNear; 324}; 325 326int SkIntersections::horizontal(const SkDConic& conic, double left, double right, double y, 327 bool flipped) { 328 SkDLine line = {{{ left, y }, { right, y }}}; 329 LineConicIntersections c(conic, line, this); 330 return c.horizontalIntersect(y, left, right, flipped); 331} 332 333int SkIntersections::vertical(const SkDConic& conic, double top, double bottom, double x, 334 bool flipped) { 335 SkDLine line = {{{ x, top }, { x, bottom }}}; 336 LineConicIntersections c(conic, line, this); 337 return c.verticalIntersect(x, top, bottom, flipped); 338} 339 340int SkIntersections::intersect(const SkDConic& conic, const SkDLine& line) { 341 LineConicIntersections c(conic, line, this); 342 c.allowNear(fAllowNear); 343 return c.intersect(); 344} 345 346int SkIntersections::intersectRay(const SkDConic& conic, const SkDLine& line) { 347 LineConicIntersections c(conic, line, this); 348 fUsed = c.intersectRay(fT[0]); 349 for (int index = 0; index < fUsed; ++index) { 350 fPt[index] = conic.ptAtT(fT[0][index]); 351 } 352 return fUsed; 353} 354 355int SkIntersections::HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots) { 356 LineConicIntersections c(conic); 357 return c.horizontalIntersect(y, roots); 358} 359 360int SkIntersections::VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots) { 361 LineConicIntersections c(conic); 362 return c.verticalIntersect(x, roots); 363} 364