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