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