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