10910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* 20910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Copyright (C) 2006-2008 The Android Open Source Project 30910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 40910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 50910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * you may not use this file except in compliance with the License. 60910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * You may obtain a copy of the License at 70910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 80910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 90910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * 100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * See the License for the specific language governing permissions and 140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project * limitations under the License. 150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project */ 160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "SkPoint.h" 180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkIPoint::rotateCW(SkIPoint* dst) const { 200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(dst); 210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // use a tmp in case this == dst 230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int32_t tmp = fX; 240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fX = -fY; 250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fY = tmp; 260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkIPoint::rotateCCW(SkIPoint* dst) const { 290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(dst); 300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // use a tmp in case this == dst 320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int32_t tmp = fX; 330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fX = fY; 340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fY = -tmp; 350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/////////////////////////////////////////////////////////////////////////////// 380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) { 4035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(stride >= sizeof(SkPoint)); 4135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 4235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l), 4335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkIntToScalar(t)); 4435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l), 4535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkIntToScalar(b)); 4635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r), 4735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkIntToScalar(b)); 4835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r), 4935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkIntToScalar(t)); 5035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 5135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 5235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenbergervoid SkPoint::setRectFan(SkScalar l, SkScalar t, SkScalar r, SkScalar b, 5335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger size_t stride) { 5435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkASSERT(stride >= sizeof(SkPoint)); 5535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 5635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 0 * stride))->set(l, t); 5735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 1 * stride))->set(l, b); 5835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 2 * stride))->set(r, b); 5935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger ((SkPoint*)((intptr_t)this + 3 * stride))->set(r, t); 6035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 6135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::rotateCW(SkPoint* dst) const { 630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(dst); 640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // use a tmp in case this == dst 660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkScalar tmp = fX; 670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fX = -fY; 680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fY = tmp; 690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::rotateCCW(SkPoint* dst) const { 720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(dst); 730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // use a tmp in case this == dst 750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkScalar tmp = fX; 760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fX = fY; 770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->fY = -tmp; 780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectvoid SkPoint::scale(SkScalar scale, SkPoint* dst) const { 810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(dst); 820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale)); 830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define kNearlyZero (SK_Scalar1 / 8092) 860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::normalize() { 880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return this->setLength(fX, fY, SK_Scalar1); 890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setNormalize(SkScalar x, SkScalar y) { 920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return this->setLength(x, y, SK_Scalar1); 930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkScalar length) { 960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return this->setLength(fX, fY, length); 970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_SCALAR_IS_FLOAT 1000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 1020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return sk_float_sqrt(dx * dx + dy * dy); 1030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 10575c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike ReedSkScalar SkPoint::Normalize(SkPoint* pt) { 10675c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed float mag = SkPoint::Length(pt->fX, pt->fY); 10775c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed if (mag > kNearlyZero) { 10875c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed float scale = 1 / mag; 10975c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed pt->fX *= scale; 11075c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed pt->fY *= scale; 11175c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed return mag; 11275c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed } 11375c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed return 0; 11475c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed} 11575c8af293816b94cd8fd9a3d9b3a4d6e052dedfeMike Reed 1160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(float x, float y, float length) { 1170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float mag = sk_float_sqrt(x * x + y * y); 1180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (mag > kNearlyZero) { 1190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project length /= mag; 1200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fX = x * length; 1210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fY = y * length; 1220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 1230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return false; 1250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#else 1280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#include "Sk64.h" 1300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source ProjectSkScalar SkPoint::Length(SkScalar dx, SkScalar dy) { 1320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Sk64 tmp1, tmp2; 1330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp1.setMul(dx, dx); 1350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp2.setMul(dy, dy); 1360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp1.add(tmp2); 1370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return tmp1.getSqrt(); 1390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_DEBUGx 1420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic SkFixed fixlen(SkFixed x, SkFixed y) { 1430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float fx = (float)x; 1440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float fy = (float)y; 1450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f); 1470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 1490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic inline uint32_t squarefixed(unsigned x) { 1510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x >>= 16; 1520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return x*x; 1530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#if 1 // Newton iter for setLength 1560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic inline unsigned invsqrt_iter(unsigned V, unsigned U) { 1580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned x = V * U >> 14; 1590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = x * U >> 14; 1600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = (3 << 14) - x; 1610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = (U >> 1) * x >> 14; 1620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return x; 1630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic const uint16_t gInvSqrt14GuessTable[] = { 1660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061, 1670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780, 1680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235, 1690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99, 1700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee, 1710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc, 1720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830, 1730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce 1740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project}; 1750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#define BUILD_INVSQRT_TABLEx 1770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef BUILD_INVSQRT_TABLE 1780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic void build_invsqrt14_guess_table() { 1790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project for (int i = 8; i <= 63; i++) { 1800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25)); 1810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project printf("0x%x, ", x); 1820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project printf("\n"); 1840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 1850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 1860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectstatic unsigned fast_invsqrt(uint32_t x) { 1880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef BUILD_INVSQRT_TABLE 1890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned top2 = x >> 25; 1900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(top2 >= 8 && top2 <= 63); 1910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project static bool gOnce; 1930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (!gOnce) { 1940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project build_invsqrt14_guess_table(); 1950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project gOnce = true; 1960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 1970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 1980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 1990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned V = x >> 14; // make V .14 2000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned top = x >> 25; 2020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(top >= 8 && top <= 63); 2030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable)); 2040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned U = gInvSqrt14GuessTable[top - 8]; 2050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project U = invsqrt_iter(V, U); 2070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return invsqrt_iter(V, U); 2080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 2090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* We "normalize" x,y to be .14 values (so we can square them and stay 32bits. 2110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Then we Newton-iterate this in .14 space to compute the invser-sqrt, and 2120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project scale by it at the end. The .14 space means we can execute our iterations 2130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project and stay in 32bits as well, making the multiplies much cheaper than calling 2140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixedMul. 2150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/ 2160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { 2170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (ox == 0) { 2180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (oy == 0) { 2190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return false; 2200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(0, SkApplySign(length, SkExtractSign(oy))); 2220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 2230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (oy == 0) { 2250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(SkApplySign(length, SkExtractSign(ox)), 0); 2260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 2270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned x = SkAbs32(ox); 2300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned y = SkAbs32(oy); 2310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int zeros = SkCLZ(x | y); 2320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // make x,y 1.14 values so our fast sqr won't overflow 2340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (zeros > 17) { 2350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x <<= zeros - 17; 2360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y <<= zeros - 17; 2370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 2380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x >>= 17 - zeros; 2390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y >>= 17 - zeros; 2400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkASSERT((x | y) <= 0x7FFF); 2420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project unsigned invrt = fast_invsqrt(x*x + y*y); 2440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = x * invrt >> 12; 2460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y = y * invrt >> 12; 2470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (length != SK_Fixed1) { 2490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = SkFixedMul(x, length); 2500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y = SkFixedMul(y, length); 2510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(SkApplySign(x, SkExtractSign(ox)), 2530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkApplySign(y, SkExtractSign(oy))); 2540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 2550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 2560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#else 2570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project/* 2580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Normalize x,y, and then scale them by length. 2590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project The obvious way to do this would be the following: 2610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project S64 tmp1, tmp2; 2620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp1.setMul(x,x); 2630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp2.setMul(y,y); 2640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project tmp1.add(tmp2); 2650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project len = tmp1.getSqrt(); 2660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x' = SkFixedDiv(x, len); 2670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y' = SkFixedDiv(y, len); 2680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project This is fine, but slower than what we do below. 2690910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2700910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project The present technique does not compute the starting length, but 2710910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project rather fiddles with x,y iteratively, all the while checking its 2720910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project magnitude^2 (avoiding a sqrt). 2730910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2740910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project We normalize by first shifting x,y so that at least one of them 2750910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project has bit 31 set (after taking the abs of them). 2760910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project Then we loop, refining x,y by squaring them and comparing 2770910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project against a very large 1.0 (1 << 28), and then adding or subtracting 2780910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project a delta (which itself is reduced by half each time through the loop). 2790910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project For speed we want the squaring to be with a simple integer mul. To keep 2800910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project that from overflowing we shift our coordinates down until we are dealing 2810910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits) 2820910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project When our square is close to 1.0, we shift x,y down into fixed range. 2830910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project*/ 2840910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Projectbool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) { 2850910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (ox == 0) { 2860910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (oy == 0) 2870910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return false; 2880910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(0, SkApplySign(length, SkExtractSign(oy))); 2890910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 2900910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2910910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (oy == 0) { 2920910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(SkApplySign(length, SkExtractSign(ox)), 0); 2930910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 2940910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 2950910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2960910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed x = SkAbs32(ox); 2970910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed y = SkAbs32(oy); 2980910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 2990910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // shift x,y so that the greater of them is 15bits (1.14 fixed point) 3000910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 3010910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int shift = SkCLZ(x | y); 3020910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project // make them .30 3030910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x <<= shift - 1; 3040910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y <<= shift - 1; 3050910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3060910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3070910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed dx = x; 3080910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed dy = y; 3090910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3100910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project for (int i = 0; i < 17; i++) { 3110910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dx >>= 1; 3120910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project dy >>= 1; 3130910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3140910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project U32 len2 = squarefixed(x) + squarefixed(y); 3150910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (len2 >> 28) { 3160910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x -= dx; 3170910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y -= dy; 3180910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } else { 3190910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x += dx; 3200910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y += dy; 3210910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3220910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3230910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x >>= 14; 3240910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y >>= 14; 3250910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3260910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#ifdef SK_DEBUGx // measure how far we are from unit-length 3270910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project { 3280910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project static int gMaxError; 3290910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project static int gMaxDiff; 3300910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3310910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed len = fixlen(x, y); 3320910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project int err = len - SK_Fixed1; 3330910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project err = SkAbs32(err); 3340910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3350910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (err > gMaxError) { 3360910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project gMaxError = err; 3370910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkDebugf("gMaxError %d\n", err); 3380910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3390910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3400910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float fx = SkAbs32(ox)/65536.0f; 3410910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float fy = SkAbs32(oy)/65536.0f; 3420910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project float mag = sqrtf(fx*fx + fy*fy); 3430910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fx /= mag; 3440910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project fy /= mag; 3450910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed xx = (int)floorf(fx * 65536 + 0.5f); 3460910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkFixed yy = (int)floorf(fy * 65536 + 0.5f); 3470910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y)); 3480910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (err > gMaxDiff) { 3490910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project gMaxDiff = err; 3500910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project SkDebugf("gMaxDiff %d\n", err); 3510910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3520910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3530910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 3540910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3550910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = SkApplySign(x, SkExtractSign(ox)); 3560910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y = SkApplySign(y, SkExtractSign(oy)); 3570910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project if (length != SK_Fixed1) { 3580910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project x = SkFixedMul(x, length); 3590910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project y = SkFixedMul(y, length); 3600910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project } 3610910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3620910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project this->set(x, y); 3630910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project return true; 3640910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project} 3650910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 3660910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 3670910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project#endif 3680910916c0f7b951ee55c4b7c6358295b9bca0565The Android Open Source Project 36935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger/////////////////////////////////////////////////////////////////////////////// 37035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 37135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek SollenbergerSkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a, 37235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger const SkPoint& b) const { 37335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // See comments to distanceToLineBetweenSqd. If the projection of c onto 37435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // u is between a and b then this returns the same result as that 37535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // function. Otherwise, it returns the distance to the closer of a and 37635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // b. Let the projection of v onto u be v'. There are three cases: 37735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // 1. v' points opposite to u. c is not between a and b and is closer 37835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // to a than b. 37935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // 2. v' points along u and has magnitude less than y. c is between 38035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // a and b and the distance to the segment is the same as distance 38135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // to the line ab. 38235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // 3. v' points along u and has greater magnitude than u. c is not 38335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // not between a and b and is closer to b than a. 38435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're 38535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise 38635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to 38735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger // avoid a sqrt to compute |u|. 38835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 38935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkVector u = b - a; 39035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkVector v = *this - a; 39135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 39235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkScalar uLengthSqd = u.lengthSqd(); 39335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkScalar uDotV = SkPoint::DotProduct(u, v); 39435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 39535e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger if (uDotV <= 0) { 39635e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return v.lengthSqd(); 39735e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else if (uDotV > uLengthSqd) { 39835e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return b.distanceToSqd(*this); 39935e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } else { 40035e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger SkScalar det = u.cross(v); 40135e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger return SkScalarMulDiv(det, det, uLengthSqd); 40235e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger } 40335e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger} 40435e2e62b55598210f6999fc2ea26ff8f41446ffeDerek Sollenberger 405