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