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