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 "SkMathPriv.h"
11#include "SkPoint.h"
12
13void SkIPoint::rotateCW(SkIPoint* dst) const {
14    SkASSERT(dst);
15
16    // use a tmp in case this == dst
17    int32_t tmp = fX;
18    dst->fX = -fY;
19    dst->fY = tmp;
20}
21
22void SkIPoint::rotateCCW(SkIPoint* dst) const {
23    SkASSERT(dst);
24
25    // use a tmp in case this == dst
26    int32_t tmp = fX;
27    dst->fX = fY;
28    dst->fY = -tmp;
29}
30
31///////////////////////////////////////////////////////////////////////////////
32
33void SkPoint::setIRectFan(int l, int t, int r, int b, size_t stride) {
34    SkASSERT(stride >= sizeof(SkPoint));
35
36    ((SkPoint*)((intptr_t)this + 0 * stride))->set(SkIntToScalar(l),
37                                                   SkIntToScalar(t));
38    ((SkPoint*)((intptr_t)this + 1 * stride))->set(SkIntToScalar(l),
39                                                   SkIntToScalar(b));
40    ((SkPoint*)((intptr_t)this + 2 * stride))->set(SkIntToScalar(r),
41                                                   SkIntToScalar(b));
42    ((SkPoint*)((intptr_t)this + 3 * stride))->set(SkIntToScalar(r),
43                                                   SkIntToScalar(t));
44}
45
46void SkPoint::rotateCW(SkPoint* dst) const {
47    SkASSERT(dst);
48
49    // use a tmp in case this == dst
50    SkScalar tmp = fX;
51    dst->fX = -fY;
52    dst->fY = tmp;
53}
54
55void SkPoint::rotateCCW(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
64void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
65    SkASSERT(dst);
66    dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
67}
68
69bool SkPoint::normalize() {
70    return this->setLength(fX, fY, SK_Scalar1);
71}
72
73bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
74    return this->setLength(x, y, SK_Scalar1);
75}
76
77bool SkPoint::setLength(SkScalar length) {
78    return this->setLength(fX, fY, length);
79}
80
81// Returns the square of the Euclidian distance to (dx,dy).
82static inline float getLengthSquared(float dx, float dy) {
83    return dx * dx + dy * dy;
84}
85
86// Calculates the square of the Euclidian distance to (dx,dy) and stores it in
87// *lengthSquared.  Returns true if the distance is judged to be "nearly zero".
88//
89// This logic is encapsulated in a helper method to make it explicit that we
90// always perform this check in the same manner, to avoid inconsistencies
91// (see http://code.google.com/p/skia/issues/detail?id=560 ).
92static inline bool isLengthNearlyZero(float dx, float dy,
93                                      float *lengthSquared) {
94    *lengthSquared = getLengthSquared(dx, dy);
95    return *lengthSquared <= (SK_ScalarNearlyZero * SK_ScalarNearlyZero);
96}
97
98SkScalar SkPoint::Normalize(SkPoint* pt) {
99    float x = pt->fX;
100    float y = pt->fY;
101    float mag2;
102    if (isLengthNearlyZero(x, y, &mag2)) {
103        pt->set(0, 0);
104        return 0;
105    }
106
107    float mag, scale;
108    if (SkScalarIsFinite(mag2)) {
109        mag = sk_float_sqrt(mag2);
110        scale = 1 / mag;
111    } else {
112        // our mag2 step overflowed to infinity, so use doubles instead.
113        // much slower, but needed when x or y are very large, other wise we
114        // divide by inf. and return (0,0) vector.
115        double xx = x;
116        double yy = y;
117        double magmag = sqrt(xx * xx + yy * yy);
118        mag = (float)magmag;
119        // we perform the divide with the double magmag, to stay exactly the
120        // same as setLength. It would be faster to perform the divide with
121        // mag, but it is possible that mag has overflowed to inf. but still
122        // have a non-zero value for scale (thanks to denormalized numbers).
123        scale = (float)(1 / magmag);
124    }
125    pt->set(x * scale, y * scale);
126    return mag;
127}
128
129SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
130    float mag2 = dx * dx + dy * dy;
131    if (SkScalarIsFinite(mag2)) {
132        return sk_float_sqrt(mag2);
133    } else {
134        double xx = dx;
135        double yy = dy;
136        return (float)sqrt(xx * xx + yy * yy);
137    }
138}
139
140/*
141 *  We have to worry about 2 tricky conditions:
142 *  1. underflow of mag2 (compared against nearlyzero^2)
143 *  2. overflow of mag2 (compared w/ isfinite)
144 *
145 *  If we underflow, we return false. If we overflow, we compute again using
146 *  doubles, which is much slower (3x in a desktop test) but will not overflow.
147 */
148bool SkPoint::setLength(float x, float y, float length) {
149    float mag2;
150    if (isLengthNearlyZero(x, y, &mag2)) {
151        this->set(0, 0);
152        return false;
153    }
154
155    float scale;
156    if (SkScalarIsFinite(mag2)) {
157        scale = length / sk_float_sqrt(mag2);
158    } else {
159        // our mag2 step overflowed to infinity, so use doubles instead.
160        // much slower, but needed when x or y are very large, other wise we
161        // divide by inf. and return (0,0) vector.
162        double xx = x;
163        double yy = y;
164    #ifdef SK_DISCARD_DENORMALIZED_FOR_SPEED
165        // The iOS ARM processor discards small denormalized numbers to go faster.
166        // Casting this to a float would cause the scale to go to zero. Keeping it
167        // as a double for the multiply keeps the scale non-zero.
168        double dscale = length / sqrt(xx * xx + yy * yy);
169        fX = x * dscale;
170        fY = y * dscale;
171        return true;
172    #else
173        scale = (float)(length / sqrt(xx * xx + yy * yy));
174    #endif
175    }
176    fX = x * scale;
177    fY = y * scale;
178    return true;
179}
180
181bool SkPoint::setLengthFast(float length) {
182    return this->setLengthFast(fX, fY, length);
183}
184
185bool SkPoint::setLengthFast(float x, float y, float length) {
186    float mag2;
187    if (isLengthNearlyZero(x, y, &mag2)) {
188        this->set(0, 0);
189        return false;
190    }
191
192    float scale;
193    if (SkScalarIsFinite(mag2)) {
194        scale = length * sk_float_rsqrt(mag2);  // <--- this is the difference
195    } else {
196        // our mag2 step overflowed to infinity, so use doubles instead.
197        // much slower, but needed when x or y are very large, other wise we
198        // divide by inf. and return (0,0) vector.
199        double xx = x;
200        double yy = y;
201        scale = (float)(length / sqrt(xx * xx + yy * yy));
202    }
203    fX = x * scale;
204    fY = y * scale;
205    return true;
206}
207
208
209///////////////////////////////////////////////////////////////////////////////
210
211SkScalar SkPoint::distanceToLineBetweenSqd(const SkPoint& a,
212                                           const SkPoint& b,
213                                           Side* side) const {
214
215    SkVector u = b - a;
216    SkVector v = *this - a;
217
218    SkScalar uLengthSqd = u.lengthSqd();
219    SkScalar det = u.cross(v);
220    if (side) {
221        SkASSERT(-1 == SkPoint::kLeft_Side &&
222                  0 == SkPoint::kOn_Side &&
223                  1 == kRight_Side);
224        *side = (Side) SkScalarSignAsInt(det);
225    }
226    SkScalar temp = det / uLengthSqd;
227    temp *= det;
228    return temp;
229}
230
231SkScalar SkPoint::distanceToLineSegmentBetweenSqd(const SkPoint& a,
232                                                  const SkPoint& b) const {
233    // See comments to distanceToLineBetweenSqd. If the projection of c onto
234    // u is between a and b then this returns the same result as that
235    // function. Otherwise, it returns the distance to the closer of a and
236    // b. Let the projection of v onto u be v'.  There are three cases:
237    //    1. v' points opposite to u. c is not between a and b and is closer
238    //       to a than b.
239    //    2. v' points along u and has magnitude less than y. c is between
240    //       a and b and the distance to the segment is the same as distance
241    //       to the line ab.
242    //    3. v' points along u and has greater magnitude than u. c is not
243    //       not between a and b and is closer to b than a.
244    // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're
245    // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise
246    // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to
247    // avoid a sqrt to compute |u|.
248
249    SkVector u = b - a;
250    SkVector v = *this - a;
251
252    SkScalar uLengthSqd = u.lengthSqd();
253    SkScalar uDotV = SkPoint::DotProduct(u, v);
254
255    if (uDotV <= 0) {
256        return v.lengthSqd();
257    } else if (uDotV > uLengthSqd) {
258        return b.distanceToSqd(*this);
259    } else {
260        SkScalar det = u.cross(v);
261        SkScalar temp = det / uLengthSqd;
262        temp *= det;
263        return temp;
264    }
265}
266