src/utility.cpp

   1 /*
   2 Minetest-c55
   3 Copyright (C) 2010 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 General Public License as published by
   7 the Free Software Foundation; either version 2 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 General Public License for more details.
  14
  15 You should have received a copy of the GNU 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 /*
  21 (c) 2010 Perttu Ahola <celeron55@gmail.com>
  22 */
  23
  24 #include "utility.h"
  25 #include "irrlichtwrapper.h"
  26 #include "gettime.h"
  27 #include "mapblock.h"
  28
  29 TimeTaker::TimeTaker(const char *name, u32 *result)
  30 {
  31         m_name = name;
  32         m_result = result;
  33         m_running = true;
  34         m_time1 = getTimeMs();
  35 }
  36
  37 u32 TimeTaker::stop(bool quiet)
  38 {
  39         if(m_running)
  40         {
  41                 u32 time2 = getTimeMs();
  42                 u32 dtime = time2 - m_time1;
  43                 if(m_result != NULL)
  44                 {
  45                         (*m_result) += dtime;
  46                 }
  47                 else
  48                 {
  49                         if(quiet == false)
  50                                 std::cout<<m_name<<" took "<<dtime<<"ms"<<std::endl;
  51                 }
  52                 m_running = false;
  53                 return dtime;
  54         }
  55         return 0;
  56 }
  57
  58 const v3s16 g_26dirs[26] =
  59 {
  60         // +right, +top, +back
  61         v3s16( 0, 0, 1), // back
  62         v3s16( 0, 1, 0), // top
  63         v3s16( 1, 0, 0), // right
  64         v3s16( 0, 0,-1), // front
  65         v3s16( 0,-1, 0), // bottom
  66         v3s16(-1, 0, 0), // left
  67         // 6
  68         v3s16(-1, 1, 0), // top left
  69         v3s16( 1, 1, 0), // top right
  70         v3s16( 0, 1, 1), // top back
  71         v3s16( 0, 1,-1), // top front
  72         v3s16(-1, 0, 1), // back left
  73         v3s16( 1, 0, 1), // back right
  74         v3s16(-1, 0,-1), // front left
  75         v3s16( 1, 0,-1), // front right
  76         v3s16(-1,-1, 0), // bottom left
  77         v3s16( 1,-1, 0), // bottom right
  78         v3s16( 0,-1, 1), // bottom back
  79         v3s16( 0,-1,-1), // bottom front
  80         // 18
  81         v3s16(-1, 1, 1), // top back-left
  82         v3s16( 1, 1, 1), // top back-right
  83         v3s16(-1, 1,-1), // top front-left
  84         v3s16( 1, 1,-1), // top front-right
  85         v3s16(-1,-1, 1), // bottom back-left
  86         v3s16( 1,-1, 1), // bottom back-right
  87         v3s16(-1,-1,-1), // bottom front-left
  88         v3s16( 1,-1,-1), // bottom front-right
  89         // 26
  90 };
  91
  92 static unsigned long next = 1;
  93
  94 /* RAND_MAX assumed to be 32767 */
  95 int myrand(void)
  96 {
  97    next = next * 1103515245 + 12345;
  98    return((unsigned)(next/65536) % 32768);
  99 }
 100
 101 void mysrand(unsigned seed)
 102 {
 103    next = seed;
 104 }
 105
 106 // Float with distance
 107 struct DFloat
 108 {
 109         float v;
 110         u32 d;
 111 };
 112
 113 float PointAttributeList::getInterpolatedFloat(v3s16 p)
 114 {
 115         const u32 near_wanted_count = 5;
 116         // Last is nearest, first is farthest
 117         core::list<DFloat> near;
 118
 119         for(core::list<PointWithAttr>::Iterator
 120                         i = m_points.begin();
 121                         i != m_points.end(); i++)
 122         {
 123                 PointWithAttr &pwa = *i;
 124                 u32 d = pwa.p.getDistanceFrom(p);
 125
 126                 DFloat df;
 127                 df.v = pwa.attr.getFloat();
 128                 df.d = d;
 129
 130                 // If near list is empty, add directly and continue
 131                 if(near.size() == 0)
 132                 {
 133                         near.push_back(df);
 134                         continue;
 135                 }
 136
 137                 // Get distance of farthest in near list
 138                 u32 near_d = 100000;
 139                 if(near.size() > 0)
 140                 {
 141                         core::list<DFloat>::Iterator i = near.begin();
 142                         near_d = i->d;
 143                 }
 144
 145                 /*
 146                         If point is closer than the farthest in the near list or
 147                         there are not yet enough points on the list
 148                 */
 149                 if(d < near_d || near.size() < near_wanted_count)
 150                 {
 151                         // Find the right place in the near list and put it there
 152
 153                         // Go from farthest to near in the near list
 154                         core::list<DFloat>::Iterator i = near.begin();
 155                         for(; i != near.end(); i++)
 156                         {
 157                                 // Stop when i is at the first nearer node
 158                                 if(i->d < d)
 159                                         break;
 160                         }
 161                         // Add df to before i
 162                         if(i == near.end())
 163                                 near.push_back(df);
 164                         else
 165                                 near.insert_before(i, df);
 166
 167                         // Keep near list at right size
 168                         if(near.size() > near_wanted_count)
 169                         {
 170                                 core::list<DFloat>::Iterator j = near.begin();
 171                                 near.erase(j);
 172                         }
 173                 }
 174         }
 175
 176         // Return if no values found
 177         if(near.size() == 0)
 178                 return 0.0;
 179
 180         /*
 181 20:58:29 < tejeez> joka pisteelle a += arvo / etäisyys^6; b += 1 / etäisyys^6; ja
 182 lopuks sit otetaan a/b
 183         */
 184
 185         float a = 0;
 186         float b = 0;
 187         for(core::list<DFloat>::Iterator i = near.begin();
 188                         i != near.end(); i++)
 189         {
 190                 if(i->d == 0)
 191                         return i->v;
 192
 193                 //float dd = pow((float)i->d, 6);
 194                 float dd = pow((float)i->d, 5);
 195                 float v = i->v;
 196                 //dstream<<"dd="<<dd<<", v="<<v<<std::endl;
 197                 a += v / dd;
 198                 b += 1 / dd;
 199         }
 200
 201         return a / b;
 202 }
 203
 204 #if 0
 205 float PointAttributeList::getInterpolatedFloat(v3s16 p)
 206 {
 207         const u32 near_wanted_count = 2;
 208         const u32 nearest_wanted_count = 2;
 209         // Last is near
 210         core::list<DFloat> near;
 211
 212         for(core::list<PointWithAttr>::Iterator
 213                         i = m_points.begin();
 214                         i != m_points.end(); i++)
 215         {
 216                 PointWithAttr &pwa = *i;
 217                 u32 d = pwa.p.getDistanceFrom(p);
 218
 219                 DFloat df;
 220                 df.v = pwa.attr.getFloat();
 221                 df.d = d;
 222
 223                 // If near list is empty, add directly and continue
 224                 if(near.size() == 0)
 225                 {
 226                         near.push_back(df);
 227                         continue;
 228                 }
 229
 230                 // Get distance of farthest in near list
 231                 u32 near_d = 100000;
 232                 if(near.size() > 0)
 233                 {
 234                         core::list<DFloat>::Iterator i = near.begin();
 235                         near_d = i->d;
 236                 }
 237
 238                 /*
 239                         If point is closer than the farthest in the near list or
 240                         there are not yet enough points on the list
 241                 */
 242                 if(d < near_d || near.size() < near_wanted_count)
 243                 {
 244                         // Find the right place in the near list and put it there
 245
 246                         // Go from farthest to near in the near list
 247                         core::list<DFloat>::Iterator i = near.begin();
 248                         for(; i != near.end(); i++)
 249                         {
 250                                 // Stop when i is at the first nearer node
 251                                 if(i->d < d)
 252                                         break;
 253                         }
 254                         // Add df to before i
 255                         if(i == near.end())
 256                                 near.push_back(df);
 257                         else
 258                                 near.insert_before(i, df);
 259
 260                         // Keep near list at right size
 261                         if(near.size() > near_wanted_count)
 262                         {
 263                                 core::list<DFloat>::Iterator j = near.begin();
 264                                 near.erase(j);
 265                         }
 266                 }
 267         }
 268
 269         // Return if no values found
 270         if(near.size() == 0)
 271                 return 0.0;
 272
 273         /*
 274                 Get nearest ones
 275         */
 276
 277         u32 nearest_count = nearest_wanted_count;
 278         if(nearest_count > near.size())
 279                 nearest_count = near.size();
 280         core::list<DFloat> nearest;
 281         {
 282                 core::list<DFloat>::Iterator i = near.getLast();
 283                 for(u32 j=0; j<nearest_count; j++)
 284                 {
 285                         nearest.push_front(*i);
 286                         i--;
 287                 }
 288         }
 289
 290         /*
 291                 TODO: Try this:
 292 20:58:29 < tejeez> joka pisteelle a += arvo / etäisyys^6; b += 1 / etäisyys^6; ja
 293 lopuks sit otetaan a/b
 294         */
 295
 296         /*
 297                 Get total distance to nearest points
 298         */
 299
 300         float nearest_d_sum = 0;
 301         for(core::list<DFloat>::Iterator i = nearest.begin();
 302                         i != nearest.end(); i++)
 303         {
 304                 nearest_d_sum += (float)i->d;
 305         }
 306
 307         /*
 308                 Interpolate a value between the first ones
 309         */
 310
 311         dstream<<"nearest.size()="<<nearest.size()<<std::endl;
 312
 313         float interpolated = 0;
 314
 315         for(core::list<DFloat>::Iterator i = nearest.begin();
 316                         i != nearest.end(); i++)
 317         {
 318                 float weight;
 319                 if(nearest_d_sum > 0.001)
 320                         weight = (float)i->d / nearest_d_sum;
 321                 else
 322                         weight = 1. / nearest.size();
 323                 /*dstream<<"i->d="<<i->d<<" nearest_d_sum="<<nearest_d_sum
 324                                 <<" weight="<<weight<<std::endl;*/
 325                 interpolated += weight * i->v;
 326         }
 327
 328         return interpolated;
 329 }
 330 #endif
 331
 332 /*
 333         blockpos: position of block in block coordinates
 334         camera_pos: position of camera in nodes
 335         camera_dir: an unit vector pointing to camera direction
 336         range: viewing range
 337 */
 338 bool isBlockInSight(v3s16 blockpos_b, v3f camera_pos, v3f camera_dir, f32 range)
 339 {
 340         v3s16 blockpos_nodes = blockpos_b * MAP_BLOCKSIZE;
 341
 342         // Block center position
 343         v3f blockpos(
 344                         ((float)blockpos_nodes.X + MAP_BLOCKSIZE/2) * BS,
 345                         ((float)blockpos_nodes.Y + MAP_BLOCKSIZE/2) * BS,
 346                         ((float)blockpos_nodes.Z + MAP_BLOCKSIZE/2) * BS
 347         );
 348
 349         // Block position relative to camera
 350         v3f blockpos_relative = blockpos - camera_pos;
 351
 352         // Distance in camera direction (+=front, -=back)
 353         f32 dforward = blockpos_relative.dotProduct(camera_dir);
 354
 355         // Total distance
 356         f32 d = blockpos_relative.getLength();
 357
 358         // If block is far away, it's not in sight
 359         if(d > range * BS)
 360                 return false;
 361
 362         // Maximum radius of a block
 363         f32 block_max_radius = 0.5*1.44*1.44*MAP_BLOCKSIZE*BS;
 364
 365         // If block is (nearly) touching the camera, don't
 366         // bother validating further (that is, render it anyway)
 367         if(d > block_max_radius * 1.5)
 368         {
 369                 // Cosine of the angle between the camera direction
 370                 // and the block direction (camera_dir is an unit vector)
 371                 f32 cosangle = dforward / d;
 372
 373                 // Compensate for the size of the block
 374                 // (as the block has to be shown even if it's a bit off FOV)
 375                 // This is an estimate.
 376                 cosangle += block_max_radius / dforward;
 377
 378                 // If block is not in the field of view, skip it
 379                 //if(cosangle < cos(FOV_ANGLE/2))
 380                 if(cosangle < cos(FOV_ANGLE/2. * 4./3.))
 381                         return false;
 382         }
 383
 384         return true;
 385 }
 386