src/third_party/skia/src/pathops/SkPathOpsTypes.h

   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 // Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
  26 bool AlmostEqualUlps(float a, float b);
  27 inline bool AlmostEqualUlps(double a, double b) {
  28     return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  29 }
  30
  31 // Use Almost Dequal when comparing should not special case denormalized values.
  32 bool AlmostDequalUlps(float a, float b);
  33 inline bool AlmostDequalUlps(double a, double b) {
  34     return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  35 }
  36
  37 bool NotAlmostEqualUlps(float a, float b);
  38 inline bool NotAlmostEqualUlps(double a, double b) {
  39     return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  40 }
  41
  42 bool NotAlmostDequalUlps(float a, float b);
  43 inline bool NotAlmostDequalUlps(double a, double b) {
  44     return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  45 }
  46
  47 // Use Almost Bequal when comparing coordinates in conjunction with between.
  48 bool AlmostBequalUlps(float a, float b);
  49 inline bool AlmostBequalUlps(double a, double b) {
  50     return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  51 }
  52
  53 bool AlmostPequalUlps(float a, float b);
  54 inline bool AlmostPequalUlps(double a, double b) {
  55     return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  56 }
  57
  58 bool RoughlyEqualUlps(float a, float b);
  59 inline bool RoughlyEqualUlps(double a, double b) {
  60     return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  61 }
  62
  63 bool AlmostLessUlps(float a, float b);
  64 inline bool AlmostLessUlps(double a, double b) {
  65     return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  66 }
  67
  68 bool AlmostLessOrEqualUlps(float a, float b);
  69 inline bool AlmostLessOrEqualUlps(double a, double b) {
  70     return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  71 }
  72
  73 bool AlmostBetweenUlps(float a, float b, float c);
  74 inline bool AlmostBetweenUlps(double a, double b, double c) {
  75     return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
  76 }
  77
  78 int UlpsDistance(float a, float b);
  79 inline int UlpsDistance(double a, double b) {
  80     return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
  81 }
  82
  83 // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
  84 // DBL_EPSILON == 2.22045e-16
  85 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
  86 const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
  87 const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
  88 const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16;
  89 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
  90 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
  91 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
  92 const double DBL_EPSILON_ERR = DBL_EPSILON * 4;  // FIXME: tune -- allow a few bits of error
  93 const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
  94 const double ROUGH_EPSILON = FLT_EPSILON * 64;
  95 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
  96
  97 inline bool approximately_zero(double x) {
  98     return fabs(x) < FLT_EPSILON;
  99 }
 100
 101 inline bool precisely_zero(double x) {
 102     return fabs(x) < DBL_EPSILON_ERR;
 103 }
 104
 105 inline bool precisely_subdivide_zero(double x) {
 106     return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
 107 }
 108
 109 inline bool approximately_zero(float x) {
 110     return fabs(x) < FLT_EPSILON;
 111 }
 112
 113 inline bool approximately_zero_cubed(double x) {
 114     return fabs(x) < FLT_EPSILON_CUBED;
 115 }
 116
 117 inline bool approximately_zero_half(double x) {
 118     return fabs(x) < FLT_EPSILON_HALF;
 119 }
 120
 121 inline bool approximately_zero_double(double x) {
 122     return fabs(x) < FLT_EPSILON_DOUBLE;
 123 }
 124
 125 inline bool approximately_zero_orderable(double x) {
 126     return fabs(x) < FLT_EPSILON_ORDERABLE_ERR;
 127 }
 128
 129 inline bool approximately_zero_squared(double x) {
 130     return fabs(x) < FLT_EPSILON_SQUARED;
 131 }
 132
 133 inline bool approximately_zero_sqrt(double x) {
 134     return fabs(x) < FLT_EPSILON_SQRT;
 135 }
 136
 137 inline bool roughly_zero(double x) {
 138     return fabs(x) < ROUGH_EPSILON;
 139 }
 140
 141 inline bool approximately_zero_inverse(double x) {
 142     return fabs(x) > FLT_EPSILON_INVERSE;
 143 }
 144
 145 // OPTIMIZATION: if called multiple times with the same denom, we want to pass 1/y instead
 146 inline bool approximately_zero_when_compared_to(double x, double y) {
 147     return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
 148 }
 149
 150 // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
 151 // AlmostEqualUlps instead.
 152 inline bool approximately_equal(double x, double y) {
 153     return approximately_zero(x - y);
 154 }
 155
 156 inline bool precisely_equal(double x, double y) {
 157     return precisely_zero(x - y);
 158 }
 159
 160 inline bool precisely_subdivide_equal(double x, double y) {
 161     return precisely_subdivide_zero(x - y);
 162 }
 163
 164 inline bool approximately_equal_half(double x, double y) {
 165     return approximately_zero_half(x - y);
 166 }
 167
 168 inline bool approximately_equal_double(double x, double y) {
 169     return approximately_zero_double(x - y);
 170 }
 171
 172 inline bool approximately_equal_orderable(double x, double y) {
 173     return approximately_zero_orderable(x - y);
 174 }
 175
 176 inline bool approximately_equal_squared(double x, double y) {
 177     return approximately_equal(x, y);
 178 }
 179
 180 inline bool approximately_greater(double x, double y) {
 181     return x - FLT_EPSILON >= y;
 182 }
 183
 184 inline bool approximately_greater_double(double x, double y) {
 185     return x - FLT_EPSILON_DOUBLE >= y;
 186 }
 187
 188 inline bool approximately_greater_orderable(double x, double y) {
 189     return x - FLT_EPSILON_ORDERABLE_ERR >= y;
 190 }
 191
 192 inline bool approximately_greater_or_equal(double x, double y) {
 193     return x + FLT_EPSILON > y;
 194 }
 195
 196 inline bool approximately_greater_or_equal_double(double x, double y) {
 197     return x + FLT_EPSILON_DOUBLE > y;
 198 }
 199
 200 inline bool approximately_greater_or_equal_orderable(double x, double y) {
 201     return x + FLT_EPSILON_ORDERABLE_ERR > y;
 202 }
 203
 204 inline bool approximately_lesser(double x, double y) {
 205     return x + FLT_EPSILON <= y;
 206 }
 207
 208 inline bool approximately_lesser_double(double x, double y) {
 209     return x + FLT_EPSILON_DOUBLE <= y;
 210 }
 211
 212 inline bool approximately_lesser_orderable(double x, double y) {
 213     return x + FLT_EPSILON_ORDERABLE_ERR <= y;
 214 }
 215
 216 inline bool approximately_lesser_or_equal(double x, double y) {
 217     return x - FLT_EPSILON < y;
 218 }
 219
 220 inline bool approximately_lesser_or_equal_double(double x, double y) {
 221     return x - FLT_EPSILON_DOUBLE < y;
 222 }
 223
 224 inline bool approximately_lesser_or_equal_orderable(double x, double y) {
 225     return x - FLT_EPSILON_ORDERABLE_ERR < y;
 226 }
 227
 228 inline bool approximately_greater_than_one(double x) {
 229     return x > 1 - FLT_EPSILON;
 230 }
 231
 232 inline bool precisely_greater_than_one(double x) {
 233     return x > 1 - DBL_EPSILON_ERR;
 234 }
 235
 236 inline bool approximately_less_than_zero(double x) {
 237     return x < FLT_EPSILON;
 238 }
 239
 240 inline bool precisely_less_than_zero(double x) {
 241     return x < DBL_EPSILON_ERR;
 242 }
 243
 244 inline bool approximately_negative(double x) {
 245     return x < FLT_EPSILON;
 246 }
 247
 248 inline bool approximately_negative_orderable(double x) {
 249     return x < FLT_EPSILON_ORDERABLE_ERR;
 250 }
 251
 252 inline bool precisely_negative(double x) {
 253     return x < DBL_EPSILON_ERR;
 254 }
 255
 256 inline bool approximately_one_or_less(double x) {
 257     return x < 1 + FLT_EPSILON;
 258 }
 259
 260 inline bool approximately_one_or_less_double(double x) {
 261     return x < 1 + FLT_EPSILON_DOUBLE;
 262 }
 263
 264 inline bool approximately_positive(double x) {
 265     return x > -FLT_EPSILON;
 266 }
 267
 268 inline bool approximately_positive_squared(double x) {
 269     return x > -(FLT_EPSILON_SQUARED);
 270 }
 271
 272 inline bool approximately_zero_or_more(double x) {
 273     return x > -FLT_EPSILON;
 274 }
 275
 276 inline bool approximately_zero_or_more_double(double x) {
 277     return x > -FLT_EPSILON_DOUBLE;
 278 }
 279
 280 inline bool approximately_between_orderable(double a, double b, double c) {
 281     return a <= c
 282             ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c)
 283             : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b);
 284 }
 285
 286 inline bool approximately_between(double a, double b, double c) {
 287     return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
 288             : approximately_negative(b - a) && approximately_negative(c - b);
 289 }
 290
 291 inline bool precisely_between(double a, double b, double c) {
 292     return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
 293             : precisely_negative(b - a) && precisely_negative(c - b);
 294 }
 295
 296 // returns true if (a <= b <= c) || (a >= b >= c)
 297 inline bool between(double a, double b, double c) {
 298     SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0));
 299     return (a - b) * (c - b) <= 0;
 300 }
 301
 302 inline bool more_roughly_equal(double x, double y) {
 303     return fabs(x - y) < MORE_ROUGH_EPSILON;
 304 }
 305
 306 inline bool roughly_equal(double x, double y) {
 307     return fabs(x - y) < ROUGH_EPSILON;
 308 }
 309
 310 struct SkDPoint;
 311 struct SkDVector;
 312 struct SkDLine;
 313 struct SkDQuad;
 314 struct SkDTriangle;
 315 struct SkDCubic;
 316 struct SkDRect;
 317
 318 inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
 319     int verb = (1 << points) >> 1;
 320 #ifdef SK_DEBUG
 321     switch (points) {
 322         case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
 323         case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
 324         case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
 325         case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
 326         default: SkDEBUGFAIL("should not be here");
 327     }
 328 #endif
 329     return (SkPath::Verb)verb;
 330 }
 331
 332 inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
 333     int points = (int) verb - ((int) verb >> 2);
 334 #ifdef SK_DEBUG
 335     switch (verb) {
 336         case SkPath::kLine_Verb: SkASSERT(1 == points); break;
 337         case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
 338         case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
 339         default: SkDEBUGFAIL("should not get here");
 340     }
 341 #endif
 342     return points;
 343 }
 344
 345 inline double SkDInterp(double A, double B, double t) {
 346     return A + (B - A) * t;
 347 }
 348
 349 double SkDCubeRoot(double x);
 350
 351 /* Returns -1 if negative, 0 if zero, 1 if positive
 352 */
 353 inline int SkDSign(double x) {
 354     return (x > 0) - (x < 0);
 355 }
 356
 357 /* Returns 0 if negative, 1 if zero, 2 if positive
 358 */
 359 inline int SKDSide(double x) {
 360     return (x > 0) + (x >= 0);
 361 }
 362
 363 /* Returns 1 if negative, 2 if zero, 4 if positive
 364 */
 365 inline int SkDSideBit(double x) {
 366     return 1 << SKDSide(x);
 367 }
 368
 369 inline double SkPinT(double t) {
 370     return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
 371 }
 372
 373 #endif