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 #include "SkMathPriv.h"
9 #include "SkPointPriv.h"
10
11 ///////////////////////////////////////////////////////////////////////////////
12
scale(SkScalar scale,SkPoint * dst) const13 void SkPoint::scale(SkScalar scale, SkPoint* dst) const {
14 SkASSERT(dst);
15 dst->set(fX * scale, fY * scale);
16 }
17
normalize()18 bool SkPoint::normalize() {
19 return this->setLength(fX, fY, SK_Scalar1);
20 }
21
setNormalize(SkScalar x,SkScalar y)22 bool SkPoint::setNormalize(SkScalar x, SkScalar y) {
23 return this->setLength(x, y, SK_Scalar1);
24 }
25
setLength(SkScalar length)26 bool SkPoint::setLength(SkScalar length) {
27 return this->setLength(fX, fY, length);
28 }
29
30 /*
31 * We have to worry about 2 tricky conditions:
32 * 1. underflow of mag2 (compared against nearlyzero^2)
33 * 2. overflow of mag2 (compared w/ isfinite)
34 *
35 * If we underflow, we return false. If we overflow, we compute again using
36 * doubles, which is much slower (3x in a desktop test) but will not overflow.
37 */
set_point_length(SkPoint * pt,float x,float y,float length,float * orig_length=nullptr)38 template <bool use_rsqrt> bool set_point_length(SkPoint* pt, float x, float y, float length,
39 float* orig_length = nullptr) {
40 SkASSERT(!use_rsqrt || (orig_length == nullptr));
41
42 // our mag2 step overflowed to infinity, so use doubles instead.
43 // much slower, but needed when x or y are very large, other wise we
44 // divide by inf. and return (0,0) vector.
45 double xx = x;
46 double yy = y;
47 double dmag = sqrt(xx * xx + yy * yy);
48 double dscale = sk_ieee_double_divide(length, dmag);
49 x *= dscale;
50 y *= dscale;
51 // check if we're not finite, or we're zero-length
52 if (!sk_float_isfinite(x) || !sk_float_isfinite(y) || (x == 0 && y == 0)) {
53 pt->set(0, 0);
54 return false;
55 }
56 float mag = 0;
57 if (orig_length) {
58 mag = sk_double_to_float(dmag);
59 }
60 pt->set(x, y);
61 if (orig_length) {
62 *orig_length = mag;
63 }
64 return true;
65 }
66
Normalize(SkPoint * pt)67 SkScalar SkPoint::Normalize(SkPoint* pt) {
68 float mag;
69 if (set_point_length<false>(pt, pt->fX, pt->fY, 1.0f, &mag)) {
70 return mag;
71 }
72 return 0;
73 }
74
Length(SkScalar dx,SkScalar dy)75 SkScalar SkPoint::Length(SkScalar dx, SkScalar dy) {
76 float mag2 = dx * dx + dy * dy;
77 if (SkScalarIsFinite(mag2)) {
78 return sk_float_sqrt(mag2);
79 } else {
80 double xx = dx;
81 double yy = dy;
82 return sk_double_to_float(sqrt(xx * xx + yy * yy));
83 }
84 }
85
setLength(float x,float y,float length)86 bool SkPoint::setLength(float x, float y, float length) {
87 return set_point_length<false>(this, x, y, length);
88 }
89
SetLengthFast(SkPoint * pt,float length)90 bool SkPointPriv::SetLengthFast(SkPoint* pt, float length) {
91 return set_point_length<true>(pt, pt->fX, pt->fY, length);
92 }
93
94
95 ///////////////////////////////////////////////////////////////////////////////
96
DistanceToLineBetweenSqd(const SkPoint & pt,const SkPoint & a,const SkPoint & b,Side * side)97 SkScalar SkPointPriv::DistanceToLineBetweenSqd(const SkPoint& pt, const SkPoint& a,
98 const SkPoint& b,
99 Side* side) {
100
101 SkVector u = b - a;
102 SkVector v = pt - a;
103
104 SkScalar uLengthSqd = LengthSqd(u);
105 SkScalar det = u.cross(v);
106 if (side) {
107 SkASSERT(-1 == kLeft_Side &&
108 0 == kOn_Side &&
109 1 == kRight_Side);
110 *side = (Side) SkScalarSignAsInt(det);
111 }
112 SkScalar temp = sk_ieee_float_divide(det, uLengthSqd);
113 temp *= det;
114 // It's possible we have a degenerate line vector, or we're so far away it looks degenerate
115 // In this case, return squared distance to point A.
116 if (!SkScalarIsFinite(temp)) {
117 return LengthSqd(v);
118 }
119 return temp;
120 }
121
DistanceToLineSegmentBetweenSqd(const SkPoint & pt,const SkPoint & a,const SkPoint & b)122 SkScalar SkPointPriv::DistanceToLineSegmentBetweenSqd(const SkPoint& pt, const SkPoint& a,
123 const SkPoint& b) {
124 // See comments to distanceToLineBetweenSqd. If the projection of c onto
125 // u is between a and b then this returns the same result as that
126 // function. Otherwise, it returns the distance to the closer of a and
127 // b. Let the projection of v onto u be v'. There are three cases:
128 // 1. v' points opposite to u. c is not between a and b and is closer
129 // to a than b.
130 // 2. v' points along u and has magnitude less than y. c is between
131 // a and b and the distance to the segment is the same as distance
132 // to the line ab.
133 // 3. v' points along u and has greater magnitude than u. c is not
134 // not between a and b and is closer to b than a.
135 // v' = (u dot v) * u / |u|. So if (u dot v)/|u| is less than zero we're
136 // in case 1. If (u dot v)/|u| is > |u| we are in case 3. Otherwise
137 // we're in case 2. We actually compare (u dot v) to 0 and |u|^2 to
138 // avoid a sqrt to compute |u|.
139
140 SkVector u = b - a;
141 SkVector v = pt - a;
142
143 SkScalar uLengthSqd = LengthSqd(u);
144 SkScalar uDotV = SkPoint::DotProduct(u, v);
145
146 // closest point is point A
147 if (uDotV <= 0) {
148 return LengthSqd(v);
149 // closest point is point B
150 } else if (uDotV > uLengthSqd) {
151 return DistanceToSqd(b, pt);
152 // closest point is inside segment
153 } else {
154 SkScalar det = u.cross(v);
155 SkScalar temp = sk_ieee_float_divide(det, uLengthSqd);
156 temp *= det;
157 // It's possible we have a degenerate segment, or we're so far away it looks degenerate
158 // In this case, return squared distance to point A.
159 if (!SkScalarIsFinite(temp)) {
160 return LengthSqd(v);
161 }
162 return temp;
163 }
164 }
165