SkPoint.cpp revision 8a1c16ff38322f0210116fa7293eb8817c7e477e 
1/*
2 * Copyright (C) 2006-2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "SkPoint.h"
18
19void SkIPoint::rotateCW(SkIPoint* dst) const {
20    SkASSERT(dst);
21
22    // use a tmp in case this == dst
23    int32_t tmp = fX;
24    dst->fX = -fY;
25    dst->fY = tmp;
26}
27
28void SkIPoint::rotateCCW(SkIPoint* dst) const {
29    SkASSERT(dst);
30
31    // use a tmp in case this == dst
32    int32_t tmp = fX;
33    dst->fX = fY;
34    dst->fY = -tmp;
35}
36
37///////////////////////////////////////////////////////////////////////////////
38
39void SkPoint::rotateCW(SkPoint* dst) const {
40    SkASSERT(dst);
41
42    // use a tmp in case this == dst
43    SkScalar tmp = fX;
44    dst->fX = -fY;
45    dst->fY = tmp;
46}
47
48void SkPoint::rotateCCW(SkPoint* dst) const {
49    SkASSERT(dst);
50
51    // use a tmp in case this == dst
52    SkScalar tmp = fX;
53    dst->fX = fY;
54    dst->fY = -tmp;
55}
56
57void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
58    SkASSERT(dst);
59    dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
60}
61
62#define kNearlyZero     (SK_Scalar1 / 8092)
63
64bool SkPoint::normalize() {
65    return this->setLength(fX, fY, SK_Scalar1);
66}
67
68bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
69    return this->setLength(x, y, SK_Scalar1);
70}
71
72bool SkPoint::setLength(SkScalar length) {
73    return this->setLength(fX, fY, length);
74}
75
76#ifdef SK_SCALAR_IS_FLOAT
77
78SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
79    return sk_float_sqrt(dx * dx + dy * dy);
80}
81
82bool SkPoint::setLength(float x, float y, float length) {
83    float mag = sk_float_sqrt(x * x + y * y);
84    if (mag > kNearlyZero) {
85        length /= mag;
86        fX = x * length;
87        fY = y * length;
88        return true;
89    }
90    return false;
91}
92
93#else
94
95#include "Sk64.h"
96
97SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
98    Sk64    tmp1, tmp2;
99
100    tmp1.setMul(dx, dx);
101    tmp2.setMul(dy, dy);
102    tmp1.add(tmp2);
103
104    return tmp1.getSqrt();
105}
106
107#ifdef SK_DEBUGx
108static SkFixed fixlen(SkFixed x, SkFixed y) {
109    float fx = (float)x;
110    float fy = (float)y;
111
112    return (int)floorf(sqrtf(fx*fx + fy*fy) + 0.5f);
113}
114#endif
115
116static inline uint32_t squarefixed(unsigned x) {
117    x >>= 16;
118    return x*x;
119}
120
121#if 1   // Newton iter for setLength
122
123static inline unsigned invsqrt_iter(unsigned V, unsigned U) {
124    unsigned x = V * U >> 14;
125    x = x * U >> 14;
126    x = (3 << 14) - x;
127    x = (U >> 1) * x >> 14;
128    return x;
129}
130
131static const uint16_t gInvSqrt14GuessTable[] = {
132    0x4000, 0x3c57, 0x393e, 0x3695, 0x3441, 0x3235, 0x3061,
133    0x2ebd, 0x2d41, 0x2be7, 0x2aaa, 0x2987, 0x287a, 0x2780,
134    0x2698, 0x25be, 0x24f3, 0x2434, 0x2380, 0x22d6, 0x2235,
135    0x219d, 0x210c, 0x2083, 0x2000, 0x1f82, 0x1f0b, 0x1e99,
136    0x1e2b, 0x1dc2, 0x1d5d, 0x1cfc, 0x1c9f, 0x1c45, 0x1bee,
137    0x1b9b, 0x1b4a, 0x1afc, 0x1ab0, 0x1a67, 0x1a20, 0x19dc,
138    0x1999, 0x1959, 0x191a, 0x18dd, 0x18a2, 0x1868, 0x1830,
139    0x17fa, 0x17c4, 0x1791, 0x175e, 0x172d, 0x16fd, 0x16ce
140};
141
142#define BUILD_INVSQRT_TABLEx
143#ifdef BUILD_INVSQRT_TABLE
144static void build_invsqrt14_guess_table() {
145    for (int i = 8; i <= 63; i++) {
146        unsigned x = SkToU16((1 << 28) / SkSqrt32(i << 25));
147        printf("0x%x, ", x);
148    }
149    printf("\n");
150}
151#endif
152
153static unsigned fast_invsqrt(uint32_t x) {
154#ifdef BUILD_INVSQRT_TABLE
155    unsigned top2 = x >> 25;
156    SkASSERT(top2 >= 8 && top2 <= 63);
157
158    static bool gOnce;
159    if (!gOnce) {
160        build_invsqrt14_guess_table();
161        gOnce = true;
162    }
163#endif
164
165    unsigned V = x >> 14;   // make V .14
166
167    unsigned top = x >> 25;
168    SkASSERT(top >= 8 && top <= 63);
169    SkASSERT(top - 8 < SK_ARRAY_COUNT(gInvSqrt14GuessTable));
170    unsigned U = gInvSqrt14GuessTable[top - 8];
171
172    U = invsqrt_iter(V, U);
173    return invsqrt_iter(V, U);
174}
175
176/*  We "normalize" x,y to be .14 values (so we can square them and stay 32bits.
177    Then we Newton-iterate this in .14 space to compute the invser-sqrt, and
178    scale by it at the end. The .14 space means we can execute our iterations
179    and stay in 32bits as well, making the multiplies much cheaper than calling
180    SkFixedMul.
181*/
182bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
183    if (ox == 0) {
184        if (oy == 0) {
185            return false;
186        }
187        this->set(0, SkApplySign(length, SkExtractSign(oy)));
188        return true;
189    }
190    if (oy == 0) {
191        this->set(SkApplySign(length, SkExtractSign(ox)), 0);
192        return true;
193    }
194
195    unsigned x = SkAbs32(ox);
196    unsigned y = SkAbs32(oy);
197    int zeros = SkCLZ(x | y);
198
199    // make x,y 1.14 values so our fast sqr won't overflow
200    if (zeros > 17) {
201        x <<= zeros - 17;
202        y <<= zeros - 17;
203    } else {
204        x >>= 17 - zeros;
205        y >>= 17 - zeros;
206    }
207    SkASSERT((x | y) <= 0x7FFF);
208
209    unsigned invrt = fast_invsqrt(x*x + y*y);
210
211    x = x * invrt >> 12;
212    y = y * invrt >> 12;
213
214    if (length != SK_Fixed1) {
215        x = SkFixedMul(x, length);
216        y = SkFixedMul(y, length);
217    }
218    this->set(SkApplySign(x, SkExtractSign(ox)),
219              SkApplySign(y, SkExtractSign(oy)));
220    return true;
221}
222#else
223/*
224    Normalize x,y, and then scale them by length.
225
226    The obvious way to do this would be the following:
227        S64 tmp1, tmp2;
228        tmp1.setMul(x,x);
229        tmp2.setMul(y,y);
230        tmp1.add(tmp2);
231        len = tmp1.getSqrt();
232        x' = SkFixedDiv(x, len);
233        y' = SkFixedDiv(y, len);
234    This is fine, but slower than what we do below.
235
236    The present technique does not compute the starting length, but
237    rather fiddles with x,y iteratively, all the while checking its
238    magnitude^2 (avoiding a sqrt).
239
240    We normalize by first shifting x,y so that at least one of them
241    has bit 31 set (after taking the abs of them).
242    Then we loop, refining x,y by squaring them and comparing
243    against a very large 1.0 (1 << 28), and then adding or subtracting
244    a delta (which itself is reduced by half each time through the loop).
245    For speed we want the squaring to be with a simple integer mul. To keep
246    that from overflowing we shift our coordinates down until we are dealing
247    with at most 15 bits (2^15-1)^2 * 2 says withing 32 bits)
248    When our square is close to 1.0, we shift x,y down into fixed range.
249*/
250bool SkPoint::setLength(SkFixed ox, SkFixed oy, SkFixed length) {
251    if (ox == 0) {
252        if (oy == 0)
253            return false;
254        this->set(0, SkApplySign(length, SkExtractSign(oy)));
255        return true;
256    }
257    if (oy == 0) {
258        this->set(SkApplySign(length, SkExtractSign(ox)), 0);
259        return true;
260    }
261
262    SkFixed x = SkAbs32(ox);
263    SkFixed y = SkAbs32(oy);
264
265    // shift x,y so that the greater of them is 15bits (1.14 fixed point)
266    {
267        int shift = SkCLZ(x | y);
268        // make them .30
269        x <<= shift - 1;
270        y <<= shift - 1;
271    }
272
273    SkFixed dx = x;
274    SkFixed dy = y;
275
276    for (int i = 0; i < 17; i++) {
277        dx >>= 1;
278        dy >>= 1;
279
280        U32 len2 = squarefixed(x) + squarefixed(y);
281        if (len2 >> 28) {
282            x -= dx;
283            y -= dy;
284        } else {
285            x += dx;
286            y += dy;
287        }
288    }
289    x >>= 14;
290    y >>= 14;
291
292#ifdef SK_DEBUGx    // measure how far we are from unit-length
293    {
294        static int gMaxError;
295        static int gMaxDiff;
296
297        SkFixed len = fixlen(x, y);
298        int err = len - SK_Fixed1;
299        err = SkAbs32(err);
300
301        if (err > gMaxError) {
302            gMaxError = err;
303            SkDebugf("gMaxError %d\n", err);
304        }
305
306        float fx = SkAbs32(ox)/65536.0f;
307        float fy = SkAbs32(oy)/65536.0f;
308        float mag = sqrtf(fx*fx + fy*fy);
309        fx /= mag;
310        fy /= mag;
311        SkFixed xx = (int)floorf(fx * 65536 + 0.5f);
312        SkFixed yy = (int)floorf(fy * 65536 + 0.5f);
313        err = SkMax32(SkAbs32(xx-x), SkAbs32(yy-y));
314        if (err > gMaxDiff) {
315            gMaxDiff = err;
316            SkDebugf("gMaxDiff %d\n", err);
317        }
318    }
319#endif
320
321    x = SkApplySign(x, SkExtractSign(ox));
322    y = SkApplySign(y, SkExtractSign(oy));
323    if (length != SK_Fixed1) {
324        x = SkFixedMul(x, length);
325        y = SkFixedMul(y, length);
326    }
327
328    this->set(x, y);
329    return true;
330}
331#endif
332
333#endif
334
335