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