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