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 #ifndef SkPathOpsTypes_DEFINED 8 #define SkPathOpsTypes_DEFINED 9 10 #include <float.h> // for FLT_EPSILON 11 #include <math.h> // for fabs, sqrt 12 13 #include "SkFloatingPoint.h" 14 #include "SkPath.h" 15 #include "SkPathOps.h" 16 #include "SkPathOpsDebug.h" 17 #include "SkScalar.h" 18 19 enum SkPathOpsMask { 20 kWinding_PathOpsMask = -1, 21 kNo_PathOpsMask = 0, 22 kEvenOdd_PathOpsMask = 1 23 }; 24 25 class SkOpCoincidence; 26 class SkOpContour; 27 class SkOpContourHead; 28 29 class SkOpGlobalState { 30 public: 31 SkOpGlobalState(SkOpCoincidence* coincidence, SkOpContourHead* head) 32 : fCoincidence(coincidence) 33 , fContourHead(head) 34 , fWindingFailed(false) 35 , fAngleCoincidence(false) 36 #if DEBUG_VALIDATE 37 , fPhase(kIntersecting) 38 #endif 39 SkDEBUGPARAMS(fAngleID(0)) 40 SkDEBUGPARAMS(fContourID(0)) 41 SkDEBUGPARAMS(fPtTID(0)) 42 SkDEBUGPARAMS(fSegmentID(0)) 43 SkDEBUGPARAMS(fSpanID(0)) { 44 } 45 46 #if DEBUG_VALIDATE 47 enum Phase { 48 kIntersecting, 49 kWalking 50 }; 51 #endif 52 53 enum { 54 kMaxWindingTries = 10 55 }; 56 57 bool angleCoincidence() { 58 return fAngleCoincidence; 59 } 60 61 SkOpCoincidence* coincidence() { 62 return fCoincidence; 63 } 64 65 SkOpContourHead* contourHead() { 66 return fContourHead; 67 } 68 69 #ifdef SK_DEBUG 70 const struct SkOpAngle* debugAngle(int id) const; 71 SkOpContour* debugContour(int id); 72 const class SkOpPtT* debugPtT(int id) const; 73 const class SkOpSegment* debugSegment(int id) const; 74 const class SkOpSpanBase* debugSpan(int id) const; 75 76 int nextAngleID() { 77 return ++fAngleID; 78 } 79 80 int nextContourID() { 81 return ++fContourID; 82 } 83 int nextPtTID() { 84 return ++fPtTID; 85 } 86 87 int nextSegmentID() { 88 return ++fSegmentID; 89 } 90 91 int nextSpanID() { 92 return ++fSpanID; 93 } 94 #endif 95 96 #if DEBUG_VALIDATE 97 Phase phase() const { 98 return fPhase; 99 } 100 #endif 101 102 void setAngleCoincidence() { 103 fAngleCoincidence = true; 104 } 105 106 void setContourHead(SkOpContourHead* contourHead) { 107 fContourHead = contourHead; 108 } 109 110 #if DEBUG_VALIDATE 111 void setPhase(Phase phase) { 112 SkASSERT(fPhase != phase); 113 fPhase = phase; 114 } 115 #endif 116 117 // called in very rare cases where angles are sorted incorrectly -- signfies op will fail 118 void setWindingFailed() { 119 fWindingFailed = true; 120 } 121 122 bool windingFailed() const { 123 return fWindingFailed; 124 } 125 126 private: 127 SkOpCoincidence* fCoincidence; 128 SkOpContourHead* fContourHead; 129 bool fWindingFailed; 130 bool fAngleCoincidence; 131 #if DEBUG_VALIDATE 132 Phase fPhase; 133 #endif 134 #ifdef SK_DEBUG 135 int fAngleID; 136 int fContourID; 137 int fPtTID; 138 int fSegmentID; 139 int fSpanID; 140 #endif 141 }; 142 143 // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. 144 bool AlmostEqualUlps(float a, float b); 145 inline bool AlmostEqualUlps(double a, double b) { 146 return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 147 } 148 149 // Use Almost Dequal when comparing should not special case denormalized values. 150 bool AlmostDequalUlps(float a, float b); 151 bool AlmostDequalUlps(double a, double b); 152 153 bool NotAlmostEqualUlps(float a, float b); 154 inline bool NotAlmostEqualUlps(double a, double b) { 155 return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 156 } 157 158 bool NotAlmostDequalUlps(float a, float b); 159 inline bool NotAlmostDequalUlps(double a, double b) { 160 return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 161 } 162 163 // Use Almost Bequal when comparing coordinates in conjunction with between. 164 bool AlmostBequalUlps(float a, float b); 165 inline bool AlmostBequalUlps(double a, double b) { 166 return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 167 } 168 169 bool AlmostPequalUlps(float a, float b); 170 inline bool AlmostPequalUlps(double a, double b) { 171 return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 172 } 173 174 bool RoughlyEqualUlps(float a, float b); 175 inline bool RoughlyEqualUlps(double a, double b) { 176 return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 177 } 178 179 bool AlmostLessUlps(float a, float b); 180 inline bool AlmostLessUlps(double a, double b) { 181 return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 182 } 183 184 bool AlmostLessOrEqualUlps(float a, float b); 185 inline bool AlmostLessOrEqualUlps(double a, double b) { 186 return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 187 } 188 189 bool AlmostBetweenUlps(float a, float b, float c); 190 inline bool AlmostBetweenUlps(double a, double b, double c) { 191 return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); 192 } 193 194 int UlpsDistance(float a, float b); 195 inline int UlpsDistance(double a, double b) { 196 return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b)); 197 } 198 199 // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23) 200 // DBL_EPSILON == 2.22045e-16 201 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; 202 const double FLT_EPSILON_HALF = FLT_EPSILON / 2; 203 const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; 204 const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16; 205 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; 206 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); 207 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; 208 const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error 209 const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; 210 const double ROUGH_EPSILON = FLT_EPSILON * 64; 211 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; 212 const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; 213 const double BUMP_EPSILON = FLT_EPSILON * 4096; 214 215 inline bool zero_or_one(double x) { 216 return x == 0 || x == 1; 217 } 218 219 inline bool approximately_zero(double x) { 220 return fabs(x) < FLT_EPSILON; 221 } 222 223 inline bool precisely_zero(double x) { 224 return fabs(x) < DBL_EPSILON_ERR; 225 } 226 227 inline bool precisely_subdivide_zero(double x) { 228 return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR; 229 } 230 231 inline bool approximately_zero(float x) { 232 return fabs(x) < FLT_EPSILON; 233 } 234 235 inline bool approximately_zero_cubed(double x) { 236 return fabs(x) < FLT_EPSILON_CUBED; 237 } 238 239 inline bool approximately_zero_half(double x) { 240 return fabs(x) < FLT_EPSILON_HALF; 241 } 242 243 inline bool approximately_zero_double(double x) { 244 return fabs(x) < FLT_EPSILON_DOUBLE; 245 } 246 247 inline bool approximately_zero_orderable(double x) { 248 return fabs(x) < FLT_EPSILON_ORDERABLE_ERR; 249 } 250 251 inline bool approximately_zero_squared(double x) { 252 return fabs(x) < FLT_EPSILON_SQUARED; 253 } 254 255 inline bool approximately_zero_sqrt(double x) { 256 return fabs(x) < FLT_EPSILON_SQRT; 257 } 258 259 inline bool roughly_zero(double x) { 260 return fabs(x) < ROUGH_EPSILON; 261 } 262 263 inline bool approximately_zero_inverse(double x) { 264 return fabs(x) > FLT_EPSILON_INVERSE; 265 } 266 267 // OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead 268 inline bool approximately_zero_when_compared_to(double x, double y) { 269 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); 270 } 271 272 inline bool precisely_zero_when_compared_to(double x, double y) { 273 return x == 0 || fabs(x) < fabs(y * DBL_EPSILON); 274 } 275 276 // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use 277 // AlmostEqualUlps instead. 278 inline bool approximately_equal(double x, double y) { 279 return approximately_zero(x - y); 280 } 281 282 inline bool precisely_equal(double x, double y) { 283 return precisely_zero(x - y); 284 } 285 286 inline bool precisely_subdivide_equal(double x, double y) { 287 return precisely_subdivide_zero(x - y); 288 } 289 290 inline bool approximately_equal_half(double x, double y) { 291 return approximately_zero_half(x - y); 292 } 293 294 inline bool approximately_equal_double(double x, double y) { 295 return approximately_zero_double(x - y); 296 } 297 298 inline bool approximately_equal_orderable(double x, double y) { 299 return approximately_zero_orderable(x - y); 300 } 301 302 inline bool approximately_equal_squared(double x, double y) { 303 return approximately_equal(x, y); 304 } 305 306 inline bool approximately_greater(double x, double y) { 307 return x - FLT_EPSILON >= y; 308 } 309 310 inline bool approximately_greater_double(double x, double y) { 311 return x - FLT_EPSILON_DOUBLE >= y; 312 } 313 314 inline bool approximately_greater_orderable(double x, double y) { 315 return x - FLT_EPSILON_ORDERABLE_ERR >= y; 316 } 317 318 inline bool approximately_greater_or_equal(double x, double y) { 319 return x + FLT_EPSILON > y; 320 } 321 322 inline bool approximately_greater_or_equal_double(double x, double y) { 323 return x + FLT_EPSILON_DOUBLE > y; 324 } 325 326 inline bool approximately_greater_or_equal_orderable(double x, double y) { 327 return x + FLT_EPSILON_ORDERABLE_ERR > y; 328 } 329 330 inline bool approximately_lesser(double x, double y) { 331 return x + FLT_EPSILON <= y; 332 } 333 334 inline bool approximately_lesser_double(double x, double y) { 335 return x + FLT_EPSILON_DOUBLE <= y; 336 } 337 338 inline bool approximately_lesser_orderable(double x, double y) { 339 return x + FLT_EPSILON_ORDERABLE_ERR <= y; 340 } 341 342 inline bool approximately_lesser_or_equal(double x, double y) { 343 return x - FLT_EPSILON < y; 344 } 345 346 inline bool approximately_lesser_or_equal_double(double x, double y) { 347 return x - FLT_EPSILON_DOUBLE < y; 348 } 349 350 inline bool approximately_lesser_or_equal_orderable(double x, double y) { 351 return x - FLT_EPSILON_ORDERABLE_ERR < y; 352 } 353 354 inline bool approximately_greater_than_one(double x) { 355 return x > 1 - FLT_EPSILON; 356 } 357 358 inline bool precisely_greater_than_one(double x) { 359 return x > 1 - DBL_EPSILON_ERR; 360 } 361 362 inline bool approximately_less_than_zero(double x) { 363 return x < FLT_EPSILON; 364 } 365 366 inline bool precisely_less_than_zero(double x) { 367 return x < DBL_EPSILON_ERR; 368 } 369 370 inline bool approximately_negative(double x) { 371 return x < FLT_EPSILON; 372 } 373 374 inline bool approximately_negative_orderable(double x) { 375 return x < FLT_EPSILON_ORDERABLE_ERR; 376 } 377 378 inline bool precisely_negative(double x) { 379 return x < DBL_EPSILON_ERR; 380 } 381 382 inline bool approximately_one_or_less(double x) { 383 return x < 1 + FLT_EPSILON; 384 } 385 386 inline bool approximately_one_or_less_double(double x) { 387 return x < 1 + FLT_EPSILON_DOUBLE; 388 } 389 390 inline bool approximately_positive(double x) { 391 return x > -FLT_EPSILON; 392 } 393 394 inline bool approximately_positive_squared(double x) { 395 return x > -(FLT_EPSILON_SQUARED); 396 } 397 398 inline bool approximately_zero_or_more(double x) { 399 return x > -FLT_EPSILON; 400 } 401 402 inline bool approximately_zero_or_more_double(double x) { 403 return x > -FLT_EPSILON_DOUBLE; 404 } 405 406 inline bool approximately_between_orderable(double a, double b, double c) { 407 return a <= c 408 ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c) 409 : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b); 410 } 411 412 inline bool approximately_between(double a, double b, double c) { 413 return a <= c ? approximately_negative(a - b) && approximately_negative(b - c) 414 : approximately_negative(b - a) && approximately_negative(c - b); 415 } 416 417 inline bool precisely_between(double a, double b, double c) { 418 return a <= c ? precisely_negative(a - b) && precisely_negative(b - c) 419 : precisely_negative(b - a) && precisely_negative(c - b); 420 } 421 422 // returns true if (a <= b <= c) || (a >= b >= c) 423 inline bool between(double a, double b, double c) { 424 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0) 425 || (precisely_zero(a) && precisely_zero(b) && precisely_zero(c))); 426 return (a - b) * (c - b) <= 0; 427 } 428 429 inline bool roughly_equal(double x, double y) { 430 return fabs(x - y) < ROUGH_EPSILON; 431 } 432 433 inline bool roughly_negative(double x) { 434 return x < ROUGH_EPSILON; 435 } 436 437 inline bool roughly_between(double a, double b, double c) { 438 return a <= c ? roughly_negative(a - b) && roughly_negative(b - c) 439 : roughly_negative(b - a) && roughly_negative(c - b); 440 } 441 442 inline bool more_roughly_equal(double x, double y) { 443 return fabs(x - y) < MORE_ROUGH_EPSILON; 444 } 445 446 inline bool way_roughly_equal(double x, double y) { 447 return fabs(x - y) < WAY_ROUGH_EPSILON; 448 } 449 450 struct SkDPoint; 451 struct SkDVector; 452 struct SkDLine; 453 struct SkDQuad; 454 struct SkDConic; 455 struct SkDCubic; 456 struct SkDRect; 457 458 inline SkPath::Verb SkPathOpsPointsToVerb(int points) { 459 int verb = (1 << points) >> 1; 460 #ifdef SK_DEBUG 461 switch (points) { 462 case 0: SkASSERT(SkPath::kMove_Verb == verb); break; 463 case 1: SkASSERT(SkPath::kLine_Verb == verb); break; 464 case 2: SkASSERT(SkPath::kQuad_Verb == verb); break; 465 case 3: SkASSERT(SkPath::kCubic_Verb == verb); break; 466 default: SkDEBUGFAIL("should not be here"); 467 } 468 #endif 469 return (SkPath::Verb)verb; 470 } 471 472 inline int SkPathOpsVerbToPoints(SkPath::Verb verb) { 473 int points = (int) verb - (((int) verb + 1) >> 2); 474 #ifdef SK_DEBUG 475 switch (verb) { 476 case SkPath::kLine_Verb: SkASSERT(1 == points); break; 477 case SkPath::kQuad_Verb: SkASSERT(2 == points); break; 478 case SkPath::kConic_Verb: SkASSERT(2 == points); break; 479 case SkPath::kCubic_Verb: SkASSERT(3 == points); break; 480 default: SkDEBUGFAIL("should not get here"); 481 } 482 #endif 483 return points; 484 } 485 486 inline double SkDInterp(double A, double B, double t) { 487 return A + (B - A) * t; 488 } 489 490 double SkDCubeRoot(double x); 491 492 /* Returns -1 if negative, 0 if zero, 1 if positive 493 */ 494 inline int SkDSign(double x) { 495 return (x > 0) - (x < 0); 496 } 497 498 /* Returns 0 if negative, 1 if zero, 2 if positive 499 */ 500 inline int SKDSide(double x) { 501 return (x > 0) + (x >= 0); 502 } 503 504 /* Returns 1 if negative, 2 if zero, 4 if positive 505 */ 506 inline int SkDSideBit(double x) { 507 return 1 << SKDSide(x); 508 } 509 510 inline double SkPinT(double t) { 511 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; 512 } 513 514 #endif 515