X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fvoxel.h;h=58ad39be4a890d7f1fe6fe4ab1db6519dd4a024f;hb=9762650f978cc7bae78861b70a051b26cc5e2dc6;hp=eee9177f371cb7109ebce2b9a240606d31586c4c;hpb=af95cfc7a15788386d055a5b4a7377673d36b8bf;p=minetest.git

diff --git a/src/voxel.h b/src/voxel.h
index eee9177f3..58ad39be4 100644
--- a/src/voxel.h
+++ b/src/voxel.h
@@ -1,16 +1,57 @@
+/*
+Minetest
+Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+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 Lesser General Public License for more details.
+
+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.
+*/
+
 #ifndef VOXEL_HEADER
 #define VOXEL_HEADER
 
-#include "common_irrlicht.h"
-#include "mapblock.h"
+#include "irrlichttypes.h"
+#include "irr_v3d.h"
 #include <iostream>
+#include "debug.h"
+#include "exceptions.h"
+#include "mapnode.h"
+#include <set>
+#include <list>
+#include <map>
+
+class INodeDefManager;
+
+// For VC++
+#undef min
+#undef max
 
 /*
-	TODO: A fast voxel manipulator class
+	A fast voxel manipulator class.
+
+	In normal operation, it fetches more map when it is requested.
+	It can also be used so that all allowed area is fetched at the
+	start, using ManualMapVoxelManipulator.
 
 	Not thread-safe.
 */
 
+/*
+	Debug stuff
+*/
+extern u32 emerge_time;
+extern u32 emerge_load_time;
+
 /*
 	This class resembles aabbox3d<s16> a lot, but has inclusive
 	edges for saner handling of integer sizes
@@ -34,8 +75,18 @@ class VoxelArea
 		MaxEdge(p)
 	{
 	}
-	void addArea(VoxelArea &a)
+
+	/*
+		Modifying methods
+	*/
+
+	void addArea(const VoxelArea &a)
 	{
+		if (hasEmptyExtent())
+		{
+			*this = a;
+			return;
+		}
 		if(a.MinEdge.X < MinEdge.X) MinEdge.X = a.MinEdge.X;
 		if(a.MinEdge.Y < MinEdge.Y) MinEdge.Y = a.MinEdge.Y;
 		if(a.MinEdge.Z < MinEdge.Z) MinEdge.Z = a.MinEdge.Z;
@@ -43,8 +94,14 @@ class VoxelArea
 		if(a.MaxEdge.Y > MaxEdge.Y) MaxEdge.Y = a.MaxEdge.Y;
 		if(a.MaxEdge.Z > MaxEdge.Z) MaxEdge.Z = a.MaxEdge.Z;
 	}
-	void addPoint(v3s16 p)
+	void addPoint(const v3s16 &p)
 	{
+		if(hasEmptyExtent())
+		{
+			MinEdge = p;
+			MaxEdge = p;
+			return;
+		}
 		if(p.X < MinEdge.X) MinEdge.X = p.X;
 		if(p.Y < MinEdge.Y) MinEdge.Y = p.Y;
 		if(p.Z < MinEdge.Z) MinEdge.Z = p.Z;
@@ -52,16 +109,62 @@ class VoxelArea
 		if(p.Y > MaxEdge.Y) MaxEdge.Y = p.Y;
 		if(p.Z > MaxEdge.Z) MaxEdge.Z = p.Z;
 	}
-	v3s16 getExtent()
+
+	// Pad with d nodes
+	void pad(const v3s16 &d)
+	{
+		MinEdge -= d;
+		MaxEdge += d;
+	}
+
+	/*void operator+=(v3s16 off)
+	{
+		MinEdge += off;
+		MaxEdge += off;
+	}
+
+	void operator-=(v3s16 off)
+	{
+		MinEdge -= off;
+		MaxEdge -= off;
+	}*/
+
+	/*
+		const methods
+	*/
+
+	v3s16 getExtent() const
 	{
 		return MaxEdge - MinEdge + v3s16(1,1,1);
 	}
