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