Line data Source code
1 : /* Copyright (C) 2020 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #ifndef INCLUDED_FIXED_VECTOR2D
19 : #define INCLUDED_FIXED_VECTOR2D
20 :
21 : #include "maths/Fixed.h"
22 : #include "maths/Sqrt.h"
23 :
24 : class CFixedVector2D
25 : {
26 : public:
27 : fixed X, Y;
28 :
29 188 : CFixedVector2D() { }
30 10320 : CFixedVector2D(fixed X, fixed Y) : X(X), Y(Y) { }
31 :
32 : /// Vector equality
33 17 : bool operator==(const CFixedVector2D& v) const
34 : {
35 17 : return (X == v.X && Y == v.Y);
36 : }
37 :
38 : /// Vector inequality
39 0 : bool operator!=(const CFixedVector2D& v) const
40 : {
41 0 : return (X != v.X || Y != v.Y);
42 : }
43 :
44 : /// Vector addition
45 580 : CFixedVector2D operator+(const CFixedVector2D& v) const
46 : {
47 580 : return CFixedVector2D(X + v.X, Y + v.Y);
48 : }
49 :
50 : /// Vector subtraction
51 2412 : CFixedVector2D operator-(const CFixedVector2D& v) const
52 : {
53 2412 : return CFixedVector2D(X - v.X, Y - v.Y);
54 : }
55 :
56 : /// Negation
57 46 : CFixedVector2D operator-() const
58 : {
59 46 : return CFixedVector2D(-X, -Y);
60 : }
61 :
62 : /// Vector addition
63 1 : CFixedVector2D& operator+=(const CFixedVector2D& v)
64 : {
65 1 : *this = *this + v;
66 1 : return *this;
67 : }
68 :
69 : /// Vector subtraction
70 3 : CFixedVector2D& operator-=(const CFixedVector2D& v)
71 : {
72 3 : *this = *this - v;
73 3 : return *this;
74 : }
75 :
76 : /// Scalar multiplication by an integer
77 64 : CFixedVector2D operator*(int n) const
78 : {
79 64 : return CFixedVector2D(X*n, Y*n);
80 : }
81 :
82 : /// Scalar division by an integer. Must not have n == 0.
83 0 : CFixedVector2D operator/(int n) const
84 : {
85 0 : return CFixedVector2D(X/n, Y/n);
86 : }
87 :
88 : /**
89 : * Multiply by a CFixed. Likely to overflow if both numbers are large,
90 : * so we use an ugly name instead of operator* to make it obvious.
91 : */
92 936 : CFixedVector2D Multiply(fixed n) const
93 : {
94 936 : return CFixedVector2D(X.Multiply(n), Y.Multiply(n));
95 : }
96 :
97 : /**
98 : * Returns the length of the vector.
99 : * Will not overflow if the result can be represented as type 'fixed'.
100 : */
101 208 : fixed Length() const
102 : {
103 : // Do intermediate calculations with 64-bit ints to avoid overflows
104 208 : u64 xx = SQUARE_U64_FIXED(X);
105 208 : u64 yy = SQUARE_U64_FIXED(Y);
106 208 : u64 d2 = xx + yy;
107 208 : CheckUnsignedAdditionOverflow(d2, xx, L"Overflow in CFixedVector2D::Length() part 1")
108 :
109 208 : u32 d = isqrt64(d2);
110 :
111 208 : CheckU32CastOverflow(d, i32, L"Overflow in CFixedVector2D::Length() part 2")
112 208 : fixed r;
113 208 : r.SetInternalValue(static_cast<i32>(d));
114 208 : return r;
115 : }
116 :
117 : /**
118 : * Returns -1, 0, +1 depending on whether length is less/equal/greater
119 : * than the argument.
120 : * Avoids sqrting and overflowing.
121 : */
122 1763 : int CompareLength(fixed cmp) const
123 : {
124 1763 : u64 d2 = SQUARE_U64_FIXED(X) + SQUARE_U64_FIXED(Y); // d2 <= 2^63 (no overflow)
125 1763 : u64 cmpSquared = SQUARE_U64_FIXED(cmp);
126 :
127 1763 : if (d2 < cmpSquared)
128 95 : return -1;
129 :
130 1668 : if (d2 > cmpSquared)
131 1660 : return +1;
132 :
133 8 : return 0;
134 : }
135 :
136 : /**
137 : * Same as above, but avoids squaring the compared value.
138 : * The argument must be the result of an SQUARE_U64_FIXED operation.
139 : */
140 5 : int CompareLengthSquared(u64 cmpSquared) const
141 : {
142 5 : u64 d2 = SQUARE_U64_FIXED(X) + SQUARE_U64_FIXED(Y); // d2 <= 2^63 (no overflow)
143 :
144 5 : if (d2 < cmpSquared)
145 2 : return -1;
146 :
147 3 : if (d2 > cmpSquared)
148 2 : return +1;
149 :
150 1 : return 0;
151 : }
152 :
153 : /**
154 : * Returns -1, 0, +1 depending on whether length is less/equal/greater
155 : * than the argument's length.
156 : * Avoids sqrting and overflowing.
157 : */
158 3 : int CompareLength(const CFixedVector2D& other) const
159 : {
160 3 : u64 d2 = SQUARE_U64_FIXED(X) + SQUARE_U64_FIXED(Y);
161 3 : u64 od2 = SQUARE_U64_FIXED(other.X) + SQUARE_U64_FIXED(other.Y);
162 :
163 3 : if (d2 < od2)
164 1 : return -1;
165 :
166 2 : if (d2 > od2)
167 1 : return +1;
168 :
169 1 : return 0;
170 : }
171 :
172 5 : bool IsZero() const
173 : {
174 5 : return X.IsZero() && Y.IsZero();
175 : }
176 :
177 : /**
178 : * Normalize the vector so that length is close to 1.
179 : * If length is 0, does nothing.
180 : */
181 4 : void Normalize()
182 : {
183 4 : if (!IsZero())
184 : {
185 3 : fixed l = Length();
186 3 : X = X / l;
187 3 : Y = Y / l;
188 : }
189 4 : }
190 :
191 : /**
192 : * Normalize the vector so that length is close to n.
193 : * If length is 0, does nothing.
194 : */
195 9 : void Normalize(fixed n)
196 : {
197 9 : fixed l = Length();
198 9 : if (!l.IsZero())
199 : {
200 8 : X = X.MulDiv(n, l);
201 8 : Y = Y.MulDiv(n, l);
202 : }
203 9 : }
204 :
205 : /**
206 : * Compute the dot product of this vector with another.
207 : * Likely to overflow if both vectors are large-ish (around the 200 range).
208 : */
209 436 : fixed Dot(const CFixedVector2D& v) const
210 : {
211 436 : i64 x = MUL_I64_I32_I32(X.GetInternalValue(), v.X.GetInternalValue());
212 436 : i64 y = MUL_I64_I32_I32(Y.GetInternalValue(), v.Y.GetInternalValue());
213 436 : CheckSignedAdditionOverflow(i64, x, y, L"Overflow in CFixedVector2D::Dot() part 1", L"Underflow in CFixedVector2D::Dot() part 1")
214 436 : i64 sum = x + y;
215 436 : sum >>= fixed::fract_bits;
216 :
217 436 : CheckCastOverflow(sum, i32, L"Overflow in CFixedVector2D::Dot() part 2", L"Underflow in CFixedVector2D::Dot() part 2")
218 436 : fixed ret;
219 436 : ret.SetInternalValue(static_cast<i32>(sum));
220 436 : return ret;
221 : }
222 :
223 : /**
224 : * @return -1, 0 or 1 if this and @v face respectively opposite directions, perpendicular, or same directions.
225 : */
226 60 : int RelativeOrientation(const CFixedVector2D& v) const
227 : {
228 60 : i64 x = MUL_I64_I32_I32(X.GetInternalValue(), v.X.GetInternalValue());
229 60 : i64 y = MUL_I64_I32_I32(Y.GetInternalValue(), v.Y.GetInternalValue());
230 60 : return x > -y ? 1 : x < -y ? -1 : 0;
231 : }
232 :
233 44 : CFixedVector2D Perpendicular() const
234 : {
235 44 : return CFixedVector2D(Y, -X);
236 : }
237 :
238 : /**
239 : * Rotate the vector by the given angle (anticlockwise).
240 : */
241 0 : CFixedVector2D Rotate(fixed angle) const
242 : {
243 0 : fixed s, c;
244 0 : sincos_approx(angle, s, c);
245 0 : return CFixedVector2D(X.Multiply(c) + Y.Multiply(s), Y.Multiply(c) - X.Multiply(s));
246 : }
247 : };
248 :
249 : #endif // INCLUDED_FIXED_VECTOR2D
|
