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