1 2 /* 3 * Copyright 2008 The Android Open Source Project 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 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 32 void SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) { 33 SkASSERT(stride >= sizeof(SkPoint)); 34 35 ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l), 36 SkIntToScalar(t)); 37 ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l), 38 SkIntToScalar(b)); 39 ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r), 40 SkIntToScalar(b)); 41 ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r), 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)); 48 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 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 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 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 109 SkScalar SkPoint::Normalize(SkPoint* pt) { 110 float mag2; 111 if (!isLengthNearlyZero(pt->fX, pt->fY, &mag2)) { 112 float mag = sk_float_sqrt(mag2); 113 float scale = 1.0f / mag; 114 pt->fX = pt->fX * scale; 115 pt->fY = pt->fY * scale; 116 return mag; 117 } 118 return 0; 119 } 120 121 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 122 return sk_float_sqrt(getLengthSquared(dx, dy)); 123 } 124 125 bool SkPoint::setLength(float x, float y, float length) { 126 float mag2; 127 if (!isLengthNearlyZero(x, y, &mag2)) { 128 float scale = length / sk_float_sqrt(mag2); 129 fX = x * scale; 130 fY = y * scale; 131 return true; 132 } 133 return false; 134 } 135 136 #else 137 138 #include "Sk64.h" 139 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); 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); 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); 185 } 186 187 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 188 Sk64 tmp; 189 getLengthSquared(dx, dy, &tmp); 190 return tmp.getSqrt(); 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]; 257 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; 288 y <<= zeros - 17; 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 } 413 414 this->set(x, y); 415 return true; 416 } 417 #endif 418 419 #endif 420 421 /////////////////////////////////////////////////////////////////////////////// 422 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; 429 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, 442 const SkPoint& b) const { 443 // See comments to distanceToLineBetweenSqd. If the projection of c onto 444 // u is between a and b then this returns the same result as that 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. 454 // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're 455 // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise 456 // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to 457 // avoid a sqrt to compute |u|. 458 459 SkVector u = b - a; 460 SkVector v = *this - a; 461 462 SkScalar uLengthSqd = u.lengthSqd(); 463 SkScalar uDotV = SkPoint::DotProduct(u, v); 464 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 } 474