src/third_party/skia/experimental/Intersection/DataTypes.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 __DataTypes_h__
   8 #define __DataTypes_h__
   9
  10 #include <float.h> // for FLT_EPSILON
  11 #include <math.h> // for fabs, sqrt
  12
  13 #include "SkPoint.h"
  14
  15 #define FORCE_RELEASE 0  // set force release to 1 for multiple thread -- no debugging
  16 #define ONE_OFF_DEBUG 1
  17 #define ONE_OFF_DEBUG_MATHEMATICA 0
  18
  19 // FIXME: move these into SkTypes.h
  20 template <typename T> inline T SkTMax(T a, T b) {
  21     if (a < b)
  22         a = b;
  23     return a;
  24 }
  25
  26 template <typename T> inline T SkTMin(T a, T b) {
  27     if (a > b)
  28         a = b;
  29     return a;
  30 }
  31
  32 extern bool AlmostEqualUlps(float A, float B);
  33 inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps((float) A, (float) B); }
  34
  35 // FIXME: delete
  36 int UlpsDiff(float A, float B);
  37
  38 // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
  39 // DBL_EPSILON == 2.22045e-16
  40 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
  41 const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
  42 const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
  43 const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON);
  44 const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
  45 const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // tune -- allow a few bits of error
  46 const double ROUGH_EPSILON = FLT_EPSILON * 64;
  47 const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
  48
  49 inline bool approximately_zero(double x) {
  50     return fabs(x) < FLT_EPSILON;
  51 }
  52
  53 inline bool precisely_zero(double x) {
  54     return fabs(x) < DBL_EPSILON_ERR;
  55 }
  56
  57 inline bool approximately_zero(float x) {
  58     return fabs(x) < FLT_EPSILON;
  59 }
  60
  61 inline bool approximately_zero_cubed(double x) {
  62     return fabs(x) < FLT_EPSILON_CUBED;
  63 }
  64
  65 inline bool approximately_zero_half(double x) {
  66     return fabs(x) < FLT_EPSILON_HALF;
  67 }
  68
  69 inline bool approximately_zero_squared(double x) {
  70     return fabs(x) < FLT_EPSILON_SQUARED;
  71 }
  72
  73 inline bool approximately_zero_sqrt(double x) {
  74     return fabs(x) < FLT_EPSILON_SQRT;
  75 }
  76
  77 inline bool approximately_zero_inverse(double x) {
  78     return fabs(x) > FLT_EPSILON_INVERSE;
  79 }
  80
  81 // FIXME: if called multiple times with the same denom, we want to pass 1/y instead
  82 inline bool approximately_zero_when_compared_to(double x, double y) {
  83     return x == 0 || fabs(x / y) < FLT_EPSILON;
  84 }
  85
  86 // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
  87 // AlmostEqualUlps instead.
  88 inline bool approximately_equal(double x, double y) {
  89 #if 1
  90     return approximately_zero(x - y);
  91 #else
  92 // see http://visualstudiomagazine.com/blogs/tool-tracker/2011/11/compare-floating-point-numbers.aspx
  93 // this allows very small (e.g. degenerate) values to compare unequally, but in this case,
  94 // AlmostEqualUlps should be used instead.
  95     if (x == y) {
  96         return true;
  97     }
  98     double absY = fabs(y);
  99     if (x == 0) {
 100         return absY < FLT_EPSILON;
 101     }
 102     double absX = fabs(x);
 103     if (y == 0) {
 104         return absX < FLT_EPSILON;
 105     }
 106     return fabs(x - y) < (absX > absY ? absX : absY) * FLT_EPSILON;
 107 #endif
 108 }
 109
 110 inline bool precisely_equal(double x, double y) {
 111     return precisely_zero(x - y);
 112 }
 113
 114 inline bool approximately_equal_half(double x, double y) {
 115     return approximately_zero_half(x - y);
 116 }
 117
 118 inline bool approximately_equal_squared(double x, double y) {
 119     return approximately_equal(x, y);
 120 }
 121
 122 inline bool approximately_greater(double x, double y) {
 123     return x - FLT_EPSILON >= y;
 124 }
 125
 126 inline bool approximately_greater_or_equal(double x, double y) {
 127     return x + FLT_EPSILON > y;
 128 }
 129
 130 inline bool approximately_lesser(double x, double y) {
 131     return x + FLT_EPSILON <= y;
 132 }
 133
 134 inline bool approximately_lesser_or_equal(double x, double y) {
 135     return x - FLT_EPSILON < y;
 136 }
 137
 138 inline double approximately_pin(double x) {
 139     return approximately_zero(x) ? 0 : x;
 140 }
 141
 142 inline float approximately_pin(float x) {
 143     return approximately_zero(x) ? 0 : x;
 144 }
 145
 146 inline bool approximately_greater_than_one(double x) {
 147     return x > 1 - FLT_EPSILON;
 148 }
 149
 150 inline bool precisely_greater_than_one(double x) {
 151     return x > 1 - DBL_EPSILON_ERR;
 152 }
 153
 154 inline bool approximately_less_than_zero(double x) {
 155     return x < FLT_EPSILON;
 156 }
 157
 158 inline bool precisely_less_than_zero(double x) {
 159     return x < DBL_EPSILON_ERR;
 160 }
 161
 162 inline bool approximately_negative(double x) {
 163     return x < FLT_EPSILON;
 164 }
 165
 166 inline bool precisely_negative(double x) {
 167     return x < DBL_EPSILON_ERR;
 168 }
 169
 170 inline bool approximately_one_or_less(double x) {
 171     return x < 1 + FLT_EPSILON;
 172 }
 173
 174 inline bool approximately_positive(double x) {
 175     return x > -FLT_EPSILON;
 176 }
 177
 178 inline bool approximately_positive_squared(double x) {
 179     return x > -(FLT_EPSILON_SQUARED);
 180 }
 181
 182 inline bool approximately_zero_or_more(double x) {
 183     return x > -FLT_EPSILON;
 184 }
 185
 186 inline bool approximately_between(double a, double b, double c) {
 187     return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
 188             : approximately_negative(b - a) && approximately_negative(c - b);
 189 }
 190
 191 // returns true if (a <= b <= c) || (a >= b >= c)
 192 inline bool between(double a, double b, double c) {
 193     SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0));
 194     return (a - b) * (c - b) <= 0;
 195 }
 196
 197 inline bool more_roughly_equal(double x, double y) {
 198     return fabs(x - y) < MORE_ROUGH_EPSILON;
 199 }
 200
 201 inline bool roughly_equal(double x, double y) {
 202     return fabs(x - y) < ROUGH_EPSILON;
 203 }
 204
 205 struct _Point;
 206
 207 struct _Vector {
 208     double x;
 209     double y;
 210
 211     friend _Point operator+(const _Point& a, const _Vector& b);
 212
 213     void operator+=(const _Vector& v) {
 214         x += v.x;
 215         y += v.y;
 216     }
 217
 218     void operator-=(const _Vector& v) {
 219         x -= v.x;
 220         y -= v.y;
 221     }
 222
 223     void operator/=(const double s) {
 224         x /= s;
 225         y /= s;
 226     }
 227
 228     void operator*=(const double s) {
 229         x *= s;
 230         y *= s;
 231     }
 232
 233     double cross(const _Vector& a) const {
 234         return x * a.y - y * a.x;
 235     }
 236
 237     double dot(const _Vector& a) const {
 238         return x * a.x + y * a.y;
 239     }
 240
 241     double length() const {
 242         return sqrt(lengthSquared());
 243     }
 244
 245     double lengthSquared() const {
 246         return x * x + y * y;
 247     }
 248
 249     SkVector asSkVector() const {
 250         SkVector v = {SkDoubleToScalar(x), SkDoubleToScalar(y)};
 251         return v;
 252     }
 253 };
 254
 255 struct _Point {
 256     double x;
 257     double y;
 258
 259     friend _Vector operator-(const _Point& a, const _Point& b);
 260
 261     void operator+=(const _Vector& v) {
 262         x += v.x;
 263         y += v.y;
 264     }
 265
 266     void operator-=(const _Vector& v) {
 267         x -= v.x;
 268         y -= v.y;
 269     }
 270
 271     friend bool operator==(const _Point& a, const _Point& b) {
 272         return a.x == b.x && a.y == b.y;
 273     }
 274
 275     friend bool operator!=(const _Point& a, const _Point& b) {
 276         return a.x != b.x || a.y != b.y;
 277     }
 278
 279     // note: this can not be implemented with
 280     // return approximately_equal(a.y, y) && approximately_equal(a.x, x);
 281     // because that will not take the magnitude of the values
 282     bool approximatelyEqual(const _Point& a) const {
 283         double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.x), fabs(a.y))));
 284         if (denom == 0) {
 285             return true;
 286         }
 287         double inv = 1 / denom;
 288         return approximately_equal(x * inv, a.x * inv) && approximately_equal(y * inv, a.y * inv);
 289     }
 290
 291     bool approximatelyEqual(const SkPoint& a) const {
 292         double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.fX), fabs(a.fY))));
 293         if (denom == 0) {
 294             return true;
 295         }
 296         double inv = 1 / denom;
 297         return approximately_equal(x * inv, a.fX * inv) && approximately_equal(y * inv, a.fY * inv);
 298     }
 299
 300     bool approximatelyEqualHalf(const _Point& a) const {
 301         double denom = SkTMax(fabs(x), SkTMax(fabs(y), SkTMax(fabs(a.x), fabs(a.y))));
 302         if (denom == 0) {
 303             return true;
 304         }
 305         double inv = 1 / denom;
 306         return approximately_equal_half(x * inv, a.x * inv)
 307                 && approximately_equal_half(y * inv, a.y * inv);
 308     }
 309
 310     bool approximatelyZero() const {
 311         return approximately_zero(x) && approximately_zero(y);
 312     }
 313
 314     SkPoint asSkPoint() const {
 315         SkPoint pt = {SkDoubleToScalar(x), SkDoubleToScalar(y)};
 316         return pt;
 317     }
 318
 319     double distance(const _Point& a) const {
 320         _Vector temp = *this - a;
 321         return temp.length();
 322     }
 323
 324     double distanceSquared(const _Point& a) const {
 325         _Vector temp = *this - a;
 326         return temp.lengthSquared();
 327     }
 328
 329     double moreRoughlyEqual(const _Point& a) const {
 330         return more_roughly_equal(a.y, y) && more_roughly_equal(a.x, x);
 331     }
 332
 333     double roughlyEqual(const _Point& a) const {
 334         return roughly_equal(a.y, y) && roughly_equal(a.x, x);
 335     }
 336 };
 337
 338 typedef _Point _Line[2];
 339 typedef _Point Quadratic[3];
 340 typedef _Point Triangle[3];
 341 typedef _Point Cubic[4];
 342
 343 struct _Rect {
 344     double left;
 345     double top;
 346     double right;
 347     double bottom;
 348
 349     void add(const _Point& pt) {
 350         if (left > pt.x) {
 351             left = pt.x;
 352         }
 353         if (top > pt.y) {
 354             top = pt.y;
 355         }
 356         if (right < pt.x) {
 357             right = pt.x;
 358         }
 359         if (bottom < pt.y) {
 360             bottom = pt.y;
 361         }
 362     }
 363
 364     // FIXME: used by debugging only ?
 365     bool contains(const _Point& pt) const {
 366         return approximately_between(left, pt.x, right)
 367                 && approximately_between(top, pt.y, bottom);
 368     }
 369
 370     bool intersects(_Rect& r) const {
 371         SkASSERT(left <= right);
 372         SkASSERT(top <= bottom);
 373         SkASSERT(r.left <= r.right);
 374         SkASSERT(r.top <= r.bottom);
 375         return r.left <= right && left <= r.right && r.top <= bottom && top <= r.bottom;
 376     }
 377
 378     void set(const _Point& pt) {
 379         left = right = pt.x;
 380         top = bottom = pt.y;
 381     }
 382
 383     void setBounds(const _Line& line) {
 384         set(line[0]);
 385         add(line[1]);
 386     }
 387
 388     void setBounds(const Cubic& );
 389     void setBounds(const Quadratic& );
 390     void setRawBounds(const Cubic& );
 391     void setRawBounds(const Quadratic& );
 392 };
 393
 394 struct CubicPair {
 395     const Cubic& first() const { return (const Cubic&) pts[0]; }
 396     const Cubic& second() const { return (const Cubic&) pts[3]; }
 397     _Point pts[7];
 398 };
 399
 400 struct QuadraticPair {
 401     const Quadratic& first() const { return (const Quadratic&) pts[0]; }
 402     const Quadratic& second() const { return (const Quadratic&) pts[2]; }
 403     _Point pts[5];
 404 };
 405
 406 // FIXME: move these into SkFloatingPoint.h
 407 #include "SkFloatingPoint.h"
 408
 409 #define sk_double_isnan(a) sk_float_isnan(a)
 410
 411 // FIXME: move these to debugging file
 412 #ifdef SK_DEBUG
 413 void mathematica_ize(char* str, size_t bufferSize);
 414 bool valid_wind(int winding);
 415 void winding_printf(int winding);
 416 #endif
 417
 418 #endif // __DataTypes_h__