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 #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 <algorithm>
  29
  30 // Calculate the borders of a "d-radius" cube
  31 void getFacePositions(std::list<v3s16> &list, u16 d);
  32
  33 class IndentationRaiser
  34 {
  35 public:
  36         IndentationRaiser(u16 *indentation)
  37         {
  38                 m_indentation = indentation;
  39                 (*m_indentation)++;
  40         }
  41         ~IndentationRaiser()
  42         {
  43                 (*m_indentation)--;
  44         }
  45 private:
  46         u16 *m_indentation;
  47 };
  48
  49 inline s16 getContainerPos(s16 p, s16 d)
  50 {
  51         return (p>=0 ? p : p-d+1) / d;
  52 }
  53
  54 inline v2s16 getContainerPos(v2s16 p, s16 d)
  55 {
  56         return v2s16(
  57                 getContainerPos(p.X, d),
  58                 getContainerPos(p.Y, d)
  59         );
  60 }
  61
  62 inline v3s16 getContainerPos(v3s16 p, s16 d)
  63 {
  64         return v3s16(
  65                 getContainerPos(p.X, d),
  66                 getContainerPos(p.Y, d),
  67                 getContainerPos(p.Z, d)
  68         );
  69 }
  70
  71 inline v2s16 getContainerPos(v2s16 p, v2s16 d)
  72 {
  73         return v2s16(
  74                 getContainerPos(p.X, d.X),
  75                 getContainerPos(p.Y, d.Y)
  76         );
  77 }
  78
  79 inline v3s16 getContainerPos(v3s16 p, v3s16 d)
  80 {
  81         return v3s16(
  82                 getContainerPos(p.X, d.X),
  83                 getContainerPos(p.Y, d.Y),
  84                 getContainerPos(p.Z, d.Z)
  85         );
  86 }
  87
  88 inline void getContainerPosWithOffset(s16 p, s16 d, s16 &container, s16 &offset)
  89 {
  90         container = (p >= 0 ? p : p - d + 1) / d;
  91         offset = p & (d - 1);
  92 }
  93
  94 inline void getContainerPosWithOffset(const v2s16 &p, s16 d, v2s16 &container, v2s16 &offset)
  95 {
  96         getContainerPosWithOffset(p.X, d, container.X, offset.X);
  97         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
  98 }
  99
 100 inline void getContainerPosWithOffset(const v3s16 &p, s16 d, v3s16 &container, v3s16 &offset)
 101 {
 102         getContainerPosWithOffset(p.X, d, container.X, offset.X);
 103         getContainerPosWithOffset(p.Y, d, container.Y, offset.Y);
 104         getContainerPosWithOffset(p.Z, d, container.Z, offset.Z);
 105 }
 106
 107
 108 inline bool isInArea(v3s16 p, s16 d)
 109 {
 110         return (
 111                 p.X >= 0 && p.X < d &&
 112                 p.Y >= 0 && p.Y < d &&
 113                 p.Z >= 0 && p.Z < d
 114         );
 115 }
 116
 117 inline bool isInArea(v2s16 p, s16 d)
 118 {
 119         return (
 120                 p.X >= 0 && p.X < d &&
 121                 p.Y >= 0 && p.Y < d
 122         );
 123 }
 124
 125 inline bool isInArea(v3s16 p, v3s16 d)
 126 {
 127         return (
 128                 p.X >= 0 && p.X < d.X &&
 129                 p.Y >= 0 && p.Y < d.Y &&
 130                 p.Z >= 0 && p.Z < d.Z
 131         );
 132 }
 133
 134 #define rangelim(d, min, max) ((d) < (min) ? (min) : ((d)>(max)?(max):(d)))
 135 #define myfloor(x) ((x) > 0.0 ? (int)(x) : (int)(x) - 1)
 136
 137 inline v3s16 arealim(v3s16 p, s16 d)
 138 {
 139         if(p.X < 0)
 140                 p.X = 0;
 141         if(p.Y < 0)
 142                 p.Y = 0;
 143         if(p.Z < 0)
 144                 p.Z = 0;
 145         if(p.X > d-1)
 146                 p.X = d-1;
 147         if(p.Y > d-1)
 148                 p.Y = d-1;
 149         if(p.Z > d-1)
 150                 p.Z = d-1;
 151         return p;
 152 }
 153
 154 #define ARRLEN(x) (sizeof(x) / sizeof((x)[0]))
 155 #define CONTAINS(c, v) (std::find((c).begin(), (c).end(), (v)) != (c).end())
 156
 157 // The naive swap performs better than the xor version
 158 #define SWAP(t, x, y) do { \
 159         t temp = x;            \
 160         x = y;                 \
 161         y = temp;              \
 162 } while (0)
 163
 164 inline void sortBoxVerticies(v3s16 &p1, v3s16 &p2) {
 165         if (p1.X > p2.X)
 166                 SWAP(s16, p1.X, p2.X);
 167         if (p1.Y > p2.Y)
 168                 SWAP(s16, p1.Y, p2.Y);
 169         if (p1.Z > p2.Z)
 170                 SWAP(s16, p1.Z, p2.Z);
 171 }
 172
 173
 174 /*
 175         See test.cpp for example cases.
 176         wraps degrees to the range of -360...360
 177         NOTE: Wrapping to 0...360 is not used because pitch needs negative values.
 178 */
 179 inline float wrapDegrees(float f)
 180 {
 181         // Take examples of f=10, f=720.5, f=-0.5, f=-360.5
 182         // This results in
 183         // 10, 720, -1, -361
 184         int i = floor(f);
 185         // 0, 2, 0, -1
 186         int l = i / 360;
 187         // NOTE: This would be used for wrapping to 0...360
 188         // 0, 2, -1, -2
 189         /*if(i < 0)
 190                 l -= 1;*/
 191         // 0, 720, 0, -360
 192         int k = l * 360;
 193         // 10, 0.5, -0.5, -0.5
 194         f -= float(k);
 195         return f;
 196 }
 197
 198 /* Wrap to 0...360 */
 199 inline float wrapDegrees_0_360(float f)
 200 {
 201         // Take examples of f=10, f=720.5, f=-0.5, f=-360.5
 202         // This results in
 203         // 10, 720, -1, -361
 204         int i = floor(f);
 205         // 0, 2, 0, -1
 206         int l = i / 360;
 207         // Wrap to 0...360
 208         // 0, 2, -1, -2
 209         if(i < 0)
 210                 l -= 1;
 211         // 0, 720, 0, -360
 212         int k = l * 360;
 213         // 10, 0.5, -0.5, -0.5
 214         f -= float(k);
 215         return f;
 216 }
 217
 218 /* Wrap to -180...180 */
 219 inline float wrapDegrees_180(float f)
 220 {
 221         f += 180;
 222         f = wrapDegrees_0_360(f);
 223         f -= 180;
 224         return f;
 225 }
 226
 227 /*
 228         Pseudo-random (VC++ rand() sucks)
 229 */
 230 int myrand(void);
 231 void mysrand(unsigned seed);
 232 #define MYRAND_MAX 32767
 233
 234 int myrand_range(int min, int max);
 235
 236 /*
 237         Miscellaneous functions
 238 */
 239
 240 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed);
 241
 242 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 243                 f32 camera_fov, f32 range, f32 *distance_ptr=NULL);
 244
 245 /*
 246         Some helper stuff
 247 */
 248 #define MYMIN(a,b) ((a)<(b)?(a):(b))
 249 #define MYMAX(a,b) ((a)>(b)?(a):(b))
 250
 251 /*
 252         Returns nearest 32-bit integer for given floating point number.
 253         <cmath> and <math.h> in VC++ don't provide round().
 254 */
 255 inline s32 myround(f32 f)
 256 {
 257         return floor(f + 0.5);
 258 }
 259
 260 /*
 261         Returns integer position of node in given floating point position
 262 */
 263 inline v3s16 floatToInt(v3f p, f32 d)
 264 {
 265         v3s16 p2(
 266                 (p.X + (p.X>0 ? d/2 : -d/2))/d,
 267                 (p.Y + (p.Y>0 ? d/2 : -d/2))/d,
 268                 (p.Z + (p.Z>0 ? d/2 : -d/2))/d);
 269         return p2;
 270 }
 271
 272 /*
 273         Returns floating point position of node in given integer position
 274 */
 275 inline v3f intToFloat(v3s16 p, f32 d)
 276 {
 277         v3f p2(
 278                 (f32)p.X * d,
 279                 (f32)p.Y * d,
 280                 (f32)p.Z * d
 281         );
 282         return p2;
 283 }
 284
 285 // Random helper. Usually d=BS
 286 inline core::aabbox3d<f32> getNodeBox(v3s16 p, float d)
 287 {
 288         return core::aabbox3d<f32>(
 289                 (float)p.X * d - 0.5*d,
 290                 (float)p.Y * d - 0.5*d,
 291                 (float)p.Z * d - 0.5*d,
 292                 (float)p.X * d + 0.5*d,
 293                 (float)p.Y * d + 0.5*d,
 294                 (float)p.Z * d + 0.5*d
 295         );
 296 }
 297
 298 class IntervalLimiter
 299 {
 300 public:
 301         IntervalLimiter():
 302                 m_accumulator(0)
 303         {
 304         }
 305         /*
 306                 dtime: time from last call to this method
 307                 wanted_interval: interval wanted
 308                 return value:
 309                         true: action should be skipped
 310                         false: action should be done
 311         */
 312         bool step(float dtime, float wanted_interval)
 313         {
 314                 m_accumulator += dtime;
 315                 if(m_accumulator < wanted_interval)
 316                         return false;
 317                 m_accumulator -= wanted_interval;
 318                 return true;
 319         }
 320 protected:
 321         float m_accumulator;
 322 };
 323
 324 /*
 325         Splits a list into "pages". For example, the list [1,2,3,4,5] split
 326         into two pages would be [1,2,3],[4,5]. This function computes the
 327         minimum and maximum indices of a single page.
 328
 329         length: Length of the list that should be split
 330         page: Page number, 1 <= page <= pagecount
 331         pagecount: The number of pages, >= 1
 332         minindex: Receives the minimum index (inclusive).
 333         maxindex: Receives the maximum index (exclusive).
 334
 335         Ensures 0 <= minindex <= maxindex <= length.
 336 */
 337 inline void paging(u32 length, u32 page, u32 pagecount, u32 &minindex, u32 &maxindex)
 338 {
 339         if(length < 1 || pagecount < 1 || page < 1 || page > pagecount)
 340         {
 341                 // Special cases or invalid parameters
 342                 minindex = maxindex = 0;
 343         }
 344         else if(pagecount <= length)
 345         {
 346                 // Less pages than entries in the list:
 347                 // Each page contains at least one entry
 348                 minindex = (length * (page-1) + (pagecount-1)) / pagecount;
 349                 maxindex = (length * page + (pagecount-1)) / pagecount;
 350         }
 351         else
 352         {
 353                 // More pages than entries in the list:
 354                 // Make sure the empty pages are at the end
 355                 if(page < length)
 356                 {
 357                         minindex = page-1;
 358                         maxindex = page;
 359                 }
 360                 else
 361                 {
 362                         minindex = 0;
 363                         maxindex = 0;
 364                 }
 365         }
 366 }
 367
 368 inline float cycle_shift(float value, float by = 0, float max = 1)
 369 {
 370     if (value + by < 0) return max + by + value;
 371     if (value + by > max) return value + by - max;
 372     return value + by;
 373 }
 374
 375 inline bool is_power_of_two(u32 n)
 376 {
 377         return n != 0 && (n & (n-1)) == 0;
 378 }
 379
 380 #endif
 381