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 12#include "SkFloatingPoint.h" 13#include "SkPath.h" 14#include "SkPathOps.h" 15#include "SkPathOpsDebug.h" 16#include "SkSafe_math.h" // for fabs, sqrt 17#include "SkScalar.h" 18 19enum SkPathOpsMask { 20 kWinding_PathOpsMask = -1, 21 kNo_PathOpsMask = 0, 22 kEvenOdd_PathOpsMask = 1 23}; 24 25class SkArenaAlloc; 26class SkOpCoincidence; 27class SkOpContour; 28class SkOpContourHead; 29class SkIntersections; 30class SkIntersectionHelper; 31 32enum class SkOpPhase : char { 33 kNoChange, 34 kIntersecting, 35 kWalking, 36 kFixWinding, 37}; 38 39class SkOpGlobalState { 40public: 41 SkOpGlobalState(SkOpContourHead* head, 42 SkArenaAlloc* allocator SkDEBUGPARAMS(bool debugSkipAssert) 43 SkDEBUGPARAMS(const char* testName)); 44 45 enum { 46 kMaxWindingTries = 10 47 }; 48 49 bool allocatedOpSpan() const { 50 return fAllocatedOpSpan; 51 } 52 53 SkArenaAlloc* allocator() { 54 return fAllocator; 55 } 56 57 void bumpNested() { 58 ++fNested; 59 } 60 61 void clearNested() { 62 fNested = 0; 63 } 64 65 SkOpCoincidence* coincidence() { 66 return fCoincidence; 67 } 68 69 SkOpContourHead* contourHead() { 70 return fContourHead; 71 } 72 73#ifdef SK_DEBUG 74 const class SkOpAngle* debugAngle(int id) const; 75 const SkOpCoincidence* debugCoincidence() const; 76 SkOpContour* debugContour(int id) const; 77 const class SkOpPtT* debugPtT(int id) const; 78#endif 79 80 static bool DebugRunFail(); 81 82#ifdef SK_DEBUG 83 const class SkOpSegment* debugSegment(int id) const; 84 bool debugSkipAssert() const { return fDebugSkipAssert; } 85 const class SkOpSpanBase* debugSpan(int id) const; 86 const char* debugTestName() const { return fDebugTestName; } 87#endif 88 89#if DEBUG_T_SECT_LOOP_COUNT 90 void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& , 91 const SkIntersectionHelper& ); 92 void debugDoYourWorst(SkOpGlobalState* ); 93 void debugLoopReport(); 94 void debugResetLoopCounts(); 95#endif 96 97#if DEBUG_COINCIDENCE 98 void debugSetCheckHealth(bool check) { fDebugCheckHealth = check; } 99 bool debugCheckHealth() const { return fDebugCheckHealth; } 100#endif 101 102#if DEBUG_VALIDATE || DEBUG_COIN 103 void debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const; 104#endif 105 106#if DEBUG_COIN 107 void debugAddToCoinChangedDict(); 108 void debugAddToGlobalCoinDicts(); 109 SkPathOpsDebug::CoinDict* debugCoinChangedDict() { return &fCoinChangedDict; } 110 const SkPathOpsDebug::CoinDictEntry& debugCoinDictEntry() const { return fCoinDictEntry; } 111 112 static void DumpCoinDict(); 113#endif 114 115 116 int nested() const { 117 return fNested; 118 } 119 120#ifdef SK_DEBUG 121 int nextAngleID() { 122 return ++fAngleID; 123 } 124 125 int nextCoinID() { 126 return ++fCoinID; 127 } 128 129 int nextContourID() { 130 return ++fContourID; 131 } 132 133 int nextPtTID() { 134 return ++fPtTID; 135 } 136 137 int nextSegmentID() { 138 return ++fSegmentID; 139 } 140 141 int nextSpanID() { 142 return ++fSpanID; 143 } 144#endif 145 146 SkOpPhase phase() const { 147 return fPhase; 148 } 149 150 void resetAllocatedOpSpan() { 151 fAllocatedOpSpan = false; 152 } 153 154 void setAllocatedOpSpan() { 155 fAllocatedOpSpan = true; 156 } 157 158 void setCoincidence(SkOpCoincidence* coincidence) { 159 fCoincidence = coincidence; 160 } 161 162 void setContourHead(SkOpContourHead* contourHead) { 163 fContourHead = contourHead; 164 } 165 166 void setPhase(SkOpPhase phase) { 167 if (SkOpPhase::kNoChange == phase) { 168 return; 169 } 170 SkASSERT(fPhase != phase); 171 fPhase = phase; 172 } 173 174 // called in very rare cases where angles are sorted incorrectly -- signfies op will fail 175 void setWindingFailed() { 176 fWindingFailed = true; 177 } 178 179 bool windingFailed() const { 180 return fWindingFailed; 181 } 182 183private: 184 SkArenaAlloc* fAllocator; 185 SkOpCoincidence* fCoincidence; 186 SkOpContourHead* fContourHead; 187 int fNested; 188 bool fAllocatedOpSpan; 189 bool fWindingFailed; 190 SkOpPhase fPhase; 191#ifdef SK_DEBUG 192 const char* fDebugTestName; 193 void* fDebugReporter; 194 int fAngleID; 195 int fCoinID; 196 int fContourID; 197 int fPtTID; 198 int fSegmentID; 199 int fSpanID; 200 bool fDebugSkipAssert; 201#endif 202#if DEBUG_T_SECT_LOOP_COUNT 203 int fDebugLoopCount[3]; 204 SkPath::Verb fDebugWorstVerb[6]; 205 SkPoint fDebugWorstPts[24]; 206 float fDebugWorstWeight[6]; 207#endif 208#if DEBUG_COIN 209 SkPathOpsDebug::CoinDict fCoinChangedDict; 210 SkPathOpsDebug::CoinDict fCoinVisitedDict; 211 SkPathOpsDebug::CoinDictEntry fCoinDictEntry; 212 const char* fPreviousFuncName; 213#endif 214#if DEBUG_COINCIDENCE 215 bool fDebugCheckHealth; 216#endif 217}; 218 219#ifdef SK_DEBUG 220#if DEBUG_COINCIDENCE 221#define SkOPASSERT(cond) SkASSERT((this->globalState() && \ 222 (this->globalState()->debugCheckHealth() || \ 223 this->globalState()->debugSkipAssert())) || (cond)) 224#else 225#define SkOPASSERT(cond) SkASSERT((this->globalState() && \ 226 this->globalState()->debugSkipAssert()) || (cond)) 227#endif 228#define SkOPOBJASSERT(obj, cond) SkASSERT((obj->globalState() && \ 229 obj->globalState()->debugSkipAssert()) || (cond)) 230#else 231#define SkOPASSERT(cond) 232#define SkOPOBJASSERT(obj, cond) 233#endif 234 235// Use Almost Equal when comparing coordinates. Use epsilon to compare T values. 236bool AlmostEqualUlps(float a, float b); 237inline bool AlmostEqualUlps(double a, double b) { 238 return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 239} 240 241bool AlmostEqualUlpsNoNormalCheck(float a, float b); 242inline bool AlmostEqualUlpsNoNormalCheck(double a, double b) { 243 return AlmostEqualUlpsNoNormalCheck(SkDoubleToScalar(a), SkDoubleToScalar(b)); 244} 245 246bool AlmostEqualUlps_Pin(float a, float b); 247inline bool AlmostEqualUlps_Pin(double a, double b) { 248 return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b)); 249} 250 251// Use Almost Dequal when comparing should not special case denormalized values. 252bool AlmostDequalUlps(float a, float b); 253bool AlmostDequalUlps(double a, double b); 254 255bool NotAlmostEqualUlps(float a, float b); 256inline bool NotAlmostEqualUlps(double a, double b) { 257 return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 258} 259 260bool NotAlmostEqualUlps_Pin(float a, float b); 261inline bool NotAlmostEqualUlps_Pin(double a, double b) { 262 return NotAlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b)); 263} 264 265bool NotAlmostDequalUlps(float a, float b); 266inline bool NotAlmostDequalUlps(double a, double b) { 267 return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 268} 269 270// Use Almost Bequal when comparing coordinates in conjunction with between. 271bool AlmostBequalUlps(float a, float b); 272inline bool AlmostBequalUlps(double a, double b) { 273 return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 274} 275 276bool AlmostPequalUlps(float a, float b); 277inline bool AlmostPequalUlps(double a, double b) { 278 return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 279} 280 281bool RoughlyEqualUlps(float a, float b); 282inline bool RoughlyEqualUlps(double a, double b) { 283 return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 284} 285 286bool AlmostLessUlps(float a, float b); 287inline bool AlmostLessUlps(double a, double b) { 288 return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 289} 290 291bool AlmostLessOrEqualUlps(float a, float b); 292inline bool AlmostLessOrEqualUlps(double a, double b) { 293 return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 294} 295 296bool AlmostBetweenUlps(float a, float b, float c); 297inline bool AlmostBetweenUlps(double a, double b, double c) { 298 return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); 299} 300 301int UlpsDistance(float a, float b); 302inline int UlpsDistance(double a, double b) { 303 return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b)); 304} 305 306// FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23) 307// DBL_EPSILON == 2.22045e-16 308const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; 309const double FLT_EPSILON_HALF = FLT_EPSILON / 2; 310const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; 311const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16; 312const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; 313// Use a compile-time constant for FLT_EPSILON_SQRT to avoid initializers. 314// A 17 digit constant guarantees exact results. 315const double FLT_EPSILON_SQRT = 0.00034526697709225118; // sqrt(FLT_EPSILON); 316const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; 317const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error 318const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; 319const double ROUGH_EPSILON = FLT_EPSILON * 64; 320const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; 321const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; 322const double BUMP_EPSILON = FLT_EPSILON * 4096; 323 324const SkScalar INVERSE_NUMBER_RANGE = FLT_EPSILON_ORDERABLE_ERR; 325 326inline bool zero_or_one(double x) { 327 return x == 0 || x == 1; 328} 329 330inline bool approximately_zero(double x) { 331 return fabs(x) < FLT_EPSILON; 332} 333 334inline bool precisely_zero(double x) { 335 return fabs(x) < DBL_EPSILON_ERR; 336} 337 338inline bool precisely_subdivide_zero(double x) { 339 return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR; 340} 341 342inline bool approximately_zero(float x) { 343 return fabs(x) < FLT_EPSILON; 344} 345 346inline bool approximately_zero_cubed(double x) { 347 return fabs(x) < FLT_EPSILON_CUBED; 348} 349 350inline bool approximately_zero_half(double x) { 351 return fabs(x) < FLT_EPSILON_HALF; 352} 353 354inline bool approximately_zero_double(double x) { 355 return fabs(x) < FLT_EPSILON_DOUBLE; 356} 357 358inline bool approximately_zero_orderable(double x) { 359 return fabs(x) < FLT_EPSILON_ORDERABLE_ERR; 360} 361 362inline bool approximately_zero_squared(double x) { 363 return fabs(x) < FLT_EPSILON_SQUARED; 364} 365 366inline bool approximately_zero_sqrt(double x) { 367 return fabs(x) < FLT_EPSILON_SQRT; 368} 369 370inline bool roughly_zero(double x) { 371 return fabs(x) < ROUGH_EPSILON; 372} 373 374inline bool approximately_zero_inverse(double x) { 375 return fabs(x) > FLT_EPSILON_INVERSE; 376} 377 378inline bool approximately_zero_when_compared_to(double x, double y) { 379 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); 380} 381 382inline bool precisely_zero_when_compared_to(double x, double y) { 383 return x == 0 || fabs(x) < fabs(y * DBL_EPSILON); 384} 385 386inline bool roughly_zero_when_compared_to(double x, double y) { 387 return x == 0 || fabs(x) < fabs(y * ROUGH_EPSILON); 388} 389 390// Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use 391// AlmostEqualUlps instead. 392inline bool approximately_equal(double x, double y) { 393 return approximately_zero(x - y); 394} 395 396inline bool precisely_equal(double x, double y) { 397 return precisely_zero(x - y); 398} 399 400inline bool precisely_subdivide_equal(double x, double y) { 401 return precisely_subdivide_zero(x - y); 402} 403 404inline bool approximately_equal_half(double x, double y) { 405 return approximately_zero_half(x - y); 406} 407 408inline bool approximately_equal_double(double x, double y) { 409 return approximately_zero_double(x - y); 410} 411 412inline bool approximately_equal_orderable(double x, double y) { 413 return approximately_zero_orderable(x - y); 414} 415 416inline bool approximately_equal_squared(double x, double y) { 417 return approximately_equal(x, y); 418} 419 420inline bool approximately_greater(double x, double y) { 421 return x - FLT_EPSILON >= y; 422} 423 424inline bool approximately_greater_double(double x, double y) { 425 return x - FLT_EPSILON_DOUBLE >= y; 426} 427 428inline bool approximately_greater_orderable(double x, double y) { 429 return x - FLT_EPSILON_ORDERABLE_ERR >= y; 430} 431 432inline bool approximately_greater_or_equal(double x, double y) { 433 return x + FLT_EPSILON > y; 434} 435 436inline bool approximately_greater_or_equal_double(double x, double y) { 437 return x + FLT_EPSILON_DOUBLE > y; 438} 439 440inline bool approximately_greater_or_equal_orderable(double x, double y) { 441 return x + FLT_EPSILON_ORDERABLE_ERR > y; 442} 443 444inline bool approximately_lesser(double x, double y) { 445 return x + FLT_EPSILON <= y; 446} 447 448inline bool approximately_lesser_double(double x, double y) { 449 return x + FLT_EPSILON_DOUBLE <= y; 450} 451 452inline bool approximately_lesser_orderable(double x, double y) { 453 return x + FLT_EPSILON_ORDERABLE_ERR <= y; 454} 455 456inline bool approximately_lesser_or_equal(double x, double y) { 457 return x - FLT_EPSILON < y; 458} 459 460inline bool approximately_lesser_or_equal_double(double x, double y) { 461 return x - FLT_EPSILON_DOUBLE < y; 462} 463 464inline bool approximately_lesser_or_equal_orderable(double x, double y) { 465 return x - FLT_EPSILON_ORDERABLE_ERR < y; 466} 467 468inline bool approximately_greater_than_one(double x) { 469 return x > 1 - FLT_EPSILON; 470} 471 472inline bool precisely_greater_than_one(double x) { 473 return x > 1 - DBL_EPSILON_ERR; 474} 475 476inline bool approximately_less_than_zero(double x) { 477 return x < FLT_EPSILON; 478} 479 480inline bool precisely_less_than_zero(double x) { 481 return x < DBL_EPSILON_ERR; 482} 483 484inline bool approximately_negative(double x) { 485 return x < FLT_EPSILON; 486} 487 488inline bool approximately_negative_orderable(double x) { 489 return x < FLT_EPSILON_ORDERABLE_ERR; 490} 491 492inline bool precisely_negative(double x) { 493 return x < DBL_EPSILON_ERR; 494} 495 496inline bool approximately_one_or_less(double x) { 497 return x < 1 + FLT_EPSILON; 498} 499 500inline bool approximately_one_or_less_double(double x) { 501 return x < 1 + FLT_EPSILON_DOUBLE; 502} 503 504inline bool approximately_positive(double x) { 505 return x > -FLT_EPSILON; 506} 507 508inline bool approximately_positive_squared(double x) { 509 return x > -(FLT_EPSILON_SQUARED); 510} 511 512inline bool approximately_zero_or_more(double x) { 513 return x > -FLT_EPSILON; 514} 515 516inline bool approximately_zero_or_more_double(double x) { 517 return x > -FLT_EPSILON_DOUBLE; 518} 519 520inline bool approximately_between_orderable(double a, double b, double c) { 521 return a <= c 522 ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c) 523 : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b); 524} 525 526inline bool approximately_between(double a, double b, double c) { 527 return a <= c ? approximately_negative(a - b) && approximately_negative(b - c) 528 : approximately_negative(b - a) && approximately_negative(c - b); 529} 530 531inline bool precisely_between(double a, double b, double c) { 532 return a <= c ? precisely_negative(a - b) && precisely_negative(b - c) 533 : precisely_negative(b - a) && precisely_negative(c - b); 534} 535 536// returns true if (a <= b <= c) || (a >= b >= c) 537inline bool between(double a, double b, double c) { 538 SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0) 539 || (precisely_zero(a) && precisely_zero(b) && precisely_zero(c))); 540 return (a - b) * (c - b) <= 0; 541} 542 543inline bool roughly_equal(double x, double y) { 544 return fabs(x - y) < ROUGH_EPSILON; 545} 546 547inline bool roughly_negative(double x) { 548 return x < ROUGH_EPSILON; 549} 550 551inline bool roughly_between(double a, double b, double c) { 552 return a <= c ? roughly_negative(a - b) && roughly_negative(b - c) 553 : roughly_negative(b - a) && roughly_negative(c - b); 554} 555 556inline bool more_roughly_equal(double x, double y) { 557 return fabs(x - y) < MORE_ROUGH_EPSILON; 558} 559 560struct SkDPoint; 561struct SkDVector; 562struct SkDLine; 563struct SkDQuad; 564struct SkDConic; 565struct SkDCubic; 566struct SkDRect; 567 568inline SkPath::Verb SkPathOpsPointsToVerb(int points) { 569 int verb = (1 << points) >> 1; 570#ifdef SK_DEBUG 571 switch (points) { 572 case 0: SkASSERT(SkPath::kMove_Verb == verb); break; 573 case 1: SkASSERT(SkPath::kLine_Verb == verb); break; 574 case 2: SkASSERT(SkPath::kQuad_Verb == verb); break; 575 case 3: SkASSERT(SkPath::kCubic_Verb == verb); break; 576 default: SkDEBUGFAIL("should not be here"); 577 } 578#endif 579 return (SkPath::Verb)verb; 580} 581 582inline int SkPathOpsVerbToPoints(SkPath::Verb verb) { 583 int points = (int) verb - (((int) verb + 1) >> 2); 584#ifdef SK_DEBUG 585 switch (verb) { 586 case SkPath::kLine_Verb: SkASSERT(1 == points); break; 587 case SkPath::kQuad_Verb: SkASSERT(2 == points); break; 588 case SkPath::kConic_Verb: SkASSERT(2 == points); break; 589 case SkPath::kCubic_Verb: SkASSERT(3 == points); break; 590 default: SkDEBUGFAIL("should not get here"); 591 } 592#endif 593 return points; 594} 595 596inline double SkDInterp(double A, double B, double t) { 597 return A + (B - A) * t; 598} 599 600double SkDCubeRoot(double x); 601 602/* Returns -1 if negative, 0 if zero, 1 if positive 603*/ 604inline int SkDSign(double x) { 605 return (x > 0) - (x < 0); 606} 607 608/* Returns 0 if negative, 1 if zero, 2 if positive 609*/ 610inline int SKDSide(double x) { 611 return (x > 0) + (x >= 0); 612} 613 614/* Returns 1 if negative, 2 if zero, 4 if positive 615*/ 616inline int SkDSideBit(double x) { 617 return 1 << SKDSide(x); 618} 619 620inline double SkPinT(double t) { 621 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; 622} 623 624#endif 625