SkPathOpsQuad.cpp (13494B)
1 /* 2 * Copyright 2012 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 "src/pathops/SkPathOpsQuad.h" 8 9 #include "src/pathops/SkIntersections.h" 10 #include "src/pathops/SkLineParameters.h" 11 #include "src/pathops/SkPathOpsConic.h" 12 #include "src/pathops/SkPathOpsCubic.h" 13 #include "src/pathops/SkPathOpsLine.h" 14 #include "src/pathops/SkPathOpsRect.h" 15 #include "src/pathops/SkPathOpsTypes.h" 16 17 #include <algorithm> 18 #include <cmath> 19 20 // from blackpawn.com/texts/pointinpoly 21 static bool pointInTriangle(const SkDPoint fPts[3], const SkDPoint& test) { 22 SkDVector v0 = fPts[2] - fPts[0]; 23 SkDVector v1 = fPts[1] - fPts[0]; 24 SkDVector v2 = test - fPts[0]; 25 double dot00 = v0.dot(v0); 26 double dot01 = v0.dot(v1); 27 double dot02 = v0.dot(v2); 28 double dot11 = v1.dot(v1); 29 double dot12 = v1.dot(v2); 30 // Compute barycentric coordinates 31 double denom = dot00 * dot11 - dot01 * dot01; 32 double u = dot11 * dot02 - dot01 * dot12; 33 double v = dot00 * dot12 - dot01 * dot02; 34 // Check if point is in triangle 35 if (denom >= 0) { 36 return u >= 0 && v >= 0 && u + v < denom; 37 } 38 return u <= 0 && v <= 0 && u + v > denom; 39 } 40 41 static bool matchesEnd(const SkDPoint fPts[3], const SkDPoint& test) { 42 return fPts[0] == test || fPts[2] == test; 43 } 44 45 /* started with at_most_end_pts_in_common from SkDQuadIntersection.cpp */ 46 // Do a quick reject by rotating all points relative to a line formed by 47 // a pair of one quad's points. If the 2nd quad's points 48 // are on the line or on the opposite side from the 1st quad's 'odd man', the 49 // curves at most intersect at the endpoints. 50 /* if returning true, check contains true if quad's hull collapsed, making the cubic linear 51 if returning false, check contains true if the the quad pair have only the end point in common 52 */ 53 bool SkDQuad::hullIntersects(const SkDQuad& q2, bool* isLinear) const { 54 bool linear = true; 55 for (int oddMan = 0; oddMan < kPointCount; ++oddMan) { 56 const SkDPoint* endPt[2]; 57 this->otherPts(oddMan, endPt); 58 double origX = endPt[0]->fX; 59 double origY = endPt[0]->fY; 60 double adj = endPt[1]->fX - origX; 61 double opp = endPt[1]->fY - origY; 62 double sign = (fPts[oddMan].fY - origY) * adj - (fPts[oddMan].fX - origX) * opp; 63 if (approximately_zero(sign)) { 64 continue; 65 } 66 linear = false; 67 bool foundOutlier = false; 68 for (int n = 0; n < kPointCount; ++n) { 69 double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 70 if (test * sign > 0 && !precisely_zero(test)) { 71 foundOutlier = true; 72 break; 73 } 74 } 75 if (!foundOutlier) { 76 return false; 77 } 78 } 79 if (linear && !matchesEnd(fPts, q2.fPts[0]) && !matchesEnd(fPts, q2.fPts[2])) { 80 // if the end point of the opposite quad is inside the hull that is nearly a line, 81 // then representing the quad as a line may cause the intersection to be missed. 82 // Check to see if the endpoint is in the triangle. 83 if (pointInTriangle(fPts, q2.fPts[0]) || pointInTriangle(fPts, q2.fPts[2])) { 84 linear = false; 85 } 86 } 87 *isLinear = linear; 88 return true; 89 } 90 91 bool SkDQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const { 92 return conic.hullIntersects(*this, isLinear); 93 } 94 95 bool SkDQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 96 return cubic.hullIntersects(*this, isLinear); 97 } 98 99 /* bit twiddling for finding the off curve index (x&~m is the pair in [0,1,2] excluding oddMan) 100 oddMan opp x=oddMan^opp x=x-oddMan m=x>>2 x&~m 101 0 1 1 1 0 1 102 2 2 2 0 2 103 1 1 0 -1 -1 0 104 2 3 2 0 2 105 2 1 3 1 0 1 106 2 0 -2 -1 0 107 */ 108 void SkDQuad::otherPts(int oddMan, const SkDPoint* endPt[2]) const { 109 for (int opp = 1; opp < kPointCount; ++opp) { 110 int end = (oddMan ^ opp) - oddMan; // choose a value not equal to oddMan 111 end &= ~(end >> 2); // if the value went negative, set it to zero 112 endPt[opp - 1] = &fPts[end]; 113 } 114 } 115 116 int SkDQuad::AddValidTs(double s[], int realRoots, double* t) { 117 int foundRoots = 0; 118 for (int index = 0; index < realRoots; ++index) { 119 double tValue = s[index]; 120 if (approximately_zero_or_more(tValue) && approximately_one_or_less(tValue)) { 121 if (approximately_less_than_zero(tValue)) { 122 tValue = 0; 123 } else if (approximately_greater_than_one(tValue)) { 124 tValue = 1; 125 } 126 for (int idx2 = 0; idx2 < foundRoots; ++idx2) { 127 if (approximately_equal(t[idx2], tValue)) { 128 goto nextRoot; 129 } 130 } 131 t[foundRoots++] = tValue; 132 } 133 nextRoot: 134 {} 135 } 136 return foundRoots; 137 } 138 139 // note: caller expects multiple results to be sorted smaller first 140 // note: http://en.wikipedia.org/wiki/Loss_of_significance has an interesting 141 // analysis of the quadratic equation, suggesting why the following looks at 142 // the sign of B -- and further suggesting that the greatest loss of precision 143 // is in b squared less two a c 144 int SkDQuad::RootsValidT(double A, double B, double C, double t[2]) { 145 double s[2]; 146 int realRoots = RootsReal(A, B, C, s); 147 int foundRoots = AddValidTs(s, realRoots, t); 148 return foundRoots; 149 } 150 151 static int handle_zero(const double B, const double C, double s[2]) { 152 if (approximately_zero(B)) { 153 s[0] = 0; 154 return C == 0; 155 } 156 s[0] = -C / B; 157 return 1; 158 } 159 160 /* 161 Numeric Solutions (5.6) suggests to solve the quadratic by computing 162 Q = -1/2(B + sgn(B)Sqrt(B^2 - 4 A C)) 163 and using the roots 164 t1 = Q / A 165 t2 = C / Q 166 */ 167 // this does not discard real roots <= 0 or >= 1 168 // TODO(skbug.com/40045140) Deduplicate with SkQuads::RootsReal 169 int SkDQuad::RootsReal(const double A, const double B, const double C, double s[2]) { 170 if (!A) { 171 return handle_zero(B, C, s); 172 } 173 const double p = B / (2 * A); 174 const double q = C / A; 175 if (approximately_zero(A) && (approximately_zero_inverse(p) || approximately_zero_inverse(q))) { 176 return handle_zero(B, C, s); 177 } 178 /* normal form: x^2 + px + q = 0 */ 179 const double p2 = p * p; 180 if (!AlmostDequalUlps(p2, q) && p2 < q) { 181 return 0; 182 } 183 double sqrt_D = 0; 184 if (p2 > q) { 185 sqrt_D = sqrt(p2 - q); 186 } 187 s[0] = sqrt_D - p; 188 s[1] = -sqrt_D - p; 189 return 1 + !AlmostDequalUlps(s[0], s[1]); 190 } 191 192 bool SkDQuad::isLinear(int startIndex, int endIndex) const { 193 SkLineParameters lineParameters; 194 lineParameters.quadEndPoints(*this, startIndex, endIndex); 195 // FIXME: maybe it's possible to avoid this and compare non-normalized 196 lineParameters.normalize(); 197 double distance = lineParameters.controlPtDistance(*this); 198 double tiniest = std::min(std::min(std::min(std::min(std::min(fPts[0].fX, fPts[0].fY), 199 fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY); 200 double largest = std::max(std::max(std::max(std::max(std::max(fPts[0].fX, fPts[0].fY), 201 fPts[1].fX), fPts[1].fY), fPts[2].fX), fPts[2].fY); 202 largest = std::max(largest, -tiniest); 203 return approximately_zero_when_compared_to(distance, largest); 204 } 205 206 SkDVector SkDQuad::dxdyAtT(double t) const { 207 double a = t - 1; 208 double b = 1 - 2 * t; 209 double c = t; 210 SkDVector result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 211 a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 212 if (result.fX == 0 && result.fY == 0) { 213 if (zero_or_one(t)) { 214 result = fPts[2] - fPts[0]; 215 } else { 216 // incomplete 217 SkDebugf("!q"); 218 } 219 } 220 return result; 221 } 222 223 // OPTIMIZE: assert if caller passes in t == 0 / t == 1 ? 224 SkDPoint SkDQuad::ptAtT(double t) const { 225 if (0 == t) { 226 return fPts[0]; 227 } 228 if (1 == t) { 229 return fPts[2]; 230 } 231 double one_t = 1 - t; 232 double a = one_t * one_t; 233 double b = 2 * one_t * t; 234 double c = t * t; 235 SkDPoint result = { a * fPts[0].fX + b * fPts[1].fX + c * fPts[2].fX, 236 a * fPts[0].fY + b * fPts[1].fY + c * fPts[2].fY }; 237 return result; 238 } 239 240 static double interp_quad_coords(const double* src, double t) { 241 if (0 == t) { 242 return src[0]; 243 } 244 if (1 == t) { 245 return src[4]; 246 } 247 double ab = SkDInterp(src[0], src[2], t); 248 double bc = SkDInterp(src[2], src[4], t); 249 double abc = SkDInterp(ab, bc, t); 250 return abc; 251 } 252 253 bool SkDQuad::monotonicInX() const { 254 return between(fPts[0].fX, fPts[1].fX, fPts[2].fX); 255 } 256 257 bool SkDQuad::monotonicInY() const { 258 return between(fPts[0].fY, fPts[1].fY, fPts[2].fY); 259 } 260 261 /* 262 Given a quadratic q, t1, and t2, find a small quadratic segment. 263 264 The new quadratic is defined by A, B, and C, where 265 A = c[0]*(1 - t1)*(1 - t1) + 2*c[1]*t1*(1 - t1) + c[2]*t1*t1 266 C = c[3]*(1 - t1)*(1 - t1) + 2*c[2]*t1*(1 - t1) + c[1]*t1*t1 267 268 To find B, compute the point halfway between t1 and t2: 269 270 q(at (t1 + t2)/2) == D 271 272 Next, compute where D must be if we know the value of B: 273 274 _12 = A/2 + B/2 275 12_ = B/2 + C/2 276 123 = A/4 + B/2 + C/4 277 = D 278 279 Group the known values on one side: 280 281 B = D*2 - A/2 - C/2 282 */ 283 284 // OPTIMIZE? : special case t1 = 1 && t2 = 0 285 SkDQuad SkDQuad::subDivide(double t1, double t2) const { 286 if (0 == t1 && 1 == t2) { 287 return *this; 288 } 289 SkDQuad dst; 290 double ax = dst[0].fX = interp_quad_coords(&fPts[0].fX, t1); 291 double ay = dst[0].fY = interp_quad_coords(&fPts[0].fY, t1); 292 double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); 293 double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); 294 double cx = dst[2].fX = interp_quad_coords(&fPts[0].fX, t2); 295 double cy = dst[2].fY = interp_quad_coords(&fPts[0].fY, t2); 296 /* bx = */ dst[1].fX = 2 * dx - (ax + cx) / 2; 297 /* by = */ dst[1].fY = 2 * dy - (ay + cy) / 2; 298 return dst; 299 } 300 301 void SkDQuad::align(int endIndex, SkDPoint* dstPt) const { 302 if (fPts[endIndex].fX == fPts[1].fX) { 303 dstPt->fX = fPts[endIndex].fX; 304 } 305 if (fPts[endIndex].fY == fPts[1].fY) { 306 dstPt->fY = fPts[endIndex].fY; 307 } 308 } 309 310 SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const { 311 SkASSERT(t1 != t2); 312 SkDPoint b; 313 SkDQuad sub = subDivide(t1, t2); 314 SkDLine b0 = {{a, sub[1] + (a - sub[0])}}; 315 SkDLine b1 = {{c, sub[1] + (c - sub[2])}}; 316 SkIntersections i; 317 i.intersectRay(b0, b1); 318 if (i.used() == 1 && i[0][0] >= 0 && i[1][0] >= 0) { 319 b = i.pt(0); 320 } else { 321 SkASSERT(i.used() <= 2); 322 return SkDPoint::Mid(b0[1], b1[1]); 323 } 324 if (t1 == 0 || t2 == 0) { 325 align(0, &b); 326 } 327 if (t1 == 1 || t2 == 1) { 328 align(2, &b); 329 } 330 if (AlmostBequalUlps(b.fX, a.fX)) { 331 b.fX = a.fX; 332 } else if (AlmostBequalUlps(b.fX, c.fX)) { 333 b.fX = c.fX; 334 } 335 if (AlmostBequalUlps(b.fY, a.fY)) { 336 b.fY = a.fY; 337 } else if (AlmostBequalUlps(b.fY, c.fY)) { 338 b.fY = c.fY; 339 } 340 return b; 341 } 342 343 /* classic one t subdivision */ 344 static void interp_quad_coords(const double* src, double* dst, double t) { 345 double ab = SkDInterp(src[0], src[2], t); 346 double bc = SkDInterp(src[2], src[4], t); 347 dst[0] = src[0]; 348 dst[2] = ab; 349 dst[4] = SkDInterp(ab, bc, t); 350 dst[6] = bc; 351 dst[8] = src[4]; 352 } 353 354 SkDQuadPair SkDQuad::chopAt(double t) const 355 { 356 SkDQuadPair dst; 357 interp_quad_coords(&fPts[0].fX, &dst.pts[0].fX, t); 358 interp_quad_coords(&fPts[0].fY, &dst.pts[0].fY, t); 359 return dst; 360 } 361 362 static int valid_unit_divide(double numer, double denom, double* ratio) 363 { 364 if (numer < 0) { 365 numer = -numer; 366 denom = -denom; 367 } 368 if (denom == 0 || numer == 0 || numer >= denom) { 369 return 0; 370 } 371 double r = numer / denom; 372 if (r == 0) { // catch underflow if numer <<<< denom 373 return 0; 374 } 375 *ratio = r; 376 return 1; 377 } 378 379 /** Quad'(t) = At + B, where 380 A = 2(a - 2b + c) 381 B = 2(b - a) 382 Solve for t, only if it fits between 0 < t < 1 383 */ 384 int SkDQuad::FindExtrema(const double src[], double tValue[1]) { 385 /* At + B == 0 386 t = -B / A 387 */ 388 double a = src[0]; 389 double b = src[2]; 390 double c = src[4]; 391 return valid_unit_divide(a - b, a - b - b + c, tValue); 392 } 393 394 /* Parameterization form, given A*t*t + 2*B*t*(1-t) + C*(1-t)*(1-t) 395 * 396 * a = A - 2*B + C 397 * b = 2*B - 2*C 398 * c = C 399 */ 400 void SkDQuad::SetABC(const double* quad, double* a, double* b, double* c) { 401 *a = quad[0]; // a = A 402 *b = 2 * quad[2]; // b = 2*B 403 *c = quad[4]; // c = C 404 *b -= *c; // b = 2*B - C 405 *a -= *b; // a = A - 2*B + C 406 *b -= *c; // b = 2*B - 2*C 407 } 408 409 int SkTQuad::intersectRay(SkIntersections* i, const SkDLine& line) const { 410 return i->intersectRay(fQuad, line); 411 } 412 413 bool SkTQuad::hullIntersects(const SkDConic& conic, bool* isLinear) const { 414 return conic.hullIntersects(fQuad, isLinear); 415 } 416 417 bool SkTQuad::hullIntersects(const SkDCubic& cubic, bool* isLinear) const { 418 return cubic.hullIntersects(fQuad, isLinear); 419 } 420 421 void SkTQuad::setBounds(SkDRect* rect) const { 422 rect->setBounds(fQuad); 423 }