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