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