X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fvoxel.cpp;h=1299a5296da9c5eef0d25e243b6f2ca721f5e052;hb=7289d61e99625b46eb2c4d6b90a2a5de42f207e6;hp=fe176a27a7d55d0998432dff54af85f3f07bd92d;hpb=5e0c284f3a8debdd9ebb080f80e36dceb7bc4ce2;p=minetest.git diff --git a/src/voxel.cpp b/src/voxel.cpp index fe176a27a..1299a5296 100644 --- a/src/voxel.cpp +++ b/src/voxel.cpp @@ -1,24 +1,41 @@ /* -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), @@ -29,31 +46,26 @@ VoxelManipulator::VoxelManipulator(): 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; + delete[] m_data; m_data = NULL; - if(m_flags) - delete[] m_flags; + delete[] m_flags; m_flags = NULL; } -void VoxelManipulator::print(std::ostream &o) +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) @@ -70,16 +82,51 @@ void VoxelManipulator::print(std::ostream &o) { u8 f = m_flags[m_area.index(x,y,z)]; char c; - if(f & VOXELFLAG_NOT_LOADED) + if(f & VOXELFLAG_NO_DATA) c = 'N'; - else if(f & VOXELFLAG_INEXISTENT) - c = 'I'; else { c = 'X'; - u8 m = m_data[m_area.index(x,y,z)].d; - if(m <= 9) - c = m + '0'; + 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< buf(area.getVolume()); + /* 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; + } + i_local += dest_mod; + } +} - 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++) +void VoxelManipulator::copyTo(MapNode *dst, const VoxelArea& dst_area, + v3s16 dst_pos, v3s16 from_pos, v3s16 size) +{ + for(s16 z=0; z -total/2 ? MATERIAL_AIR : m; - //buf[area.index(p)] = airness > -total ? MATERIAL_AIR : m; - //buf[area.index(p)] = airness >= -7 ? MATERIAL_AIR : m; + //s32 count = 0; + + /*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) { v3s16 dirs[6] = { + v3s16(0,0,1), // back v3s16(0,1,0), // top - v3s16(-1,0,0), // left v3s16(1,0,0), // right v3s16(0,0,-1), // front - v3s16(0,0,1), // back v3s16(0,-1,0), // bottom + v3s16(-1,0,0), // left }; - v3s16 p; - - // Load neighboring nodes - // TODO: A bigger area would be better - emerge(VoxelArea(removed_pos - v3s16(1,1,1), removed_pos + v3s16(1,1,1))); + VoxelArea voxel_area(p - v3s16(1,1,1), p + v3s16(1,1,1)); + addArea(voxel_area); - s32 i; - for(i=0; i<6; i++) + // Loop through 6 neighbors + for(u16 i=0; i<6; i++) { - p = removed_pos + dirs[i]; - u8 f = m_flags[m_area.index(p)]; - // Inexistent or checked nodes can't move - if(f & (VOXELFLAG_INEXISTENT | VOXELFLAG_CHECKED)) - continue; - MapNode &n = m_data[m_area.index(p)]; - // Only liquid nodes can move - if(material_liquid(n.d) == false) + // 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; - // If block is at top, select it always - if(i == 0) - { - break; - } - // If block is at bottom, select it if it has enough pressure - if(i == 5) + + 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) { - if(n.pressure >= 3) - break; - continue; + /* + 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"<= 2) - { - break; + else{ + light_sources.insert(n2pos); } } +} + +#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. - // If there is nothing to move, return - if(i==6) + values of from_nodes are lighting values. +*/ +void VoxelManipulator::unspreadLight(enum LightBank bank, + std::map & from_nodes, + std::set & light_sources, INodeDefManager *nodemgr) +{ + if(from_nodes.empty()) return; - - // Switch nodes at p and removed_pos - MapNode n = m_data[m_area.index(p)]; - u8 f = m_flags[m_area.index(p)]; - m_data[m_area.index(p)] = m_data[m_area.index(removed_pos)]; - m_flags[m_area.index(p)] = m_flags[m_area.index(removed_pos)]; - m_data[m_area.index(removed_pos)] = n; - m_flags[m_area.index(removed_pos)] = f; - - // Mark p checked - m_flags[m_area.index(p)] |= VOXELFLAG_CHECKED; - - // Update pressure - //TODO - - // Flow water to the newly created empty position - flowWater(p); - - // Try flowing water to empty positions around removed_pos. - // They are checked in reverse order compared to the previous loop. - for(i=5; i>=0; i--) + + for(std::map::iterator j = from_nodes.begin(); + j != from_nodes.end(); ++j) { - p = removed_pos + dirs[i]; - u8 f = m_flags[m_area.index(p)]; - // Water can't move to inexistent nodes - if(f & VOXELFLAG_INEXISTENT) - continue; - MapNode &n = m_data[m_area.index(p)]; - // Water can only move to air - if(n.d != MATERIAL_AIR) - continue; - flowWater(p); + unspreadLight(bank, j->first, j->second, light_sources, nodemgr); } } +#endif +#if 0 /* - MapVoxelManipulator -*/ + Goes recursively through the neighbours of the node. -MapVoxelManipulator::MapVoxelManipulator(Map *map) + 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, + 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[i] = n; - m_flags[i] = 0; + + 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) { - m_flags[i] = VOXELFLAG_INEXISTENT; + 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) +{ + if(from_nodes.size() == 0) + return; + + core::map lighted_nodes; + core::map::Iterator j; + j = from_nodes.getIterator(); + + for(; j.atEnd() == false; j++) + { + v3s16 pos = j.getNode()->getKey(); + + 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) { - /* - Initialize block cache - */ - v3s16 blockpos_last; - MapBlock *block = NULL; - bool block_checked_in_modified = false; + 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 + }; - 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++) + if(from_nodes.empty()) + return; + + std::set lighted_nodes; + + for(std::set::iterator j = from_nodes.begin(); + j != from_nodes.end(); ++j) { - v3s16 p(x,y,z); + 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); - u8 f = m_flags[m_area.index(p)]; - if(f & (VOXELFLAG_NOT_LOADED|VOXELFLAG_INEXISTENT)) + if(m_flags[i] & VOXELFLAG_NO_DATA) continue; - MapNode &n = m_data[m_area.index(p)]; - - v3s16 blockpos = getNodeBlockPos(p); - - try + MapNode &n = m_data[i]; + + u8 oldlight = n.getLight(bank, nodemgr); + u8 newlight = diminish_light(oldlight); + + // Loop through 6 neighbors + for(u16 i=0; i<6; i++) { - // 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; + // Get the position of the neighbor node + v3s16 n2pos = pos + dirs[i]; - // Don't continue if nothing has changed here - if(block->getNode(relpos) == n) - continue; + try + { + u32 n2i = m_area.index(n2pos); - //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) + 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) { - modified_blocks[blockpos] = block; - block_checked_in_modified = true; + continue; } } - catch(InvalidPositionException &e) - { - } } + + /*dstream<<"spreadLight(): Changed block " + <