-	s32 getVolume()
+
+	/* Because MaxEdge and MinEdge are included in the voxel area an empty extent
+	 * is not represented by (0, 0, 0), but instead (-1, -1, -1)
+	 */
+	bool hasEmptyExtent() const
+	{
+		return MaxEdge - MinEdge == v3s16(-1, -1, -1);
+	}
+
+	s32 getVolume() const
 	{
 		v3s16 e = getExtent();
 		return (s32)e.X * (s32)e.Y * (s32)e.Z;
 	}
-	bool isInside(v3s16 p)
+	bool contains(const VoxelArea &a) const
+	{
+		// No area contains an empty area
+		// NOTE: Algorithms depend on this, so do not change.
+		if(a.hasEmptyExtent())
+			return false;
+
+		return(
+			a.MinEdge.X >= MinEdge.X && a.MaxEdge.X <= MaxEdge.X &&
+			a.MinEdge.Y >= MinEdge.Y && a.MaxEdge.Y <= MaxEdge.Y &&
+			a.MinEdge.Z >= MinEdge.Z && a.MaxEdge.Z <= MaxEdge.Z
+		);
+	}
+	bool contains(v3s16 p) const
 	{
 		return(
 			p.X >= MinEdge.X && p.X <= MaxEdge.X &&
@@ -69,16 +172,109 @@ class VoxelArea
 			p.Z >= MinEdge.Z && p.Z <= MaxEdge.Z
 		);
 	}
-	bool operator==(const VoxelArea &other)
+	bool contains(s32 i) const
+	{
+		return (i >= 0 && i < getVolume());
+	}
+	bool operator==(const VoxelArea &other) const
 	{
 		return (MinEdge == other.MinEdge
 				&& MaxEdge == other.MaxEdge);
 	}
