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
rotateCW(SkIPoint * dst) const13 void 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
rotateCCW(SkIPoint * dst) const22 void 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
setIRectFan(int l,int t,int r,int b,size_t stride)33 void 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
rotateCW(SkPoint * dst) const46 void 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
rotateCCW(SkPoint * dst) const55 void 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
scale(SkScalar scale,SkPoint * dst) const64 void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
65 SkASSERT(dst);
66 dst->set(SkScalarMul(fX, scale), SkScalarMul(fY, scale));
67 }
68
normalize()69 bool SkPoint::normalize() {
70 return this->setLength(fX, fY, SK_Scalar1);
71 }
72
setNormalize(SkScalar x,SkScalar y)73 bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
74 return this->setLength(x, y, SK_Scalar1);
75 }
76
setLength(SkScalar length)77 bool SkPoint::setLength(SkScalar length) {
78 return this->setLength(fX, fY, length);
79 }
80
81 // Returns the square of the Euclidian distance to (dx,dy).
getLengthSquared(float dx,float dy)82 static 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 ).
isLengthNearlyZero(float dx,float dy,float * lengthSquared)92 static inline bool isLengthNearlyZero(float dx, float dy,
93 float *lengthSquared) {
94 *lengthSquared = getLengthSquared(dx, dy);
95 return *lengthSquared <= (SK_ScalarNearlyZero * SK_ScalarNearlyZero);
96 }
97
Normalize(SkPoint * pt)98 SkScalar 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
Length(SkScalar dx,SkScalar dy)129 SkScalar 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 */
setLength(float x,float y,float length)148 bool 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
setLengthFast(float length)181 bool SkPoint::setLengthFast(float length) {
182 return this->setLengthFast(fX, fY, length);
183 }
184
setLengthFast(float x,float y,float length)185 bool 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
distanceToLineBetweenSqd(const SkPoint & a,const SkPoint & b,Side * side) const211 SkScalar 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
distanceToLineSegmentBetweenSqd(const SkPoint & a,const SkPoint & b) const231 SkScalar 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