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