src/voxel.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2013 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 Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser 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 #include "voxel.h"
  21 #include "map.h"
  22 #include "gettime.h"
  23 #include "nodedef.h"
  24 #include "util/timetaker.h"
  25 #include <string.h>  // memcpy, memset
  26
  27 /*
  28         Debug stuff
  29 */
  30 u32 addarea_time = 0;
  31 u32 emerge_time = 0;
  32 u32 emerge_load_time = 0;
  33 u32 clearflag_time = 0;
  34 //u32 getwaterpressure_time = 0;
  35 //u32 spreadwaterpressure_time = 0;
  36 u32 updateareawaterpressure_time = 0;
  37 u32 flowwater_pre_time = 0;
  38
  39
  40 VoxelManipulator::VoxelManipulator():
  41         m_data(NULL),
  42         m_flags(NULL)
  43 {
  44 }
  45
  46 VoxelManipulator::~VoxelManipulator()
  47 {
  48         clear();
  49 }
  50
  51 void VoxelManipulator::clear()
  52 {
  53         // Reset area to volume=0
  54         m_area = VoxelArea();
  55         delete[] m_data;
  56         m_data = NULL;
  57         delete[] m_flags;
  58         m_flags = NULL;
  59 }
  60
  61 void VoxelManipulator::print(std::ostream &o, INodeDefManager *ndef,
  62                 VoxelPrintMode mode)
  63 {
  64         v3s16 em = m_area.getExtent();
  65         v3s16 of = m_area.MinEdge;
  66         o<<"size: "<<em.X<<"x"<<em.Y<<"x"<<em.Z
  67          <<" offset: ("<<of.X<<","<<of.Y<<","<<of.Z<<")"<<std::endl;
  68
  69         for(s32 y=m_area.MaxEdge.Y; y>=m_area.MinEdge.Y; y--)
  70         {
  71                 if(em.X >= 3 && em.Y >= 3)
  72                 {
  73                         if     (y==m_area.MinEdge.Y+2) o<<"^     ";
  74                         else if(y==m_area.MinEdge.Y+1) o<<"|     ";
  75                         else if(y==m_area.MinEdge.Y+0) o<<"y x-> ";
  76                         else                           o<<"      ";
  77                 }
  78
  79                 for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
  80                 {
  81                         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
  82                         {
  83                                 u8 f = m_flags[m_area.index(x,y,z)];
  84                                 char c;
  85                                 if(f & VOXELFLAG_NO_DATA)
  86                                         c = 'N';
  87                                 else
  88                                 {
  89                                         c = 'X';
  90                                         MapNode n = m_data[m_area.index(x,y,z)];
  91                                         content_t m = n.getContent();
  92                                         u8 pr = n.param2;
  93                                         if(mode == VOXELPRINT_MATERIAL)
  94                                         {
  95                                                 if(m <= 9)
  96                                                         c = m + '0';
  97                                         }
  98                                         else if(mode == VOXELPRINT_WATERPRESSURE)
  99                                         {
 100                                                 if(ndef->get(m).isLiquid())
 101                                                 {
 102                                                         c = 'w';
 103                                                         if(pr <= 9)
 104                                                                 c = pr + '0';
 105                                                 }
 106                                                 else if(m == CONTENT_AIR)
 107                                                 {
 108                                                         c = ' ';
 109                                                 }
 110                                                 else
 111                                                 {
 112                                                         c = '#';
 113                                                 }
 114                                         }
 115                                         else if(mode == VOXELPRINT_LIGHT_DAY)
 116                                         {
 117                                                 if(ndef->get(m).light_source != 0)
 118                                                         c = 'S';
 119                                                 else if(ndef->get(m).light_propagates == false)
 120                                                         c = 'X';
 121                                                 else
 122                                                 {
 123                                                         u8 light = n.getLight(LIGHTBANK_DAY, ndef);
 124                                                         if(light < 10)
 125                                                                 c = '0' + light;
 126                                                         else
 127                                                                 c = 'a' + (light-10);
 128                                                 }
 129                                         }
 130                                 }
 131                                 o<<c;
 132                         }
 133                         o<<' ';
 134                 }
 135                 o<<std::endl;
 136         }
 137 }
 138
 139 void VoxelManipulator::addArea(const VoxelArea &area)
 140 {
 141         // Cancel if requested area has zero volume
 142         if (area.hasEmptyExtent())
 143                 return;
 144
 145         // Cancel if m_area already contains the requested area
 146         if(m_area.contains(area))
 147                 return;
 148
 149         TimeTaker timer("addArea", &addarea_time);
 150
 151         // Calculate new area
 152         VoxelArea new_area;
 153         // New area is the requested area if m_area has zero volume
 154         if(m_area.hasEmptyExtent())
 155         {
 156                 new_area = area;
 157         }
 158         // Else add requested area to m_area
 159         else
 160         {
 161                 new_area = m_area;
 162                 new_area.addArea(area);
 163         }
 164
 165         s32 new_size = new_area.getVolume();
 166
 167         /*dstream<<"adding area ";
 168         area.print(dstream);
 169         dstream<<", old area ";
 170         m_area.print(dstream);
 171         dstream<<", new area ";
 172         new_area.print(dstream);
 173         dstream<<", new_size="<<new_size;
 174         dstream<<std::endl;*/
 175
 176         // Allocate new data and clear flags
 177         MapNode *new_data = new MapNode[new_size];
 178         assert(new_data);
 179         u8 *new_flags = new u8[new_size];
 180         assert(new_flags);
 181         memset(new_flags, VOXELFLAG_NO_DATA, new_size);
 182
 183         // Copy old data
 184         s32 old_x_width = m_area.MaxEdge.X - m_area.MinEdge.X + 1;
 185         for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 186         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 187         {
 188                 unsigned int old_index = m_area.index(m_area.MinEdge.X,y,z);
 189                 unsigned int new_index = new_area.index(m_area.MinEdge.X,y,z);
 190
 191                 memcpy(&new_data[new_index], &m_data[old_index],
 192                                 old_x_width * sizeof(MapNode));
 193                 memcpy(&new_flags[new_index], &m_flags[old_index],
 194                                 old_x_width * sizeof(u8));
 195         }
 196
 197         // Replace area, data and flags
 198
 199         m_area = new_area;
 200
 201         MapNode *old_data = m_data;
 202         u8 *old_flags = m_flags;
 203
 204         /*dstream<<"old_data="<<(int)old_data<<", new_data="<<(int)new_data
 205         <<", old_flags="<<(int)m_flags<<", new_flags="<<(int)new_flags<<std::endl;*/
 206
 207         m_data = new_data;
 208         m_flags = new_flags;
 209
 210         delete[] old_data;
 211         delete[] old_flags;
 212
 213         //dstream<<"addArea done"<<std::endl;
 214 }
 215
 216 void VoxelManipulator::copyFrom(MapNode *src, const VoxelArea& src_area,
 217                 v3s16 from_pos, v3s16 to_pos, v3s16 size)
 218 {
 219         /* The reason for this optimised code is that we're a member function
 220          * and the data type/layout of m_data is know to us: it's stored as
 221          * [z*h*w + y*h + x]. Therefore we can take the calls to m_area index
 222          * (which performs the preceding mapping/indexing of m_data) out of the
 223          * inner loop and calculate the next index as we're iterating to gain
 224          * performance.
 225          *
 226          * src_step and dest_step is the amount required to be added to our index
 227          * every time y increments. Because the destination area may be larger
 228          * than the source area we need one additional variable (otherwise we could
 229          * just continue adding dest_step as is done for the source data): dest_mod.
 230          * dest_mod is the difference in size between a "row" in the source data
 231          * and a "row" in the destination data (I am using the term row loosely
 232          * and for illustrative purposes). E.g.
 233          *
 234          * src       <-------------------->|'''''' dest mod ''''''''
 235          * dest      <--------------------------------------------->
 236          *
 237          * dest_mod (it's essentially a modulus) is added to the destination index
 238          * after every full iteration of the y span.
 239          *
 240          * This method falls under the category "linear array and incrementing
 241          * index".
 242          */
 243
 244         s32 src_step = src_area.getExtent().X;
 245         s32 dest_step = m_area.getExtent().X;
 246         s32 dest_mod = m_area.index(to_pos.X, to_pos.Y, to_pos.Z + 1)
 247                         - m_area.index(to_pos.X, to_pos.Y, to_pos.Z)
 248                         - dest_step * size.Y;
 249
 250         s32 i_src = src_area.index(from_pos.X, from_pos.Y, from_pos.Z);
 251         s32 i_local = m_area.index(to_pos.X, to_pos.Y, to_pos.Z);
 252
 253         for (s16 z = 0; z < size.Z; z++) {
 254                 for (s16 y = 0; y < size.Y; y++) {
 255                         memcpy(&m_data[i_local], &src[i_src], size.X * sizeof(*m_data));
 256                         memset(&m_flags[i_local], 0, size.X);
 257                         i_src += src_step;
 258                         i_local += dest_step;
 259                 }
 260                 i_local += dest_mod;
 261         }
 262 }
 263
 264 void VoxelManipulator::copyTo(MapNode *dst, const VoxelArea& dst_area,
 265                 v3s16 dst_pos, v3s16 from_pos, v3s16 size)
 266 {
 267         for(s16 z=0; z<size.Z; z++)
 268         for(s16 y=0; y<size.Y; y++)
 269         {
 270                 s32 i_dst = dst_area.index(dst_pos.X, dst_pos.Y+y, dst_pos.Z+z);
 271                 s32 i_local = m_area.index(from_pos.X, from_pos.Y+y, from_pos.Z+z);
 272                 for (s16 x = 0; x < size.X; x++) {
 273                         if (m_data[i_local].getContent() != CONTENT_IGNORE)
 274                                 dst[i_dst] = m_data[i_local];
 275                         i_dst++;
 276                         i_local++;
 277                 }
 278         }
 279 }
 280
 281 /*
 282         Algorithms
 283         -----------------------------------------------------
 284 */
 285
 286 void VoxelManipulator::clearFlag(u8 flags)
 287 {
 288         // 0-1ms on moderate area
 289         TimeTaker timer("clearFlag", &clearflag_time);
 290
 291         //v3s16 s = m_area.getExtent();
 292
 293         /*dstream<<"clearFlag clearing area of size "
 294                         <<""<<s.X<<"x"<<s.Y<<"x"<<s.Z<<""
 295                         <<std::endl;*/
 296
 297         //s32 count = 0;
 298
 299         /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++)
 300         for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++)
 301         for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++)
 302         {
 303                 u8 f = m_flags[m_area.index(x,y,z)];
 304                 m_flags[m_area.index(x,y,z)] &= ~flags;
 305                 if(m_flags[m_area.index(x,y,z)] != f)
 306                         count++;
 307         }*/
 308
 309         s32 volume = m_area.getVolume();
 310         for(s32 i=0; i<volume; i++)
 311         {
 312                 m_flags[i] &= ~flags;
 313         }
 314
 315         /*s32 volume = m_area.getVolume();
 316         for(s32 i=0; i<volume; i++)
 317         {
 318                 u8 f = m_flags[i];
 319                 m_flags[i] &= ~flags;
 320                 if(m_flags[i] != f)
 321                         count++;
 322         }
 323
 324         dstream<<"clearFlag changed "<<count<<" flags out of "
 325                         <<volume<<" nodes"<<std::endl;*/
 326 }
 327
 328 void VoxelManipulator::unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
 329                 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
 330 {
 331         v3s16 dirs[6] = {
 332                 v3s16(0,0,1), // back
 333                 v3s16(0,1,0), // top
 334                 v3s16(1,0,0), // right
 335                 v3s16(0,0,-1), // front
 336                 v3s16(0,-1,0), // bottom
 337                 v3s16(-1,0,0), // left
 338         };
 339
 340         VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
 341         addArea(voxel_area);
 342
 343         // Loop through 6 neighbors
 344         for(u16 i=0; i<6; i++)
 345         {
 346                 // Get the position of the neighbor node
 347                 v3s16 n2pos = p + dirs[i];
 348
 349                 u32 n2i = m_area.index(n2pos);
 350
 351                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 352                         continue;
 353
 354                 MapNode &n2 = m_data[n2i];
 355
 356                 /*
 357                         If the neighbor is dimmer than what was specified
 358                         as oldlight (the light of the previous node)
 359                 */
 360                 u8 light2 = n2.getLight(bank, nodemgr);
 361                 if(light2 < oldlight)
 362                 {
 363                         /*
 364                                 And the neighbor is transparent and it has some light
 365                         */
 366                         if(nodemgr->get(n2).light_propagates && light2 != 0)
 367                         {
 368                                 /*
 369                                         Set light to 0 and add to queue
 370                                 */
 371
 372                                 n2.setLight(bank, 0, nodemgr);
 373
 374                                 unspreadLight(bank, n2pos, light2, light_sources, nodemgr);
 375
 376                                 /*
 377                                         Remove from light_sources if it is there
 378                                         NOTE: This doesn't happen nearly at all
 379                                 */
 380                                 /*if(light_sources.find(n2pos))
 381                                 {
 382                                         std::cout<<"Removed from light_sources"<<std::endl;
 383                                         light_sources.remove(n2pos);
 384                                 }*/
 385                         }
 386                 }
 387                 else{
 388                         light_sources.insert(n2pos);
 389                 }
 390         }
 391 }
 392
 393 /*
 394         Goes recursively through the neighbours of the node.
 395
 396         Alters only transparent nodes.
 397
 398         If the lighting of the neighbour is lower than the lighting of
 399         the node was (before changing it to 0 at the step before), the
 400         lighting of the neighbour is set to 0 and then the same stuff
 401         repeats for the neighbour.
 402
 403         The ending nodes of the routine are stored in light_sources.
 404         This is useful when a light is removed. In such case, this
 405         routine can be called for the light node and then again for
 406         light_sources to re-light the area without the removed light.
 407
 408         values of from_nodes are lighting values.
 409 */
 410 void VoxelManipulator::unspreadLight(enum LightBank bank,
 411                 std::map<v3s16, u8> & from_nodes,
 412                 std::set<v3s16> & light_sources, INodeDefManager *nodemgr)
 413 {
 414         if(from_nodes.empty())
 415                 return;
 416
 417         for(std::map<v3s16, u8>::iterator j = from_nodes.begin();
 418                 j != from_nodes.end(); ++j)
 419         {
 420                 unspreadLight(bank, j->first, j->second, light_sources, nodemgr);
 421         }
 422 }
 423
 424 void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p,
 425                 INodeDefManager *nodemgr)
 426 {
 427         const v3s16 dirs[6] = {
 428                 v3s16(0,0,1), // back
 429                 v3s16(0,1,0), // top
 430                 v3s16(1,0,0), // right
 431                 v3s16(0,0,-1), // front
 432                 v3s16(0,-1,0), // bottom
 433                 v3s16(-1,0,0), // left
 434         };
 435
 436         VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1));
 437         addArea(voxel_area);
 438
 439         u32 i = m_area.index(p);
 440
 441         if(m_flags[i] & VOXELFLAG_NO_DATA)
 442                 return;
 443
 444         MapNode &n = m_data[i];
 445
 446         u8 oldlight = n.getLight(bank, nodemgr);
 447         u8 newlight = diminish_light(oldlight);
 448
 449         // Loop through 6 neighbors
 450         for(u16 i=0; i<6; i++)
 451         {
 452                 // Get the position of the neighbor node
 453                 v3s16 n2pos = p + dirs[i];
 454
 455                 u32 n2i = m_area.index(n2pos);
 456
 457                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 458                         continue;
 459
 460                 MapNode &n2 = m_data[n2i];
 461
 462                 u8 light2 = n2.getLight(bank, nodemgr);
 463
 464                 /*
 465                         If the neighbor is brighter than the current node,
 466                         add to list (it will light up this node on its turn)
 467                 */
 468                 if(light2 > undiminish_light(oldlight))
 469                 {
 470                         spreadLight(bank, n2pos, nodemgr);
 471                 }
 472                 /*
 473                         If the neighbor is dimmer than how much light this node
 474                         would spread on it, add to list
 475                 */
 476                 if(light2 < newlight)
 477                 {
 478                         if(nodemgr->get(n2).light_propagates)
 479                         {
 480                                 n2.setLight(bank, newlight, nodemgr);
 481                                 spreadLight(bank, n2pos, nodemgr);
 482                         }
 483                 }
 484         }
 485 }
 486
 487
 488 const MapNode VoxelManipulator::ContentIgnoreNode = MapNode(CONTENT_IGNORE);
 489
 490 /*
 491         Lights neighbors of from_nodes, collects all them and then
 492         goes on recursively.
 493 */
 494 void VoxelManipulator::spreadLight(enum LightBank bank,
 495                 std::set<v3s16> & from_nodes, INodeDefManager *nodemgr)
 496 {
 497         const v3s16 dirs[6] = {
 498                 v3s16(0,0,1), // back
 499                 v3s16(0,1,0), // top
 500                 v3s16(1,0,0), // right
 501                 v3s16(0,0,-1), // front
 502                 v3s16(0,-1,0), // bottom
 503                 v3s16(-1,0,0), // left
 504         };
 505
 506         if(from_nodes.empty())
 507                 return;
 508
 509         std::set<v3s16> lighted_nodes;
 510
 511         for(std::set<v3s16>::iterator j = from_nodes.begin();
 512                 j != from_nodes.end(); ++j)
 513         {
 514                 v3s16 pos = *j;
 515
 516                 VoxelArea voxel_area(pos - v3s16(1,1,1), pos + v3s16(1,1,1));
 517                 addArea(voxel_area);
 518
 519                 u32 i = m_area.index(pos);
 520
 521                 if(m_flags[i] & VOXELFLAG_NO_DATA)
 522                         continue;
 523
 524                 MapNode &n = m_data[i];
 525
 526                 u8 oldlight = n.getLight(bank, nodemgr);
 527                 u8 newlight = diminish_light(oldlight);
 528
 529                 // Loop through 6 neighbors
 530                 for(u16 i=0; i<6; i++)
 531                 {
 532                         // Get the position of the neighbor node
 533                         v3s16 n2pos = pos + dirs[i];
 534
 535                         try
 536                         {
 537                                 u32 n2i = m_area.index(n2pos);
 538
 539                                 if(m_flags[n2i] & VOXELFLAG_NO_DATA)
 540                                         continue;
 541
 542                                 MapNode &n2 = m_data[n2i];
 543
 544                                 u8 light2 = n2.getLight(bank, nodemgr);
 545
 546                                 /*
 547                                         If the neighbor is brighter than the current node,
 548                                         add to list (it will light up this node on its turn)
 549                                 */
 550                                 if(light2 > undiminish_light(oldlight))
 551                                 {
 552                                         lighted_nodes.insert(n2pos);
 553                                 }
 554                                 /*
 555                                         If the neighbor is dimmer than how much light this node
 556                                         would spread on it, add to list
 557                                 */
 558                                 if(light2 < newlight)
 559                                 {
 560                                         if(nodemgr->get(n2).light_propagates)
 561                                         {
 562                                                 n2.setLight(bank, newlight, nodemgr);
 563                                                 lighted_nodes.insert(n2pos);
 564                                         }
 565                                 }
 566                         }
 567                         catch(InvalidPositionException &e)
 568                         {
 569                                 continue;
 570                         }
 571                 }
 572         }
 573
 574         /*dstream<<"spreadLight(): Changed block "
 575                         <<blockchangecount<<" times"
 576                         <<" for "<<from_nodes.size()<<" nodes"
 577                         <<std::endl;*/
 578
 579         if(!lighted_nodes.empty())
 580                 spreadLight(bank, lighted_nodes, nodemgr);
 581 }
 582
 583 //END