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 25// Use Almost Equal when comparing coordinates. Use epsilon to compare T values. 26bool AlmostEqualUlps(float a, float b); 27inline 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. 32bool AlmostDequalUlps(float a, float b); 33bool AlmostDequalUlps(double a, double b); 34 35bool NotAlmostEqualUlps(float a, float b); 36inline bool NotAlmostEqualUlps(double a, double b) { 37 return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 38} 39 40bool NotAlmostDequalUlps(float a, float b); 41inline 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. 46bool AlmostBequalUlps(float a, float b); 47inline bool AlmostBequalUlps(double a, double b) { 48 return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 49} 50 51bool AlmostPequalUlps(float a, float b); 52inline bool AlmostPequalUlps(double a, double b) { 53 return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 54} 55 56bool RoughlyEqualUlps(float a, float b); 57inline bool RoughlyEqualUlps(double a, double b) { 58 return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 59} 60 61bool AlmostLessUlps(float a, float b); 62inline bool AlmostLessUlps(double a, double b) { 63 return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 64} 65 66bool AlmostLessOrEqualUlps(float a, float b); 67inline bool AlmostLessOrEqualUlps(double a, double b) { 68 return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b)); 69} 70 71bool AlmostBetweenUlps(float a, float b, float c); 72inline bool AlmostBetweenUlps(double a, double b, double c) { 73 return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c)); 74} 75 76int UlpsDistance(float a, float b); 77inline 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 83const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; 84const double FLT_EPSILON_HALF = FLT_EPSILON / 2; 85const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; 86const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16; 87const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; 88const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); 89const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; 90const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error 91const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; 92const double ROUGH_EPSILON = FLT_EPSILON * 64; 93const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; 94const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048; 95 96inline bool zero_or_one(double x) { 97 return x == 0 || x == 1; 98} 99 100inline bool approximately_zero(double x) { 101 return fabs(x) < FLT_EPSILON; 102} 103 104inline bool precisely_zero(double x) { 105 return fabs(x) < DBL_EPSILON_ERR; 106} 107 108inline bool precisely_subdivide_zero(double x) { 109 return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR; 110} 111 112inline bool approximately_zero(float x) { 113 return fabs(x) < FLT_EPSILON; 114} 115 116inline bool approximately_zero_cubed(double x) { 117 return fabs(x) < FLT_EPSILON_CUBED; 118} 119 120inline bool approximately_zero_half(double x) { 121 return fabs(x) < FLT_EPSILON_HALF; 122} 123 124inline bool approximately_zero_double(double x) { 125 return fabs(x) < FLT_EPSILON_DOUBLE; 126} 127 128inline bool approximately_zero_orderable(double x) { 129 return fabs(x) < FLT_EPSILON_ORDERABLE_ERR; 130} 131 132inline bool approximately_zero_squared(double x) { 133 return fabs(x) < FLT_EPSILON_SQUARED; 134} 135 136inline bool approximately_zero_sqrt(double x) { 137 return fabs(x) < FLT_EPSILON_SQRT; 138} 139 140inline bool roughly_zero(double x) { 141 return fabs(x) < ROUGH_EPSILON; 142} 143 144inline 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 149inline 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. 155inline bool approximately_equal(double x, double y) { 156 return approximately_zero(x - y); 157} 158 159inline bool precisely_equal(double x, double y) { 160 return precisely_zero(x - y); 161} 162 163inline bool precisely_subdivide_equal(double x, double y) { 164 return precisely_subdivide_zero(x - y); 165} 166 167inline bool approximately_equal_half(double x, double y) { 168 return approximately_zero_half(x - y); 169} 170 171inline bool approximately_equal_double(double x, double y) { 172 return approximately_zero_double(x - y); 173} 174 175inline bool approximately_equal_orderable(double x, double y) { 176 return approximately_zero_orderable(x - y); 177} 178 179inline bool approximately_equal_squared(double x, double y) { 180 return approximately_equal(x, y); 181} 182 183inline bool approximately_greater(double x, double y) { 184 return x - FLT_EPSILON >= y; 185} 186 187inline bool approximately_greater_double(double x, double y) { 188 return x - FLT_EPSILON_DOUBLE >= y; 189} 190 191inline bool approximately_greater_orderable(double x, double y) { 192 return x - FLT_EPSILON_ORDERABLE_ERR >= y; 193} 194 195inline bool approximately_greater_or_equal(double x, double y) { 196 return x + FLT_EPSILON > y; 197} 198 199inline bool approximately_greater_or_equal_double(double x, double y) { 200 return x + FLT_EPSILON_DOUBLE > y; 201} 202 203inline bool approximately_greater_or_equal_orderable(double x, double y) { 204 return x + FLT_EPSILON_ORDERABLE_ERR > y; 205} 206 207inline bool approximately_lesser(double x, double y) { 208 return x + FLT_EPSILON <= y; 209} 210 211inline bool approximately_lesser_double(double x, double y) { 212 return x + FLT_EPSILON_DOUBLE <= y; 213} 214 215inline bool approximately_lesser_orderable(double x, double y) { 216 return x + FLT_EPSILON_ORDERABLE_ERR <= y; 217} 218 219inline bool approximately_lesser_or_equal(double x, double y) { 220 return x - FLT_EPSILON < y; 221} 222 223inline bool approximately_lesser_or_equal_double(double x, double y) { 224 return x - FLT_EPSILON_DOUBLE < y; 225} 226 227inline bool approximately_lesser_or_equal_orderable(double x, double y) { 228 return x - FLT_EPSILON_ORDERABLE_ERR < y; 229} 230 231inline bool approximately_greater_than_one(double x) { 232 return x > 1 - FLT_EPSILON; 233} 234 235inline bool precisely_greater_than_one(double x) { 236 return x > 1 - DBL_EPSILON_ERR; 237} 238 239inline bool approximately_less_than_zero(double x) { 240 return x < FLT_EPSILON; 241} 242 243inline bool precisely_less_than_zero(double x) { 244 return x < DBL_EPSILON_ERR; 245} 246 247inline bool approximately_negative(double x) { 248 return x < FLT_EPSILON; 249} 250 251inline bool approximately_negative_orderable(double x) { 252 return x < FLT_EPSILON_ORDERABLE_ERR; 253} 254 255inline bool precisely_negative(double x) { 256 return x < DBL_EPSILON_ERR; 257} 258 259inline bool approximately_one_or_less(double x) { 260 return x < 1 + FLT_EPSILON; 261} 262 263inline bool approximately_one_or_less_double(double x) { 264 return x < 1 + FLT_EPSILON_DOUBLE; 265} 266 267inline bool approximately_positive(double x) { 268 return x > -FLT_EPSILON; 269} 270 271inline bool approximately_positive_squared(double x) { 272 return x > -(FLT_EPSILON_SQUARED); 273} 274 275inline bool approximately_zero_or_more(double x) { 276 return x > -FLT_EPSILON; 277} 278 279inline bool approximately_zero_or_more_double(double x) { 280 return x > -FLT_EPSILON_DOUBLE; 281} 282 283inline 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 289inline 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 294inline 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) 300inline 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 305inline bool roughly_equal(double x, double y) { 306 return fabs(x - y) < ROUGH_EPSILON; 307} 308 309inline bool more_roughly_equal(double x, double y) { 310 return fabs(x - y) < MORE_ROUGH_EPSILON; 311} 312 313inline bool way_roughly_equal(double x, double y) { 314 return fabs(x - y) < WAY_ROUGH_EPSILON; 315} 316 317struct SkDPoint; 318struct SkDVector; 319struct SkDLine; 320struct SkDQuad; 321struct SkDTriangle; 322struct SkDCubic; 323struct SkDRect; 324 325inline 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 339inline 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 352inline double SkDInterp(double A, double B, double t) { 353 return A + (B - A) * t; 354} 355 356double SkDCubeRoot(double x); 357 358/* Returns -1 if negative, 0 if zero, 1 if positive 359*/ 360inline int SkDSign(double x) { 361 return (x > 0) - (x < 0); 362} 363 364/* Returns 0 if negative, 1 if zero, 2 if positive 365*/ 366inline int SKDSide(double x) { 367 return (x > 0) + (x >= 0); 368} 369 370/* Returns 1 if negative, 2 if zero, 4 if positive 371*/ 372inline int SkDSideBit(double x) { 373 return 1 << SKDSide(x); 374} 375 376inline double SkPinT(double t) { 377 return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; 378} 379 380#endif 381