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