Line data Source code
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 : #ifndef UTIL_NUMERIC_HEADER
21 : #define UTIL_NUMERIC_HEADER
22 :
23 : #include "../irrlichttypes.h"
24 : #include "../irr_v2d.h"
25 : #include "../irr_v3d.h"
26 : #include "../irr_aabb3d.h"
27 : #include <list>
28 : #include <map>
29 : #include <vector>
30 : #include <algorithm>
31 :
32 :
33 : /*
34 : * This class permits to cache getFacePosition call results
35 : * This reduces CPU usage and vector calls
36 : */
37 : class FacePositionCache
38 : {
39 : public:
40 : static std::vector<v3s16> getFacePositions(u16 d);
41 : private:
42 : static void generateFacePosition(u16 d);
43 : static std::map<u16, std::vector<v3s16> > m_cache;
44 : };
45 :
46 : class IndentationRaiser
47 : {
48 : public:
49 : IndentationRaiser(u16 *indentation)
50 : {
51 : m_indentation = indentation;
52 : (*m_indentation)++;
53 : }
54 : ~IndentationRaiser()
55 : {
56 : (*m_indentation)--;
57 : }
58 : private:
59 : u16 *m_indentation;
60 : };
61 :
62 6723507 : inline s16 getContainerPos(s16 p, s16 d)
63 : {
64 6723507 : return (p>=0 ? p : p-d+1) / d;
65 : }
66 :
67 : inline v2s16 getContainerPos(v2s16 p, s16 d)
68 : {
69 : return v2s16(
70 : getContainerPos(p.X, d),
71 : getContainerPos(p.Y, d)
72 : );
73 : }
74 :
75 2241169 : inline v3s16 getContainerPos(v3s16 p, s16 d)
76 : {
77 : return v3s16(
78 2241169 : getContainerPos(p.X, d),
79 2241169 : getContainerPos(p.Y, d),
80 2241169 : getContainerPos(p.Z, d)
81 6723507 : );
82 : }
83 :
84 : inline v2s16 getContainerPos(v2s16 p, v2s16 d)
85 : {
86 : return v2s16(
87 : getContainerPos(p.X, d.X),
88 : getContainerPos(p.Y, d.Y)
89 : );
90 : }
91 :
92 : inline v3s16 getContainerPos(v3s16 p, v3s16 d)
93 : {
94 : return v3s16(
95 : getContainerPos(p.X, d.X),
96 : getContainerPos(p.Y, d.Y),
97 : getContainerPos(p.Z, d.Z)
98 : );
99 : }
100 :
101 71394 : inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
102 : {
103 71394 : container = (p >= 0 ? p : p - d + 1) / d;
104 71394 : offset = p & (d - 1);
105 71394 : }
106 :
107 : inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
108 : {
109 : getContainerPosWithOffset(p.X, d, container.X, offset.X);
110 : getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
111 : }
112 :
113 23798 : inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
114 : {
115 23798 : getContainerPosWithOffset(p.X, d, container.X, offset.X);
116 23798 : getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
117 23798 : getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
118 23798 : }
119 :
120 :
121 : inline bool isInArea(v3s16 p, s16 d)
122 : {
123 : return (
124 : p.X >= 0 && p.X < d &&
125 : p.Y >= 0 && p.Y < d &&
126 : p.Z >= 0 && p.Z < d
127 : );
128 : }
129 :
130 : inline bool isInArea(v2s16 p, s16 d)
131 : {
132 : return (
133 : p.X >= 0 && p.X < d &&
134 : p.Y >= 0 && p.Y < d
135 : );
136 : }
137 :
138 : inline bool isInArea(v3s16 p, v3s16 d)
139 : {
140 : return (
141 : p.X >= 0 && p.X < d.X &&
142 : p.Y >= 0 && p.Y < d.Y &&
143 : p.Z >= 0 && p.Z < d.Z
144 : );
145 : }
146 :
147 : #define rangelim(d, min, max) ((d) < (min) ? (min) : ((d)>(max)?(max):(d)))
148 : #define myfloor(x) ((x) > 0.0 ? (int)(x) : (int)(x) - 1)
149 :
150 : inline v3s16 arealim(v3s16 p, s16 d)
151 : {
152 : if(p.X < 0)
153 : p.X = 0;
154 : if(p.Y < 0)
155 : p.Y = 0;
156 : if(p.Z < 0)
157 : p.Z = 0;
158 : if(p.X > d-1)
159 : p.X = d-1;
160 : if(p.Y > d-1)
161 : p.Y = d-1;
162 : if(p.Z > d-1)
163 : p.Z = d-1;
164 : return p;
165 : }
166 :
167 : #define ARRLEN(x) (sizeof(x) / sizeof((x)[0]))
168 : #define CONTAINS(c, v) (std::find((c).begin(), (c).end(), (v)) != (c).end())
169 :
170 : // The naive swap performs better than the xor version
171 : #define SWAP(t, x, y) do { \
172 : t temp = x; \
173 : x = y; \
174 : y = temp; \
175 : } while (0)
176 :
177 0 : inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
178 0 : if (p1.X > p2.X)
179 0 : SWAP(s16, p1.X, p2.X);
180 0 : if (p1.Y > p2.Y)
181 0 : SWAP(s16, p1.Y, p2.Y);
182 0 : if (p1.Z > p2.Z)
183 0 : SWAP(s16, p1.Z, p2.Z);
184 0 : }
185 :
186 :
187 : /** Returns \p f wrapped to the range [-360, 360]
188 : *
189 : * See test.cpp for example cases.
190 : *
191 : * \note This is also used in cases where degrees wrapped to the range [0, 360]
192 : * is innapropriate (e.g. pitch needs negative values)
193 : *
194 : * \internal functionally equivalent -- although precision may vary slightly --
195 : * to fmodf((f), 360.0f) however empirical tests indicate that this approach is
196 : * faster.
197 : */
198 0 : inline float modulo360f(float f)
199 : {
200 : int sign;
201 : int whole;
202 : float fraction;
203 :
204 0 : if (f < 0) {
205 0 : f = -f;
206 0 : sign = -1;
207 : } else {
208 0 : sign = 1;
209 : }
210 :
211 0 : whole = f;
212 :
213 0 : fraction = f - whole;
214 0 : whole %= 360;
215 :
216 0 : return sign * (whole + fraction);
217 : }
218 :
219 :
220 : /** Returns \p f wrapped to the range [0, 360]
221 : */
222 0 : inline float wrapDegrees_0_360(float f)
223 : {
224 0 : float value = modulo360f(f);
225 0 : return value < 0 ? value + 360 : value;
226 : }
227 :
228 :
229 : /** Returns \p f wrapped to the range [-180, 180]
230 : */
231 0 : inline float wrapDegrees_180(float f)
232 : {
233 0 : float value = modulo360f(f + 180);
234 0 : if (value < 0)
235 0 : value += 360;
236 0 : return value - 180;
237 : }
238 :
239 : /*
240 : Pseudo-random (VC++ rand() sucks)
241 : */
242 : #define MYRAND_RANGE 0xffffffff
243 : u32 myrand();
244 : void mysrand(unsigned int seed);
245 : void myrand_bytes(void *out, size_t len);
246 : int myrand_range(int min, int max);
247 :
248 : /*
249 : Miscellaneous functions
250 : */
251 :
252 0 : inline u32 get_bits(u32 x, u32 pos, u32 len)
253 : {
254 0 : u32 mask = (1 << len) - 1;
255 0 : return (x >> pos) & mask;
256 : }
257 :
258 0 : inline void set_bits(u32 *x, u32 pos, u32 len, u32 val)
259 : {
260 0 : u32 mask = (1 << len) - 1;
261 0 : *x &= ~(mask << pos);
262 0 : *x |= (val & mask) << pos;
263 0 : }
264 :
265 0 : inline u32 calc_parity(u32 v)
266 : {
267 0 : v ^= v >> 16;
268 0 : v ^= v >> 8;
269 0 : v ^= v >> 4;
270 0 : v &= 0xf;
271 0 : return (0x6996 >> v) & 1;
272 : }
273 :
274 : u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);
275 :
276 : bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
277 : f32 camera_fov, f32 range, f32 *distance_ptr=NULL);
278 :
279 : /*
280 : Some helper stuff
281 : */
282 : #define MYMIN(a,b) ((a)<(b)?(a):(b))
283 : #define MYMAX(a,b) ((a)>(b)?(a):(b))
284 :
285 : /*
286 : Returns nearest 32-bit integer for given floating point number.
287 : <cmath> and <math.h> in VC++ don't provide round().
288 : */
289 23 : inline s32 myround(f32 f)
290 : {
291 23 : return (s32)(f < 0.f ? (f - 0.5f) : (f + 0.5f));
292 : }
293 :
294 : /*
295 : Returns integer position of node in given floating point position
296 : */
297 1113077 : inline v3s16 floatToInt(v3f p, f32 d)
298 : {
299 : v3s16 p2(
300 1113077 : (p.X + (p.X>0 ? d/2 : -d/2))/d,
301 1113077 : (p.Y + (p.Y>0 ? d/2 : -d/2))/d,
302 3339231 : (p.Z + (p.Z>0 ? d/2 : -d/2))/d);
303 1113077 : return p2;
304 : }
305 :
306 : /*
307 : Returns floating point position of node in given integer position
308 : */
309 1700215 : inline v3f intToFloat(v3s16 p, f32 d)
310 : {
311 : v3f p2(
312 1700215 : (f32)p.X * d,
313 1700215 : (f32)p.Y * d,
314 1700215 : (f32)p.Z * d
315 5100645 : );
316 1700091 : return p2;
317 : }
318 :
319 : // Random helper. Usually d=BS
320 85778 : inline core::aabbox3d<f32> getNodeBox(v3s16 p, float d)
321 : {
322 : return core::aabbox3d<f32>(
323 85778 : (float)p.X * d - 0.5*d,
324 85778 : (float)p.Y * d - 0.5*d,
325 85778 : (float)p.Z * d - 0.5*d,
326 85778 : (float)p.X * d + 0.5*d,
327 85778 : (float)p.Y * d + 0.5*d,
328 85778 : (float)p.Z * d + 0.5*d
329 514668 : );
330 : }
331 :
332 : class IntervalLimiter
333 : {
334 : public:
335 7 : IntervalLimiter():
336 7 : m_accumulator(0)
337 : {
338 7 : }
339 : /*
340 : dtime: time from last call to this method
341 : wanted_interval: interval wanted
342 : return value:
343 : true: action should be skipped
344 : false: action should be done
345 : */
346 7096 : bool step(float dtime, float wanted_interval)
347 : {
348 7096 : m_accumulator += dtime;
349 7096 : if(m_accumulator < wanted_interval)
350 6814 : return false;
351 282 : m_accumulator -= wanted_interval;
352 282 : return true;
353 : }
354 : protected:
355 : float m_accumulator;
356 : };
357 :
358 : /*
359 : Splits a list into "pages". For example, the list [1,2,3,4,5] split
360 : into two pages would be [1,2,3],[4,5]. This function computes the
361 : minimum and maximum indices of a single page.
362 :
363 : length: Length of the list that should be split
364 : page: Page number, 1 <= page <= pagecount
365 : pagecount: The number of pages, >= 1
366 : minindex: Receives the minimum index (inclusive).
367 : maxindex: Receives the maximum index (exclusive).
368 :
369 : Ensures 0 <= minindex <= maxindex <= length.
370 : */
371 0 : inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
372 : {
373 0 : if(length < 1 || pagecount < 1 || page < 1 || page > pagecount)
374 : {
375 : // Special cases or invalid parameters
376 0 : minindex = maxindex = 0;
377 : }
378 0 : else if(pagecount <= length)
379 : {
380 : // Less pages than entries in the list:
381 : // Each page contains at least one entry
382 0 : minindex = (length * (page-1) + (pagecount-1)) / pagecount;
383 0 : maxindex = (length * page + (pagecount-1)) / pagecount;
384 : }
385 : else
386 : {
387 : // More pages than entries in the list:
388 : // Make sure the empty pages are at the end
389 0 : if(page < length)
390 : {
391 0 : minindex = page-1;
392 0 : maxindex = page;
393 : }
394 : else
395 : {
396 0 : minindex = 0;
397 0 : maxindex = 0;
398 : }
399 : }
400 0 : }
401 :
402 : inline float cycle_shift(float value, float by = 0, float max = 1)
403 : {
404 : if (value + by < 0) return max + by + value;
405 : if (value + by > max) return value + by - max;
406 : return value + by;
407 : }
408 :
409 28 : inline bool is_power_of_two(u32 n)
410 : {
411 28 : return n != 0 && (n & (n-1)) == 0;
412 : }
413 :
414 : // Compute next-higher power of 2 efficiently, e.g. for power-of-2 texture sizes.
415 : // Public Domain: https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
416 : inline u32 npot2(u32 orig) {
417 : orig--;
418 : orig |= orig >> 1;
419 : orig |= orig >> 2;
420 : orig |= orig >> 4;
421 : orig |= orig >> 8;
422 : orig |= orig >> 16;
423 : return orig + 1;
424 : }
425 :
426 : #endif
|