SkPathOpsTypes.cpp 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255
  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. #include "include/private/SkFloatBits.h"
  8. #include "src/core/SkArenaAlloc.h"
  9. #include "src/pathops/SkOpCoincidence.h"
  10. #include "src/pathops/SkPathOpsTypes.h"
  11. static bool arguments_denormalized(float a, float b, int epsilon) {
  12. float denormalizedCheck = FLT_EPSILON * epsilon / 2;
  13. return fabsf(a) <= denormalizedCheck && fabsf(b) <= denormalizedCheck;
  14. }
  15. // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
  16. // FIXME: move to SkFloatBits.h
  17. static bool equal_ulps(float a, float b, int epsilon, int depsilon) {
  18. if (arguments_denormalized(a, b, depsilon)) {
  19. return true;
  20. }
  21. int aBits = SkFloatAs2sCompliment(a);
  22. int bBits = SkFloatAs2sCompliment(b);
  23. // Find the difference in ULPs.
  24. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  25. }
  26. static bool equal_ulps_no_normal_check(float a, float b, int epsilon, int depsilon) {
  27. int aBits = SkFloatAs2sCompliment(a);
  28. int bBits = SkFloatAs2sCompliment(b);
  29. // Find the difference in ULPs.
  30. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  31. }
  32. static bool equal_ulps_pin(float a, float b, int epsilon, int depsilon) {
  33. if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
  34. return false;
  35. }
  36. if (arguments_denormalized(a, b, depsilon)) {
  37. return true;
  38. }
  39. int aBits = SkFloatAs2sCompliment(a);
  40. int bBits = SkFloatAs2sCompliment(b);
  41. // Find the difference in ULPs.
  42. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  43. }
  44. static bool d_equal_ulps(float a, float b, int epsilon) {
  45. int aBits = SkFloatAs2sCompliment(a);
  46. int bBits = SkFloatAs2sCompliment(b);
  47. // Find the difference in ULPs.
  48. return aBits < bBits + epsilon && bBits < aBits + epsilon;
  49. }
  50. static bool not_equal_ulps(float a, float b, int epsilon) {
  51. if (arguments_denormalized(a, b, epsilon)) {
  52. return false;
  53. }
  54. int aBits = SkFloatAs2sCompliment(a);
  55. int bBits = SkFloatAs2sCompliment(b);
  56. // Find the difference in ULPs.
  57. return aBits >= bBits + epsilon || bBits >= aBits + epsilon;
  58. }
  59. static bool not_equal_ulps_pin(float a, float b, int epsilon) {
  60. if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
  61. return false;
  62. }
  63. if (arguments_denormalized(a, b, epsilon)) {
  64. return false;
  65. }
  66. int aBits = SkFloatAs2sCompliment(a);
  67. int bBits = SkFloatAs2sCompliment(b);
  68. // Find the difference in ULPs.
  69. return aBits >= bBits + epsilon || bBits >= aBits + epsilon;
  70. }
  71. static bool d_not_equal_ulps(float a, float b, int epsilon) {
  72. int aBits = SkFloatAs2sCompliment(a);
  73. int bBits = SkFloatAs2sCompliment(b);
  74. // Find the difference in ULPs.
  75. return aBits >= bBits + epsilon || bBits >= aBits + epsilon;
  76. }
  77. static bool less_ulps(float a, float b, int epsilon) {
  78. if (arguments_denormalized(a, b, epsilon)) {
  79. return a <= b - FLT_EPSILON * epsilon;
  80. }
  81. int aBits = SkFloatAs2sCompliment(a);
  82. int bBits = SkFloatAs2sCompliment(b);
  83. // Find the difference in ULPs.
  84. return aBits <= bBits - epsilon;
  85. }
  86. static bool less_or_equal_ulps(float a, float b, int epsilon) {
  87. if (arguments_denormalized(a, b, epsilon)) {
  88. return a < b + FLT_EPSILON * epsilon;
  89. }
  90. int aBits = SkFloatAs2sCompliment(a);
  91. int bBits = SkFloatAs2sCompliment(b);
  92. // Find the difference in ULPs.
  93. return aBits < bBits + epsilon;
  94. }
  95. // equality using the same error term as between
  96. bool AlmostBequalUlps(float a, float b) {
  97. const int UlpsEpsilon = 2;
  98. return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
  99. }
  100. bool AlmostPequalUlps(float a, float b) {
  101. const int UlpsEpsilon = 8;
  102. return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
  103. }
  104. bool AlmostDequalUlps(float a, float b) {
  105. const int UlpsEpsilon = 16;
  106. return d_equal_ulps(a, b, UlpsEpsilon);
  107. }
  108. bool AlmostDequalUlps(double a, double b) {
  109. if (fabs(a) < SK_ScalarMax && fabs(b) < SK_ScalarMax) {
  110. return AlmostDequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
  111. }
  112. return fabs(a - b) / SkTMax(fabs(a), fabs(b)) < FLT_EPSILON * 16;
  113. }
  114. bool AlmostEqualUlps(float a, float b) {
  115. const int UlpsEpsilon = 16;
  116. return equal_ulps(a, b, UlpsEpsilon, UlpsEpsilon);
  117. }
  118. bool AlmostEqualUlpsNoNormalCheck(float a, float b) {
  119. const int UlpsEpsilon = 16;
  120. return equal_ulps_no_normal_check(a, b, UlpsEpsilon, UlpsEpsilon);
  121. }
  122. bool AlmostEqualUlps_Pin(float a, float b) {
  123. const int UlpsEpsilon = 16;
  124. return equal_ulps_pin(a, b, UlpsEpsilon, UlpsEpsilon);
  125. }
  126. bool NotAlmostEqualUlps(float a, float b) {
  127. const int UlpsEpsilon = 16;
  128. return not_equal_ulps(a, b, UlpsEpsilon);
  129. }
  130. bool NotAlmostEqualUlps_Pin(float a, float b) {
  131. const int UlpsEpsilon = 16;
  132. return not_equal_ulps_pin(a, b, UlpsEpsilon);
  133. }
  134. bool NotAlmostDequalUlps(float a, float b) {
  135. const int UlpsEpsilon = 16;
  136. return d_not_equal_ulps(a, b, UlpsEpsilon);
  137. }
  138. bool RoughlyEqualUlps(float a, float b) {
  139. const int UlpsEpsilon = 256;
  140. const int DUlpsEpsilon = 1024;
  141. return equal_ulps(a, b, UlpsEpsilon, DUlpsEpsilon);
  142. }
  143. bool AlmostBetweenUlps(float a, float b, float c) {
  144. const int UlpsEpsilon = 2;
  145. return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon)
  146. : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon);
  147. }
  148. bool AlmostLessUlps(float a, float b) {
  149. const int UlpsEpsilon = 16;
  150. return less_ulps(a, b, UlpsEpsilon);
  151. }
  152. bool AlmostLessOrEqualUlps(float a, float b) {
  153. const int UlpsEpsilon = 16;
  154. return less_or_equal_ulps(a, b, UlpsEpsilon);
  155. }
  156. int UlpsDistance(float a, float b) {
  157. SkFloatIntUnion floatIntA, floatIntB;
  158. floatIntA.fFloat = a;
  159. floatIntB.fFloat = b;
  160. // Different signs means they do not match.
  161. if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
  162. // Check for equality to make sure +0 == -0
  163. return a == b ? 0 : SK_MaxS32;
  164. }
  165. // Find the difference in ULPs.
  166. return SkTAbs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
  167. }
  168. // cube root approximation using bit hack for 64-bit float
  169. // adapted from Kahan's cbrt
  170. static double cbrt_5d(double d) {
  171. const unsigned int B1 = 715094163;
  172. double t = 0.0;
  173. unsigned int* pt = (unsigned int*) &t;
  174. unsigned int* px = (unsigned int*) &d;
  175. pt[1] = px[1] / 3 + B1;
  176. return t;
  177. }
  178. // iterative cube root approximation using Halley's method (double)
  179. static double cbrta_halleyd(const double a, const double R) {
  180. const double a3 = a * a * a;
  181. const double b = a * (a3 + R + R) / (a3 + a3 + R);
  182. return b;
  183. }
  184. // cube root approximation using 3 iterations of Halley's method (double)
  185. static double halley_cbrt3d(double d) {
  186. double a = cbrt_5d(d);
  187. a = cbrta_halleyd(a, d);
  188. a = cbrta_halleyd(a, d);
  189. return cbrta_halleyd(a, d);
  190. }
  191. double SkDCubeRoot(double x) {
  192. if (approximately_zero_cubed(x)) {
  193. return 0;
  194. }
  195. double result = halley_cbrt3d(fabs(x));
  196. if (x < 0) {
  197. result = -result;
  198. }
  199. return result;
  200. }
  201. SkOpGlobalState::SkOpGlobalState(SkOpContourHead* head,
  202. SkArenaAlloc* allocator
  203. SkDEBUGPARAMS(bool debugSkipAssert)
  204. SkDEBUGPARAMS(const char* testName))
  205. : fAllocator(allocator)
  206. , fCoincidence(nullptr)
  207. , fContourHead(head)
  208. , fNested(0)
  209. , fWindingFailed(false)
  210. , fPhase(SkOpPhase::kIntersecting)
  211. SkDEBUGPARAMS(fDebugTestName(testName))
  212. SkDEBUGPARAMS(fAngleID(0))
  213. SkDEBUGPARAMS(fCoinID(0))
  214. SkDEBUGPARAMS(fContourID(0))
  215. SkDEBUGPARAMS(fPtTID(0))
  216. SkDEBUGPARAMS(fSegmentID(0))
  217. SkDEBUGPARAMS(fSpanID(0))
  218. SkDEBUGPARAMS(fDebugSkipAssert(debugSkipAssert)) {
  219. #if DEBUG_T_SECT_LOOP_COUNT
  220. debugResetLoopCounts();
  221. #endif
  222. #if DEBUG_COIN
  223. fPreviousFuncName = nullptr;
  224. #endif
  225. }