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 SkScalar SkPoint::Normalize(SkPoint* pt) { 91 SkScalar mag = SkPoint::Length(pt->fX, pt->fY); 92 if (mag > SK_ScalarNearlyZero) { 93 SkScalar scale = SkScalarInvert(mag); 94 pt->fX = SkScalarMul(pt->fX, scale); 95 pt->fY = SkScalarMul(pt->fY, scale); 96 return mag; 97 } 98 return 0; 99 } 100 101 #ifdef SK_SCALAR_IS_FLOAT 102 103 bool SkPoint::CanNormalize(SkScalar dx, SkScalar dy) { 104 float mag2 = dx * dx + dy * dy; 105 return mag2 > SK_ScalarNearlyZero * SK_ScalarNearlyZero; 106 } 107 108 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 109 return sk_float_sqrt(dx * dx + dy * dy); 110 } 111 112 bool SkPoint::setLength(float x, float y, float length) { 113 float mag2 = x * x + y * y; 114 if (mag2 > SK_ScalarNearlyZero * SK_ScalarNearlyZero) { 115 float scale = length / sk_float_sqrt(mag2); 116 fX = x * scale; 117 fY = y * scale; 118 return true; 119 } 120 return false; 121 } 122 123 #else 124 125 #include "Sk64.h" 126 127 bool SkPoint::CanNormalize(SkScalar dx, SkScalar dy) { 128 Sk64 tmp1, tmp2, tolSqr; 129 130 tmp1.setMul(dx, dx); 131 tmp2.setMul(dy, dy); 132 tmp1.add(tmp2); 133 134 // we want nearlyzero^2, but to compute it fast we want to just do a 135 // 32bit multiply, so we require that it not exceed 31bits. That is true 136 // if nearlyzero is <= 0xB504, which should be trivial, since usually 137 // nearlyzero is a very small fixed-point value. 138 SkASSERT(SK_ScalarNearlyZero <= 0xB504); 139 140 tolSqr.set(0, SK_ScalarNearlyZero * SK_ScalarNearlyZero); 141 return tmp1 > tolSqr; 142 } 143 144 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 145 Sk64 tmp1, tmp2; 146 147 tmp1.setMul(dx, dx); 148 tmp2.setMul(dy, dy); 149 tmp1.add(tmp2); 150 151 return tmp1.getSqrt(); 152 } 153 154 #ifdef SK_DEBUGx 155 static SkFixed fixlen(SkFixed x, SkFixed y) { 156 float fx = (float)x; 157 float fy = (float)y; 158 159 return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f); 160 } 161 #endif 162 163 static inline uint32_t squarefixed(unsigned x) { 164 x >>= 16; 165 return x*x; 166 } 167 168 #if 1 // Newton iter for setLength 169 170 static inline unsigned invsqrt_iter(unsigned V, unsigned U) { 171 unsigned x = V * U >> 14; 172 x = x * U >> 14; 173 x = (3 << 14) - x; 174 x = (U >> 1) * x >> 14; 175 return x; 176 } 177 178 static const uint16_t gInvSqrt14GuessTable[] = { 179 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061, 180 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780, 181 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235, 182 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99, 183 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee, 184 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc, 185 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830, 186 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce 187 }; 188 189 #define BUILD_INVSQRT_TABLEx 190 #ifdef BUILD_INVSQRT_TABLE 191 static void build_invsqrt14_guess_table() { 192 for (int i = 8; i <= 63; i++) { 193 unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25)); 194 printf("0x%x, ", x); 195 } 196 printf("\n"); 197 } 198 #endif 199 200 static unsigned fast_invsqrt(uint32_t x) { 201 #ifdef BUILD_INVSQRT_TABLE 202 unsigned top2 = x >> 25; 203 SkASSERT(top2 >= 8 && top2 <= 63); 204 205 static bool gOnce; 206 if (!gOnce) { 207 build_invsqrt14_guess_table(); 208 gOnce = true; 209 } 210 #endif 211 212 unsigned V = x >> 14; // make V .14 213 214 unsigned top = x >> 25; 215 SkASSERT(top >= 8 && top <= 63); 216 SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable)); 217 unsigned U = gInvSqrt14GuessTable[top - 8]; 218 219 U = invsqrt_iter(V, U); 220 return invsqrt_iter(V, U); 221 } 222 223 /* We "normalize" x,y to be .14 values (so we can square them and stay 32bits. 224 Then we Newton-iterate this in .14 space to compute the invser-sqrt, and 225 scale by it at the end. The .14 space means we can execute our iterations 226 and stay in 32bits as well, making the multiplies much cheaper than calling 227 SkFixedMul. 228 */ 229 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { 230 if (ox == 0) { 231 if (oy == 0) { 232 return false; 233 } 234 this->set(0, SkApplySign(length, SkExtractSign(oy))); 235 return true; 236 } 237 if (oy == 0) { 238 this->set(SkApplySign(length, SkExtractSign(ox)), 0); 239 return true; 240 } 241 242 unsigned x = SkAbs32(ox); 243 unsigned y = SkAbs32(oy); 244 int zeros = SkCLZ(x | y); 245 246 // make x,y 1.14 values so our fast sqr won't overflow 247 if (zeros > 17) { 248 x <<= zeros - 17; 249 y <<= zeros - 17; 250 } else { 251 x >>= 17 - zeros; 252 y >>= 17 - zeros; 253 } 254 SkASSERT((x | y) <= 0x7FFF); 255 256 unsigned invrt = fast_invsqrt(x*x + y*y); 257 258 x = x * invrt >> 12; 259 y = y * invrt >> 12; 260 261 if (length != SK_Fixed1) { 262 x = SkFixedMul(x, length); 263 y = SkFixedMul(y, length); 264 } 265 this->set(SkApplySign(x, SkExtractSign(ox)), 266 SkApplySign(y, SkExtractSign(oy))); 267 return true; 268 } 269 #else 270 /* 271 Normalize x,y, and then scale them by length. 272 273 The obvious way to do this would be the following: 274 S64 tmp1, tmp2; 275 tmp1.setMul(x,x); 276 tmp2.setMul(y,y); 277 tmp1.add(tmp2); 278 len = tmp1.getSqrt(); 279 x' = SkFixedDiv(x, len); 280 y' = SkFixedDiv(y, len); 281 This is fine, but slower than what we do below. 282 283 The present technique does not compute the starting length, but 284 rather fiddles with x,y iteratively, all the while checking its 285 magnitude^2 (avoiding a sqrt). 286 287 We normalize by first shifting x,y so that at least one of them 288 has bit 31 set (after taking the abs of them). 289 Then we loop, refining x,y by squaring them and comparing 290 against a very large 1.0 (1 << 28), and then adding or subtracting 291 a delta (which itself is reduced by half each time through the loop). 292 For speed we want the squaring to be with a simple integer mul. To keep 293 that from overflowing we shift our coordinates down until we are dealing 294 with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits) 295 When our square is close to 1.0, we shift x,y down into fixed range. 296 */ 297 bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { 298 if (ox == 0) { 299 if (oy == 0) 300 return false; 301 this->set(0, SkApplySign(length, SkExtractSign(oy))); 302 return true; 303 } 304 if (oy == 0) { 305 this->set(SkApplySign(length, SkExtractSign(ox)), 0); 306 return true; 307 } 308 309 SkFixed x = SkAbs32(ox); 310 SkFixed y = SkAbs32(oy); 311 312 // shift x,y so that the greater of them is 15bits (1.14 fixed point) 313 { 314 int shift = SkCLZ(x | y); 315 // make them .30 316 x <<= shift - 1; 317 y <<= shift - 1; 318 } 319 320 SkFixed dx = x; 321 SkFixed dy = y; 322 323 for (int i = 0; i < 17; i++) { 324 dx >>= 1; 325 dy >>= 1; 326 327 U32 len2 = squarefixed(x) + squarefixed(y); 328 if (len2 >> 28) { 329 x -= dx; 330 y -= dy; 331 } else { 332 x += dx; 333 y += dy; 334 } 335 } 336 x >>= 14; 337 y >>= 14; 338 339 #ifdef SK_DEBUGx // measure how far we are from unit-length 340 { 341 static int gMaxError; 342 static int gMaxDiff; 343 344 SkFixed len = fixlen(x, y); 345 int err = len - SK_Fixed1; 346 err = SkAbs32(err); 347 348 if (err > gMaxError) { 349 gMaxError = err; 350 SkDebugf("gMaxError %d\n", err); 351 } 352 353 float fx = SkAbs32(ox)/65536.0f; 354 float fy = SkAbs32(oy)/65536.0f; 355 float mag = sqrtf(fx*fx + fy*fy); 356 fx /= mag; 357 fy /= mag; 358 SkFixed xx = (int)floorf(fx * 65536 + 0.5f); 359 SkFixed yy = (int)floorf(fy * 65536 + 0.5f); 360 err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y)); 361 if (err > gMaxDiff) { 362 gMaxDiff = err; 363 SkDebugf("gMaxDiff %d\n", err); 364 } 365 } 366 #endif 367 368 x = SkApplySign(x, SkExtractSign(ox)); 369 y = SkApplySign(y, SkExtractSign(oy)); 370 if (length != SK_Fixed1) { 371 x = SkFixedMul(x, length); 372 y = SkFixedMul(y, length); 373 } 374 375 this->set(x, y); 376 return true; 377 } 378 #endif 379 380 #endif 381 382 /////////////////////////////////////////////////////////////////////////////// 383 384 SkScalar SkPoint::distanceToLineBetweenSqd(const SkPoint& a, 385 const SkPoint& b, 386 Side* side) const { 387 388 SkVector u = b - a; 389 SkVector v = *this - a; 390 391 SkScalar uLengthSqd = u.lengthSqd(); 392 SkScalar det = u.cross(v); 393 if (NULL != side) { 394 SkASSERT(-1 == SkPoint::kLeft_Side && 395 0 == SkPoint::kOn_Side && 396 1 == kRight_Side); 397 *side = (Side) SkScalarSignAsInt(det); 398 } 399 return SkScalarMulDiv(det, det, uLengthSqd); 400 } 401 402 SkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a, 403 const SkPoint& b) const { 404 // See comments to distanceToLineBetweenSqd. If the projection of c onto 405 // u is between a and b then this returns the same result as that 406 // function. Otherwise, it returns the distance to the closer of a and 407 // b. Let the projection of v onto u be v'. There are three cases: 408 // 1. v' points opposite to u. c is not between a and b and is closer 409 // to a than b. 410 // 2. v' points along u and has magnitude less than y. c is between 411 // a and b and the distance to the segment is the same as distance 412 // to the line ab. 413 // 3. v' points along u and has greater magnitude than u. c is not 414 // not between a and b and is closer to b than a. 415 // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're 416 // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise 417 // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to 418 // avoid a sqrt to compute |u|. 419 420 SkVector u = b - a; 421 SkVector v = *this - a; 422 423 SkScalar uLengthSqd = u.lengthSqd(); 424 SkScalar uDotV = SkPoint::DotProduct(u, v); 425 426 if (uDotV <= 0) { 427 return v.lengthSqd(); 428 } else if (uDotV > uLengthSqd) { 429 return b.distanceToSqd(*this); 430 } else { 431 SkScalar det = u.cross(v); 432 return SkScalarMulDiv(det, det, uLengthSqd); 433 } 434 } 435
