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