src/util/numeric.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010-2012 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 <iostream>
  25
  26 // Calculate the borders of a "d-radius" cube
  27 void getFacePositions(core::list<v3s16> &list, u16 d)
  28 {
  29         if(d == 0)
  30         {
  31                 list.push_back(v3s16(0,0,0));
  32                 return;
  33         }
  34         if(d == 1)
  35         {
  36                 /*
  37                         This is an optimized sequence of coordinates.
  38                 */
  39                 list.push_back(v3s16( 0, 1, 0)); // top
  40                 list.push_back(v3s16( 0, 0, 1)); // back
  41                 list.push_back(v3s16(-1, 0, 0)); // left
  42                 list.push_back(v3s16( 1, 0, 0)); // right
  43                 list.push_back(v3s16( 0, 0,-1)); // front
  44                 list.push_back(v3s16( 0,-1, 0)); // bottom
  45                 // 6
  46                 list.push_back(v3s16(-1, 0, 1)); // back left
  47                 list.push_back(v3s16( 1, 0, 1)); // back right
  48                 list.push_back(v3s16(-1, 0,-1)); // front left
  49                 list.push_back(v3s16( 1, 0,-1)); // front right
  50                 list.push_back(v3s16(-1,-1, 0)); // bottom left
  51                 list.push_back(v3s16( 1,-1, 0)); // bottom right
  52                 list.push_back(v3s16( 0,-1, 1)); // bottom back
  53                 list.push_back(v3s16( 0,-1,-1)); // bottom front
  54                 list.push_back(v3s16(-1, 1, 0)); // top left
  55                 list.push_back(v3s16( 1, 1, 0)); // top right
  56                 list.push_back(v3s16( 0, 1, 1)); // top back
  57                 list.push_back(v3s16( 0, 1,-1)); // top front
  58                 // 18
  59                 list.push_back(v3s16(-1, 1, 1)); // top back-left
  60                 list.push_back(v3s16( 1, 1, 1)); // top back-right
  61                 list.push_back(v3s16(-1, 1,-1)); // top front-left
  62                 list.push_back(v3s16( 1, 1,-1)); // top front-right
  63                 list.push_back(v3s16(-1,-1, 1)); // bottom back-left
  64                 list.push_back(v3s16( 1,-1, 1)); // bottom back-right
  65                 list.push_back(v3s16(-1,-1,-1)); // bottom front-left
  66                 list.push_back(v3s16( 1,-1,-1)); // bottom front-right
  67                 // 26
  68                 return;
  69         }
  70
  71         // Take blocks in all sides, starting from y=0 and going +-y
  72         for(s16 y=0; y<=d-1; y++)
  73         {
  74                 // Left and right side, including borders
  75                 for(s16 z=-d; z<=d; z++)
  76                 {
  77                         list.push_back(v3s16(d,y,z));
  78                         list.push_back(v3s16(-d,y,z));
  79                         if(y != 0)
  80                         {
  81                                 list.push_back(v3s16(d,-y,z));
  82                                 list.push_back(v3s16(-d,-y,z));
  83                         }
  84                 }
  85                 // Back and front side, excluding borders
  86                 for(s16 x=-d+1; x<=d-1; x++)
  87                 {
  88                         list.push_back(v3s16(x,y,d));
  89                         list.push_back(v3s16(x,y,-d));
  90                         if(y != 0)
  91                         {
  92                                 list.push_back(v3s16(x,-y,d));
  93                                 list.push_back(v3s16(x,-y,-d));
  94                         }
  95                 }
  96         }
  97
  98         // Take the bottom and top face with borders
  99         // -d<x<d, y=+-d, -d<z<d
 100         for(s16 x=-d; x<=d; x++)
 101         for(s16 z=-d; z<=d; z++)
 102         {
 103                 list.push_back(v3s16(x,-d,z));
 104                 list.push_back(v3s16(x,d,z));
 105         }
 106 }
 107
 108 /*
 109     myrand
 110 */
 111
 112 static unsigned long next = 1;
 113
 114 /* RAND_MAX assumed to be 32767 */
 115 int myrand(void)
 116 {
 117    next = next * 1103515245 + 12345;
 118    return((unsigned)(next/65536) % 32768);
 119 }
 120
 121 void mysrand(unsigned seed)
 122 {
 123    next = seed;
 124 }
 125
 126 int myrand_range(int min, int max)
 127 {
 128         if(max-min > MYRAND_MAX)
 129         {
 130                 errorstream<<"WARNING: myrand_range: max-min > MYRAND_MAX"<<std::endl;
 131         max = min + MYRAND_MAX;
 132         }
 133         if(min > max)
 134         {
 135                 errorstream<<"WARNING: myrand_range: min > max"<<std::endl;
 136                 return max;
 137         }
 138         return (myrand()%(max-min+1))+min;
 139 }
 140
 141 /*
 142         blockpos: position of block in block coordinates
 143         camera_pos: position of camera in nodes
 144         camera_dir: an unit vector pointing to camera direction
 145         range: viewing range
 146 */
 147 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir,
 148                 f32 camera_fov, f32 range, f32 *distance_ptr)
 149 {
 150         v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
 151
 152         // Block center position
 153         v3f blockpos(
 154                         ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
 155                         ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
 156                         ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
 157         );
 158
 159         // Block position relative to camera
 160         v3f blockpos_relative = blockpos - camera_pos;
 161
 162         // Distance in camera direction (+=front, -=back)
 163         f32 dforward = blockpos_relative.dotProduct(camera_dir);
 164
 165         // Total distance
 166         f32 d = blockpos_relative.getLength();
 167
 168         if(distance_ptr)
 169                 *distance_ptr = d;
 170
 171         // If block is very close, it is always in sight
 172         if(d < 1.44*1.44*MAP_BLOCKSIZE*BS/2)
 173                 return true;
 174
 175         // If block is far away, it's not in sight
 176         if(d > range)
 177                 return false;
 178
 179         // Maximum radius of a block
 180         f32 block_max_radius = 0.5*1.44*1.44*MAP_BLOCKSIZE*BS;
 181
 182         // If block is (nearly) touching the camera, don't
 183         // bother validating further (that is, render it anyway)
 184         if(d < block_max_radius)
 185                 return true;
 186
 187         // Cosine of the angle between the camera direction
 188         // and the block direction (camera_dir is an unit vector)
 189         f32 cosangle = dforward / d;
 190
 191         // Compensate for the size of the block
 192         // (as the block has to be shown even if it's a bit off FOV)
 193         // This is an estimate, plus an arbitary factor
 194         cosangle += block_max_radius / d * 0.5;
 195
 196         // If block is not in the field of view, skip it
 197         if(cosangle < cos(camera_fov / 2))
 198                 return false;
 199
 200         return true;
 201 }
 202