X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fvoxel.cpp;h=e6d4bdcd22587d5bad6895f61e337f8df029f9bf;hb=00fc0babe0c6c5464fa9ffbc5a257b1e2aa93111;hp=fc3b4c428681ffa31f422acf79052e486f2dc70a;hpb=fc26dcdb19dd4e296d850714019ed7da1de0b021;p=oweals%2Fminetest.git diff --git a/src/voxel.cpp b/src/voxel.cpp index fc3b4c428..e6d4bdcd2 100644 --- a/src/voxel.cpp +++ b/src/voxel.cpp @@ -1,56 +1,173 @@ /* -Minetest-c55 -Copyright (C) 2010 celeron55, Perttu Ahola +Minetest +Copyright (C) 2013 celeron55, Perttu Ahola This program is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. +GNU Lesser General Public License for more details. -You should have received a copy of the GNU General Public License along +You should have received a copy of the GNU Lesser General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ #include "voxel.h" #include "map.h" +#include "gettime.h" +#include "nodedef.h" +#include "util/timetaker.h" +#include // memcpy, memset + +/* + Debug stuff +*/ +u32 addarea_time = 0; +u32 emerge_time = 0; +u32 emerge_load_time = 0; +u32 clearflag_time = 0; +//u32 getwaterpressure_time = 0; +//u32 spreadwaterpressure_time = 0; +u32 updateareawaterpressure_time = 0; +u32 flowwater_pre_time = 0; + VoxelManipulator::VoxelManipulator(): - m_data(NULL) + m_data(NULL), + m_flags(NULL) { } VoxelManipulator::~VoxelManipulator() { + clear(); if(m_data) delete[] m_data; + if(m_flags) + delete[] m_flags; +} + +void VoxelManipulator::clear() +{ + // Reset area to volume=0 + m_area = VoxelArea(); + if(m_data) + delete[] m_data; + m_data = NULL; + if(m_flags) + delete[] m_flags; + m_flags = NULL; +} + +void VoxelManipulator::print(std::ostream &o, INodeDefManager *ndef, + VoxelPrintMode mode) +{ + v3s16 em = m_area.getExtent(); + v3s16 of = m_area.MinEdge; + o<<"size: "<=m_area.MinEdge.Y; y--) + { + if(em.X >= 3 && em.Y >= 3) + { + if (y==m_area.MinEdge.Y+2) o<<"^ "; + else if(y==m_area.MinEdge.Y+1) o<<"| "; + else if(y==m_area.MinEdge.Y+0) o<<"y x-> "; + else o<<" "; + } + + for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++) + { + for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++) + { + u8 f = m_flags[m_area.index(x,y,z)]; + char c; + if(f & VOXELFLAG_NO_DATA) + c = 'N'; + else + { + c = 'X'; + MapNode n = m_data[m_area.index(x,y,z)]; + content_t m = n.getContent(); + u8 pr = n.param2; + if(mode == VOXELPRINT_MATERIAL) + { + if(m <= 9) + c = m + '0'; + } + else if(mode == VOXELPRINT_WATERPRESSURE) + { + if(ndef->get(m).isLiquid()) + { + c = 'w'; + if(pr <= 9) + c = pr + '0'; + } + else if(m == CONTENT_AIR) + { + c = ' '; + } + else + { + c = '#'; + } + } + else if(mode == VOXELPRINT_LIGHT_DAY) + { + if(ndef->get(m).light_source != 0) + c = 'S'; + else if(ndef->get(m).light_propagates == false) + c = 'X'; + else + { + u8 light = n.getLight(LIGHTBANK_DAY, ndef); + if(light < 10) + c = '0' + light; + else + c = 'a' + (light-10); + } + } + } + o<= 3 && em.Y >= 3) - { - if(y==m_area.MinEdge.Y+0) o<<"y x-> "; - if(y==m_area.MinEdge.Y+1) o<<"| "; - if(y==m_area.MinEdge.Y+2) o<<"V "; + /* The reason for this optimised code is that we're a member function + * and the data type/layout of m_data is know to us: it's stored as + * [z*h*w + y*h + x]. Therefore we can take the calls to m_area index + * (which performs the preceding mapping/indexing of m_data) out of the + * inner loop and calculate the next index as we're iterating to gain + * performance. + * + * src_step and dest_step is the amount required to be added to our index + * every time y increments. Because the destination area may be larger + * than the source area we need one additional variable (otherwise we could + * just continue adding dest_step as is done for the source data): dest_mod. + * dest_mod is the difference in size between a "row" in the source data + * and a "row" in the destination data (I am using the term row loosely + * and for illustrative purposes). E.g. + * + * src <-------------------->|'''''' dest mod '''''''' + * dest <---------------------------------------------> + * + * dest_mod (it's essentially a modulus) is added to the destination index + * after every full iteration of the y span. + * + * This method falls under the category "linear array and incrementing + * index". + */ + + s32 src_step = src_area.getExtent().X; + s32 dest_step = m_area.getExtent().X; + s32 dest_mod = m_area.index(to_pos.X, to_pos.Y, to_pos.Z + 1) + - m_area.index(to_pos.X, to_pos.Y, to_pos.Z) + - dest_step * size.Y; + + s32 i_src = src_area.index(from_pos.X, from_pos.Y, from_pos.Z); + s32 i_local = m_area.index(to_pos.X, to_pos.Y, to_pos.Z); + + for (s16 z = 0; z < size.Z; z++) { + for (s16 y = 0; y < size.Y; y++) { + memcpy(&m_data[i_local], &src[i_src], size.X * sizeof(*m_data)); + memset(&m_flags[i_local], 0, size.X); + i_src += src_step; + i_local += dest_step; } - - for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++) - { - for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++) - { - u8 m = m_data[m_area.index(x,y,z)].d; - char c = 'X'; - if(m == MATERIAL_IGNORE) - c = 'I'; - else if(m <= 9) - c = m + '0'; - o< buf(area.getVolume()); +/* + Algorithms + ----------------------------------------------------- +*/ - for(s32 z=area.MinEdge.Z; z<=area.MaxEdge.Z; z++) - for(s32 y=area.MinEdge.Y; y<=area.MaxEdge.Y; y++) - for(s32 x=area.MinEdge.X; x<=area.MaxEdge.X; x++) - { - v3s16 p(x,y,z); - - v3s16 dirs[] = { - v3s16(1,1,0), - v3s16(1,0,1), - v3s16(1,-1,0), - v3s16(1,0,-1), - v3s16(-1,1,0), - v3s16(-1,0,1), - v3s16(-1,-1,0), - v3s16(-1,0,-1), - }; - //const v3s16 *dirs = g_26dirs; - - s16 total = 0; - s16 airness = 0; - u8 m = MATERIAL_IGNORE; - - for(s16 i=0; i<8; i++) - //for(s16 i=0; i<26; i++) - { - v3s16 p2 = p + dirs[i]; +void VoxelManipulator::clearFlag(u8 flags) +{ + // 0-1ms on moderate area + TimeTaker timer("clearFlag", &clearflag_time); - MapNode &n = m_data[m_area.index(p2)]; - if(n.d == MATERIAL_IGNORE) - continue; + //v3s16 s = m_area.getExtent(); - airness += (n.d == MATERIAL_AIR) ? 1 : -1; - total++; + /*dstream<<"clearFlag clearing area of size " + <<""< -total/2 ? MATERIAL_AIR : m; - //buf[area.index(p)] = airness > -total ? MATERIAL_AIR : m; - //buf[area.index(p)] = airness >= -7 ? MATERIAL_AIR : m; + /*for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++) + for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++) + for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++) + { + u8 f = m_flags[m_area.index(x,y,z)]; + m_flags[m_area.index(x,y,z)] &= ~flags; + if(m_flags[m_area.index(x,y,z)] != f) + count++; + }*/ + + s32 volume = m_area.getVolume(); + for(s32 i=0; i & light_sources, INodeDefManager *nodemgr) { - VoxelArea a_to(p_to, p_to+size-v3s16(1,1,1)); - addArea(a_to); - for(s16 z=0; zgetNode(p_from + p); - m_data[m_area.index(p_to + p)] = n; - } - catch(InvalidPositionException &e) + // Get the position of the neighbor node + v3s16 n2pos = p + dirs[i]; + + u32 n2i = m_area.index(n2pos); + + if(m_flags[n2i] & VOXELFLAG_NO_DATA) + continue; + + MapNode &n2 = m_data[n2i]; + + /* + If the neighbor is dimmer than what was specified + as oldlight (the light of the previous node) + */ + u8 light2 = n2.getLight(bank, nodemgr); + if(light2 < oldlight) { + /* + And the neighbor is transparent and it has some light + */ + if(nodemgr->get(n2).light_propagates && light2 != 0) + { + /* + Set light to 0 and add to queue + */ + + n2.setLight(bank, 0, nodemgr); + + unspreadLight(bank, n2pos, light2, light_sources, nodemgr); + + /* + Remove from light_sources if it is there + NOTE: This doesn't happen nearly at all + */ + /*if(light_sources.find(n2pos)) + { + std::cout<<"Removed from light_sources"<getNode(p_from + p); - } - catch(InvalidPositionException &e) - { + else{ + light_sources.insert(n2pos); } - m_data[m_area.index(p_to + p)] = n;*/ } } -void VoxelManipulator::blitToNodeContainer - (v3s16 p_from, v3s16 p_to, v3s16 size, NodeContainer *c) +#if 1 +/* + Goes recursively through the neighbours of the node. + + Alters only transparent nodes. + + If the lighting of the neighbour is lower than the lighting of + the node was (before changing it to 0 at the step before), the + lighting of the neighbour is set to 0 and then the same stuff + repeats for the neighbour. + + The ending nodes of the routine are stored in light_sources. + This is useful when a light is removed. In such case, this + routine can be called for the light node and then again for + light_sources to re-light the area without the removed light. + + values of from_nodes are lighting values. +*/ +void VoxelManipulator::unspreadLight(enum LightBank bank, + std::map & from_nodes, + std::set & light_sources, INodeDefManager *nodemgr) { - for(s16 z=0; z::iterator j = from_nodes.begin(); + j != from_nodes.end(); ++j) { - v3s16 p(x,y,z); - try{ - MapNode &n = m_data[m_area.index(p_from + p)]; - if(n.d == MATERIAL_IGNORE) - continue; - c->setNode(p_to + p, n); - } - catch(InvalidPositionException &e) - { - } + unspreadLight(bank, j->first, j->second, light_sources, nodemgr); } } #endif +#if 0 /* - MapVoxelManipulator -*/ + Goes recursively through the neighbours of the node. + + Alters only transparent nodes. + + If the lighting of the neighbour is lower than the lighting of + the node was (before changing it to 0 at the step before), the + lighting of the neighbour is set to 0 and then the same stuff + repeats for the neighbour. + + The ending nodes of the routine are stored in light_sources. + This is useful when a light is removed. In such case, this + routine can be called for the light node and then again for + light_sources to re-light the area without the removed light. -MapVoxelManipulator::MapVoxelManipulator(Map *map) + values of from_nodes are lighting values. +*/ +void VoxelManipulator::unspreadLight(enum LightBank bank, + core::map & from_nodes, + core::map & light_sources) { - m_map = map; + v3s16 dirs[6] = { + v3s16(0,0,1), // back + v3s16(0,1,0), // top + v3s16(1,0,0), // right + v3s16(0,0,-1), // front + v3s16(0,-1,0), // bottom + v3s16(-1,0,0), // left + }; + + if(from_nodes.size() == 0) + return; + + core::map unlighted_nodes; + core::map::Iterator j; + j = from_nodes.getIterator(); + + for(; j.atEnd() == false; j++) + { + v3s16 pos = j.getNode()->getKey(); + + addArea(VoxelArea(pos - v3s16(1,1,1), pos + v3s16(1,1,1))); + + //MapNode &n = m_data[m_area.index(pos)]; + + u8 oldlight = j.getNode()->getValue(); + + // Loop through 6 neighbors + for(u16 i=0; i<6; i++) + { + // Get the position of the neighbor node + v3s16 n2pos = pos + dirs[i]; + + u32 n2i = m_area.index(n2pos); + + if(m_flags[n2i] & VOXELFLAG_NO_DATA) + continue; + + MapNode &n2 = m_data[n2i]; + + /* + If the neighbor is dimmer than what was specified + as oldlight (the light of the previous node) + */ + if(n2.getLight(bank, nodemgr) < oldlight) + { + /* + And the neighbor is transparent and it has some light + */ + if(nodemgr->get(n2).light_propagates && n2.getLight(bank, nodemgr) != 0) + { + /* + Set light to 0 and add to queue + */ + + u8 current_light = n2.getLight(bank, nodemgr); + n2.setLight(bank, 0); + + unlighted_nodes.insert(n2pos, current_light); + + /* + Remove from light_sources if it is there + NOTE: This doesn't happen nearly at all + */ + /*if(light_sources.find(n2pos)) + { + std::cout<<"Removed from light_sources"< 0) + unspreadLight(bank, unlighted_nodes, light_sources); } +#endif -void MapVoxelManipulator::emerge(VoxelArea a) +void VoxelManipulator::spreadLight(enum LightBank bank, v3s16 p, + INodeDefManager *nodemgr) { - v3s16 size = a.getExtent(); + const v3s16 dirs[6] = { + v3s16(0,0,1), // back + v3s16(0,1,0), // top + v3s16(1,0,0), // right + v3s16(0,0,-1), // front + v3s16(0,-1,0), // bottom + v3s16(-1,0,0), // left + }; - addArea(a); + VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1)); + addArea(voxel_area); - for(s16 z=0; zgetNode(a.MinEdge + p); - m_data[m_area.index(a.MinEdge + p)] = n; + // Get the position of the neighbor node + v3s16 n2pos = p + dirs[i]; + + u32 n2i = m_area.index(n2pos); + + if(m_flags[n2i] & VOXELFLAG_NO_DATA) + continue; + + MapNode &n2 = m_data[n2i]; + + u8 light2 = n2.getLight(bank, nodemgr); + + /* + If the neighbor is brighter than the current node, + add to list (it will light up this node on its turn) + */ + if(light2 > undiminish_light(oldlight)) + { + spreadLight(bank, n2pos, nodemgr); } - catch(InvalidPositionException &e) + /* + If the neighbor is dimmer than how much light this node + would spread on it, add to list + */ + if(light2 < newlight) { + if(nodemgr->get(n2).light_propagates) + { + n2.setLight(bank, newlight, nodemgr); + spreadLight(bank, n2pos, nodemgr); + } } } } -void MapVoxelManipulator::blitBack - (core::map & modified_blocks) +#if 0 +/* + Lights neighbors of from_nodes, collects all them and then + goes on recursively. + + NOTE: This is faster on small areas but will overflow the + stack on large areas. Thus it is not used. +*/ +void VoxelManipulator::spreadLight(enum LightBank bank, + core::map & from_nodes) { - /* - Initialize block cache - */ - v3s16 blockpos_last; - MapBlock *block = NULL; - bool block_checked_in_modified = false; + if(from_nodes.size() == 0) + return; - for(s32 z=m_area.MinEdge.Z; z<=m_area.MaxEdge.Z; z++) - for(s32 y=m_area.MinEdge.Y; y<=m_area.MaxEdge.Y; y++) - for(s32 x=m_area.MinEdge.X; x<=m_area.MaxEdge.X; x++) + core::map lighted_nodes; + core::map::Iterator j; + j = from_nodes.getIterator(); + + for(; j.atEnd() == false; j++) { - v3s16 p(x,y,z); + v3s16 pos = j.getNode()->getKey(); - MapNode &n = m_data[m_area.index(p)]; - if(n.d == MATERIAL_IGNORE) + spreadLight(bank, pos); + } +} +#endif + +#if 1 +/* + Lights neighbors of from_nodes, collects all them and then + goes on recursively. +*/ +void VoxelManipulator::spreadLight(enum LightBank bank, + std::set & from_nodes, INodeDefManager *nodemgr) +{ + const v3s16 dirs[6] = { + v3s16(0,0,1), // back + v3s16(0,1,0), // top + v3s16(1,0,0), // right + v3s16(0,0,-1), // front + v3s16(0,-1,0), // bottom + v3s16(-1,0,0), // left + }; + + if(from_nodes.size() == 0) + return; + + std::set lighted_nodes; + + for(std::set::iterator j = from_nodes.begin(); + j != from_nodes.end(); ++j) + { + v3s16 pos = *j; + + VoxelArea voxel_area(pos - v3s16(1,1,1), pos + v3s16(1,1,1)); + addArea(voxel_area); + + u32 i = m_area.index(pos); + + if(m_flags[i] & VOXELFLAG_NO_DATA) continue; - - v3s16 blockpos = getNodeBlockPos(p); - - try - { - // Get block - if(block == NULL || blockpos != blockpos_last){ - block = m_map->getBlockNoCreate(blockpos); - blockpos_last = blockpos; - block_checked_in_modified = false; - } - - // Calculate relative position in block - v3s16 relpos = p - blockpos * MAP_BLOCKSIZE; - // Don't continue if nothing has changed here - if(block->getNode(relpos) == n) - continue; + MapNode &n = m_data[i]; - //m_map->setNode(m_area.MinEdge + p, n); - block->setNode(relpos, n); - - /* - Make sure block is in modified_blocks - */ - if(block_checked_in_modified == false) + u8 oldlight = n.getLight(bank, nodemgr); + u8 newlight = diminish_light(oldlight); + + // Loop through 6 neighbors + for(u16 i=0; i<6; i++) + { + // Get the position of the neighbor node + v3s16 n2pos = pos + dirs[i]; + + try { - modified_blocks[blockpos] = block; - block_checked_in_modified = true; + u32 n2i = m_area.index(n2pos); + + if(m_flags[n2i] & VOXELFLAG_NO_DATA) + continue; + + MapNode &n2 = m_data[n2i]; + + u8 light2 = n2.getLight(bank, nodemgr); + + /* + If the neighbor is brighter than the current node, + add to list (it will light up this node on its turn) + */ + if(light2 > undiminish_light(oldlight)) + { + lighted_nodes.insert(n2pos); + } + /* + If the neighbor is dimmer than how much light this node + would spread on it, add to list + */ + if(light2 < newlight) + { + if(nodemgr->get(n2).light_propagates) + { + n2.setLight(bank, newlight, nodemgr); + lighted_nodes.insert(n2pos); + } + } + } + catch(InvalidPositionException &e) + { + continue; } - } - catch(InvalidPositionException &e) - { } } + + /*dstream<<"spreadLight(): Changed block " + < 0) + spreadLight(bank, lighted_nodes, nodemgr); } +#endif //END