SkPathOpsTypes.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624
  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. #include <float.h> // for FLT_EPSILON
  10. #include "include/core/SkPath.h"
  11. #include "include/core/SkScalar.h"
  12. #include "include/pathops/SkPathOps.h"
  13. #include "include/private/SkFloatingPoint.h"
  14. #include "include/private/SkSafe_math.h"
  15. #include "src/pathops/SkPathOpsDebug.h"
  16. enum SkPathOpsMask {
  17. kWinding_PathOpsMask = -1,
  18. kNo_PathOpsMask = 0,
  19. kEvenOdd_PathOpsMask = 1
  20. };
  21. class SkArenaAlloc;
  22. class SkOpCoincidence;
  23. class SkOpContour;
  24. class SkOpContourHead;
  25. class SkIntersections;
  26. class SkIntersectionHelper;
  27. enum class SkOpPhase : char {
  28. kNoChange,
  29. kIntersecting,
  30. kWalking,
  31. kFixWinding,
  32. };
  33. class SkOpGlobalState {
  34. public:
  35. SkOpGlobalState(SkOpContourHead* head,
  36. SkArenaAlloc* allocator SkDEBUGPARAMS(bool debugSkipAssert)
  37. SkDEBUGPARAMS(const char* testName));
  38. enum {
  39. kMaxWindingTries = 10
  40. };
  41. bool allocatedOpSpan() const {
  42. return fAllocatedOpSpan;
  43. }
  44. SkArenaAlloc* allocator() {
  45. return fAllocator;
  46. }
  47. void bumpNested() {
  48. ++fNested;
  49. }
  50. void clearNested() {
  51. fNested = 0;
  52. }
  53. SkOpCoincidence* coincidence() {
  54. return fCoincidence;
  55. }
  56. SkOpContourHead* contourHead() {
  57. return fContourHead;
  58. }
  59. #ifdef SK_DEBUG
  60. const class SkOpAngle* debugAngle(int id) const;
  61. const SkOpCoincidence* debugCoincidence() const;
  62. SkOpContour* debugContour(int id) const;
  63. const class SkOpPtT* debugPtT(int id) const;
  64. #endif
  65. static bool DebugRunFail();
  66. #ifdef SK_DEBUG
  67. const class SkOpSegment* debugSegment(int id) const;
  68. bool debugSkipAssert() const { return fDebugSkipAssert; }
  69. const class SkOpSpanBase* debugSpan(int id) const;
  70. const char* debugTestName() const { return fDebugTestName; }
  71. #endif
  72. #if DEBUG_T_SECT_LOOP_COUNT
  73. void debugAddLoopCount(SkIntersections* , const SkIntersectionHelper& ,
  74. const SkIntersectionHelper& );
  75. void debugDoYourWorst(SkOpGlobalState* );
  76. void debugLoopReport();
  77. void debugResetLoopCounts();
  78. #endif
  79. #if DEBUG_COINCIDENCE
  80. void debugSetCheckHealth(bool check) { fDebugCheckHealth = check; }
  81. bool debugCheckHealth() const { return fDebugCheckHealth; }
  82. #endif
  83. #if DEBUG_VALIDATE || DEBUG_COIN
  84. void debugSetPhase(const char* funcName DEBUG_COIN_DECLARE_PARAMS()) const;
  85. #endif
  86. #if DEBUG_COIN
  87. void debugAddToCoinChangedDict();
  88. void debugAddToGlobalCoinDicts();
  89. SkPathOpsDebug::CoinDict* debugCoinChangedDict() { return &fCoinChangedDict; }
  90. const SkPathOpsDebug::CoinDictEntry& debugCoinDictEntry() const { return fCoinDictEntry; }
  91. static void DumpCoinDict();
  92. #endif
  93. int nested() const {
  94. return fNested;
  95. }
  96. #ifdef SK_DEBUG
  97. int nextAngleID() {
  98. return ++fAngleID;
  99. }
  100. int nextCoinID() {
  101. return ++fCoinID;
  102. }
  103. int nextContourID() {
  104. return ++fContourID;
  105. }
  106. int nextPtTID() {
  107. return ++fPtTID;
  108. }
  109. int nextSegmentID() {
  110. return ++fSegmentID;
  111. }
  112. int nextSpanID() {
  113. return ++fSpanID;
  114. }
  115. #endif
  116. SkOpPhase phase() const {
  117. return fPhase;
  118. }
  119. void resetAllocatedOpSpan() {
  120. fAllocatedOpSpan = false;
  121. }
  122. void setAllocatedOpSpan() {
  123. fAllocatedOpSpan = true;
  124. }
  125. void setCoincidence(SkOpCoincidence* coincidence) {
  126. fCoincidence = coincidence;
  127. }
  128. void setContourHead(SkOpContourHead* contourHead) {
  129. fContourHead = contourHead;
  130. }
  131. void setPhase(SkOpPhase phase) {
  132. if (SkOpPhase::kNoChange == phase) {
  133. return;
  134. }
  135. SkASSERT(fPhase != phase);
  136. fPhase = phase;
  137. }
  138. // called in very rare cases where angles are sorted incorrectly -- signfies op will fail
  139. void setWindingFailed() {
  140. fWindingFailed = true;
  141. }
  142. bool windingFailed() const {
  143. return fWindingFailed;
  144. }
  145. private:
  146. SkArenaAlloc* fAllocator;
  147. SkOpCoincidence* fCoincidence;
  148. SkOpContourHead* fContourHead;
  149. int fNested;
  150. bool fAllocatedOpSpan;
  151. bool fWindingFailed;
  152. SkOpPhase fPhase;
  153. #ifdef SK_DEBUG
  154. const char* fDebugTestName;
  155. void* fDebugReporter;
  156. int fAngleID;
  157. int fCoinID;
  158. int fContourID;
  159. int fPtTID;
  160. int fSegmentID;
  161. int fSpanID;
  162. bool fDebugSkipAssert;
  163. #endif
  164. #if DEBUG_T_SECT_LOOP_COUNT
  165. int fDebugLoopCount[3];
  166. SkPath::Verb fDebugWorstVerb[6];
  167. SkPoint fDebugWorstPts[24];
  168. float fDebugWorstWeight[6];
  169. #endif
  170. #if DEBUG_COIN
  171. SkPathOpsDebug::CoinDict fCoinChangedDict;
  172. SkPathOpsDebug::CoinDict fCoinVisitedDict;
  173. SkPathOpsDebug::CoinDictEntry fCoinDictEntry;
  174. const char* fPreviousFuncName;
  175. #endif
  176. #if DEBUG_COINCIDENCE
  177. bool fDebugCheckHealth;
  178. #endif
  179. };
  180. #ifdef SK_DEBUG
  181. #if DEBUG_COINCIDENCE
  182. #define SkOPASSERT(cond) SkASSERT((this->globalState() && \
  183. (this->globalState()->debugCheckHealth() || \
  184. this->globalState()->debugSkipAssert())) || (cond))
  185. #else
  186. #define SkOPASSERT(cond) SkASSERT((this->globalState() && \
  187. this->globalState()->debugSkipAssert()) || (cond))
  188. #endif
  189. #define SkOPOBJASSERT(obj, cond) SkASSERT((obj->globalState() && \
  190. obj->globalState()->debugSkipAssert()) || (cond))
  191. #else
  192. #define SkOPASSERT(cond)
  193. #define SkOPOBJASSERT(obj, cond)
  194. #endif
  195. // Use Almost Equal when comparing coordinates. Use epsilon to compare T values.
  196. bool AlmostEqualUlps(float a, float b);
  197. inline bool AlmostEqualUlps(double a, double b) {
  198. return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  199. }
  200. bool AlmostEqualUlpsNoNormalCheck(float a, float b);
  201. inline bool AlmostEqualUlpsNoNormalCheck(double a, double b) {
  202. return AlmostEqualUlpsNoNormalCheck(SkDoubleToScalar(a), SkDoubleToScalar(b));
  203. }
  204. bool AlmostEqualUlps_Pin(float a, float b);
  205. inline bool AlmostEqualUlps_Pin(double a, double b) {
  206. return AlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
  207. }
  208. // Use Almost Dequal when comparing should not special case denormalized values.
  209. bool AlmostDequalUlps(float a, float b);
  210. bool AlmostDequalUlps(double a, double b);
  211. bool NotAlmostEqualUlps(float a, float b);
  212. inline bool NotAlmostEqualUlps(double a, double b) {
  213. return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  214. }
  215. bool NotAlmostEqualUlps_Pin(float a, float b);
  216. inline bool NotAlmostEqualUlps_Pin(double a, double b) {
  217. return NotAlmostEqualUlps_Pin(SkDoubleToScalar(a), SkDoubleToScalar(b));
  218. }
  219. bool NotAlmostDequalUlps(float a, float b);
  220. inline bool NotAlmostDequalUlps(double a, double b) {
  221. return NotAlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  222. }
  223. // Use Almost Bequal when comparing coordinates in conjunction with between.
  224. bool AlmostBequalUlps(float a, float b);
  225. inline bool AlmostBequalUlps(double a, double b) {
  226. return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  227. }
  228. bool AlmostPequalUlps(float a, float b);
  229. inline bool AlmostPequalUlps(double a, double b) {
  230. return AlmostPequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  231. }
  232. bool RoughlyEqualUlps(float a, float b);
  233. inline bool RoughlyEqualUlps(double a, double b) {
  234. return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  235. }
  236. bool AlmostLessUlps(float a, float b);
  237. inline bool AlmostLessUlps(double a, double b) {
  238. return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  239. }
  240. bool AlmostLessOrEqualUlps(float a, float b);
  241. inline bool AlmostLessOrEqualUlps(double a, double b) {
  242. return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  243. }
  244. bool AlmostBetweenUlps(float a, float b, float c);
  245. inline bool AlmostBetweenUlps(double a, double b, double c) {
  246. return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
  247. }
  248. int UlpsDistance(float a, float b);
  249. inline int UlpsDistance(double a, double b) {
  250. return UlpsDistance(SkDoubleToScalar(a), SkDoubleToScalar(b));
  251. }
  252. // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23)
  253. // DBL_EPSILON == 2.22045e-16
  254. const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON;
  255. const double FLT_EPSILON_HALF = FLT_EPSILON / 2;
  256. const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2;
  257. const double FLT_EPSILON_ORDERABLE_ERR = FLT_EPSILON * 16;
  258. const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON;
  259. // Use a compile-time constant for FLT_EPSILON_SQRT to avoid initializers.
  260. // A 17 digit constant guarantees exact results.
  261. const double FLT_EPSILON_SQRT = 0.00034526697709225118; // sqrt(FLT_EPSILON);
  262. const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON;
  263. const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error
  264. const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
  265. const double ROUGH_EPSILON = FLT_EPSILON * 64;
  266. const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
  267. const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048;
  268. const double BUMP_EPSILON = FLT_EPSILON * 4096;
  269. const SkScalar INVERSE_NUMBER_RANGE = FLT_EPSILON_ORDERABLE_ERR;
  270. inline bool zero_or_one(double x) {
  271. return x == 0 || x == 1;
  272. }
  273. inline bool approximately_zero(double x) {
  274. return fabs(x) < FLT_EPSILON;
  275. }
  276. inline bool precisely_zero(double x) {
  277. return fabs(x) < DBL_EPSILON_ERR;
  278. }
  279. inline bool precisely_subdivide_zero(double x) {
  280. return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR;
  281. }
  282. inline bool approximately_zero(float x) {
  283. return fabs(x) < FLT_EPSILON;
  284. }
  285. inline bool approximately_zero_cubed(double x) {
  286. return fabs(x) < FLT_EPSILON_CUBED;
  287. }
  288. inline bool approximately_zero_half(double x) {
  289. return fabs(x) < FLT_EPSILON_HALF;
  290. }
  291. inline bool approximately_zero_double(double x) {
  292. return fabs(x) < FLT_EPSILON_DOUBLE;
  293. }
  294. inline bool approximately_zero_orderable(double x) {
  295. return fabs(x) < FLT_EPSILON_ORDERABLE_ERR;
  296. }
  297. inline bool approximately_zero_squared(double x) {
  298. return fabs(x) < FLT_EPSILON_SQUARED;
  299. }
  300. inline bool approximately_zero_sqrt(double x) {
  301. return fabs(x) < FLT_EPSILON_SQRT;
  302. }
  303. inline bool roughly_zero(double x) {
  304. return fabs(x) < ROUGH_EPSILON;
  305. }
  306. inline bool approximately_zero_inverse(double x) {
  307. return fabs(x) > FLT_EPSILON_INVERSE;
  308. }
  309. inline bool approximately_zero_when_compared_to(double x, double y) {
  310. return x == 0 || fabs(x) < fabs(y * FLT_EPSILON);
  311. }
  312. inline bool precisely_zero_when_compared_to(double x, double y) {
  313. return x == 0 || fabs(x) < fabs(y * DBL_EPSILON);
  314. }
  315. inline bool roughly_zero_when_compared_to(double x, double y) {
  316. return x == 0 || fabs(x) < fabs(y * ROUGH_EPSILON);
  317. }
  318. // Use this for comparing Ts in the range of 0 to 1. For general numbers (larger and smaller) use
  319. // AlmostEqualUlps instead.
  320. inline bool approximately_equal(double x, double y) {
  321. return approximately_zero(x - y);
  322. }
  323. inline bool precisely_equal(double x, double y) {
  324. return precisely_zero(x - y);
  325. }
  326. inline bool precisely_subdivide_equal(double x, double y) {
  327. return precisely_subdivide_zero(x - y);
  328. }
  329. inline bool approximately_equal_half(double x, double y) {
  330. return approximately_zero_half(x - y);
  331. }
  332. inline bool approximately_equal_double(double x, double y) {
  333. return approximately_zero_double(x - y);
  334. }
  335. inline bool approximately_equal_orderable(double x, double y) {
  336. return approximately_zero_orderable(x - y);
  337. }
  338. inline bool approximately_equal_squared(double x, double y) {
  339. return approximately_equal(x, y);
  340. }
  341. inline bool approximately_greater(double x, double y) {
  342. return x - FLT_EPSILON >= y;
  343. }
  344. inline bool approximately_greater_double(double x, double y) {
  345. return x - FLT_EPSILON_DOUBLE >= y;
  346. }
  347. inline bool approximately_greater_orderable(double x, double y) {
  348. return x - FLT_EPSILON_ORDERABLE_ERR >= y;
  349. }
  350. inline bool approximately_greater_or_equal(double x, double y) {
  351. return x + FLT_EPSILON > y;
  352. }
  353. inline bool approximately_greater_or_equal_double(double x, double y) {
  354. return x + FLT_EPSILON_DOUBLE > y;
  355. }
  356. inline bool approximately_greater_or_equal_orderable(double x, double y) {
  357. return x + FLT_EPSILON_ORDERABLE_ERR > y;
  358. }
  359. inline bool approximately_lesser(double x, double y) {
  360. return x + FLT_EPSILON <= y;
  361. }
  362. inline bool approximately_lesser_double(double x, double y) {
  363. return x + FLT_EPSILON_DOUBLE <= y;
  364. }
  365. inline bool approximately_lesser_orderable(double x, double y) {
  366. return x + FLT_EPSILON_ORDERABLE_ERR <= y;
  367. }
  368. inline bool approximately_lesser_or_equal(double x, double y) {
  369. return x - FLT_EPSILON < y;
  370. }
  371. inline bool approximately_lesser_or_equal_double(double x, double y) {
  372. return x - FLT_EPSILON_DOUBLE < y;
  373. }
  374. inline bool approximately_lesser_or_equal_orderable(double x, double y) {
  375. return x - FLT_EPSILON_ORDERABLE_ERR < y;
  376. }
  377. inline bool approximately_greater_than_one(double x) {
  378. return x > 1 - FLT_EPSILON;
  379. }
  380. inline bool precisely_greater_than_one(double x) {
  381. return x > 1 - DBL_EPSILON_ERR;
  382. }
  383. inline bool approximately_less_than_zero(double x) {
  384. return x < FLT_EPSILON;
  385. }
  386. inline bool precisely_less_than_zero(double x) {
  387. return x < DBL_EPSILON_ERR;
  388. }
  389. inline bool approximately_negative(double x) {
  390. return x < FLT_EPSILON;
  391. }
  392. inline bool approximately_negative_orderable(double x) {
  393. return x < FLT_EPSILON_ORDERABLE_ERR;
  394. }
  395. inline bool precisely_negative(double x) {
  396. return x < DBL_EPSILON_ERR;
  397. }
  398. inline bool approximately_one_or_less(double x) {
  399. return x < 1 + FLT_EPSILON;
  400. }
  401. inline bool approximately_one_or_less_double(double x) {
  402. return x < 1 + FLT_EPSILON_DOUBLE;
  403. }
  404. inline bool approximately_positive(double x) {
  405. return x > -FLT_EPSILON;
  406. }
  407. inline bool approximately_positive_squared(double x) {
  408. return x > -(FLT_EPSILON_SQUARED);
  409. }
  410. inline bool approximately_zero_or_more(double x) {
  411. return x > -FLT_EPSILON;
  412. }
  413. inline bool approximately_zero_or_more_double(double x) {
  414. return x > -FLT_EPSILON_DOUBLE;
  415. }
  416. inline bool approximately_between_orderable(double a, double b, double c) {
  417. return a <= c
  418. ? approximately_negative_orderable(a - b) && approximately_negative_orderable(b - c)
  419. : approximately_negative_orderable(b - a) && approximately_negative_orderable(c - b);
  420. }
  421. inline bool approximately_between(double a, double b, double c) {
  422. return a <= c ? approximately_negative(a - b) && approximately_negative(b - c)
  423. : approximately_negative(b - a) && approximately_negative(c - b);
  424. }
  425. inline bool precisely_between(double a, double b, double c) {
  426. return a <= c ? precisely_negative(a - b) && precisely_negative(b - c)
  427. : precisely_negative(b - a) && precisely_negative(c - b);
  428. }
  429. // returns true if (a <= b <= c) || (a >= b >= c)
  430. inline bool between(double a, double b, double c) {
  431. SkASSERT(((a <= b && b <= c) || (a >= b && b >= c)) == ((a - b) * (c - b) <= 0)
  432. || (precisely_zero(a) && precisely_zero(b) && precisely_zero(c)));
  433. return (a - b) * (c - b) <= 0;
  434. }
  435. inline bool roughly_equal(double x, double y) {
  436. return fabs(x - y) < ROUGH_EPSILON;
  437. }
  438. inline bool roughly_negative(double x) {
  439. return x < ROUGH_EPSILON;
  440. }
  441. inline bool roughly_between(double a, double b, double c) {
  442. return a <= c ? roughly_negative(a - b) && roughly_negative(b - c)
  443. : roughly_negative(b - a) && roughly_negative(c - b);
  444. }
  445. inline bool more_roughly_equal(double x, double y) {
  446. return fabs(x - y) < MORE_ROUGH_EPSILON;
  447. }
  448. struct SkDPoint;
  449. struct SkDVector;
  450. struct SkDLine;
  451. struct SkDQuad;
  452. struct SkDConic;
  453. struct SkDCubic;
  454. struct SkDRect;
  455. inline SkPath::Verb SkPathOpsPointsToVerb(int points) {
  456. int verb = (1 << points) >> 1;
  457. #ifdef SK_DEBUG
  458. switch (points) {
  459. case 0: SkASSERT(SkPath::kMove_Verb == verb); break;
  460. case 1: SkASSERT(SkPath::kLine_Verb == verb); break;
  461. case 2: SkASSERT(SkPath::kQuad_Verb == verb); break;
  462. case 3: SkASSERT(SkPath::kCubic_Verb == verb); break;
  463. default: SkDEBUGFAIL("should not be here");
  464. }
  465. #endif
  466. return (SkPath::Verb)verb;
  467. }
  468. inline int SkPathOpsVerbToPoints(SkPath::Verb verb) {
  469. int points = (int) verb - (((int) verb + 1) >> 2);
  470. #ifdef SK_DEBUG
  471. switch (verb) {
  472. case SkPath::kLine_Verb: SkASSERT(1 == points); break;
  473. case SkPath::kQuad_Verb: SkASSERT(2 == points); break;
  474. case SkPath::kConic_Verb: SkASSERT(2 == points); break;
  475. case SkPath::kCubic_Verb: SkASSERT(3 == points); break;
  476. default: SkDEBUGFAIL("should not get here");
  477. }
  478. #endif
  479. return points;
  480. }
  481. inline double SkDInterp(double A, double B, double t) {
  482. return A + (B - A) * t;
  483. }
  484. double SkDCubeRoot(double x);
  485. /* Returns -1 if negative, 0 if zero, 1 if positive
  486. */
  487. inline int SkDSign(double x) {
  488. return (x > 0) - (x < 0);
  489. }
  490. /* Returns 0 if negative, 1 if zero, 2 if positive
  491. */
  492. inline int SKDSide(double x) {
  493. return (x > 0) + (x >= 0);
  494. }
  495. /* Returns 1 if negative, 2 if zero, 4 if positive
  496. */
  497. inline int SkDSideBit(double x) {
  498. return 1 << SKDSide(x);
  499. }
  500. inline double SkPinT(double t) {
  501. return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
  502. }
  503. #endif