-	
+
+	VoxelArea operator+(v3s16 off) const
+	{
+		return VoxelArea(MinEdge+off, MaxEdge+off);
+	}
+
+	VoxelArea operator-(v3s16 off) const
+	{
+		return VoxelArea(MinEdge-off, MaxEdge-off);
+	}
+
+	/*
+		Returns 0-6 non-overlapping areas that can be added to
+		a to make up this area.
+
+		a: area inside *this
+	*/
+	void diff(const VoxelArea &a, std::list<VoxelArea> &result)
+	{
+		/*
+			This can result in a maximum of 6 areas
+		*/
+
+		// If a is an empty area, return the current area as a whole
+		if(a.getExtent() == v3s16(0,0,0))
+		{
+			VoxelArea b = *this;
+			if(b.getVolume() != 0)
+				result.push_back(b);
+			return;
+		}
+
+		assert(contains(a));	// pre-condition
+
+		// Take back area, XY inclusive
+		{
+			v3s16 min(MinEdge.X, MinEdge.Y, a.MaxEdge.Z+1);
+			v3s16 max(MaxEdge.X, MaxEdge.Y, MaxEdge.Z);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+		// Take front area, XY inclusive
+		{
+			v3s16 min(MinEdge.X, MinEdge.Y, MinEdge.Z);
+			v3s16 max(MaxEdge.X, MaxEdge.Y, a.MinEdge.Z-1);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+		// Take top area, X inclusive
+		{
+			v3s16 min(MinEdge.X, a.MaxEdge.Y+1, a.MinEdge.Z);
+			v3s16 max(MaxEdge.X, MaxEdge.Y, a.MaxEdge.Z);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+		// Take bottom area, X inclusive
+		{
+			v3s16 min(MinEdge.X, MinEdge.Y, a.MinEdge.Z);
+			v3s16 max(MaxEdge.X, a.MinEdge.Y-1, a.MaxEdge.Z);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+		// Take left area, non-inclusive
+		{
+			v3s16 min(MinEdge.X, a.MinEdge.Y, a.MinEdge.Z);
+			v3s16 max(a.MinEdge.X-1, a.MaxEdge.Y, a.MaxEdge.Z);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+		// Take right area, non-inclusive
+		{
+			v3s16 min(a.MaxEdge.X+1, a.MinEdge.Y, a.MinEdge.Z);
+			v3s16 max(MaxEdge.X, a.MaxEdge.Y, a.MaxEdge.Z);
+			VoxelArea b(min, max);
+			if(b.getVolume() != 0)
+				result.push_back(b);
+		}
+
+	}
+
 	/*
 		Translates position from virtual coordinates to array index
 	*/
-	s32 index(s16 x, s16 y, s16 z)
+	s32 index(s16 x, s16 y, s16 z) const
 	{
 		v3s16 em = getExtent();
 		v3s16 off = MinEdge;
@@ -86,20 +282,46 @@ class VoxelArea
 		//dstream<<" i("<<x<<","<<y<<","<<z<<")="<<i<<" ";
 		return i;
 	}
-	s32 index(v3s16 p)
+	s32 index(v3s16 p) const
 	{
 		return index(p.X, p.Y, p.Z);
 	}
 
-	void print(std::ostream &o)
+	// Translate index in the X coordinate
+	void add_x(const v3s16 &extent, u32 &i, s16 a)
+	{
+		i += a;
+	}
+	// Translate index in the Y coordinate
+	void add_y(const v3s16 &extent, u32 &i, s16 a)
+	{
+		i += a * extent.X;
+	}
+	// Translate index in the Z coordinate
+	void add_z(const v3s16 &extent, u32 &i, s16 a)
+	{
+		i += a * extent.X*extent.Y;
+	}
+	// Translate index in space
+	void add_p(const v3s16 &extent, u32 &i, v3s16 a)
+	{
+		i += a.Z*extent.X*extent.Y + a.Y*extent.X + a.X;
+	}
+
+	/*
+		Print method for debugging
+	*/
+	void print(std::ostream &o) const
 	{
+		v3s16 e = getExtent();
 		o<<"("<<MinEdge.X
 		 <<","<<MinEdge.Y
 		 <<","<<MinEdge.Z
 		 <<")("<<MaxEdge.X
 		 <<","<<MaxEdge.Y
 		 <<","<<MaxEdge.Z
-		 <<")";
+		 <<")"
+		 <<"="<<e.X<<"x"<<e.Y<<"x"<<e.Z<<"="<<getVolume();
 	}
 
 	// Edges are inclusive
@@ -107,83 +329,234 @@ class VoxelArea
 	v3s16 MaxEdge;
 };
 
-class VoxelManipulator : public NodeContainer
+// unused 
+#define VOXELFLAG_UNUSED   (1<<0)
+// no data about that node
+#define VOXELFLAG_NO_DATA  (1<<1)
+// Algorithm-dependent
+#define VOXELFLAG_CHECKED1 (1<<2)
+// Algorithm-dependent
+#define VOXELFLAG_CHECKED2 (1<<3)
+// Algorithm-dependent
+#define VOXELFLAG_CHECKED3 (1<<4)
+// Algorithm-dependent
+#define VOXELFLAG_CHECKED4 (1<<5)
+
+enum VoxelPrintMode
+{
+	VOXELPRINT_NOTHING,
+	VOXELPRINT_MATERIAL,
+	VOXELPRINT_WATERPRESSURE,
+	VOXELPRINT_LIGHT_DAY,
+};
+
+class VoxelManipulator /*: public NodeContainer*/
 {
 public:
 	VoxelManipulator();
-	~VoxelManipulator();
-	
+	virtual ~VoxelManipulator();
+
 	/*
 		Virtuals from NodeContainer
 	*/
-	virtual u16 nodeContainerId() const
+	/*virtual u16 nodeContainerId() const
 	{
 		return NODECONTAINER_ID_VOXELMANIPULATOR;
 	}
 	bool isValidPosition(v3s16 p)
 	{
-		return m_area.isInside(p);
-	}
-	// These are a bit slow and shouldn't be used internally
+		addArea(p);
+		return !(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA);
+	}*/
+
+	/*
+		These are a bit slow and shouldn't be used internally.
+		Use m_data[m_area.index(p)] instead.
+	*/
 	MapNode getNode(v3s16 p)
 	{
-		if(isValidPosition(p) == false)
-			emerge(VoxelArea(p));
+		VoxelArea voxel_area(p);
+		addArea(voxel_area);
 
-		MapNode &n = m_data[m_area.index(p)];
-
-		//TODO: Is this the right behaviour?
-		if(n.d == MATERIAL_IGNORE)
+		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
+		{
+			/*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
+					<<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
+					<<", index="<<m_area.index(p)
+					<<", flags="<<(int)m_flags[m_area.index(p)]
+					<<" is inexistent"<<std::endl;*/
 			throw InvalidPositionException
-			("Not returning MATERIAL_IGNORE in VoxelManipulator");
+			("VoxelManipulator: getNode: inexistent");
+		}
 
-		return n;
+		return m_data[m_area.index(p)];
 	}
-	void setNode(v3s16 p, MapNode & n)
+	MapNode getNodeNoEx(v3s16 p)
 	{
-		if(isValidPosition(p) == false)
-			emerge(VoxelArea(p));
+		VoxelArea voxel_area(p);
+		addArea(voxel_area);
+
+		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
+		{
+			return MapNode(CONTENT_IGNORE);
+		}
+
+		return m_data[m_area.index(p)];
+	}
+	MapNode getNodeNoExNoEmerge(v3s16 p)
+	{
+		if(m_area.contains(p) == false)
+			return MapNode(CONTENT_IGNORE);
+		if(m_flags[m_area.index(p)] & VOXELFLAG_NO_DATA)
+			return MapNode(CONTENT_IGNORE);
+		return m_data[m_area.index(p)];
+	}
+	// Stuff explodes if non-emerged area is touched with this.
+	// Emerge first, and check VOXELFLAG_NO_DATA if appropriate.
+	MapNode & getNodeRefUnsafe(const v3s16 &p)
+	{
+		return m_data[m_area.index(p)];
+	}
+
+	const MapNode & getNodeRefUnsafeCheckFlags(const v3s16 &p)
+	{
+		s32 index = m_area.index(p);
+
+		if (m_flags[index] & VOXELFLAG_NO_DATA)
+			return ContentIgnoreNode;
+
+		return m_data[index];
+	}
+
+	u8 & getFlagsRefUnsafe(v3s16 p)
+	{
+		return m_flags[m_area.index(p)];
+	}
+	bool exists(v3s16 p)
+	{
+		return m_area.contains(p) &&
+			!(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA);
+	}
+	MapNode & getNodeRef(v3s16 p)
+	{
+		VoxelArea voxel_area(p);
+		addArea(voxel_area);
+		if(getFlagsRefUnsafe(p) & VOXELFLAG_NO_DATA)
+		{
+			/*dstream<<"EXCEPT: VoxelManipulator::getNode(): "
+					<<"p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"
+					<<", index="<<m_area.index(p)
+					<<", flags="<<(int)getFlagsRefUnsafe(p)
+					<<" is inexistent"<<std::endl;*/
+			throw InvalidPositionException
+			("VoxelManipulator: getNode: inexistent");
+		}
+		return getNodeRefUnsafe(p);
+	}
+	void setNode(v3s16 p, const MapNode &n)
+	{
+		VoxelArea voxel_area(p);
+		addArea(voxel_area);
+
 		m_data[m_area.index(p)] = n;
+		m_flags[m_area.index(p)] &= ~VOXELFLAG_NO_DATA;
 	}
-	
-	MapNode & operator[](v3s16 p)
+	// TODO: Should be removed and replaced with setNode
+	void setNodeNoRef(v3s16 p, const MapNode &n)
+	{
+		setNode(p, n);
+	}
+
+	/*void setExists(VoxelArea a)
+	{
+		addArea(a);
+		for(s32 z=a.MinEdge.Z; z<=a.MaxEdge.Z; z++)
+		for(s32 y=a.MinEdge.Y; y<=a.MaxEdge.Y; y++)
+		for(s32 x=a.MinEdge.X; x<=a.MaxEdge.X; x++)
+		{
+			m_flags[m_area.index(x,y,z)] &= ~VOXELFLAG_NO_DATA;
+		}
+	}*/
+
+	/*MapNode & operator[](v3s16 p)
 	{
 		//dstream<<"operator[] p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
 		if(isValidPosition(p) == false)
-			emerge(VoxelArea(p));
+			addArea(VoxelArea(p));
+
 		return m_data[m_area.index(p)];
+	}*/
+
+	/*
+		Set stuff if available without an emerge.
+		Return false if failed.
+		This is convenient but slower than playing around directly
+		with the m_data table with indices.
+	*/
+	bool setNodeNoEmerge(v3s16 p, MapNode n)
+	{
+		if(m_area.contains(p) == false)
+			return false;
+		m_data[m_area.index(p)] = n;
+		return true;
 	}
+	bool setNodeNoEmerge(s32 i, MapNode n)
+	{
+		if(m_area.contains(i) == false)
+			return false;
+		m_data[i] = n;
+		return true;
+	}
+	/*bool setContentNoEmerge(v3s16 p, u8 c)
+	{
+		if(isValidPosition(p) == false)
+			return false;
+		m_data[m_area.index(p)].d = c;
+	}*/
 
 	/*
-		Manipulation of bigger chunks
+		Control
 	*/
-	
-	void print(std::ostream &o);
-	
-	void addArea(VoxelArea area);
 
-	void interpolate(VoxelArea area);
+	virtual void clear();
+
+	void print(std::ostream &o, INodeDefManager *nodemgr,
+			VoxelPrintMode mode=VOXELPRINT_MATERIAL);
 
-	/*void blitFromNodeContainer
-			(v3s16 p_from, v3s16 p_to, v3s16 size, NodeContainer *c);
-	
-	void blitToNodeContainer
-			(v3s16 p_from, v3s16 p_to, v3s16 size, NodeContainer *c);*/
+	void addArea(const VoxelArea &area);
 
 	/*
-		Virtual functions
+		Copy data and set flags to 0
+		dst_area.getExtent() <= src_area.getExtent()
 	*/
-	
+	void copyFrom(MapNode *src, const VoxelArea& src_area,
+			v3s16 from_pos, v3s16 to_pos, v3s16 size);
+
+	// Copy data
+	void copyTo(MapNode *dst, const VoxelArea& dst_area,
+			v3s16 dst_pos, v3s16 from_pos, v3s16 size);
+
 	/*
-		Get the contents of the requested area from somewhere.
+		Algorithms
+	*/
 
-		If not found from source, add as MATERIAL_IGNORE.
+	void clearFlag(u8 flag);
+
+	// TODO: Move to voxelalgorithms.h
+
+	void unspreadLight(enum LightBank bank, v3s16 p, u8 oldlight,
+			std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
+	void unspreadLight(enum LightBank bank,
+			std::map<v3s16, u8> & from_nodes,
+			std::set<v3s16> & light_sources, INodeDefManager *nodemgr);
+
+	void spreadLight(enum LightBank bank, v3s16 p, INodeDefManager *nodemgr);
+	void spreadLight(enum LightBank bank,
+			std::set<v3s16> & from_nodes, INodeDefManager *nodemgr);
+
+	/*
+		Virtual functions
 	*/
-	virtual void emerge(VoxelArea a)
-	{
-		//dstream<<"emerge p=("<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;
-		addArea(a);
-	}
 
 	/*
 		Member variables
@@ -195,29 +568,31 @@ class VoxelManipulator : public NodeContainer
 		MaxEdge is 1 higher than maximum allowed position
 	*/
 	VoxelArea m_area;
+
 	/*
-		NULL if data size is 0
+		NULL if data size is 0 (extent (0,0,0))
 		Data is stored as [z*h*w + y*h + x]
-		Special data values:
-			MATERIAL_IGNORE: Unspecified node
 	*/
 	MapNode *m_data;
-private:
-};
 
-class Map;
+	/*
+		Flags of all nodes
+	*/
+	u8 *m_flags;
 
-class MapVoxelManipulator : public VoxelManipulator
-{
-public:
-	MapVoxelManipulator(Map *map);
+	static const MapNode ContentIgnoreNode;
 
-	virtual void emerge(VoxelArea a);
+	//TODO: Use these or remove them
+	//TODO: Would these make any speed improvement?
+	//bool m_pressure_route_valid;
+	//v3s16 m_pressure_route_surface;
 
-	void blitBack(core::map<v3s16, MapBlock*> & modified_blocks);
+	/*
+		Some settings
+	*/
+	//bool m_disable_water_climb;
 
 private:
-	Map *m_map;
 };
 
 #endif