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