src/util/numeric.cpp

   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 #include "numeric.h"
  21
  22 #include "log.h"
  23 #include "../constants.h" // BS, MAP_BLOCKSIZE
  24 #include "../noise.h" // PseudoRandom, PcgRandom
  25 #include "../threading/mutex_auto_lock.h"
  26 #include <cstring>
  27
  28
  29 // myrand
  30
  31 PcgRandom g_pcgrand;
  32
  33 u32 myrand()
  34 {
  35         return g_pcgrand.next();
  36 }
  37
  38 void mysrand(unsigned int seed)
  39 {
  40         g_pcgrand.seed(seed);
  41 }
  42
  43 void myrand_bytes(void *out, size_t len)
  44 {
  45         g_pcgrand.bytes(out, len);
  46 }
  47
  48 int myrand_range(int min, int max)
  49 {
  50         return g_pcgrand.range(min, max);
  51 }
  52
  53
  54 /*
  55         64-bit unaligned version of MurmurHash
  56 */
  57 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed)
  58 {
  59         const u64 m = 0xc6a4a7935bd1e995ULL;
  60         const int r = 47;
  61         u64 h = seed ^ (len * m);
  62
  63         const u64 *data = (const u64 *)key;
  64         const u64 *end = data + (len / 8);
  65
  66         while (data != end) {
  67                 u64 k;
  68                 memcpy(&k, data, sizeof(u64));
  69                 data++;
  70
  71                 k *= m;
  72                 k ^= k >> r;
  73                 k *= m;
  74
  75                 h ^= k;
  76                 h *= m;
  77         }
  78
  79         const unsigned char *data2 = (const unsigned char *)data;
  80         switch (len & 7) {
  81                 case 7: h ^= (u64)data2[6] << 48;
  82                 case 6: h ^= (u64)data2[5] << 40;
  83                 case 5: h ^= (u64)data2[4] << 32;
  84                 case 4: h ^= (u64)data2[3] << 24;
  85                 case 3: h ^= (u64)data2[2] << 16;
  86                 case 2: h ^= (u64)data2[1] << 8;
  87                 case 1: h ^= (u64)data2[0];
  88                                 h *= m;
  89         }
  90
  91         h ^= h >> r;
  92         h *= m;
  93         h ^= h >> r;
  94
  95         return h;
  96 }
  97
  98 /*
  99         blockpos_b: position of block in block coordinates
 100         camera_pos: position of camera in nodes
 101         camera_dir: an unit vector pointing to camera direction
 102         range: viewing range
 103         distance_ptr: return location for distance from the camera
 104 */
 105 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 106                 f32 camera_fov, f32 range, f32 *distance_ptr)
 107 {
 108         // Maximum radius of a block.  The magic number is
 109         // sqrt(3.0) / 2.0 in literal form.
 110         const f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS;
 111
 112         v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
 113
 114         // Block center position
 115         v3f blockpos(
 116                         ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
 117                         ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
 118                         ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
 119         );
 120
 121         // Block position relative to camera
 122         v3f blockpos_relative = blockpos - camera_pos;
 123
 124         // Total distance
 125         f32 d = MYMAX(0, blockpos_relative.getLength() - block_max_radius);
 126
 127         if(distance_ptr)
 128                 *distance_ptr = d;
 129
 130         // If block is far away, it's not in sight
 131         if(d > range)
 132                 return false;
 133
 134         // If block is (nearly) touching the camera, don't
 135         // bother validating further (that is, render it anyway)
 136         if(d == 0)
 137                 return true;
 138
 139         // Adjust camera position, for purposes of computing the angle,
 140         // such that a block that has any portion visible with the
 141         // current camera position will have the center visible at the
 142         // adjusted postion
 143         f32 adjdist = block_max_radius / cos((M_PI - camera_fov) / 2);
 144
 145         // Block position relative to adjusted camera
 146         v3f blockpos_adj = blockpos - (camera_pos - camera_dir * adjdist);
 147
 148         // Distance in camera direction (+=front, -=back)
 149         f32 dforward = blockpos_adj.dotProduct(camera_dir);
 150
 151         // Cosine of the angle between the camera direction
 152         // and the block direction (camera_dir is an unit vector)
 153         f32 cosangle = dforward / blockpos_adj.getLength();
 154
 155         // If block is not in the field of view, skip it
 156         // HOTFIX: use sligthly increased angle (+10%) to fix too agressive
 157         // culling. Somebody have to find out whats wrong with the math here.
 158         // Previous value: camera_fov / 2
 159         if(cosangle < cos(camera_fov * 0.55))
 160                 return false;
 161
 162         return true;
 163 }