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