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 #include "mathconstants.h"
  22
  23 #include "log.h"
  24 #include "../constants.h" // BS, MAP_BLOCKSIZE
  25 #include "../noise.h" // PseudoRandom, PcgRandom
  26 #include "../threading/mutex_auto_lock.h"
  27 #include <string.h>
  28 #include <iostream>
  29
  30 UNORDERED_MAP<u16, std::vector<v3s16> > FacePositionCache::m_cache;
  31 Mutex FacePositionCache::m_cache_mutex;
  32 // Calculate the borders of a "d-radius" cube
  33 // TODO: Make it work without mutex and data races, probably thread-local
  34 std::vector<v3s16> FacePositionCache::getFacePositions(u16 d)
  35 {
  36         MutexAutoLock cachelock(m_cache_mutex);
  37         if (m_cache.find(d) != m_cache.end())
  38                 return m_cache[d];
  39
  40         generateFacePosition(d);
  41         return m_cache[d];
  42
  43 }
  44
  45 void FacePositionCache::generateFacePosition(u16 d)
  46 {
  47         m_cache[d] = std::vector<v3s16>();
  48         if(d == 0) {
  49                 m_cache[d].push_back(v3s16(0,0,0));
  50                 return;
  51         }
  52         if(d == 1) {
  53                 /*
  54                         This is an optimized sequence of coordinates.
  55                 */
  56                 m_cache[d].push_back(v3s16( 0, 1, 0)); // top
  57                 m_cache[d].push_back(v3s16( 0, 0, 1)); // back
  58                 m_cache[d].push_back(v3s16(-1, 0, 0)); // left
  59                 m_cache[d].push_back(v3s16( 1, 0, 0)); // right
  60                 m_cache[d].push_back(v3s16( 0, 0,-1)); // front
  61                 m_cache[d].push_back(v3s16( 0,-1, 0)); // bottom
  62                 // 6
  63                 m_cache[d].push_back(v3s16(-1, 0, 1)); // back left
  64                 m_cache[d].push_back(v3s16( 1, 0, 1)); // back right
  65                 m_cache[d].push_back(v3s16(-1, 0,-1)); // front left
  66                 m_cache[d].push_back(v3s16( 1, 0,-1)); // front right
  67                 m_cache[d].push_back(v3s16(-1,-1, 0)); // bottom left
  68                 m_cache[d].push_back(v3s16( 1,-1, 0)); // bottom right
  69                 m_cache[d].push_back(v3s16( 0,-1, 1)); // bottom back
  70                 m_cache[d].push_back(v3s16( 0,-1,-1)); // bottom front
  71                 m_cache[d].push_back(v3s16(-1, 1, 0)); // top left
  72                 m_cache[d].push_back(v3s16( 1, 1, 0)); // top right
  73                 m_cache[d].push_back(v3s16( 0, 1, 1)); // top back
  74                 m_cache[d].push_back(v3s16( 0, 1,-1)); // top front
  75                 // 18
  76                 m_cache[d].push_back(v3s16(-1, 1, 1)); // top back-left
  77                 m_cache[d].push_back(v3s16( 1, 1, 1)); // top back-right
  78                 m_cache[d].push_back(v3s16(-1, 1,-1)); // top front-left
  79                 m_cache[d].push_back(v3s16( 1, 1,-1)); // top front-right
  80                 m_cache[d].push_back(v3s16(-1,-1, 1)); // bottom back-left
  81                 m_cache[d].push_back(v3s16( 1,-1, 1)); // bottom back-right
  82                 m_cache[d].push_back(v3s16(-1,-1,-1)); // bottom front-left
  83                 m_cache[d].push_back(v3s16( 1,-1,-1)); // bottom front-right
  84                 // 26
  85                 return;
  86         }
  87
  88         // Take blocks in all sides, starting from y=0 and going +-y
  89         for(s16 y=0; y<=d-1; y++) {
  90                 // Left and right side, including borders
  91                 for(s16 z=-d; z<=d; z++) {
  92                         m_cache[d].push_back(v3s16(d,y,z));
  93                         m_cache[d].push_back(v3s16(-d,y,z));
  94                         if(y != 0) {
  95                                 m_cache[d].push_back(v3s16(d,-y,z));
  96                                 m_cache[d].push_back(v3s16(-d,-y,z));
  97                         }
  98                 }
  99                 // Back and front side, excluding borders
 100                 for(s16 x=-d+1; x<=d-1; x++) {
 101                         m_cache[d].push_back(v3s16(x,y,d));
 102                         m_cache[d].push_back(v3s16(x,y,-d));
 103                         if(y != 0) {
 104                                 m_cache[d].push_back(v3s16(x,-y,d));
 105                                 m_cache[d].push_back(v3s16(x,-y,-d));
 106                         }
 107                 }
 108         }
 109
 110         // Take the bottom and top face with borders
 111         // -d<x<d, y=+-d, -d<z<d
 112         for(s16 x=-d; x<=d; x++)
 113         for(s16 z=-d; z<=d; z++) {
 114                 m_cache[d].push_back(v3s16(x,-d,z));
 115                 m_cache[d].push_back(v3s16(x,d,z));
 116         }
 117 }
 118
 119 /*
 120     myrand
 121 */
 122
 123 PcgRandom g_pcgrand;
 124
 125 u32 myrand()
 126 {
 127         return g_pcgrand.next();
 128 }
 129
 130 void mysrand(unsigned int seed)
 131 {
 132         g_pcgrand.seed(seed);
 133 }
 134
 135 void myrand_bytes(void *out, size_t len)
 136 {
 137         g_pcgrand.bytes(out, len);
 138 }
 139
 140 int myrand_range(int min, int max)
 141 {
 142         return g_pcgrand.range(min, max);
 143 }
 144
 145
 146 /*
 147         64-bit unaligned version of MurmurHash
 148 */
 149 u64 murmur_hash_64_ua(const void *key, int len, unsigned int seed)
 150 {
 151         const u64 m = 0xc6a4a7935bd1e995ULL;
 152         const int r = 47;
 153         u64 h = seed ^ (len * m);
 154
 155         const u64 *data = (const u64 *)key;
 156         const u64 *end = data + (len / 8);
 157
 158         while (data != end) {
 159                 u64 k;
 160                 memcpy(&k, data, sizeof(u64));
 161                 data++;
 162
 163                 k *= m;
 164                 k ^= k >> r;
 165                 k *= m;
 166
 167                 h ^= k;
 168                 h *= m;
 169         }
 170
 171         const unsigned char *data2 = (const unsigned char *)data;
 172         switch (len & 7) {
 173                 case 7: h ^= (u64)data2[6] << 48;
 174                 case 6: h ^= (u64)data2[5] << 40;
 175                 case 5: h ^= (u64)data2[4] << 32;
 176                 case 4: h ^= (u64)data2[3] << 24;
 177                 case 3: h ^= (u64)data2[2] << 16;
 178                 case 2: h ^= (u64)data2[1] << 8;
 179                 case 1: h ^= (u64)data2[0];
 180                                 h *= m;
 181         }
 182
 183         h ^= h >> r;
 184         h *= m;
 185         h ^= h >> r;
 186
 187         return h;
 188 }
 189
 190 /*
 191         blockpos_b: position of block in block coordinates
 192         camera_pos: position of camera in nodes
 193         camera_dir: an unit vector pointing to camera direction
 194         range: viewing range
 195         distance_ptr: return location for distance from the camera
 196 */
 197 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 198                 f32 camera_fov, f32 range, f32 *distance_ptr)
 199 {
 200         // Maximum radius of a block.  The magic number is
 201         // sqrt(3.0) / 2.0 in literal form.
 202         const f32 block_max_radius = 0.866025403784 * MAP_BLOCKSIZE * BS;
 203
 204         v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
 205
 206         // Block center position
 207         v3f blockpos(
 208                         ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
 209                         ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
 210                         ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
 211         );
 212
 213         // Block position relative to camera
 214         v3f blockpos_relative = blockpos - camera_pos;
 215
 216         // Total distance
 217         f32 d = MYMAX(0, blockpos_relative.getLength() - block_max_radius);
 218
 219         if(distance_ptr)
 220                 *distance_ptr = d;
 221
 222         // If block is far away, it's not in sight
 223         if(d > range)
 224                 return false;
 225
 226         // If block is (nearly) touching the camera, don't
 227         // bother validating further (that is, render it anyway)
 228         if(d == 0)
 229                 return true;
 230
 231         // Adjust camera position, for purposes of computing the angle,
 232         // such that a block that has any portion visible with the
 233         // current camera position will have the center visible at the
 234         // adjusted postion
 235         f32 adjdist = block_max_radius / cos((M_PI - camera_fov) / 2);
 236
 237         // Block position relative to adjusted camera
 238         v3f blockpos_adj = blockpos - (camera_pos - camera_dir * adjdist);
 239
 240         // Distance in camera direction (+=front, -=back)
 241         f32 dforward = blockpos_adj.dotProduct(camera_dir);
 242
 243         // Cosine of the angle between the camera direction
 244         // and the block direction (camera_dir is an unit vector)
 245         f32 cosangle = dforward / blockpos_adj.getLength();
 246
 247         // If block is not in the field of view, skip it
 248         // HOTFIX: use sligthly increased angle (+10%) to fix too agressive
 249         // culling. Somebody have to find out whats wrong with the math here.
 250         // Previous value: camera_fov / 2
 251         if(cosangle < cos(camera_fov * 0.55))
 252                 return false;
 253
 254         return true;
 255 }