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