Fix player rotations (#7941)
[oweals/minetest.git] / src / util / numeric.h
1 /*
2 Minetest
3 Copyright (C) 2010-2013 celeron55, Perttu Ahola <celeron55@gmail.com>
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as published by
7 the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License along
16 with this program; if not, write to the Free Software Foundation, Inc.,
17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 #pragma once
21
22 #include "basic_macros.h"
23 #include "irrlichttypes.h"
24 #include "irr_v2d.h"
25 #include "irr_v3d.h"
26 #include "irr_aabb3d.h"
27
28 #define rangelim(d, min, max) ((d) < (min) ? (min) : ((d) > (max) ? (max) : (d)))
29 #define myfloor(x) ((x) < 0.0 ? (int)(x) - 1 : (int)(x))
30 // The naive swap performs better than the xor version
31 #define SWAP(t, x, y) do { \
32         t temp = x; \
33         x = y; \
34         y = temp; \
35 } while (0)
36
37
38 inline s16 getContainerPos(s16 p, s16 d)
39 {
40         return (p >= 0 ? p : p - d + 1) / d;
41 }
42
43 inline v2s16 getContainerPos(v2s16 p, s16 d)
44 {
45         return v2s16(
46                 getContainerPos(p.X, d),
47                 getContainerPos(p.Y, d)
48         );
49 }
50
51 inline v3s16 getContainerPos(v3s16 p, s16 d)
52 {
53         return v3s16(
54                 getContainerPos(p.X, d),
55                 getContainerPos(p.Y, d),
56                 getContainerPos(p.Z, d)
57         );
58 }
59
60 inline v2s16 getContainerPos(v2s16 p, v2s16 d)
61 {
62         return v2s16(
63                 getContainerPos(p.X, d.X),
64                 getContainerPos(p.Y, d.Y)
65         );
66 }
67
68 inline v3s16 getContainerPos(v3s16 p, v3s16 d)
69 {
70         return v3s16(
71                 getContainerPos(p.X, d.X),
72                 getContainerPos(p.Y, d.Y),
73                 getContainerPos(p.Z, d.Z)
74         );
75 }
76
77 inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
78 {
79         container = (p >= 0 ? p : p - d + 1) / d;
80         offset = p & (d - 1);
81 }
82
83 inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
84 {
85         getContainerPosWithOffset(p.X, d, container.X, offset.X);
86         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
87 }
88
89 inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
90 {
91         getContainerPosWithOffset(p.X, d, container.X, offset.X);
92         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
93         getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
94 }
95
96
97 inline bool isInArea(v3s16 p, s16 d)
98 {
99         return (
100                 p.X >= 0 && p.X < d &&
101                 p.Y >= 0 && p.Y < d &&
102                 p.Z >= 0 && p.Z < d
103         );
104 }
105
106 inline bool isInArea(v2s16 p, s16 d)
107 {
108         return (
109                 p.X >= 0 && p.X < d &&
110                 p.Y >= 0 && p.Y < d
111         );
112 }
113
114 inline bool isInArea(v3s16 p, v3s16 d)
115 {
116         return (
117                 p.X >= 0 && p.X < d.X &&
118                 p.Y >= 0 && p.Y < d.Y &&
119                 p.Z >= 0 && p.Z < d.Z
120         );
121 }
122
123 inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
124         if (p1.X > p2.X)
125                 SWAP(s16, p1.X, p2.X);
126         if (p1.Y > p2.Y)
127                 SWAP(s16, p1.Y, p2.Y);
128         if (p1.Z > p2.Z)
129                 SWAP(s16, p1.Z, p2.Z);
130 }
131
132 inline v3s16 componentwise_min(const v3s16 &a, const v3s16 &b)
133 {
134         return v3s16(MYMIN(a.X, b.X), MYMIN(a.Y, b.Y), MYMIN(a.Z, b.Z));
135 }
136
137 inline v3s16 componentwise_max(const v3s16 &a, const v3s16 &b)
138 {
139         return v3s16(MYMAX(a.X, b.X), MYMAX(a.Y, b.Y), MYMAX(a.Z, b.Z));
140 }
141
142
143 /** Returns \p f wrapped to the range [-360, 360]
144  *
145  *  See test.cpp for example cases.
146  *
147  *  \note This is also used in cases where degrees wrapped to the range [0, 360]
148  *  is innapropriate (e.g. pitch needs negative values)
149  *
150  *  \internal functionally equivalent -- although precision may vary slightly --
151  *  to fmodf((f), 360.0f) however empirical tests indicate that this approach is
152  *  faster.
153  */
154 inline float modulo360f(float f)
155 {
156         int sign;
157         int whole;
158         float fraction;
159
160         if (f < 0) {
161                 f = -f;
162                 sign = -1;
163         } else {
164                 sign = 1;
165         }
166
167         whole = f;
168
169         fraction = f - whole;
170         whole %= 360;
171
172         return sign * (whole + fraction);
173 }
174
175
176 /** Returns \p f wrapped to the range [0, 360]
177   */
178 inline float wrapDegrees_0_360(float f)
179 {
180         float value = modulo360f(f);
181         return value < 0 ? value + 360 : value;
182 }
183
184
185 /** Returns \p v3f wrapped to the range [0, 360]
186   */
187 inline v3f wrapDegrees_0_360_v3f(v3f v)
188 {
189         v3f value_v3f;
190         value_v3f.X = modulo360f(v.X);
191         value_v3f.Y = modulo360f(v.Y);
192         value_v3f.Z = modulo360f(v.Z);
193
194         // Now that values are wrapped, use to get values for certain ranges
195         value_v3f.X = value_v3f.X < 0 ? value_v3f.X + 360 : value_v3f.X;
196         value_v3f.Y = value_v3f.Y < 0 ? value_v3f.Y + 360 : value_v3f.Y;
197         value_v3f.Z = value_v3f.Z < 0 ? value_v3f.Z + 360 : value_v3f.Z;
198         return value_v3f;
199 }
200
201
202 /** Returns \p f wrapped to the range [-180, 180]
203   */
204 inline float wrapDegrees_180(float f)
205 {
206         float value = modulo360f(f + 180);
207         if (value < 0)
208                 value += 360;
209         return value - 180;
210 }
211
212 /*
213         Pseudo-random (VC++ rand() sucks)
214 */
215 #define MYRAND_RANGE 0xffffffff
216 u32 myrand();
217 void mysrand(unsigned int seed);
218 void myrand_bytes(void *out, size_t len);
219 int myrand_range(int min, int max);
220
221 /*
222         Miscellaneous functions
223 */
224
225 inline u32 get_bits(u32 x, u32 pos, u32 len)
226 {
227         u32 mask = (1 << len) - 1;
228         return (x >> pos) & mask;
229 }
230
231 inline void set_bits(u32 *x, u32 pos, u32 len, u32 val)
232 {
233         u32 mask = (1 << len) - 1;
234         *x &= ~(mask << pos);
235         *x |= (val & mask) << pos;
236 }
237
238 inline u32 calc_parity(u32 v)
239 {
240         v ^= v >> 16;
241         v ^= v >> 8;
242         v ^= v >> 4;
243         v &= 0xf;
244         return (0x6996 >> v) & 1;
245 }
246
247 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);
248
249 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
250                 f32 camera_fov, f32 range, f32 *distance_ptr=NULL);
251
252 s16 adjustDist(s16 dist, float zoom_fov);
253
254 /*
255         Returns nearest 32-bit integer for given floating point number.
256         <cmath> and <math.h> in VC++ don't provide round().
257 */
258 inline s32 myround(f32 f)
259 {
260         return (s32)(f < 0.f ? (f - 0.5f) : (f + 0.5f));
261 }
262
263 inline constexpr f32 sqr(f32 f)
264 {
265         return f * f;
266 }
267
268 /*
269         Returns integer position of node in given floating point position
270 */
271 inline v3s16 floatToInt(v3f p, f32 d)
272 {
273         return v3s16(
274                 (p.X + (p.X > 0 ? d / 2 : -d / 2)) / d,
275                 (p.Y + (p.Y > 0 ? d / 2 : -d / 2)) / d,
276                 (p.Z + (p.Z > 0 ? d / 2 : -d / 2)) / d);
277 }
278
279 /*
280         Returns integer position of node in given double precision position
281  */
282 inline v3s16 doubleToInt(v3d p, double d)
283 {
284         return v3s16(
285                 (p.X + (p.X > 0 ? d / 2 : -d / 2)) / d,
286                 (p.Y + (p.Y > 0 ? d / 2 : -d / 2)) / d,
287                 (p.Z + (p.Z > 0 ? d / 2 : -d / 2)) / d);
288 }
289
290 /*
291         Returns floating point position of node in given integer position
292 */
293 inline v3f intToFloat(v3s16 p, f32 d)
294 {
295         return v3f(
296                 (f32)p.X * d,
297                 (f32)p.Y * d,
298                 (f32)p.Z * d
299         );
300 }
301
302 // Random helper. Usually d=BS
303 inline aabb3f getNodeBox(v3s16 p, float d)
304 {
305         return aabb3f(
306                 (float)p.X * d - 0.5f * d,
307                 (float)p.Y * d - 0.5f * d,
308                 (float)p.Z * d - 0.5f * d,
309                 (float)p.X * d + 0.5f * d,
310                 (float)p.Y * d + 0.5f * d,
311                 (float)p.Z * d + 0.5f * d
312         );
313 }
314
315
316 class IntervalLimiter
317 {
318 public:
319         IntervalLimiter() = default;
320
321         /*
322                 dtime: time from last call to this method
323                 wanted_interval: interval wanted
324                 return value:
325                         true: action should be skipped
326                         false: action should be done
327         */
328         bool step(float dtime, float wanted_interval)
329         {
330                 m_accumulator += dtime;
331                 if (m_accumulator < wanted_interval)
332                         return false;
333                 m_accumulator -= wanted_interval;
334                 return true;
335         }
336
337 private:
338         float m_accumulator = 0.0f;
339 };
340
341
342 /*
343         Splits a list into "pages". For example, the list [1,2,3,4,5] split
344         into two pages would be [1,2,3],[4,5]. This function computes the
345         minimum and maximum indices of a single page.
346
347         length: Length of the list that should be split
348         page: Page number, 1 <= page <= pagecount
349         pagecount: The number of pages, >= 1
350         minindex: Receives the minimum index (inclusive).
351         maxindex: Receives the maximum index (exclusive).
352
353         Ensures 0 <= minindex <= maxindex <= length.
354 */
355 inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
356 {
357         if (length < 1 || pagecount < 1 || page < 1 || page > pagecount) {
358                 // Special cases or invalid parameters
359                 minindex = maxindex = 0;
360         } else if(pagecount <= length) {
361                 // Less pages than entries in the list:
362                 // Each page contains at least one entry
363                 minindex = (length * (page-1) + (pagecount-1)) / pagecount;
364                 maxindex = (length * page + (pagecount-1)) / pagecount;
365         } else {
366                 // More pages than entries in the list:
367                 // Make sure the empty pages are at the end
368                 if (page < length) {
369                         minindex = page-1;
370                         maxindex = page;
371                 } else {
372                         minindex = 0;
373                         maxindex = 0;
374                 }
375         }
376 }
377
378 inline float cycle_shift(float value, float by = 0, float max = 1)
379 {
380     if (value + by < 0)   return value + by + max;
381     if (value + by > max) return value + by - max;
382     return value + by;
383 }
384
385 inline bool is_power_of_two(u32 n)
386 {
387         return n != 0 && (n & (n - 1)) == 0;
388 }
389
390 // Compute next-higher power of 2 efficiently, e.g. for power-of-2 texture sizes.
391 // Public Domain: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
392 inline u32 npot2(u32 orig) {
393         orig--;
394         orig |= orig >> 1;
395         orig |= orig >> 2;
396         orig |= orig >> 4;
397         orig |= orig >> 8;
398         orig |= orig >> 16;
399         return orig + 1;
400 }
401
402 // Gradual steps towards the target value in a wrapped (circular) system
403 // using the shorter of both ways
404 template<typename T>
405 inline void wrappedApproachShortest(T &current, const T target, const T stepsize,
406         const T maximum)
407 {
408         T delta = target - current;
409         if (delta < 0)
410                 delta += maximum;
411
412         if (delta > stepsize && maximum - delta > stepsize) {
413                 current += (delta < maximum / 2) ? stepsize : -stepsize;
414                 if (current >= maximum)
415                         current -= maximum;
416         } else {
417                 current = target;
418         }
419 }