epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 2 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 3 | * Copyright 2008 The Android Open Source Project |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 4 | * |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 7 | */ |
| 8 | |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 9 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 10 | #include "SkPoint.h" |
| 11 | |
| 12 | void SkIPoint::rotateCW(SkIPoint* dst) const { |
| 13 | SkASSERT(dst); |
| 14 | |
| 15 | // use a tmp in case this == dst |
| 16 | int32_t tmp = fX; |
| 17 | dst->fX = -fY; |
| 18 | dst->fY = tmp; |
| 19 | } |
| 20 | |
| 21 | void SkIPoint::rotateCCW(SkIPoint* dst) const { |
| 22 | SkASSERT(dst); |
| 23 | |
| 24 | // use a tmp in case this == dst |
| 25 | int32_t tmp = fX; |
| 26 | dst->fX = fY; |
| 27 | dst->fY = -tmp; |
| 28 | } |
| 29 | |
| 30 | /////////////////////////////////////////////////////////////////////////////// |
| 31 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 32 | void SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) { |
| 33 | SkASSERT(stride >= sizeof(SkPoint)); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 34 | |
| 35 | ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l), |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 36 | SkIntToScalar(t)); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 37 | ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l), |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 38 | SkIntToScalar(b)); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 39 | ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r), |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 40 | SkIntToScalar(b)); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 41 | ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r), |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 42 | SkIntToScalar(t)); |
| 43 | } |
| 44 | |
| 45 | void SkPoint::setRectFan(SkScalar l, SkScalar t, SkScalar r, SkScalar b, |
| 46 | size_t stride) { |
| 47 | SkASSERT(stride >= sizeof(SkPoint)); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 48 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 49 | ((SkPoint*)((intptr_t)this + 0 * stride))->set(l, t); |
| 50 | ((SkPoint*)((intptr_t)this + 1 * stride))->set(l, b); |
| 51 | ((SkPoint*)((intptr_t)this + 2 * stride))->set(r, b); |
| 52 | ((SkPoint*)((intptr_t)this + 3 * stride))->set(r, t); |
| 53 | } |
| 54 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 55 | void SkPoint::rotateCW(SkPoint* dst) const { |
| 56 | SkASSERT(dst); |
| 57 | |
| 58 | // use a tmp in case this == dst |
| 59 | SkScalar tmp = fX; |
| 60 | dst->fX = -fY; |
| 61 | dst->fY = tmp; |
| 62 | } |
| 63 | |
| 64 | void SkPoint::rotateCCW(SkPoint* dst) const { |
| 65 | SkASSERT(dst); |
| 66 | |
| 67 | // use a tmp in case this == dst |
| 68 | SkScalar tmp = fX; |
| 69 | dst->fX = fY; |
| 70 | dst->fY = -tmp; |
| 71 | } |
| 72 | |
| 73 | void SkPoint::scale(SkScalar scale, SkPoint* dst) const { |
| 74 | SkASSERT(dst); |
| 75 | dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale)); |
| 76 | } |
| 77 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 78 | bool SkPoint::normalize() { |
| 79 | return this->setLength(fX, fY, SK_Scalar1); |
| 80 | } |
| 81 | |
| 82 | bool SkPoint::setNormalize(SkScalar x, SkScalar y) { |
| 83 | return this->setLength(x, y, SK_Scalar1); |
| 84 | } |
| 85 | |
| 86 | bool SkPoint::setLength(SkScalar length) { |
| 87 | return this->setLength(fX, fY, length); |
| 88 | } |
| 89 | |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 90 | #ifdef SK_SCALAR_IS_FLOAT |
| 91 | |
| 92 | // Returns the square of the Euclidian distance to (dx,dy). |
| 93 | static inline float getLengthSquared(float dx, float dy) { |
| 94 | return dx * dx + dy * dy; |
| 95 | } |
| 96 | |
| 97 | // Calculates the square of the Euclidian distance to (dx,dy) and stores it in |
| 98 | // *lengthSquared. Returns true if the distance is judged to be "nearly zero". |
| 99 | // |
| 100 | // This logic is encapsulated in a helper method to make it explicit that we |
| 101 | // always perform this check in the same manner, to avoid inconsistencies |
| 102 | // (see http://code.google.com/p/skia/issues/detail?id=560 ). |
| 103 | static inline bool isLengthNearlyZero(float dx, float dy, |
| 104 | float *lengthSquared) { |
| 105 | *lengthSquared = getLengthSquared(dx, dy); |
| 106 | return *lengthSquared <= (SK_ScalarNearlyZero * SK_ScalarNearlyZero); |
| 107 | } |
| 108 | |
epoger@google.com | 1fd56dc | 2011-06-15 18:04:58 +0000 | [diff] [blame] | 109 | SkScalar SkPoint::Normalize(SkPoint* pt) { |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 110 | float mag2; |
| 111 | if (!isLengthNearlyZero(pt->fX, pt->fY, &mag2)) { |
| 112 | float mag = sk_float_sqrt(mag2); |
caryclark@google.com | 803eceb | 2012-06-06 12:09:34 +0000 | [diff] [blame] | 113 | float scale = 1.0f / mag; |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 114 | pt->fX = pt->fX * scale; |
| 115 | pt->fY = pt->fY * scale; |
epoger@google.com | 1fd56dc | 2011-06-15 18:04:58 +0000 | [diff] [blame] | 116 | return mag; |
| 117 | } |
| 118 | return 0; |
| 119 | } |
| 120 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 121 | SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 122 | return sk_float_sqrt(getLengthSquared(dx, dy)); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 123 | } |
| 124 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 125 | bool SkPoint::setLength(float x, float y, float length) { |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 126 | float mag2; |
| 127 | if (!isLengthNearlyZero(x, y, &mag2)) { |
reed@google.com | 55b5f4b | 2011-09-07 12:23:41 +0000 | [diff] [blame] | 128 | float scale = length / sk_float_sqrt(mag2); |
| 129 | fX = x * scale; |
| 130 | fY = y * scale; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 131 | return true; |
| 132 | } |
| 133 | return false; |
| 134 | } |
| 135 | |
| 136 | #else |
| 137 | |
| 138 | #include "Sk64.h" |
| 139 | |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 140 | // Returns the square of the Euclidian distance to (dx,dy) in *result. |
| 141 | static inline void getLengthSquared(SkScalar dx, SkScalar dy, Sk64 *result) { |
| 142 | Sk64 dySqr; |
| 143 | |
| 144 | result->setMul(dx, dx); |
| 145 | dySqr.setMul(dy, dy); |
| 146 | result->add(dySqr); |
| 147 | } |
| 148 | |
| 149 | // Calculates the square of the Euclidian distance to (dx,dy) and stores it in |
| 150 | // *lengthSquared. Returns true if the distance is judged to be "nearly zero". |
| 151 | // |
| 152 | // This logic is encapsulated in a helper method to make it explicit that we |
| 153 | // always perform this check in the same manner, to avoid inconsistencies |
| 154 | // (see http://code.google.com/p/skia/issues/detail?id=560 ). |
| 155 | static inline bool isLengthNearlyZero(SkScalar dx, SkScalar dy, |
| 156 | Sk64 *lengthSquared) { |
| 157 | Sk64 tolSqr; |
| 158 | getLengthSquared(dx, dy, lengthSquared); |
reed@google.com | 55b5f4b | 2011-09-07 12:23:41 +0000 | [diff] [blame] | 159 | |
| 160 | // we want nearlyzero^2, but to compute it fast we want to just do a |
| 161 | // 32bit multiply, so we require that it not exceed 31bits. That is true |
| 162 | // if nearlyzero is <= 0xB504, which should be trivial, since usually |
| 163 | // nearlyzero is a very small fixed-point value. |
| 164 | SkASSERT(SK_ScalarNearlyZero <= 0xB504); |
| 165 | |
| 166 | tolSqr.set(0, SK_ScalarNearlyZero * SK_ScalarNearlyZero); |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 167 | return *lengthSquared <= tolSqr; |
| 168 | } |
| 169 | |
| 170 | SkScalar SkPoint::Normalize(SkPoint* pt) { |
| 171 | Sk64 mag2; |
| 172 | if (!isLengthNearlyZero(pt->fX, pt->fY, &mag2)) { |
| 173 | SkScalar mag = mag2.getSqrt(); |
| 174 | SkScalar scale = SkScalarInvert(mag); |
| 175 | pt->fX = SkScalarMul(pt->fX, scale); |
| 176 | pt->fY = SkScalarMul(pt->fY, scale); |
| 177 | return mag; |
| 178 | } |
| 179 | return 0; |
| 180 | } |
| 181 | |
| 182 | bool SkPoint::CanNormalize(SkScalar dx, SkScalar dy) { |
| 183 | Sk64 mag2_unused; |
| 184 | return !isLengthNearlyZero(dx, dy, &mag2_unused); |
reed@google.com | 55b5f4b | 2011-09-07 12:23:41 +0000 | [diff] [blame] | 185 | } |
| 186 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 187 | SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { |
epoger@google.com | 94fa43c | 2012-04-11 17:51:01 +0000 | [diff] [blame] | 188 | Sk64 tmp; |
| 189 | getLengthSquared(dx, dy, &tmp); |
| 190 | return tmp.getSqrt(); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 191 | } |
| 192 | |
| 193 | #ifdef SK_DEBUGx |
| 194 | static SkFixed fixlen(SkFixed x, SkFixed y) { |
| 195 | float fx = (float)x; |
| 196 | float fy = (float)y; |
| 197 | |
| 198 | return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f); |
| 199 | } |
| 200 | #endif |
| 201 | |
| 202 | static inline uint32_t squarefixed(unsigned x) { |
| 203 | x >>= 16; |
| 204 | return x*x; |
| 205 | } |
| 206 | |
| 207 | #if 1 // Newton iter for setLength |
| 208 | |
| 209 | static inline unsigned invsqrt_iter(unsigned V, unsigned U) { |
| 210 | unsigned x = V * U >> 14; |
| 211 | x = x * U >> 14; |
| 212 | x = (3 << 14) - x; |
| 213 | x = (U >> 1) * x >> 14; |
| 214 | return x; |
| 215 | } |
| 216 | |
| 217 | static const uint16_t gInvSqrt14GuessTable[] = { |
| 218 | 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061, |
| 219 | 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780, |
| 220 | 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235, |
| 221 | 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99, |
| 222 | 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee, |
| 223 | 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc, |
| 224 | 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830, |
| 225 | 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce |
| 226 | }; |
| 227 | |
| 228 | #define BUILD_INVSQRT_TABLEx |
| 229 | #ifdef BUILD_INVSQRT_TABLE |
| 230 | static void build_invsqrt14_guess_table() { |
| 231 | for (int i = 8; i <= 63; i++) { |
| 232 | unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25)); |
| 233 | printf("0x%x, ", x); |
| 234 | } |
| 235 | printf("\n"); |
| 236 | } |
| 237 | #endif |
| 238 | |
| 239 | static unsigned fast_invsqrt(uint32_t x) { |
| 240 | #ifdef BUILD_INVSQRT_TABLE |
| 241 | unsigned top2 = x >> 25; |
| 242 | SkASSERT(top2 >= 8 && top2 <= 63); |
| 243 | |
| 244 | static bool gOnce; |
| 245 | if (!gOnce) { |
| 246 | build_invsqrt14_guess_table(); |
| 247 | gOnce = true; |
| 248 | } |
| 249 | #endif |
| 250 | |
| 251 | unsigned V = x >> 14; // make V .14 |
| 252 | |
| 253 | unsigned top = x >> 25; |
| 254 | SkASSERT(top >= 8 && top <= 63); |
| 255 | SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable)); |
| 256 | unsigned U = gInvSqrt14GuessTable[top - 8]; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 257 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 258 | U = invsqrt_iter(V, U); |
| 259 | return invsqrt_iter(V, U); |
| 260 | } |
| 261 | |
| 262 | /* We "normalize" x,y to be .14 values (so we can square them and stay 32bits. |
| 263 | Then we Newton-iterate this in .14 space to compute the invser-sqrt, and |
| 264 | scale by it at the end. The .14 space means we can execute our iterations |
| 265 | and stay in 32bits as well, making the multiplies much cheaper than calling |
| 266 | SkFixedMul. |
| 267 | */ |
| 268 | bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { |
| 269 | if (ox == 0) { |
| 270 | if (oy == 0) { |
| 271 | return false; |
| 272 | } |
| 273 | this->set(0, SkApplySign(length, SkExtractSign(oy))); |
| 274 | return true; |
| 275 | } |
| 276 | if (oy == 0) { |
| 277 | this->set(SkApplySign(length, SkExtractSign(ox)), 0); |
| 278 | return true; |
| 279 | } |
| 280 | |
| 281 | unsigned x = SkAbs32(ox); |
| 282 | unsigned y = SkAbs32(oy); |
| 283 | int zeros = SkCLZ(x | y); |
| 284 | |
| 285 | // make x,y 1.14 values so our fast sqr won't overflow |
| 286 | if (zeros > 17) { |
| 287 | x <<= zeros - 17; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 288 | y <<= zeros - 17; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 289 | } else { |
| 290 | x >>= 17 - zeros; |
| 291 | y >>= 17 - zeros; |
| 292 | } |
| 293 | SkASSERT((x | y) <= 0x7FFF); |
| 294 | |
| 295 | unsigned invrt = fast_invsqrt(x*x + y*y); |
| 296 | |
| 297 | x = x * invrt >> 12; |
| 298 | y = y * invrt >> 12; |
| 299 | |
| 300 | if (length != SK_Fixed1) { |
| 301 | x = SkFixedMul(x, length); |
| 302 | y = SkFixedMul(y, length); |
| 303 | } |
| 304 | this->set(SkApplySign(x, SkExtractSign(ox)), |
| 305 | SkApplySign(y, SkExtractSign(oy))); |
| 306 | return true; |
| 307 | } |
| 308 | #else |
| 309 | /* |
| 310 | Normalize x,y, and then scale them by length. |
| 311 | |
| 312 | The obvious way to do this would be the following: |
| 313 | S64 tmp1, tmp2; |
| 314 | tmp1.setMul(x,x); |
| 315 | tmp2.setMul(y,y); |
| 316 | tmp1.add(tmp2); |
| 317 | len = tmp1.getSqrt(); |
| 318 | x' = SkFixedDiv(x, len); |
| 319 | y' = SkFixedDiv(y, len); |
| 320 | This is fine, but slower than what we do below. |
| 321 | |
| 322 | The present technique does not compute the starting length, but |
| 323 | rather fiddles with x,y iteratively, all the while checking its |
| 324 | magnitude^2 (avoiding a sqrt). |
| 325 | |
| 326 | We normalize by first shifting x,y so that at least one of them |
| 327 | has bit 31 set (after taking the abs of them). |
| 328 | Then we loop, refining x,y by squaring them and comparing |
| 329 | against a very large 1.0 (1 << 28), and then adding or subtracting |
| 330 | a delta (which itself is reduced by half each time through the loop). |
| 331 | For speed we want the squaring to be with a simple integer mul. To keep |
| 332 | that from overflowing we shift our coordinates down until we are dealing |
| 333 | with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits) |
| 334 | When our square is close to 1.0, we shift x,y down into fixed range. |
| 335 | */ |
| 336 | bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { |
| 337 | if (ox == 0) { |
| 338 | if (oy == 0) |
| 339 | return false; |
| 340 | this->set(0, SkApplySign(length, SkExtractSign(oy))); |
| 341 | return true; |
| 342 | } |
| 343 | if (oy == 0) { |
| 344 | this->set(SkApplySign(length, SkExtractSign(ox)), 0); |
| 345 | return true; |
| 346 | } |
| 347 | |
| 348 | SkFixed x = SkAbs32(ox); |
| 349 | SkFixed y = SkAbs32(oy); |
| 350 | |
| 351 | // shift x,y so that the greater of them is 15bits (1.14 fixed point) |
| 352 | { |
| 353 | int shift = SkCLZ(x | y); |
| 354 | // make them .30 |
| 355 | x <<= shift - 1; |
| 356 | y <<= shift - 1; |
| 357 | } |
| 358 | |
| 359 | SkFixed dx = x; |
| 360 | SkFixed dy = y; |
| 361 | |
| 362 | for (int i = 0; i < 17; i++) { |
| 363 | dx >>= 1; |
| 364 | dy >>= 1; |
| 365 | |
| 366 | U32 len2 = squarefixed(x) + squarefixed(y); |
| 367 | if (len2 >> 28) { |
| 368 | x -= dx; |
| 369 | y -= dy; |
| 370 | } else { |
| 371 | x += dx; |
| 372 | y += dy; |
| 373 | } |
| 374 | } |
| 375 | x >>= 14; |
| 376 | y >>= 14; |
| 377 | |
| 378 | #ifdef SK_DEBUGx // measure how far we are from unit-length |
| 379 | { |
| 380 | static int gMaxError; |
| 381 | static int gMaxDiff; |
| 382 | |
| 383 | SkFixed len = fixlen(x, y); |
| 384 | int err = len - SK_Fixed1; |
| 385 | err = SkAbs32(err); |
| 386 | |
| 387 | if (err > gMaxError) { |
| 388 | gMaxError = err; |
| 389 | SkDebugf("gMaxError %d\n", err); |
| 390 | } |
| 391 | |
| 392 | float fx = SkAbs32(ox)/65536.0f; |
| 393 | float fy = SkAbs32(oy)/65536.0f; |
| 394 | float mag = sqrtf(fx*fx + fy*fy); |
| 395 | fx /= mag; |
| 396 | fy /= mag; |
| 397 | SkFixed xx = (int)floorf(fx * 65536 + 0.5f); |
| 398 | SkFixed yy = (int)floorf(fy * 65536 + 0.5f); |
| 399 | err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y)); |
| 400 | if (err > gMaxDiff) { |
| 401 | gMaxDiff = err; |
| 402 | SkDebugf("gMaxDiff %d\n", err); |
| 403 | } |
| 404 | } |
| 405 | #endif |
| 406 | |
| 407 | x = SkApplySign(x, SkExtractSign(ox)); |
| 408 | y = SkApplySign(y, SkExtractSign(oy)); |
| 409 | if (length != SK_Fixed1) { |
| 410 | x = SkFixedMul(x, length); |
| 411 | y = SkFixedMul(y, length); |
| 412 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 413 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 414 | this->set(x, y); |
| 415 | return true; |
| 416 | } |
| 417 | #endif |
| 418 | |
| 419 | #endif |
| 420 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 421 | /////////////////////////////////////////////////////////////////////////////// |
| 422 | |
bsalomon@google.com | 647a804 | 2011-08-23 14:39:01 +0000 | [diff] [blame] | 423 | SkScalar SkPoint::distanceToLineBetweenSqd(const SkPoint& a, |
| 424 | const SkPoint& b, |
| 425 | Side* side) const { |
| 426 | |
| 427 | SkVector u = b - a; |
| 428 | SkVector v = *this - a; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 429 | |
bsalomon@google.com | 647a804 | 2011-08-23 14:39:01 +0000 | [diff] [blame] | 430 | SkScalar uLengthSqd = u.lengthSqd(); |
| 431 | SkScalar det = u.cross(v); |
| 432 | if (NULL != side) { |
| 433 | SkASSERT(-1 == SkPoint::kLeft_Side && |
| 434 | 0 == SkPoint::kOn_Side && |
| 435 | 1 == kRight_Side); |
| 436 | *side = (Side) SkScalarSignAsInt(det); |
| 437 | } |
| 438 | return SkScalarMulDiv(det, det, uLengthSqd); |
| 439 | } |
| 440 | |
| 441 | SkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a, |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 442 | const SkPoint& b) const { |
| 443 | // See comments to distanceToLineBetweenSqd. If the projection of c onto |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 444 | // u is between a and b then this returns the same result as that |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 445 | // function. Otherwise, it returns the distance to the closer of a and |
| 446 | // b. Let the projection of v onto u be v'. There are three cases: |
| 447 | // 1. v' points opposite to u. c is not between a and b and is closer |
| 448 | // to a than b. |
| 449 | // 2. v' points along u and has magnitude less than y. c is between |
| 450 | // a and b and the distance to the segment is the same as distance |
| 451 | // to the line ab. |
| 452 | // 3. v' points along u and has greater magnitude than u. c is not |
| 453 | // not between a and b and is closer to b than a. |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 454 | // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 455 | // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 456 | // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 457 | // avoid a sqrt to compute |u|. |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 458 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 459 | SkVector u = b - a; |
| 460 | SkVector v = *this - a; |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 461 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 462 | SkScalar uLengthSqd = u.lengthSqd(); |
| 463 | SkScalar uDotV = SkPoint::DotProduct(u, v); |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame^] | 464 | |
reed@google.com | 7744c20 | 2011-05-06 19:26:26 +0000 | [diff] [blame] | 465 | if (uDotV <= 0) { |
| 466 | return v.lengthSqd(); |
| 467 | } else if (uDotV > uLengthSqd) { |
| 468 | return b.distanceToSqd(*this); |
| 469 | } else { |
| 470 | SkScalar det = u.cross(v); |
| 471 | return SkScalarMulDiv(det, det, uLengthSqd); |
| 472 | } |
| 473 | } |