123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SkPathOpsTypes_DEFINED
- #define SkPathOpsTypes_DEFINED
- #include <float.h> // for FLT_EPSILON
- #include "include/core/SkPath.h"
- #include "include/core/SkScalar.h"
- #include "include/pathops/SkPathOps.h"
- #include "include/private/SkFloatingPoint.h"
- #include "include/private/SkSafe_math.h"
- #include "src/pathops/SkPathOpsDebug.h"
- enum SkPathOpsMask {
- kWinding_PathOpsMask = -1,
- kNo_PathOpsMask = 0,
- kEvenOdd_PathOpsMask = 1
- };
- class SkArenaAlloc;
- class SkOpCoincidence;
- class SkOpContour;
- class SkOpContourHead;
- class SkIntersections;
- class SkIntersectionHelper;
- enum class SkOpPhase : char {
- kNoChange,
- kIntersecting,
- kWalking,
- kFixWinding,
- };
- class SkOpGlobalState {
- public:
- SkOpGlobalState(SkOpContourHead* head,
- SkArenaAlloc* allocator SkDEBUGPARAMS(bool debugSkipAssert)
- SkDEBUGPARAMS(const char* testName));
- enum {
- kMaxWindingTries = 10
- };
- bool allocatedOpSpan() const {
- return fAllocatedOpSpan;
- }
- SkArenaAlloc* allocator() {
- return fAllocator;
- }
- void bumpNested() {
- ++fNested;
- }
- void clearNested() {
- fNested = 0;
- }
- SkOpCoincidence* coincidence() {
- return fCoincidence;
- }
- SkOpContourHead* contourHead() {
- return fContourHead;
- }
- #ifdef SK_DEBUG
- const class SkOpAngle* debugAngle(int id) const;
- const SkOpCoincidence* debugCoincidence() const;
- SkOpContour* debugContour(int id) const;
- const class SkOpPtT* debugPtT(int id) const;
- #endif
- static bool DebugRunFail();
- #ifdef SK_DEBUG
- const class SkOpSegment* debugSegment(int id) const;
- bool debugSkipAssert() const { return fDebugSkipAssert; }
- const class SkOpSpanBase* debugSpan(int id) const;
- const char* debugTestName() const { return fDebugTestName; }
- #endif
- #if DEBUG_T_SECT_LOOP_COUNT
- void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& ,
- const SkIntersectionHelper& );
- void debugDoYourWorst(SkOpGlobalState* );
- void debugLoopReport();
- void debugResetLoopCounts();
- #endif
- #if DEBUG_COINCIDENCE
- void debugSetCheckHealth(bool check) { fDebugCheckHealth = check; }
- bool debugCheckHealth() const { return fDebugCheckHealth; }
- #endif
- #if DEBUG_VALIDATE || DEBUG_COIN
- void debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const;
- #endif
- #if DEBUG_COIN
- void debugAddToCoinChangedDict();
- void debugAddToGlobalCoinDicts();
- SkPathOpsDebug::CoinDict* debugCoinChangedDict() { return &fCoinChangedDict; }
- const SkPathOpsDebug::CoinDictEntry& debugCoinDictEntry() const { return fCoinDictEntry; }
- static void DumpCoinDict();
- #endif
- int nested() const {
- return fNested;
- }
- #ifdef SK_DEBUG
- int nextAngleID() {
- return ++fAngleID;
- }
- int nextCoinID() {
- return ++fCoinID;
- }
- int nextContourID() {
- return ++fContourID;
- }
- int nextPtTID() {
- return ++fPtTID;
- }
- int nextSegmentID() {
- return ++fSegmentID;
- }
- int nextSpanID() {
- return ++fSpanID;
- }
- #endif
- SkOpPhase phase() const {
- return fPhase;
- }
- void resetAllocatedOpSpan() {
- fAllocatedOpSpan = false;
- }
- void setAllocatedOpSpan() {
- fAllocatedOpSpan = true;
- }
- void setCoincidence(SkOpCoincidence* coincidence) {
- fCoincidence = coincidence;
- }
- void setContourHead(SkOpContourHead* contourHead) {
- fContourHead = contourHead;
- }
- void setPhase(SkOpPhase phase) {
- if (SkOpPhase::kNoChange == phase) {
- return;
- }
- SkASSERT(fPhase != phase);
- fPhase = phase;
- }
- // called in very rare cases where angles are sorted incorrectly -- signfies op will fail
- void setWindingFailed() {
- fWindingFailed = true;
- }
- bool windingFailed() const {
- return fWindingFailed;
- }
- private:
- SkArenaAlloc* fAllocator;
- SkOpCoincidence* fCoincidence;
- SkOpContourHead* fContourHead;
- int fNested;
- bool fAllocatedOpSpan;
- bool fWindingFailed;
- SkOpPhase fPhase;
- #ifdef SK_DEBUG
- const char* fDebugTestName;
- void* fDebugReporter;
- int fAngleID;
- int fCoinID;
- int fContourID;
- int fPtTID;
- int fSegmentID;
- int fSpanID;
- bool fDebugSkipAssert;
- #endif
- #if DEBUG_T_SECT_LOOP_COUNT
- int fDebugLoopCount[3];
- SkPath::Verb fDebugWorstVerb[6];
- SkPoint fDebugWorstPts[24];
- float fDebugWorstWeight[6];
- #endif
- #if DEBUG_COIN
- SkPathOpsDebug::CoinDict fCoinChangedDict;
- SkPathOpsDebug::CoinDict fCoinVisitedDict;
- SkPathOpsDebug::CoinDictEntry fCoinDictEntry;
- const char* fPreviousFuncName;
- #endif
- #if DEBUG_COINCIDENCE
- bool fDebugCheckHealth;
- #endif
- };
- #ifdef SK_DEBUG
- #if DEBUG_COINCIDENCE
- #define SkOPASSERT(cond) SkASSERT((this->globalState() && \
- (this->globalState()->debugCheckHealth() || \
- this->globalState()->debugSkipAssert())) || (cond))
- #else
- #define SkOPASSERT(cond) SkASSERT((this->globalState() && \
- this->globalState()->debugSkipAssert()) || (cond))
- #endif
- #define SkOPOBJASSERT(obj, cond) SkASSERT((obj->globalState() && \
- obj->globalState()->debugSkipAssert()) || (cond))
- #else
- #define SkOPASSERT(cond)
- #define SkOPOBJASSERT(obj, cond)
- #endif
- // Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
- bool AlmostEqualUlps(float a, float b);
- inline bool AlmostEqualUlps(double a, double b) {
- return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostEqualUlpsNoNormalCheck(float a, float b);
- inline bool AlmostEqualUlpsNoNormalCheck(double a, double b) {
- return AlmostEqualUlpsNoNormalCheck(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostEqualUlps_Pin(float a, float b);
- inline bool AlmostEqualUlps_Pin(double a, double b) {
- return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- // Use Almost Dequal when comparing should not special case denormalized values.
- bool AlmostDequalUlps(float a, float b);
- bool AlmostDequalUlps(double a, double b);
- bool NotAlmostEqualUlps(float a, float b);
- inline bool NotAlmostEqualUlps(double a, double b) {
- return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool NotAlmostEqualUlps_Pin(float a, float b);
- inline bool NotAlmostEqualUlps_Pin(double a, double b) {
- return NotAlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool NotAlmostDequalUlps(float a, float b);
- inline bool NotAlmostDequalUlps(double a, double b) {
- return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- // Use Almost Bequal when comparing coordinates in conjunction with between.
- bool AlmostBequalUlps(float a, float b);
- inline bool AlmostBequalUlps(double a, double b) {
- return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostPequalUlps(float a, float b);
- inline bool AlmostPequalUlps(double a, double b) {
- return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool RoughlyEqualUlps(float a, float b);
- inline bool RoughlyEqualUlps(double a, double b) {
- return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostLessUlps(float a, float b);
- inline bool AlmostLessUlps(double a, double b) {
- return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostLessOrEqualUlps(float a, float b);
- inline bool AlmostLessOrEqualUlps(double a, double b) {
- return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- bool AlmostBetweenUlps(float a, float b, float c);
- inline bool AlmostBetweenUlps(double a, double b, double c) {
- return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
- }
- int UlpsDistance(float a, float b);
- inline int UlpsDistance(double a, double b) {
- return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
- }
- // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
- // DBL_EPSILON == 2.22045e-16
- const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
- const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
- const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
- const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16;
- const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
- // Use a compile-time constant for FLT_EPSILON_SQRT to avoid initializers.
- // A 17 digit constant guarantees exact results.
- const double FLT_EPSILON_SQRT = 0.00034526697709225118; // sqrt(FLT_EPSILON);
- const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
- const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error
- const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
- const double ROUGH_EPSILON = FLT_EPSILON * 64;
- const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
- const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048;
- const double BUMP_EPSILON = FLT_EPSILON * 4096;
- const SkScalar INVERSE_NUMBER_RANGE = FLT_EPSILON_ORDERABLE_ERR;
- inline bool zero_or_one(double x) {
- return x == 0 || x == 1;
- }
- inline bool approximately_zero(double x) {
- return fabs(x) < FLT_EPSILON;
- }
- inline bool precisely_zero(double x) {
- return fabs(x) < DBL_EPSILON_ERR;
- }
- inline bool precisely_subdivide_zero(double x) {
- return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
- }
- inline bool approximately_zero(float x) {
- return fabs(x) < FLT_EPSILON;
- }
- inline bool approximately_zero_cubed(double x) {
- return fabs(x) < FLT_EPSILON_CUBED;
- }
- inline bool approximately_zero_half(double x) {
- return fabs(x) < FLT_EPSILON_HALF;
- }
- inline bool approximately_zero_double(double x) {
- return fabs(x) < FLT_EPSILON_DOUBLE;
- }
- inline bool approximately_zero_orderable(double x) {
- return fabs(x) < FLT_EPSILON_ORDERABLE_ERR;
- }
- inline bool approximately_zero_squared(double x) {
- return fabs(x) < FLT_EPSILON_SQUARED;
- }
- inline bool approximately_zero_sqrt(double x) {
- return fabs(x) < FLT_EPSILON_SQRT;
- }
- inline bool roughly_zero(double x) {
- return fabs(x) < ROUGH_EPSILON;
- }
- inline bool approximately_zero_inverse(double x) {
- return fabs(x) > FLT_EPSILON_INVERSE;
- }
- inline bool approximately_zero_when_compared_to(double x, double y) {
- return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
- }
- inline bool precisely_zero_when_compared_to(double x, double y) {
- return x == 0 || fabs(x) < fabs(y * DBL_EPSILON);
- }
- inline bool roughly_zero_when_compared_to(double x, double y) {
- return x == 0 || fabs(x) < fabs(y * ROUGH_EPSILON);
- }
- // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
- // AlmostEqualUlps instead.
- inline bool approximately_equal(double x, double y) {
- return approximately_zero(x - y);
- }
- inline bool precisely_equal(double x, double y) {
- return precisely_zero(x - y);
- }
- inline bool precisely_subdivide_equal(double x, double y) {
- return precisely_subdivide_zero(x - y);
- }
- inline bool approximately_equal_half(double x, double y) {
- return approximately_zero_half(x - y);
- }
- inline bool approximately_equal_double(double x, double y) {
- return approximately_zero_double(x - y);
- }
- inline bool approximately_equal_orderable(double x, double y) {
- return approximately_zero_orderable(x - y);
- }
- inline bool approximately_equal_squared(double x, double y) {
- return approximately_equal(x, y);
- }
- inline bool approximately_greater(double x, double y) {
- return x - FLT_EPSILON >= y;
- }
- inline bool approximately_greater_double(double x, double y) {
- return x - FLT_EPSILON_DOUBLE >= y;
- }
- inline bool approximately_greater_orderable(double x, double y) {
- return x - FLT_EPSILON_ORDERABLE_ERR >= y;
- }
- inline bool approximately_greater_or_equal(double x, double y) {
- return x + FLT_EPSILON > y;
- }
- inline bool approximately_greater_or_equal_double(double x, double y) {
- return x + FLT_EPSILON_DOUBLE > y;
- }
- inline bool approximately_greater_or_equal_orderable(double x, double y) {
- return x + FLT_EPSILON_ORDERABLE_ERR > y;
- }
- inline bool approximately_lesser(double x, double y) {
- return x + FLT_EPSILON <= y;
- }
- inline bool approximately_lesser_double(double x, double y) {
- return x + FLT_EPSILON_DOUBLE <= y;
- }
- inline bool approximately_lesser_orderable(double x, double y) {
- return x + FLT_EPSILON_ORDERABLE_ERR <= y;
- }
- inline bool approximately_lesser_or_equal(double x, double y) {
- return x - FLT_EPSILON < y;
- }
- inline bool approximately_lesser_or_equal_double(double x, double y) {
- return x - FLT_EPSILON_DOUBLE < y;
- }
- inline bool approximately_lesser_or_equal_orderable(double x, double y) {
- return x - FLT_EPSILON_ORDERABLE_ERR < y;
- }
- inline bool approximately_greater_than_one(double x) {
- return x > 1 - FLT_EPSILON;
- }
- inline bool precisely_greater_than_one(double x) {
- return x > 1 - DBL_EPSILON_ERR;
- }
- inline bool approximately_less_than_zero(double x) {
- return x < FLT_EPSILON;
- }
- inline bool precisely_less_than_zero(double x) {
- return x < DBL_EPSILON_ERR;
- }
- inline bool approximately_negative(double x) {
- return x < FLT_EPSILON;
- }
- inline bool approximately_negative_orderable(double x) {
- return x < FLT_EPSILON_ORDERABLE_ERR;
- }
- inline bool precisely_negative(double x) {
- return x < DBL_EPSILON_ERR;
- }
- inline bool approximately_one_or_less(double x) {
- return x < 1 + FLT_EPSILON;
- }
- inline bool approximately_one_or_less_double(double x) {
- return x < 1 + FLT_EPSILON_DOUBLE;
- }
- inline bool approximately_positive(double x) {
- return x > -FLT_EPSILON;
- }
- inline bool approximately_positive_squared(double x) {
- return x > -(FLT_EPSILON_SQUARED);
- }
- inline bool approximately_zero_or_more(double x) {
- return x > -FLT_EPSILON;
- }
- inline bool approximately_zero_or_more_double(double x) {
- return x > -FLT_EPSILON_DOUBLE;
- }
- inline bool approximately_between_orderable(double a, double b, double c) {
- return a <= c
- ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c)
- : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b);
- }
- inline bool approximately_between(double a, double b, double c) {
- return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
- : approximately_negative(b - a) && approximately_negative(c - b);
- }
- inline bool precisely_between(double a, double b, double c) {
- return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
- : precisely_negative(b - a) && precisely_negative(c - b);
- }
- // returns true if (a <= b <= c) || (a >= b >= c)
- inline bool between(double a, double b, double c) {
- SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
- || (precisely_zero(a) && precisely_zero(b) && precisely_zero(c)));
- return (a - b) * (c - b) <= 0;
- }
- inline bool roughly_equal(double x, double y) {
- return fabs(x - y) < ROUGH_EPSILON;
- }
- inline bool roughly_negative(double x) {
- return x < ROUGH_EPSILON;
- }
- inline bool roughly_between(double a, double b, double c) {
- return a <= c ? roughly_negative(a - b) && roughly_negative(b - c)
- : roughly_negative(b - a) && roughly_negative(c - b);
- }
- inline bool more_roughly_equal(double x, double y) {
- return fabs(x - y) < MORE_ROUGH_EPSILON;
- }
- struct SkDPoint;
- struct SkDVector;
- struct SkDLine;
- struct SkDQuad;
- struct SkDConic;
- struct SkDCubic;
- struct SkDRect;
- inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
- int verb = (1 << points) >> 1;
- #ifdef SK_DEBUG
- switch (points) {
- case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
- case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
- case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
- case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
- default: SkDEBUGFAIL("should not be here");
- }
- #endif
- return (SkPath::Verb)verb;
- }
- inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
- int points = (int) verb - (((int) verb + 1) >> 2);
- #ifdef SK_DEBUG
- switch (verb) {
- case SkPath::kLine_Verb: SkASSERT(1 == points); break;
- case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
- case SkPath::kConic_Verb: SkASSERT(2 == points); break;
- case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
- default: SkDEBUGFAIL("should not get here");
- }
- #endif
- return points;
- }
- inline double SkDInterp(double A, double B, double t) {
- return A + (B - A) * t;
- }
- double SkDCubeRoot(double x);
- /* Returns -1 if negative, 0 if zero, 1 if positive
- */
- inline int SkDSign(double x) {
- return (x > 0) - (x < 0);
- }
- /* Returns 0 if negative, 1 if zero, 2 if positive
- */
- inline int SKDSide(double x) {
- return (x > 0) + (x >= 0);
- }
- /* Returns 1 if negative, 2 if zero, 4 if positive
- */
- inline int SkDSideBit(double x) {
- return 1 << SKDSide(x);
- }
- inline double SkPinT(double t) {
- return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
- }
- #endif
|