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 SkOpCoincidence; 26class SkOpContour; 27class SkOpContourHead; 28 29class SkOpGlobalState { 30public: 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 126private: 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. 144bool AlmostEqualUlps(float a, float b); 145inline 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. 150bool AlmostDequalUlps(float a, float b); 151bool AlmostDequalUlps(double a, double b); 152 153bool NotAlmostEqualUlps(float a, float b); 154inline bool NotAlmostEqualUlps(double a, double b) { 155 return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 156} 157 158bool NotAlmostDequalUlps(float a, float b); 159inline 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. 164bool AlmostBequalUlps(float a, float b); 165inline bool AlmostBequalUlps(double a, double b) { 166 return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 167} 168 169bool AlmostPequalUlps(float a, float b); 170inline bool AlmostPequalUlps(double a, double b) { 171 return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 172} 173 174bool RoughlyEqualUlps(float a, float b); 175inline bool RoughlyEqualUlps(double a, double b) { 176 return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 177} 178 179bool AlmostLessUlps(float a, float b); 180inline bool AlmostLessUlps(double a, double b) { 181 return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 182} 183 184bool AlmostLessOrEqualUlps(float a, float b); 185inline bool AlmostLessOrEqualUlps(double a, double b) { 186 return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 187} 188 189bool AlmostBetweenUlps(float a, float b, float c); 190inline bool AlmostBetweenUlps(double a, double b, double c) { 191 return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); 192} 193 194int UlpsDistance(float a, float b); 195inline 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 201const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; 202const double FLT_EPSILON_HALF = FLT_EPSILON / 2; 203const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; 204const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16; 205const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; 206const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); 207const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; 208const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error 209const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; 210const double ROUGH_EPSILON = FLT_EPSILON * 64; 211const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; 212const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; 213const double BUMP_EPSILON = FLT_EPSILON * 4096; 214 215inline bool zero_or_one(double x) { 216 return x == 0 || x == 1; 217} 218 219inline bool approximately_zero(double x) { 220 return fabs(x) < FLT_EPSILON; 221} 222 223inline bool precisely_zero(double x) { 224 return fabs(x) < DBL_EPSILON_ERR; 225} 226 227inline bool precisely_subdivide_zero(double x) { 228 return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR; 229} 230 231inline bool approximately_zero(float x) { 232 return fabs(x) < FLT_EPSILON; 233} 234 235inline bool approximately_zero_cubed(double x) { 236 return fabs(x) < FLT_EPSILON_CUBED; 237} 238 239inline bool approximately_zero_half(double x) { 240 return fabs(x) < FLT_EPSILON_HALF; 241} 242 243inline bool approximately_zero_double(double x) { 244 return fabs(x) < FLT_EPSILON_DOUBLE; 245} 246 247inline bool approximately_zero_orderable(double x) { 248 return fabs(x) < FLT_EPSILON_ORDERABLE_ERR; 249} 250 251inline bool approximately_zero_squared(double x) { 252 return fabs(x) < FLT_EPSILON_SQUARED; 253} 254 255inline bool approximately_zero_sqrt(double x) { 256 return fabs(x) < FLT_EPSILON_SQRT; 257} 258 259inline bool roughly_zero(double x) { 260 return fabs(x) < ROUGH_EPSILON; 261} 262 263inline 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 268inline bool approximately_zero_when_compared_to(double x, double y) { 269 return x == 0 || fabs(x) < fabs(y * FLT_EPSILON); 270} 271 272inline 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. 278inline bool approximately_equal(double x, double y) { 279 return approximately_zero(x - y); 280} 281 282inline bool precisely_equal(double x, double y) { 283 return precisely_zero(x - y); 284} 285 286inline bool precisely_subdivide_equal(double x, double y) { 287 return precisely_subdivide_zero(x - y); 288} 289 290inline bool approximately_equal_half(double x, double y) { 291 return approximately_zero_half(x - y); 292} 293 294inline bool approximately_equal_double(double x, double y) { 295 return approximately_zero_double(x - y); 296} 297 298inline bool approximately_equal_orderable(double x, double y) { 299 return approximately_zero_orderable(x - y); 300} 301 302inline bool approximately_equal_squared(double x, double y) { 303 return approximately_equal(x, y); 304} 305 306inline bool approximately_greater(double x, double y) { 307 return x - FLT_EPSILON >= y; 308} 309 310inline bool approximately_greater_double(double x, double y) { 311 return x - FLT_EPSILON_DOUBLE >= y; 312} 313 314inline bool approximately_greater_orderable(double x, double y) { 315 return x - FLT_EPSILON_ORDERABLE_ERR >= y; 316} 317 318inline bool approximately_greater_or_equal(double x, double y) { 319 return x + FLT_EPSILON > y; 320} 321 322inline bool approximately_greater_or_equal_double(double x, double y) { 323 return x + FLT_EPSILON_DOUBLE > y; 324} 325 326inline bool approximately_greater_or_equal_orderable(double x, double y) { 327 return x + FLT_EPSILON_ORDERABLE_ERR > y; 328} 329 330inline bool approximately_lesser(double x, double y) { 331 return x + FLT_EPSILON <= y; 332} 333 334inline bool approximately_lesser_double(double x, double y) { 335 return x + FLT_EPSILON_DOUBLE <= y; 336} 337 338inline bool approximately_lesser_orderable(double x, double y) { 339 return x + FLT_EPSILON_ORDERABLE_ERR <= y; 340} 341 342inline bool approximately_lesser_or_equal(double x, double y) { 343 return x - FLT_EPSILON < y; 344} 345 346inline bool approximately_lesser_or_equal_double(double x, double y) { 347 return x - FLT_EPSILON_DOUBLE < y; 348} 349 350inline bool approximately_lesser_or_equal_orderable(double x, double y) { 351 return x - FLT_EPSILON_ORDERABLE_ERR < y; 352} 353 354inline bool approximately_greater_than_one(double x) { 355 return x > 1 - FLT_EPSILON; 356} 357 358inline bool precisely_greater_than_one(double x) { 359 return x > 1 - DBL_EPSILON_ERR; 360} 361 362inline bool approximately_less_than_zero(double x) { 363 return x < FLT_EPSILON; 364} 365 366inline bool precisely_less_than_zero(double x) { 367 return x < DBL_EPSILON_ERR; 368} 369 370inline bool approximately_negative(double x) { 371 return x < FLT_EPSILON; 372} 373 374inline bool approximately_negative_orderable(double x) { 375 return x < FLT_EPSILON_ORDERABLE_ERR; 376} 377 378inline bool precisely_negative(double x) { 379 return x < DBL_EPSILON_ERR; 380} 381 382inline bool approximately_one_or_less(double x) { 383 return x < 1 + FLT_EPSILON; 384} 385 386inline bool approximately_one_or_less_double(double x) { 387 return x < 1 + FLT_EPSILON_DOUBLE; 388} 389 390inline bool approximately_positive(double x) { 391 return x > -FLT_EPSILON; 392} 393 394inline bool approximately_positive_squared(double x) { 395 return x > -(FLT_EPSILON_SQUARED); 396} 397 398inline bool approximately_zero_or_more(double x) { 399 return x > -FLT_EPSILON; 400} 401 402inline bool approximately_zero_or_more_double(double x) { 403 return x > -FLT_EPSILON_DOUBLE; 404} 405 406inline 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 412inline 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 417inline 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) 423inline 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 429inline bool roughly_equal(double x, double y) { 430 return fabs(x - y) < ROUGH_EPSILON; 431} 432 433inline bool roughly_negative(double x) { 434 return x < ROUGH_EPSILON; 435} 436 437inline 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 442inline bool more_roughly_equal(double x, double y) { 443 return fabs(x - y) < MORE_ROUGH_EPSILON; 444} 445 446inline bool way_roughly_equal(double x, double y) { 447 return fabs(x - y) < WAY_ROUGH_EPSILON; 448} 449 450struct SkDPoint; 451struct SkDVector; 452struct SkDLine; 453struct SkDQuad; 454struct SkDConic; 455struct SkDCubic; 456struct SkDRect; 457 458inline 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 472inline 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 486inline double SkDInterp(double A, double B, double t) { 487 return A + (B - A) * t; 488} 489 490double SkDCubeRoot(double x); 491 492/* Returns -1 if negative, 0 if zero, 1 if positive 493*/ 494inline int SkDSign(double x) { 495 return (x > 0) - (x < 0); 496} 497 498/* Returns 0 if negative, 1 if zero, 2 if positive 499*/ 500inline int SKDSide(double x) { 501 return (x > 0) + (x >= 0); 502} 503 504/* Returns 1 if negative, 2 if zero, 4 if positive 505*/ 506inline int SkDSideBit(double x) { 507 return 1 << SKDSide(x); 508} 509 510inline double SkPinT(double t) { 511 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; 512} 513 514#endif 515