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