1/*
2 * Copyright 2008 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8
9#include "SkMathPriv.h"
10#include "SkPointPriv.h"
11
12#if 0
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#endif
31
32///////////////////////////////////////////////////////////////////////////////
33
34void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
35    SkASSERT(dst);
36    dst->set(fX * scale, fY * scale);
37}
38
39bool SkPoint::normalize() {
40    return this->setLength(fX, fY, SK_Scalar1);
41}
42
43bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
44    return this->setLength(x, y, SK_Scalar1);
45}
46
47bool SkPoint::setLength(SkScalar length) {
48    return this->setLength(fX, fY, length);
49}
50
51// Returns the square of the Euclidian distance to (dx,dy).
52static inline float getLengthSquared(float dx, float dy) {
53    return dx * dx + dy * dy;
54}
55
56// Calculates the square of the Euclidian distance to (dx,dy) and stores it in
57// *lengthSquared.  Returns true if the distance is judged to be "nearly zero".
58//
59// This logic is encapsulated in a helper method to make it explicit that we
60// always perform this check in the same manner, to avoid inconsistencies
61// (see http://code.google.com/p/skia/issues/detail?id=560 ).
62static inline bool is_length_nearly_zero(float dx, float dy,
63                                         float *lengthSquared) {
64    *lengthSquared = getLengthSquared(dx, dy);
65    return *lengthSquared <= (SK_ScalarNearlyZero * SK_ScalarNearlyZero);
66}
67
68SkScalar SkPoint::Normalize(SkPoint* pt) {
69    float x = pt->fX;
70    float y = pt->fY;
71    float mag2;
72    if (is_length_nearly_zero(x, y, &mag2)) {
73        pt->set(0, 0);
74        return 0;
75    }
76
77    float mag, scale;
78    if (SkScalarIsFinite(mag2)) {
79        mag = sk_float_sqrt(mag2);
80        scale = 1 / mag;
81    } else {
82        // our mag2 step overflowed to infinity, so use doubles instead.
83        // much slower, but needed when x or y are very large, other wise we
84        // divide by inf. and return (0,0) vector.
85        double xx = x;
86        double yy = y;
87        double magmag = sqrt(xx * xx + yy * yy);
88        mag = (float)magmag;
89        // we perform the divide with the double magmag, to stay exactly the
90        // same as setLength. It would be faster to perform the divide with
91        // mag, but it is possible that mag has overflowed to inf. but still
92        // have a non-zero value for scale (thanks to denormalized numbers).
93        scale = (float)(1 / magmag);
94    }
95    pt->set(x * scale, y * scale);
96    return mag;
97}
98
99SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
100    float mag2 = dx * dx + dy * dy;
101    if (SkScalarIsFinite(mag2)) {
102        return sk_float_sqrt(mag2);
103    } else {
104        double xx = dx;
105        double yy = dy;
106        return sk_double_to_float(sqrt(xx * xx + yy * yy));
107    }
108}
109
110/*
111 *  We have to worry about 2 tricky conditions:
112 *  1. underflow of mag2 (compared against nearlyzero^2)
113 *  2. overflow of mag2 (compared w/ isfinite)
114 *
115 *  If we underflow, we return false. If we overflow, we compute again using
116 *  doubles, which is much slower (3x in a desktop test) but will not overflow.
117 */
118bool SkPoint::setLength(float x, float y, float length) {
119    float mag2;
120    if (is_length_nearly_zero(x, y, &mag2)) {
121        this->set(0, 0);
122        return false;
123    }
124
125    float scale;
126    if (SkScalarIsFinite(mag2)) {
127        scale = length / sk_float_sqrt(mag2);
128    } else {
129        // our mag2 step overflowed to infinity, so use doubles instead.
130        // much slower, but needed when x or y are very large, other wise we
131        // divide by inf. and return (0,0) vector.
132        double xx = x;
133        double yy = y;
134    #ifdef SK_CPU_FLUSH_TO_ZERO
135        // The iOS ARM processor discards small denormalized numbers to go faster.
136        // Casting this to a float would cause the scale to go to zero. Keeping it
137        // as a double for the multiply keeps the scale non-zero.
138        double dscale = length / sqrt(xx * xx + yy * yy);
139        fX = x * dscale;
140        fY = y * dscale;
141        return true;
142    #else
143        scale = (float)(length / sqrt(xx * xx + yy * yy));
144    #endif
145    }
146    fX = x * scale;
147    fY = y * scale;
148    return true;
149}
150
151bool SkPointPriv::SetLengthFast(SkPoint* pt, float length) {
152    float mag2;
153    if (is_length_nearly_zero(pt->fX, pt->fY, &mag2)) {
154        pt->set(0, 0);
155        return false;
156    }
157
158    float scale;
159    if (SkScalarIsFinite(mag2)) {
160        scale = length * sk_float_rsqrt(mag2);  // <--- this is the difference
161    } else {
162        // our mag2 step overflowed to infinity, so use doubles instead.
163        // much slower, but needed when x or y are very large, other wise we
164        // divide by inf. and return (0,0) vector.
165        double xx = pt->fX;
166        double yy = pt->fY;
167        scale = (float)(length / sqrt(xx * xx + yy * yy));
168    }
169    pt->fX *= scale;
170    pt->fY *= scale;
171    return true;
172}
173
174
175///////////////////////////////////////////////////////////////////////////////
176
177SkScalar SkPointPriv::DistanceToLineBetweenSqd(const SkPoint& pt, const SkPoint& a,
178                                           const SkPoint& b,
179                                           Side* side) {
180
181    SkVector u = b - a;
182    SkVector v = pt - a;
183
184    SkScalar uLengthSqd = LengthSqd(u);
185    SkScalar det = u.cross(v);
186    if (side) {
187        SkASSERT(-1 == kLeft_Side &&
188                  0 == kOn_Side &&
189                  1 == kRight_Side);
190        *side = (Side) SkScalarSignAsInt(det);
191    }
192    SkScalar temp = det / uLengthSqd;
193    temp *= det;
194    return temp;
195}
196
197SkScalar SkPointPriv::DistanceToLineSegmentBetweenSqd(const SkPoint& pt, const SkPoint& a,
198                                                  const SkPoint& b) {
199    // See comments to distanceToLineBetweenSqd. If the projection of c onto
200    // u is between a and b then this returns the same result as that
201    // function. Otherwise, it returns the distance to the closer of a and
202    // b. Let the projection of v onto u be v'.  There are three cases:
203    //    1. v' points opposite to u. c is not between a and b and is closer
204    //       to a than b.
205    //    2. v' points along u and has magnitude less than y. c is between
206    //       a and b and the distance to the segment is the same as distance
207    //       to the line ab.
208    //    3. v' points along u and has greater magnitude than u. c is not
209    //       not between a and b and is closer to b than a.
210    // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're
211    // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise
212    // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to
213    // avoid a sqrt to compute |u|.
214
215    SkVector u = b - a;
216    SkVector v = pt - a;
217
218    SkScalar uLengthSqd = LengthSqd(u);
219    SkScalar uDotV = SkPoint::DotProduct(u, v);
220
221    if (uDotV <= 0) {
222        return LengthSqd(v);
223    } else if (uDotV > uLengthSqd) {
224        return DistanceToSqd(b, pt);
225    } else {
226        SkScalar det = u.cross(v);
227        SkScalar temp = det / uLengthSqd;
228        temp *= det;
229        return temp;
230    }
231}
232