code:
/*
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.
*/

#include "irrlichttypes_extrabloated.h"
#include "mapnode.h"
#include "porting.h"
#include "nodedef.h"
#include "map.h"
#include "content_mapnode.h" // For mapnode_translate_*_internal
#include "serialization.h" // For ser_ver_supported
#include "util/serialize.h"
#include "log.h"
#include "util/numeric.h"
#include <string>
#include <sstream>

static const Rotation wallmounted_to_rot[] = {
	ROTATE_0, ROTATE_180, ROTATE_90, ROTATE_270
};

static const u8 rot_to_wallmounted[] = {
	2, 4, 3, 5
};

/*
	MapNode
*/

// Create directly from a nodename
// If name is unknown, sets CONTENT_IGNORE
MapNode::MapNode(INodeDefManager *ndef, const std::string &name,
		u8 a_param1, u8 a_param2)
{
	content_t id = CONTENT_IGNORE;
	ndef->getId(name, id);
	param0 = id;
	param1 = a_param1;
	param2 = a_param2;
}

void MapNode::getColor(const ContentFeatures &f, video::SColor *color) const
{
	if (f.palette) {
		*color = (*f.palette)[param2];
		return;
	}
	*color = f.color;
}

void MapNode::setLight(enum LightBank bank, u8 a_light, const ContentFeatures &f)
{
	// If node doesn't contain light data, ignore this
	if(f.param_type != CPT_LIGHT)
		return;
	if(bank == LIGHTBANK_DAY)
	{
		param1 &= 0xf0;
		param1 |= a_light & 0x0f;
	}
	else if(bank == LIGHTBANK_NIGHT)
	{
		param1 &= 0x0f;
		param1 |= (a_light & 0x0f)<<4;
	}
	else
		assert("Invalid light bank" == NULL);
}

void MapNode::setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr)
{
	setLight(bank, a_light, nodemgr->get(*this));
}

bool MapNode::isLightDayNightEq(INodeDefManager *nodemgr) const
{
	const ContentFeatures &f = nodemgr->get(*this);
	bool isEqual;

	if (f.param_type == CPT_LIGHT) {
		u8 day   = MYMAX(f.light_source, param1 & 0x0f);
		u8 night = MYMAX(f.light_source, (param1 >> 4) & 0x0f);
		isEqual = day == night;
	} else {
		isEqual = true;
	}

	return isEqual;
}

u8 MapNode::getLight(enum LightBank bank, INodeDefManager *nodemgr) const
{
	// Select the brightest of [light source, propagated light]
	const ContentFeatures &f = nodemgr->get(*this);

	u8 light;
	if(f.param_type == CPT_LIGHT)
		light = bank == LIGHTBANK_DAY ? param1 & 0x0f : (param1 >> 4) & 0x0f;
	else
		light = 0;

	return MYMAX(f.light_source, light);
}

u8 MapNode::getLightRaw(enum LightBank bank, const ContentFeatures &f) const
{
	if(f.param_type == CPT_LIGHT)
		return bank == LIGHTBANK_DAY ? param1 & 0x0f : (param1 >> 4) & 0x0f;
	return 0;
}

u8 MapNode::getLightNoChecks(enum LightBank bank, const ContentFeatures *f) const
{
	return MYMAX(f->light_source,
	             bank == LIGHTBANK_DAY ? param1 & 0x0f : (param1 >> 4) & 0x0f);
}

bool MapNode::getLightBanks(u8 &lightday, u8 &lightnight, INodeDefManager *nodemgr) const
{
	// Select the brightest of [light source, propagated light]
	const ContentFeatures &f = nodemgr->get(*this);
	if(f.param_type == CPT_LIGHT)
	{
		lightday = param1 & 0x0f;
		lightnight = (param1>>4)&0x0f;
	}
	else
	{
		lightday = 0;
		lightnight = 0;
	}
	if(f.light_source > lightday)
		lightday = f.light_source;
	if(f.light_source > lightnight)
		lightnight = f.light_source;
	return f.param_type == CPT_LIGHT || f.light_source != 0;
}

u8 MapNode::getFaceDir(INodeDefManager *nodemgr) const
{
	const ContentFeatures &f = nodemgr->get(*this);
	if (f.param_type_2 == CPT2_FACEDIR ||
			f.param_type_2 == CPT2_COLORED_FACEDIR)
		return (getParam2() & 0x1F) % 24;
	return 0;
}

u8 MapNode::getWallMounted(INodeDefManager *nodemgr) const
{
	const ContentFeatures &f = nodemgr->get(*this);
	if (f.param_type_2 == CPT2_WALLMOUNTED ||
			f.param_type_2 == CPT2_COLORED_WALLMOUNTED)
		return getParam2() & 0x07;
	return 0;
}

v3s16 MapNode::getWallMountedDir(INodeDefManager *nodemgr) const
{
	switch(getWallMounted(nodemgr))
	{
	case 0: default: return v3s16(0,1,0);
	case 1: return v3s16(0,-1,0);
	case 2: return v3s16(1,0,0);
	case 3: return v3s16(-1,0,0);
	case 4: return v3s16(0,0,1);
	case 5: return v3s16(0,0,-1);
	}
}

void MapNode::rotateAlongYAxis(INodeDefManager *nodemgr, Rotation rot)
{
	ContentParamType2 cpt2 = nodemgr->get(*this).param_type_2;

	if (cpt2 == CPT2_FACEDIR || cpt2 == CPT2_COLORED_FACEDIR) {
		static const u8 rotate_facedir[24 * 4] = {
			// Table value = rotated facedir
			// Columns: 0, 90, 180, 270 degrees rotation around vertical axis
			// Rotation is anticlockwise as seen from above (+Y)

			0, 1, 2, 3,  // Initial facedir 0 to 3
			1, 2, 3, 0,
			2, 3, 0, 1,
			3, 0, 1, 2,

			4, 13, 10, 19,  // 4 to 7
			5, 14, 11, 16,
			6, 15, 8, 17,
			7, 12, 9, 18,

			8, 17, 6, 15,  // 8 to 11
			9, 18, 7, 12,
			10, 19, 4, 13,
			11, 16, 5, 14,

			12, 9, 18, 7,  // 12 to 15
			13, 10, 19, 4,
			14, 11, 16, 5,
			15, 8, 17, 6,

			16, 5, 14, 11,  // 16 to 19
			17, 6, 15, 8,
			18, 7, 12, 9,
			19, 4, 13, 10,

			20, 23, 22, 21,  // 20 to 23
			21, 20, 23, 22,
			22, 21, 20, 23,
			23, 22, 21, 20
		};
		u8 facedir = (param2 & 31) % 24;
		u8 index = facedir * 4 + rot;
		param2 &= ~31;
		param2 |= rotate_facedir[index];
	} else if (cpt2 == CPT2_WALLMOUNTED ||
			cpt2 == CPT2_COLORED_WALLMOUNTED) {
		u8 wmountface = (param2 & 7);
		if (wmountface <= 1)
			return;

		Rotation oldrot = wallmounted_to_rot[wmountface - 2];
		param2 &= ~7;
		param2 |= rot_to_wallmounted[(oldrot - rot) & 3];
	}
}

void transformNodeBox(const MapNode &n, const NodeBox &nodebox,
		INodeDefManager *nodemgr, std::vector<aabb3f> *p_boxes, u8 neighbors = 0)
{
	std::vector<aabb3f> &boxes = *p_boxes;

	if (nodebox.type == NODEBOX_FIXED || nodebox.type == NODEBOX_LEVELED) {
		const std::vector<aabb3f> &fixed = nodebox.fixed;
		int facedir = n.getFaceDir(nodemgr);
		u8 axisdir = facedir>>2;
		facedir&=0x03;
		for (aabb3f box : fixed) {
			if (nodebox.type == NODEBOX_LEVELED)
				box.MaxEdge.Y = (-0.5f + n.getLevel(nodemgr) / 64.0f) * BS;

			switch (axisdir) {
			case 0:
				if(facedir == 1)
				{
					box.MinEdge.rotateXZBy(-90);
					box.MaxEdge.rotateXZBy(-90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateXZBy(180);
					box.MaxEdge.rotateXZBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateXZBy(90);
					box.MaxEdge.rotateXZBy(90);
				}
				break;
			case 1: // z+
				box.MinEdge.rotateYZBy(90);
				box.MaxEdge.rotateYZBy(90);
				if(facedir == 1)
				{
					box.MinEdge.rotateXYBy(90);
					box.MaxEdge.rotateXYBy(90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateXYBy(180);
					box.MaxEdge.rotateXYBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateXYBy(-90);
					box.MaxEdge.rotateXYBy(-90);
				}
				break;
			case 2: //z-
				box.MinEdge.rotateYZBy(-90);
				box.MaxEdge.rotateYZBy(-90);
				if(facedir == 1)
				{
					box.MinEdge.rotateXYBy(-90);
					box.MaxEdge.rotateXYBy(-90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateXYBy(180);
					box.MaxEdge.rotateXYBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateXYBy(90);
					box.MaxEdge.rotateXYBy(90);
				}
				break;
			case 3:  //x+
				box.MinEdge.rotateXYBy(-90);
				box.MaxEdge.rotateXYBy(-90);
				if(facedir == 1)
				{
					box.MinEdge.rotateYZBy(90);
					box.MaxEdge.rotateYZBy(90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateYZBy(180);
					box.MaxEdge.rotateYZBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateYZBy(-90);
					box.MaxEdge.rotateYZBy(-90);
				}
				break;
			case 4:  //x-
				box.MinEdge.rotateXYBy(90);
				box.MaxEdge.rotateXYBy(90);
				if(facedir == 1)
				{
					box.MinEdge.rotateYZBy(-90);
					box.MaxEdge.rotateYZBy(-90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateYZBy(180);
					box.MaxEdge.rotateYZBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateYZBy(90);
					box.MaxEdge.rotateYZBy(90);
				}
				break;
			case 5:
				box.MinEdge.rotateXYBy(-180);
				box.MaxEdge.rotateXYBy(-180);
				if(facedir == 1)
				{
					box.MinEdge.rotateXZBy(90);
					box.MaxEdge.rotateXZBy(90);
				}
				else if(facedir == 2)
				{
					box.MinEdge.rotateXZBy(180);
					box.MaxEdge.rotateXZBy(180);
				}
				else if(facedir == 3)
				{
					box.MinEdge.rotateXZBy(-90);
					box.MaxEdge.rotateXZBy(-90);
				}
				break;
			default:
				break;
			}
			box.repair();
			boxes.push_back(box);
		}
	}
	else if(nodebox.type == NODEBOX_WALLMOUNTED)
	{
		v3s16 dir = n.getWallMountedDir(nodemgr);

		// top
		if(dir == v3s16(0,1,0))
		{
			boxes.push_back(nodebox.wall_top);
		}
		// bottom
		else if(dir == v3s16(0,-1,0))
		{
			boxes.push_back(nodebox.wall_bottom);
		}
		// side
		else
		{
			v3f vertices[2] =
			{
				nodebox.wall_side.MinEdge,
				nodebox.wall_side.MaxEdge
			};

			for(s32 i=0; i<2; i++)
			{
				if(dir == v3s16(-1,0,0))
					vertices[i].rotateXZBy(0);
				if(dir == v3s16(1,0,0))
					vertices[i].rotateXZBy(180);
				if(dir == v3s16(0,0,-1))
					vertices[i].rotateXZBy(90);
				if(dir == v3s16(0,0,1))
					vertices[i].rotateXZBy(-90);
			}

			aabb3f box = aabb3f(vertices[0]);
			box.addInternalPoint(vertices[1]);
			boxes.push_back(box);
		}
	}
	else if (nodebox.type == NODEBOX_CONNECTED)
	{
		size_t boxes_size = boxes.size();
		boxes_size += nodebox.fixed.size();
		if (neighbors & 1)
			boxes_size += nodebox.connect_top.size();
		if (neighbors & 2)
			boxes_size += nodebox.connect_bottom.size();
		if (neighbors & 4)
			boxes_size += nodebox.connect_front.size();
		if (neighbors & 8)
			boxes_size += nodebox.connect_left.size();
		if (neighbors & 16)
			boxes_size += nodebox.connect_back.size();
		if (neighbors & 32)
			boxes_size += nodebox.connect_right.size();
		boxes.reserve(boxes_size);

#define BOXESPUSHBACK(c) do { \
		for (std::vector<aabb3f>::const_iterator \
				it = (c).begin(); \
				it != (c).end(); ++it) \
			(boxes).push_back(*it); \
		} while (0)

		BOXESPUSHBACK(nodebox.fixed);

		if (neighbors & 1)
			BOXESPUSHBACK(nodebox.connect_top);
		if (neighbors & 2)
			BOXESPUSHBACK(nodebox.connect_bottom);
		if (neighbors & 4)
			BOXESPUSHBACK(nodebox.connect_front);
		if (neighbors & 8)
			BOXESPUSHBACK(nodebox.connect_left);
		if (neighbors & 16)
			BOXESPUSHBACK(nodebox.connect_back);
		if (neighbors & 32)
			BOXESPUSHBACK(nodebox.connect_right);
	}
	else // NODEBOX_REGULAR
	{
		boxes.push_back(aabb3f(-BS/2,-BS/2,-BS/2,BS/2,BS/2,BS/2));
	}
}

static inline void getNeighborConnectingFace(
	v3s16 p, INodeDefManager *nodedef,
	Map *map, MapNode n, u8 bitmask, u8 *neighbors)
{
	MapNode n2 = map->getNodeNoEx(p);
	if (nodedef->nodeboxConnects(n, n2, bitmask))
		*neighbors |= bitmask;
}

u8 MapNode::getNeighbors(v3s16 p, Map *map)
{
	INodeDefManager *nodedef=map->getNodeDefManager();
	u8 neighbors = 0;
	const ContentFeatures &f = nodedef->get(*this);
	// locate possible neighboring nodes to connect to
	if (f.drawtype == NDT_NODEBOX && f.node_box.type == NODEBOX_CONNECTED) {
		v3s16 p2 = p;

		p2.Y++;
		getNeighborConnectingFace(p2, nodedef, map, *this, 1, &neighbors);

		p2 = p;
		p2.Y--;
		getNeighborConnectingFace(p2, nodedef, map, *this, 2, &neighbors);

		p2 = p;
		p2.Z--;
		getNeighborConnectingFace(p2, nodedef, map, *this, 4, &neighbors);

		p2 = p;
		p2.X--;
		getNeighborConnectingFace(p2, nodedef, map, *this, 8, &neighbors);

		p2 = p;
		p2.Z++;
		getNeighborConnectingFace(p2, nodedef, map, *this, 16, &neighbors);

		p2 = p;
		p2.X++;
		getNeighborConnectingFace(p2, nodedef, map, *this, 32, &neighbors);
	}

	return neighbors;
}

void MapNode::getNodeBoxes(INodeDefManager *nodemgr, std::vector<aabb3f> *boxes, u8 neighbors)
{
	const ContentFeatures &f = nodemgr->get(*this);
	transformNodeBox(*this, f.node_box, nodemgr, boxes, neighbors);
}

void MapNode::getCollisionBoxes(INodeDefManager *nodemgr, std::vector<aabb3f> *boxes, u8 neighbors)
{
	const ContentFeatures &f = nodemgr->get(*this);
	if (f.collision_box.fixed.empty())
		transformNodeBox(*this, f.node_box, nodemgr, boxes, neighbors);
	else
		transformNodeBox(*this, f.collision_box, nodemgr, boxes, neighbors);
}

void MapNode::getSelectionBoxes(INodeDefManager *nodemgr, std::vector<aabb3f> *boxes, u8 neighbors)
{
	const ContentFeatures &f = nodemgr->get(*this);
	transformNodeBox(*this, f.selection_box, nodemgr, boxes, neighbors);
}

u8 MapNode::getMaxLevel(INodeDefManager *nodemgr) const
{
	const ContentFeatures &f = nodemgr->get(*this);
	// todo: after update in all games leave only if (f.param_type_2 ==
	if( f.liquid_type == LIQUID_FLOWING || f.param_type_2 == CPT2_FLOWINGLIQUID)
		return LIQUID_LEVEL_MAX;
	if(f.leveled || f.param_type_2 == CPT2_LEVELED)
		return LEVELED_MAX;
	return 0;
}

u8 MapNode::getLevel(INodeDefManager *nodemgr) const
{
	const ContentFeatures &f = nodemgr->get(*this);
	// todo: after update in all games leave only if (f.param_type_2 ==
	if(f.liquid_type == LIQUID_SOURCE)
		return LIQUID_LEVEL_SOURCE;
	if (f.param_type_2 == CPT2_FLOWINGLIQUID)
		return getParam2() & LIQUID_LEVEL_MASK;
	if(f.liquid_type == LIQUID_FLOWING) // can remove if all param_type_2 setted
		return getParam2() & LIQUID_LEVEL_MASK;
	if(f.leveled || f.param_type_2 == CPT2_LEVELED) {
		 u8 level = getParam2() & LEVELED_MASK;
		 if(level)
			return level;
		 if(f.leveled > LEVELED_MAX)
		 	return LEVELED_MAX;
		 return f.leveled; //default
	}
	return 0;
}

u8 MapNode::setLevel(INodeDefManager *nodemgr, s8 level)
{
	u8 rest = 0;
	if (level < 1) {
		setContent(CONTENT_AIR);
		return 0;
	}
	const ContentFeatures &f = nodemgr->get(*this);
	if (f.param_type_2 == CPT2_FLOWINGLIQUID
		|| f.liquid_type == LIQUID_FLOWING
		|| f.liquid_type == LIQUID_SOURCE) {
		if (level >= LIQUID_LEVEL_SOURCE) {
			rest = level - LIQUID_LEVEL_SOURCE;
			setContent(nodemgr->getId(f.liquid_alternative_source));
		} else {
			setContent(nodemgr->getId(f.liquid_alternative_flowing));
			setParam2(level & LIQUID_LEVEL_MASK);
		}
	} else if (f.leveled || f.param_type_2 == CPT2_LEVELED) {
		if (level > LEVELED_MAX) {
			rest = level - LEVELED_MAX;
			level = LEVELED_MAX;
		}
		setParam2(level & LEVELED_MASK);
	}
	return rest;
}

u8 MapNode::addLevel(INodeDefManager *nodemgr, s8 add)
{
	s8 level = getLevel(nodemgr);
	if (add == 0) level = 1;
	level += add;
	return setLevel(nodemgr, level);
}

u32 MapNode::serializedLength(u8 version)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapNode format not supported");

	if(version == 0)
		return 1;
	else if(version <= 9)
		return 2;
	else if(version <= 23)
		return 3;
	else
		return 4;
}
void MapNode::serialize(u8 *dest, u8 version)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapNode format not supported");

	// Can't do this anymore; we have 16-bit dynamically allocated node IDs
	// in memory; conversion just won't work in this direction.
	if(version < 24)
		throw SerializationError("MapNode::serialize: serialization to "
				"version < 24 not possible");

	writeU16(dest+0, param0);
	writeU8(dest+2, param1);
	writeU8(dest+3, param2);
}
void MapNode::deSerialize(u8 *source, u8 version)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapNode format not supported");

	if(version <= 21)
	{
		deSerialize_pre22(source, version);
		return;
	}

	if(version >= 24){
		param0 = readU16(source+0);
		param1 = readU8(source+2);
		param2 = readU8(source+3);
	}else{
		param0 = readU8(source+0);
		param1 = readU8(source+1);
		param2 = readU8(source+2);
		if(param0 > 0x7F){
			param0 |= ((param2&0xF0)<<4);
			param2 &= 0x0F;
		}
	}
}
void MapNode::serializeBulk(std::ostream &os, int version,
		const MapNode *nodes, u32 nodecount,
		u8 content_width, u8 params_width, bool compressed)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapNode format not supported");

	sanity_check(content_width == 2);
	sanity_check(params_width == 2);

	// Can't do this anymore; we have 16-bit dynamically allocated node IDs
	// in memory; conversion just won't work in this direction.
	if(version < 24)
		throw SerializationError("MapNode::serializeBulk: serialization to "
				"version < 24 not possible");

	SharedBuffer<u8> databuf(nodecount * (content_width + params_width));

	// Serialize content
	for(u32 i=0; i<nodecount; i++)
		writeU16(&databuf[i*2], nodes[i].param0);

	// Serialize param1
	u32 start1 = content_width * nodecount;
	for(u32 i=0; i<nodecount; i++)
		writeU8(&databuf[start1 + i], nodes[i].param1);

	// Serialize param2
	u32 start2 = (content_width + 1) * nodecount;
	for(u32 i=0; i<nodecount; i++)
		writeU8(&databuf[start2 + i], nodes[i].param2);

	/*
		Compress data to output stream
	*/

	if(compressed)
	{
		compressZlib(databuf, os);
	}
	else
	{
		os.write((const char*) &databuf[0], databuf.getSize());
	}
}

// Deserialize bulk node data
void MapNode::deSerializeBulk(std::istream &is, int version,
		MapNode *nodes, u32 nodecount,
		u8 content_width, u8 params_width, bool compressed)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapNode format not supported");

	if (version < 22
			|| (content_width != 1 && content_width != 2)
			|| params_width != 2)
		FATAL_ERROR("Deserialize bulk node data error");

	// Uncompress or read data
	u32 len = nodecount * (content_width + params_width);
	SharedBuffer<u8> databuf(len);
	if(compressed)
	{
		std::ostringstream os(std::ios_base::binary);
		decompressZlib(is, os);
		std::string s = os.str();
		if(s.size() != len)
			throw SerializationError("deSerializeBulkNodes: "
					"decompress resulted in invalid size");
		memcpy(&databuf[0], s.c_str(), len);
	}
	else
	{
		is.read((char*) &databuf[0], len);
		if(is.eof() || is.fail())
			throw SerializationError("deSerializeBulkNodes: "
					"failed to read bulk node data");
	}

	// Deserialize content
	if(content_width == 1)
	{
		for(u32 i=0; i<nodecount; i++)
			nodes[i].param0 = readU8(&databuf[i]);
	}
	else if(content_width == 2)
	{
		for(u32 i=0; i<nodecount; i++)
			nodes[i].param0 = readU16(&databuf[i*2]);
	}

	// Deserialize param1
	u32 start1 = content_width * nodecount;
	for(u32 i=0; i<nodecount; i++)
		nodes[i].param1 = readU8(&databuf[start1 + i]);

	// Deserialize param2
	u32 start2 = (content_width + 1) * nodecount;
	if(content_width == 1)
	{
		for(u32 i=0; i<nodecount; i++) {
			nodes[i].param2 = readU8(&databuf[start2 + i]);
			if(nodes[i].param0 > 0x7F){
				nodes[i].param0 <<= 4;
				nodes[i].param0 |= (nodes[i].param2&0xF0)>>4;
				nodes[i].param2 &= 0x0F;
			}
		}
	}
	else if(content_width == 2)
	{
		for(u32 i=0; i<nodecount; i++)
			nodes[i].param2 = readU8(&databuf[start2 + i]);
	}
}

/*
	Legacy serialization
*/
void MapNode::deSerialize_pre22(u8 *source, u8 version)
{
	if(version <= 1)
	{
		param0 = source[0];
	}
	else if(version <= 9)
	{
		param0 = source[0];
		param1 = source[1];
	}
	else
	{
		param0 = source[0];
		param1 = source[1];
		param2 = source[2];
		if(param0 > 0x7f){
			param0 <<= 4;
			param0 |= (param2&0xf0)>>4;
			param2 &= 0x0f;
		}
	}

	// Convert special values from old version to new
	if(version <= 19)
	{
		// In these versions, CONTENT_IGNORE and CONTENT_AIR
		// are 255 and 254
		// Version 19 is fucked up with sometimes the old values and sometimes not
		if(param0 == 255)
			param0 = CONTENT_IGNORE;
		else if(param0 == 254)
			param0 = CONTENT_AIR;
	}

	// Translate to our known version
	*this = mapnode_translate_to_internal(*this, version);
}


code:
/*
Minetest
Copyright (C) 2010-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 MAPNODE_HEADER
#define MAPNODE_HEADER

#include "irrlichttypes_bloated.h"
#include "light.h"
#include <string>
#include <vector>

class INodeDefManager;
class Map;

/*
	Naming scheme:
	- Material = irrlicht's Material class
	- Content = (content_t) content of a node
	- Tile = TileSpec at some side of a node of some content type
*/
typedef u16 content_t;

/*
	The maximum node ID that can be registered by mods. This must
	be significantly lower than the maximum content_t value, so that
	there is enough room for dummy node IDs, which are created when
	a MapBlock containing unknown node names is loaded from disk.
*/
#define MAX_REGISTERED_CONTENT 0x7fffU

/*
	A solid walkable node with the texture unknown_node.png.

	For example, used on the client to display unregistered node IDs
	(instead of expanding the vector of node definitions each time
	such a node is received).
*/
#define CONTENT_UNKNOWN 125

/*
	The common material through which the player can walk and which
	is transparent to light
*/
#define CONTENT_AIR 126

/*
	Ignored node.

	Unloaded chunks are considered to consist of this. Several other
	methods return this when an error occurs. Also, during
	map generation this means the node has not been set yet.

	Doesn't create faces with anything and is considered being
	out-of-map in the game map.
*/
#define CONTENT_IGNORE 127

enum LightBank
{
	LIGHTBANK_DAY,
	LIGHTBANK_NIGHT
};

/*
	Simple rotation enum.
*/
enum Rotation {
	ROTATE_0,
	ROTATE_90,
	ROTATE_180,
	ROTATE_270,
	ROTATE_RAND,
};

/*
	Masks for MapNode.param2 of flowing liquids
 */
#define LIQUID_LEVEL_MASK 0x07
#define LIQUID_FLOW_DOWN_MASK 0x08

//#define LIQUID_LEVEL_MASK 0x3f // better finite water
//#define LIQUID_FLOW_DOWN_MASK 0x40 // not used when finite water

/* maximum amount of liquid in a block */
#define LIQUID_LEVEL_MAX LIQUID_LEVEL_MASK
#define LIQUID_LEVEL_SOURCE (LIQUID_LEVEL_MAX+1)

#define LIQUID_INFINITY_MASK 0x80 //0b10000000

// mask for leveled nodebox param2
#define LEVELED_MASK 0x7F
#define LEVELED_MAX LEVELED_MASK

struct ContentFeatures;

/*
	This is the stuff what the whole world consists of.
*/

struct MapNode
{
	/*
		Main content
	*/
	u16 param0;

	/*
		Misc parameter. Initialized to 0.
		- For light_propagates() blocks, this is light intensity,
		  stored logarithmically from 0 to LIGHT_MAX.
		  Sunlight is LIGHT_SUN, which is LIGHT_MAX+1.
		  - Contains 2 values, day- and night lighting. Each takes 4 bits.
		- Uhh... well, most blocks have light or nothing in here.
	*/
	u8 param1;

	/*
		The second parameter. Initialized to 0.
		E.g. direction for torches and flowing water.
	*/
	u8 param2;

	MapNode()
	{ }

	MapNode(content_t content, u8 a_param1=0, u8 a_param2=0)
		: param0(content),
		  param1(a_param1),
		  param2(a_param2)
	{ }

	// Create directly from a nodename
	// If name is unknown, sets CONTENT_IGNORE
	MapNode(INodeDefManager *ndef, const std::string &name,
			u8 a_param1=0, u8 a_param2=0);

	bool operator==(const MapNode &other)
	{
		return (param0 == other.param0
				&& param1 == other.param1
				&& param2 == other.param2);
	}

	// To be used everywhere
	content_t getContent() const
	{
		return param0;
	}
	void setContent(content_t c)
	{
		param0 = c;
	}
	u8 getParam1() const
	{
		return param1;
	}
	void setParam1(u8 p)
	{
		param1 = p;
	}
	u8 getParam2() const
	{
		return param2;
	}
	void setParam2(u8 p)
	{
		param2 = p;
	}

	/*!
	 * Returns the color of the node.
	 *
	 * \param f content features of this node
	 * \param color output, contains the node's color.
	 */
	void getColor(const ContentFeatures &f, video::SColor *color) const;

	void setLight(enum LightBank bank, u8 a_light, const ContentFeatures &f);

	void setLight(enum LightBank bank, u8 a_light, INodeDefManager *nodemgr);

	/**
	 * Check if the light value for night differs from the light value for day.
	 *
	 * @return If the light values are equal, returns true; otherwise false
	 */
	bool isLightDayNightEq(INodeDefManager *nodemgr) const;

	u8 getLight(enum LightBank bank, INodeDefManager *nodemgr) const;

	/*!
	 * Returns the node's light level from param1.
	 * If the node emits light, it is ignored.
	 * \param f the ContentFeatures of this node.
	 */
	u8 getLightRaw(enum LightBank bank, const ContentFeatures &f) const;

	/**
	 * This function differs from getLight(enum LightBank bank, INodeDefManager *nodemgr)
	 * in that the ContentFeatures of the node in question are not retrieved by
	 * the function itself.  Thus, if you have already called nodemgr->get() to
	 * get the ContentFeatures you pass it to this function instead of the
	 * function getting ContentFeatures itself.  Since INodeDefManager::get()
	 * is relatively expensive this can lead to significant performance
	 * improvements in some situations.  Call this function if (and only if)
	 * you have already retrieved the ContentFeatures by calling
	 * INodeDefManager::get() for the node you're working with and the
	 * pre-conditions listed are true.
	 *
	 * @pre f != NULL
	 * @pre f->param_type == CPT_LIGHT
	 */
	u8 getLightNoChecks(LightBank bank, const ContentFeatures *f) const;

	bool getLightBanks(u8 &lightday, u8 &lightnight, INodeDefManager *nodemgr) const;

	// 0 <= daylight_factor <= 1000
	// 0 <= return value <= LIGHT_SUN
	u8 getLightBlend(u32 daylight_factor, INodeDefManager *nodemgr) const
	{
		u8 lightday = 0;
		u8 lightnight = 0;
		getLightBanks(lightday, lightnight, nodemgr);
		return blend_light(daylight_factor, lightday, lightnight);
	}

	u8 getFaceDir(INodeDefManager *nodemgr) const;
	u8 getWallMounted(INodeDefManager *nodemgr) const;
	v3s16 getWallMountedDir(INodeDefManager *nodemgr) const;

	void rotateAlongYAxis(INodeDefManager *nodemgr, Rotation rot);

	/*!
	 * Checks which neighbors does this node connect to.
	 *
	 * \param p coordinates of the node
	 */
	u8 getNeighbors(v3s16 p, Map *map);

	/*
		Gets list of node boxes (used for rendering (NDT_NODEBOX))
	*/
	void getNodeBoxes(INodeDefManager *nodemgr, std::vector<aabb3f> *boxes, u8 neighbors = 0);

	/*
		Gets list of selection boxes
	*/
	void getSelectionBoxes(INodeDefManager *nodemg, std::vector<aabb3f> *boxes, u8 neighbors = 0);

	/*
		Gets list of collision boxes
	*/
	void getCollisionBoxes(INodeDefManager *nodemgr, std::vector<aabb3f> *boxes, u8 neighbors = 0);

	/*
		Liquid helpers
	*/
	u8 getMaxLevel(INodeDefManager *nodemgr) const;
	u8 getLevel(INodeDefManager *nodemgr) const;
	u8 setLevel(INodeDefManager *nodemgr, s8 level = 1);
	u8 addLevel(INodeDefManager *nodemgr, s8 add = 1);

	/*
		Serialization functions
	*/

	static u32 serializedLength(u8 version);
	void serialize(u8 *dest, u8 version);
	void deSerialize(u8 *source, u8 version);

	// Serializes or deserializes a list of nodes in bulk format (first the
	// content of all nodes, then the param1 of all nodes, then the param2
	// of all nodes).
	//   version = serialization version. Must be >= 22
	//   content_width = the number of bytes of content per node
	//   params_width = the number of bytes of params per node
	//   compressed = true to zlib-compress output
	static void serializeBulk(std::ostream &os, int version,
			const MapNode *nodes, u32 nodecount,
			u8 content_width, u8 params_width, bool compressed);
	static void deSerializeBulk(std::istream &is, int version,
			MapNode *nodes, u32 nodecount,
			u8 content_width, u8 params_width, bool compressed);

private:
	// Deprecated serialization methods
	void deSerialize_pre22(u8 *source, u8 version);
};

#endif

repo_name: pgimeno/minetest

license: unknown


code:
/*
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.
*/

#include "mapsector.h"
#include "exceptions.h"
#include "mapblock.h"
#include "serialization.h"

MapSector::MapSector(Map *parent, v2s16 pos, IGameDef *gamedef):
		differs_from_disk(false),
		m_parent(parent),
		m_pos(pos),
		m_gamedef(gamedef),
		m_block_cache(NULL)
{
}

MapSector::~MapSector()
{
	deleteBlocks();
}

void MapSector::deleteBlocks()
{
	// Clear cache
	m_block_cache = NULL;

	// Delete all
	for (UNORDERED_MAP<s16, MapBlock*>::iterator i = m_blocks.begin();
		 	i != m_blocks.end(); ++i) {
		delete i->second;
	}

	// Clear container
	m_blocks.clear();
}

MapBlock * MapSector::getBlockBuffered(s16 y)
{
	MapBlock *block;

	if (m_block_cache != NULL && y == m_block_cache_y) {
		return m_block_cache;
	}

	// If block doesn't exist, return NULL
	UNORDERED_MAP<s16, MapBlock*>::iterator n = m_blocks.find(y);
	block = (n != m_blocks.end() ? n->second : NULL);

	// Cache the last result
	m_block_cache_y = y;
	m_block_cache = block;

	return block;
}

MapBlock * MapSector::getBlockNoCreateNoEx(s16 y)
{
	return getBlockBuffered(y);
}

MapBlock * MapSector::createBlankBlockNoInsert(s16 y)
{
	assert(getBlockBuffered(y) == NULL);	// Pre-condition

	v3s16 blockpos_map(m_pos.X, y, m_pos.Y);

	MapBlock *block = new MapBlock(m_parent, blockpos_map, m_gamedef);

	return block;
}

MapBlock * MapSector::createBlankBlock(s16 y)
{
	MapBlock *block = createBlankBlockNoInsert(y);

	m_blocks[y] = block;

	return block;
}

void MapSector::insertBlock(MapBlock *block)
{
	s16 block_y = block->getPos().Y;

	MapBlock *block2 = getBlockBuffered(block_y);
	if(block2 != NULL){
		throw AlreadyExistsException("Block already exists");
	}

	v2s16 p2d(block->getPos().X, block->getPos().Z);
	assert(p2d == m_pos);

	// Insert into container
	m_blocks[block_y] = block;
}

void MapSector::deleteBlock(MapBlock *block)
{
	s16 block_y = block->getPos().Y;

	// Clear from cache
	m_block_cache = NULL;

	// Remove from container
	m_blocks.erase(block_y);

	// Delete
	delete block;
}

void MapSector::getBlocks(MapBlockVect &dest)
{
	for (UNORDERED_MAP<s16, MapBlock*>::iterator bi = m_blocks.begin();
		bi != m_blocks.end(); ++bi) {
		dest.push_back(bi->second);
	}
}

/*
	ServerMapSector
*/

ServerMapSector::ServerMapSector(Map *parent, v2s16 pos, IGameDef *gamedef):
		MapSector(parent, pos, gamedef)
{
}

ServerMapSector::~ServerMapSector()
{
}

void ServerMapSector::serialize(std::ostream &os, u8 version)
{
	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapSector format not supported");

	/*
		[0] u8 serialization version
		+ heightmap data
	*/

	// Server has both of these, no need to support not having them.
	//assert(m_objects != NULL);

	// Write version
	os.write((char*)&version, 1);

	/*
		Add stuff here, if needed
	*/

}

ServerMapSector* ServerMapSector::deSerialize(
		std::istream &is,
		Map *parent,
		v2s16 p2d,
		std::map<v2s16, MapSector*> & sectors,
		IGameDef *gamedef
	)
{
	/*
		[0] u8 serialization version
		+ heightmap data
	*/

	/*
		Read stuff
	*/

	// Read version
	u8 version = SER_FMT_VER_INVALID;
	is.read((char*)&version, 1);

	if(!ser_ver_supported(version))
		throw VersionMismatchException("ERROR: MapSector format not supported");

	/*
		Add necessary reading stuff here
	*/

	/*
		Get or create sector
	*/

	ServerMapSector *sector = NULL;

	std::map<v2s16, MapSector*>::iterator n = sectors.find(p2d);

	if(n != sectors.end())
	{
		warningstream<<"deSerializing existent sectors not supported "
				"at the moment, because code hasn't been tested."
				<<std::endl;

		MapSector *sector = n->second;
		assert(sector->getId() == MAPSECTOR_SERVER);
		return (ServerMapSector*)sector;
	}
	else
	{
		sector = new ServerMapSector(parent, p2d, gamedef);
		sectors[p2d] = sector;
	}

	/*
		Set stuff in sector
	*/

	// Nothing here

	return sector;
}

#ifndef SERVER
/*
	ClientMapSector
*/

ClientMapSector::ClientMapSector(Map *parent, v2s16 pos, IGameDef *gamedef):
		MapSector(parent, pos, gamedef)
{
}

ClientMapSector::~ClientMapSector()
{
}

#endif // !SERVER

//END


code:
/*
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 MAPSECTOR_HEADER
#define MAPSECTOR_HEADER

#include "irrlichttypes.h"
#include "irr_v2d.h"
#include "mapblock.h"
#include <ostream>
#include <map>
#include <vector>

class Map;
class IGameDef;

/*
	This is an Y-wise stack of MapBlocks.
*/

#define MAPSECTOR_SERVER 0
#define MAPSECTOR_CLIENT 1

class MapSector
{
public:

	MapSector(Map *parent, v2s16 pos, IGameDef *gamedef);
	virtual ~MapSector();

	virtual u32 getId() const = 0;

	void deleteBlocks();

	v2s16 getPos()
	{
		return m_pos;
	}

	MapBlock * getBlockNoCreateNoEx(s16 y);
	MapBlock * createBlankBlockNoInsert(s16 y);
	MapBlock * createBlankBlock(s16 y);

	void insertBlock(MapBlock *block);

	void deleteBlock(MapBlock *block);

	void getBlocks(MapBlockVect &dest);

	bool empty() const { return m_blocks.empty(); }

	// Always false at the moment, because sector contains no metadata.
	bool differs_from_disk;

protected:

	// The pile of MapBlocks
	UNORDERED_MAP<s16, MapBlock*> m_blocks;

	Map *m_parent;
	// Position on parent (in MapBlock widths)
	v2s16 m_pos;

	IGameDef *m_gamedef;

	// Last-used block is cached here for quicker access.
	// Be sure to set this to NULL when the cached block is deleted
	MapBlock *m_block_cache;
	s16 m_block_cache_y;

	/*
		Private methods
	*/
	MapBlock *getBlockBuffered(s16 y);

};

class ServerMapSector : public MapSector
{
public:
	ServerMapSector(Map *parent, v2s16 pos, IGameDef *gamedef);
	~ServerMapSector();

	u32 getId() const
	{
		return MAPSECTOR_SERVER;
	}

	/*
		These functions handle metadata.
		They do not handle blocks.
	*/

	void serialize(std::ostream &os, u8 version);

	static ServerMapSector* deSerialize(
			std::istream &is,
			Map *parent,
			v2s16 p2d,
			std::map<v2s16, MapSector*> & sectors,
			IGameDef *gamedef
		);

private:
};

#ifndef SERVER
class ClientMapSector : public MapSector
{
public:
	ClientMapSector(Map *parent, v2s16 pos, IGameDef *gamedef);
	~ClientMapSector();

	u32 getId() const
	{
		return MAPSECTOR_CLIENT;
	}

private:
};
#endif

#endif


code:
/*
Minetest
Copyright (C) 2010-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.
*/

#include "mesh.h"
#include "debug.h"
#include "log.h"
#include "irrMap.h"
#include <iostream>
#include <IAnimatedMesh.h>
#include <SAnimatedMesh.h>

// In Irrlicht 1.8 the signature of ITexture::lock was changed from
// (bool, u32) to (E_TEXTURE_LOCK_MODE, u32).
#if IRRLICHT_VERSION_MAJOR == 1 && IRRLICHT_VERSION_MINOR <= 7
#define MY_ETLM_READ_ONLY true
#else
#define MY_ETLM_READ_ONLY video::ETLM_READ_ONLY
#endif

inline static void applyShadeFactor(video::SColor& color, float factor)
{
	color.setRed(core::clamp(core::round32(color.getRed()*factor), 0, 255));
	color.setGreen(core::clamp(core::round32(color.getGreen()*factor), 0, 255));
	color.setBlue(core::clamp(core::round32(color.getBlue()*factor), 0, 255));
}

void applyFacesShading(video::SColor &color, const v3f &normal)
{
	/*
		Some drawtypes have normals set to (0, 0, 0), this must result in
		maximum brightness: shade factor 1.0.
		Shade factors for aligned cube faces are:
		+Y 1.000000 sqrt(1.0)
		-Y 0.447213 sqrt(0.2)
		+-X 0.670820 sqrt(0.45)
		+-Z 0.836660 sqrt(0.7)
	*/
	float x2 = normal.X * normal.X;
	float y2 = normal.Y * normal.Y;
	float z2 = normal.Z * normal.Z;
	if (normal.Y < 0)
		applyShadeFactor(color, 0.670820f * x2 + 0.447213f * y2 + 0.836660f * z2);
	else if ((x2 > 1e-3) || (z2 > 1e-3))
		applyShadeFactor(color, 0.670820f * x2 + 1.000000f * y2 + 0.836660f * z2);
}

scene::IAnimatedMesh* createCubeMesh(v3f scale)
{
	video::SColor c(255,255,255,255);
	video::S3DVertex vertices[24] =
	{
		// Up
		video::S3DVertex(-0.5,+0.5,-0.5, 0,1,0, c, 0,1),
		video::S3DVertex(-0.5,+0.5,+0.5, 0,1,0, c, 0,0),
		video::S3DVertex(+0.5,+0.5,+0.5, 0,1,0, c, 1,0),
		video::S3DVertex(+0.5,+0.5,-0.5, 0,1,0, c, 1,1),
		// Down
		video::S3DVertex(-0.5,-0.5,-0.5, 0,-1,0, c, 0,0),
		video::S3DVertex(+0.5,-0.5,-0.5, 0,-1,0, c, 1,0),
		video::S3DVertex(+0.5,-0.5,+0.5, 0,-1,0, c, 1,1),
		video::S3DVertex(-0.5,-0.5,+0.5, 0,-1,0, c, 0,1),
		// Right
		video::S3DVertex(+0.5,-0.5,-0.5, 1,0,0, c, 0,1),
		video::S3DVertex(+0.5,+0.5,-0.5, 1,0,0, c, 0,0),
		video::S3DVertex(+0.5,+0.5,+0.5, 1,0,0, c, 1,0),
		video::S3DVertex(+0.5,-0.5,+0.5, 1,0,0, c, 1,1),
		// Left
		video::S3DVertex(-0.5,-0.5,-0.5, -1,0,0, c, 1,1),
		video::S3DVertex(-0.5,-0.5,+0.5, -1,0,0, c, 0,1),
		video::S3DVertex(-0.5,+0.5,+0.5, -1,0,0, c, 0,0),
		video::S3DVertex(-0.5,+0.5,-0.5, -1,0,0, c, 1,0),
		// Back
		video::S3DVertex(-0.5,-0.5,+0.5, 0,0,1, c, 1,1),
		video::S3DVertex(+0.5,-0.5,+0.5, 0,0,1, c, 0,1),
		video::S3DVertex(+0.5,+0.5,+0.5, 0,0,1, c, 0,0),
		video::S3DVertex(-0.5,+0.5,+0.5, 0,0,1, c, 1,0),
		// Front
		video::S3DVertex(-0.5,-0.5,-0.5, 0,0,-1, c, 0,1),
		video::S3DVertex(-0.5,+0.5,-0.5, 0,0,-1, c, 0,0),
		video::S3DVertex(+0.5,+0.5,-0.5, 0,0,-1, c, 1,0),
		video::S3DVertex(+0.5,-0.5,-0.5, 0,0,-1, c, 1,1),
	};

	u16 indices[6] = {0,1,2,2,3,0};

	scene::SMesh *mesh = new scene::SMesh();
	for (u32 i=0; i<6; ++i)
	{
		scene::IMeshBuffer *buf = new scene::SMeshBuffer();
		buf->append(vertices + 4 * i, 4, indices, 6);
		// Set default material
		buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
		buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
		buf->getMaterial().MaterialType = video::EMT_TRANSPARENT_ALPHA_CHANNEL_REF;
		// Add mesh buffer to mesh
		mesh->addMeshBuffer(buf);
		buf->drop();
	}

	scene::SAnimatedMesh *anim_mesh = new scene::SAnimatedMesh(mesh);
	mesh->drop();
	scaleMesh(anim_mesh, scale);  // also recalculates bounding box
	return anim_mesh;
}

void scaleMesh(scene::IMesh *mesh, v3f scale)
{
	if (mesh == NULL)
		return;

	aabb3f bbox;
	bbox.reset(0, 0, 0);

	u32 mc = mesh->getMeshBufferCount();
	for (u32 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++)
			((video::S3DVertex *)(vertices + i * stride))->Pos *= scale;

		buf->recalculateBoundingBox();

		// calculate total bounding box
		if (j == 0)
			bbox = buf->getBoundingBox();
		else
			bbox.addInternalBox(buf->getBoundingBox());
	}
	mesh->setBoundingBox(bbox);
}

void translateMesh(scene::IMesh *mesh, v3f vec)
{
	if (mesh == NULL)
		return;

	aabb3f bbox;
	bbox.reset(0, 0, 0);

	u32 mc = mesh->getMeshBufferCount();
	for (u32 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++)
			((video::S3DVertex *)(vertices + i * stride))->Pos += vec;

		buf->recalculateBoundingBox();

		// calculate total bounding box
		if (j == 0)
			bbox = buf->getBoundingBox();
		else
			bbox.addInternalBox(buf->getBoundingBox());
	}
	mesh->setBoundingBox(bbox);
}

void setMeshBufferColor(scene::IMeshBuffer *buf, const video::SColor &color)
{
	const u32 stride = getVertexPitchFromType(buf->getVertexType());
	u32 vertex_count = buf->getVertexCount();
	u8 *vertices = (u8 *) buf->getVertices();
	for (u32 i = 0; i < vertex_count; i++)
		((video::S3DVertex *) (vertices + i * stride))->Color = color;
}

void setMeshColor(scene::IMesh *mesh, const video::SColor &color)
{
	if (mesh == NULL)
		return;

	u32 mc = mesh->getMeshBufferCount();
	for (u32 j = 0; j < mc; j++)
		setMeshBufferColor(mesh->getMeshBuffer(j), color);
}

void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor)
{
	const u32 stride = getVertexPitchFromType(buf->getVertexType());
	u32 vertex_count = buf->getVertexCount();
	u8 *vertices = (u8 *) buf->getVertices();
	for (u32 i = 0; i < vertex_count; i++) {
		video::S3DVertex *vertex = (video::S3DVertex *) (vertices + i * stride);
		video::SColor *vc = &(vertex->Color);
		// Reset color
		*vc = *buffercolor;
		// Apply shading
		applyFacesShading(*vc, vertex->Normal);
	}
}

void setMeshColorByNormalXYZ(scene::IMesh *mesh,
		const video::SColor &colorX,
		const video::SColor &colorY,
		const video::SColor &colorZ)
{
	if (mesh == NULL)
		return;

	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++) {
			video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
			f32 x = fabs(vertex->Normal.X);
			f32 y = fabs(vertex->Normal.Y);
			f32 z = fabs(vertex->Normal.Z);
			if (x >= y && x >= z)
				vertex->Color = colorX;
			else if (y >= z)
				vertex->Color = colorY;
			else
				vertex->Color = colorZ;
		}
	}
}

void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
		const video::SColor &color)
{
	if (!mesh)
		return;

	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++) {
			video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
			if (normal == vertex->Normal) {
				vertex->Color = color;
			}
		}
	}
}

void rotateMeshXYby(scene::IMesh *mesh, f64 degrees)
{
	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++)
			((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXYBy(degrees);
	}
}

void rotateMeshXZby(scene::IMesh *mesh, f64 degrees)
{
	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++)
			((video::S3DVertex *)(vertices + i * stride))->Pos.rotateXZBy(degrees);
	}
}

void rotateMeshYZby(scene::IMesh *mesh, f64 degrees)
{
	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++)
			((video::S3DVertex *)(vertices + i * stride))->Pos.rotateYZBy(degrees);
	}
}

void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir)
{
	int axisdir = facedir >> 2;
	facedir &= 0x03;

	u16 mc = mesh->getMeshBufferCount();
	for (u16 j = 0; j < mc; j++) {
		scene::IMeshBuffer *buf = mesh->getMeshBuffer(j);
		const u32 stride = getVertexPitchFromType(buf->getVertexType());
		u32 vertex_count = buf->getVertexCount();
		u8 *vertices = (u8 *)buf->getVertices();
		for (u32 i = 0; i < vertex_count; i++) {
			video::S3DVertex *vertex = (video::S3DVertex *)(vertices + i * stride);
			switch (axisdir) {
				case 0:
					if (facedir == 1)
						vertex->Pos.rotateXZBy(-90);
					else if (facedir == 2)
						vertex->Pos.rotateXZBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateXZBy(90);
					break;
				case 1: // z+
					vertex->Pos.rotateYZBy(90);
					if (facedir == 1)
						vertex->Pos.rotateXYBy(90);
					else if (facedir == 2)
						vertex->Pos.rotateXYBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateXYBy(-90);
					break;
				case 2: //z-
					vertex->Pos.rotateYZBy(-90);
					if (facedir == 1)
						vertex->Pos.rotateXYBy(-90);
					else if (facedir == 2)
						vertex->Pos.rotateXYBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateXYBy(90);
					break;
				case 3:  //x+
					vertex->Pos.rotateXYBy(-90);
					if (facedir == 1)
						vertex->Pos.rotateYZBy(90);
					else if (facedir == 2)
						vertex->Pos.rotateYZBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateYZBy(-90);
					break;
				case 4:  //x-
					vertex->Pos.rotateXYBy(90);
					if (facedir == 1)
						vertex->Pos.rotateYZBy(-90);
					else if (facedir == 2)
						vertex->Pos.rotateYZBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateYZBy(90);
					break;
				case 5:
					vertex->Pos.rotateXYBy(-180);
					if (facedir == 1)
						vertex->Pos.rotateXZBy(90);
					else if (facedir == 2)
						vertex->Pos.rotateXZBy(180);
					else if (facedir == 3)
						vertex->Pos.rotateXZBy(-90);
					break;
				default:
					break;
			}
		}
	}
}

void recalculateBoundingBox(scene::IMesh *src_mesh)
{
	aabb3f bbox;
	bbox.reset(0,0,0);
	for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
		scene::IMeshBuffer *buf = src_mesh->getMeshBuffer(j);
		buf->recalculateBoundingBox();
		if (j == 0)
			bbox = buf->getBoundingBox();
		else
			bbox.addInternalBox(buf->getBoundingBox());
	}
	src_mesh->setBoundingBox(bbox);
}

scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer)
{
	switch (mesh_buffer->getVertexType()) {
	case video::EVT_STANDARD: {
		video::S3DVertex *v = (video::S3DVertex *) mesh_buffer->getVertices();
		u16 *indices = mesh_buffer->getIndices();
		scene::SMeshBuffer *cloned_buffer = new scene::SMeshBuffer();
		cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
			mesh_buffer->getIndexCount());
		return cloned_buffer;
	}
	case video::EVT_2TCOORDS: {
		video::S3DVertex2TCoords *v =
			(video::S3DVertex2TCoords *) mesh_buffer->getVertices();
		u16 *indices = mesh_buffer->getIndices();
		scene::SMeshBufferTangents *cloned_buffer =
			new scene::SMeshBufferTangents();
		cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
			mesh_buffer->getIndexCount());
		return cloned_buffer;
	}
	case video::EVT_TANGENTS: {
		video::S3DVertexTangents *v =
			(video::S3DVertexTangents *) mesh_buffer->getVertices();
		u16 *indices = mesh_buffer->getIndices();
		scene::SMeshBufferTangents *cloned_buffer =
			new scene::SMeshBufferTangents();
		cloned_buffer->append(v, mesh_buffer->getVertexCount(), indices,
			mesh_buffer->getIndexCount());
		return cloned_buffer;
	}
	}
	// This should not happen.
	sanity_check(false);
	return NULL;
}

scene::SMesh* cloneMesh(scene::IMesh *src_mesh)
{
	scene::SMesh* dst_mesh = new scene::SMesh();
	for (u16 j = 0; j < src_mesh->getMeshBufferCount(); j++) {
		scene::IMeshBuffer *temp_buf = cloneMeshBuffer(
			src_mesh->getMeshBuffer(j));
		dst_mesh->addMeshBuffer(temp_buf);
		temp_buf->drop();

	}
	return dst_mesh;
}

scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
		const f32 *uv_coords, float expand)
{
	scene::SMesh* dst_mesh = new scene::SMesh();

	for (u16 j = 0; j < 6; j++)
	{
		scene::IMeshBuffer *buf = new scene::SMeshBuffer();
		buf->getMaterial().setFlag(video::EMF_LIGHTING, false);
		buf->getMaterial().setFlag(video::EMF_BILINEAR_FILTER, false);
		dst_mesh->addMeshBuffer(buf);
		buf->drop();
	}

	video::SColor c(255,255,255,255);

	for (std::vector<aabb3f>::const_iterator
			i = boxes.begin();
			i != boxes.end(); ++i)
	{
		aabb3f box = *i;
		box.repair();

		box.MinEdge.X -= expand;
		box.MinEdge.Y -= expand;
		box.MinEdge.Z -= expand;
		box.MaxEdge.X += expand;
		box.MaxEdge.Y += expand;
		box.MaxEdge.Z += expand;

		// Compute texture UV coords
		f32 tx1 = (box.MinEdge.X / BS) + 0.5;
		f32 ty1 = (box.MinEdge.Y / BS) + 0.5;
		f32 tz1 = (box.MinEdge.Z / BS) + 0.5;
		f32 tx2 = (box.MaxEdge.X / BS) + 0.5;
		f32 ty2 = (box.MaxEdge.Y / BS) + 0.5;
		f32 tz2 = (box.MaxEdge.Z / BS) + 0.5;

		f32 txc_default[24] = {
			// up
			tx1, 1 - tz2, tx2, 1 - tz1,
			// down
			tx1, tz1, tx2, tz2,
			// right
			tz1, 1 - ty2, tz2, 1 - ty1,
			// left
			1 - tz2, 1 - ty2, 1 - tz1, 1 - ty1,
			// back
			1 - tx2, 1 - ty2, 1 - tx1, 1 - ty1,
			// front
			tx1, 1 - ty2, tx2, 1 - ty1,
		};

		// use default texture UV mapping if not provided
		const f32 *txc = uv_coords ? uv_coords : txc_default;

		v3f min = box.MinEdge;
		v3f max = box.MaxEdge;

		video::S3DVertex vertices[24] =
		{
			// up
			video::S3DVertex(min.X,max.Y,max.Z, 0,1,0, c, txc[0],txc[1]),
			video::S3DVertex(max.X,max.Y,max.Z, 0,1,0, c, txc[2],txc[1]),
			video::S3DVertex(max.X,max.Y,min.Z, 0,1,0, c, txc[2],txc[3]),
			video::S3DVertex(min.X,max.Y,min.Z, 0,1,0, c, txc[0],txc[3]),
			// down
			video::S3DVertex(min.X,min.Y,min.Z, 0,-1,0, c, txc[4],txc[5]),
			video::S3DVertex(max.X,min.Y,min.Z, 0,-1,0, c, txc[6],txc[5]),
			video::S3DVertex(max.X,min.Y,max.Z, 0,-1,0, c, txc[6],txc[7]),
			video::S3DVertex(min.X,min.Y,max.Z, 0,-1,0, c, txc[4],txc[7]),
			// right
			video::S3DVertex(max.X,max.Y,min.Z, 1,0,0, c, txc[ 8],txc[9]),
			video::S3DVertex(max.X,max.Y,max.Z, 1,0,0, c, txc[10],txc[9]),
			video::S3DVertex(max.X,min.Y,max.Z, 1,0,0, c, txc[10],txc[11]),
			video::S3DVertex(max.X,min.Y,min.Z, 1,0,0, c, txc[ 8],txc[11]),
			// left
			video::S3DVertex(min.X,max.Y,max.Z, -1,0,0, c, txc[12],txc[13]),
			video::S3DVertex(min.X,max.Y,min.Z, -1,0,0, c, txc[14],txc[13]),
			video::S3DVertex(min.X,min.Y,min.Z, -1,0,0, c, txc[14],txc[15]),
			video::S3DVertex(min.X,min.Y,max.Z, -1,0,0, c, txc[12],txc[15]),
			// back
			video::S3DVertex(max.X,max.Y,max.Z, 0,0,1, c, txc[16],txc[17]),
			video::S3DVertex(min.X,max.Y,max.Z, 0,0,1, c, txc[18],txc[17]),
			video::S3DVertex(min.X,min.Y,max.Z, 0,0,1, c, txc[18],txc[19]),
			video::S3DVertex(max.X,min.Y,max.Z, 0,0,1, c, txc[16],txc[19]),
			// front
			video::S3DVertex(min.X,max.Y,min.Z, 0,0,-1, c, txc[20],txc[21]),
			video::S3DVertex(max.X,max.Y,min.Z, 0,0,-1, c, txc[22],txc[21]),
			video::S3DVertex(max.X,min.Y,min.Z, 0,0,-1, c, txc[22],txc[23]),
			video::S3DVertex(min.X,min.Y,min.Z, 0,0,-1, c, txc[20],txc[23]),
		};

		u16 indices[] = {0,1,2,2,3,0};

		for(u16 j = 0; j < 24; j += 4)
		{
			scene::IMeshBuffer *buf = dst_mesh->getMeshBuffer(j / 4);
			buf->append(vertices + j, 4, indices, 6);
		}
	}
	return dst_mesh;
}

struct vcache
{
	core::array<u32> tris;
	float score;
	s16 cachepos;
	u16 NumActiveTris;
};

struct tcache
{
	u16 ind[3];
	float score;
	bool drawn;
};

const u16 cachesize = 32;

float FindVertexScore(vcache *v)
{
	const float CacheDecayPower = 1.5f;
	const float LastTriScore = 0.75f;
	const float ValenceBoostScale = 2.0f;
	const float ValenceBoostPower = 0.5f;
	const float MaxSizeVertexCache = 32.0f;

	if (v->NumActiveTris == 0)
	{
		// No tri needs this vertex!
		return -1.0f;
	}

	float Score = 0.0f;
	int CachePosition = v->cachepos;
	if (CachePosition < 0)
	{
		// Vertex is not in FIFO cache - no score.
	}
	else
	{
		if (CachePosition < 3)
		{
			// This vertex was used in the last triangle,
			// so it has a fixed score.
			Score = LastTriScore;
		}
		else
		{
			// Points for being high in the cache.
			const float Scaler = 1.0f / (MaxSizeVertexCache - 3);
			Score = 1.0f - (CachePosition - 3) * Scaler;
			Score = powf(Score, CacheDecayPower);
		}
	}

	// Bonus points for having a low number of tris still to
	// use the vert, so we get rid of lone verts quickly.
	float ValenceBoost = powf(v->NumActiveTris,
				-ValenceBoostPower);
	Score += ValenceBoostScale * ValenceBoost;

	return Score;
}

/*
	A specialized LRU cache for the Forsyth algorithm.
*/

class f_lru
{

public:
	f_lru(vcache *v, tcache *t): vc(v), tc(t)
	{
		for (u16 i = 0; i < cachesize; i++)
		{
			cache[i] = -1;
		}
	}

	// Adds this vertex index and returns the highest-scoring triangle index
	u32 add(u16 vert, bool updatetris = false)
	{
		bool found = false;

		// Mark existing pos as empty
		for (u16 i = 0; i < cachesize; i++)
		{
			if (cache[i] == vert)
			{
				// Move everything down
				for (u16 j = i; j; j--)
				{
					cache[j] = cache[j - 1];
				}

				found = true;
				break;
			}
		}

		if (!found)
		{
			if (cache[cachesize-1] != -1)
				vc[cache[cachesize-1]].cachepos = -1;

			// Move everything down
			for (u16 i = cachesize - 1; i; i--)
			{
				cache[i] = cache[i - 1];
			}
		}

		cache[0] = vert;

		u32 highest = 0;
		float hiscore = 0;

		if (updatetris)
		{
			// Update cache positions
			for (u16 i = 0; i < cachesize; i++)
			{
				if (cache[i] == -1)
					break;

				vc[cache[i]].cachepos = i;
				vc[cache[i]].score = FindVertexScore(&vc[cache[i]]);
			}

			// Update triangle scores
			for (u16 i = 0; i < cachesize; i++)
			{
				if (cache[i] == -1)
					break;

				const u16 trisize = vc[cache[i]].tris.size();
				for (u16 t = 0; t < trisize; t++)
				{
					tcache *tri = &tc[vc[cache[i]].tris[t]];

					tri->score =
						vc[tri->ind[0]].score +
						vc[tri->ind[1]].score +
						vc[tri->ind[2]].score;

					if (tri->score > hiscore)
					{
						hiscore = tri->score;
						highest = vc[cache[i]].tris[t];
					}
				}
			}
		}

		return highest;
	}

private:
	s32 cache[cachesize];
	vcache *vc;
	tcache *tc;
};

/**
Vertex cache optimization according to the Forsyth paper:
http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html

The function is thread-safe (read: you can optimize several meshes in different threads)

\param mesh Source mesh for the operation.  */
scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh)
{
	if (!mesh)
		return 0;

	scene::SMesh *newmesh = new scene::SMesh();
	newmesh->BoundingBox = mesh->getBoundingBox();

	const u32 mbcount = mesh->getMeshBufferCount();

	for (u32 b = 0; b < mbcount; ++b)
	{
		const scene::IMeshBuffer *mb = mesh->getMeshBuffer(b);

		if (mb->getIndexType() != video::EIT_16BIT)
		{
			//os::Printer::log("Cannot optimize a mesh with 32bit indices", ELL_ERROR);
			newmesh->drop();
			return 0;
		}

		const u32 icount = mb->getIndexCount();
		const u32 tcount = icount / 3;
		const u32 vcount = mb->getVertexCount();
		const u16 *ind = mb->getIndices();

		vcache *vc = new vcache[vcount];
		tcache *tc = new tcache[tcount];

		f_lru lru(vc, tc);

		// init
		for (u16 i = 0; i < vcount; i++)
		{
			vc[i].score = 0;
			vc[i].cachepos = -1;
			vc[i].NumActiveTris = 0;
		}

		// First pass: count how many times a vert is used
		for (u32 i = 0; i < icount; i += 3)
		{
			vc[ind[i]].NumActiveTris++;
			vc[ind[i + 1]].NumActiveTris++;
			vc[ind[i + 2]].NumActiveTris++;

			const u32 tri_ind = i/3;
			tc[tri_ind].ind[0] = ind[i];
			tc[tri_ind].ind[1] = ind[i + 1];
			tc[tri_ind].ind[2] = ind[i + 2];
		}

		// Second pass: list of each triangle
		for (u32 i = 0; i < tcount; i++)
		{
			vc[tc[i].ind[0]].tris.push_back(i);
			vc[tc[i].ind[1]].tris.push_back(i);
			vc[tc[i].ind[2]].tris.push_back(i);

			tc[i].drawn = false;
		}

		// Give initial scores
		for (u16 i = 0; i < vcount; i++)
		{
			vc[i].score = FindVertexScore(&vc[i]);
		}
		for (u32 i = 0; i < tcount; i++)
		{
			tc[i].score =
					vc[tc[i].ind[0]].score +
					vc[tc[i].ind[1]].score +
					vc[tc[i].ind[2]].score;
		}

		switch(mb->getVertexType())
		{
			case video::EVT_STANDARD:
			{
				video::S3DVertex *v = (video::S3DVertex *) mb->getVertices();

				scene::SMeshBuffer *buf = new scene::SMeshBuffer();
				buf->Material = mb->getMaterial();

				buf->Vertices.reallocate(vcount);
				buf->Indices.reallocate(icount);

				core::map<const video::S3DVertex, const u16> sind; // search index for fast operation
				typedef core::map<const video::S3DVertex, const u16>::Node snode;

				// Main algorithm
				u32 highest = 0;
				u32 drawcalls = 0;
				for (;;)
				{
					if (tc[highest].drawn)
					{
						bool found = false;
						float hiscore = 0;
						for (u32 t = 0; t < tcount; t++)
						{
							if (!tc[t].drawn)
							{
								if (tc[t].score > hiscore)
								{
									highest = t;
									hiscore = tc[t].score;
									found = true;
								}
							}
						}
						if (!found)
							break;
					}

					// Output the best triangle
					u16 newind = buf->Vertices.size();

					snode *s = sind.find(v[tc[highest].ind[0]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[0]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[0]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[1]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[1]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[1]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[2]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[2]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[2]], newind);
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					vc[tc[highest].ind[0]].NumActiveTris--;
					vc[tc[highest].ind[1]].NumActiveTris--;
					vc[tc[highest].ind[2]].NumActiveTris--;

					tc[highest].drawn = true;

					for (u16 j = 0; j < 3; j++)
					{
						vcache *vert = &vc[tc[highest].ind[j]];
						for (u16 t = 0; t < vert->tris.size(); t++)
						{
							if (highest == vert->tris[t])
							{
								vert->tris.erase(t);
								break;
							}
						}
					}

					lru.add(tc[highest].ind[0]);
					lru.add(tc[highest].ind[1]);
					highest = lru.add(tc[highest].ind[2], true);
					drawcalls++;
				}

				buf->setBoundingBox(mb->getBoundingBox());
				newmesh->addMeshBuffer(buf);
				buf->drop();
			}
			break;
			case video::EVT_2TCOORDS:
			{
				video::S3DVertex2TCoords *v = (video::S3DVertex2TCoords *) mb->getVertices();

				scene::SMeshBufferLightMap *buf = new scene::SMeshBufferLightMap();
				buf->Material = mb->getMaterial();

				buf->Vertices.reallocate(vcount);
				buf->Indices.reallocate(icount);

				core::map<const video::S3DVertex2TCoords, const u16> sind; // search index for fast operation
				typedef core::map<const video::S3DVertex2TCoords, const u16>::Node snode;

				// Main algorithm
				u32 highest = 0;
				u32 drawcalls = 0;
				for (;;)
				{
					if (tc[highest].drawn)
					{
						bool found = false;
						float hiscore = 0;
						for (u32 t = 0; t < tcount; t++)
						{
							if (!tc[t].drawn)
							{
								if (tc[t].score > hiscore)
								{
									highest = t;
									hiscore = tc[t].score;
									found = true;
								}
							}
						}
						if (!found)
							break;
					}

					// Output the best triangle
					u16 newind = buf->Vertices.size();

					snode *s = sind.find(v[tc[highest].ind[0]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[0]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[0]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[1]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[1]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[1]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[2]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[2]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[2]], newind);
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					vc[tc[highest].ind[0]].NumActiveTris--;
					vc[tc[highest].ind[1]].NumActiveTris--;
					vc[tc[highest].ind[2]].NumActiveTris--;

					tc[highest].drawn = true;

					for (u16 j = 0; j < 3; j++)
					{
						vcache *vert = &vc[tc[highest].ind[j]];
						for (u16 t = 0; t < vert->tris.size(); t++)
						{
							if (highest == vert->tris[t])
							{
								vert->tris.erase(t);
								break;
							}
						}
					}

					lru.add(tc[highest].ind[0]);
					lru.add(tc[highest].ind[1]);
					highest = lru.add(tc[highest].ind[2]);
					drawcalls++;
				}

				buf->setBoundingBox(mb->getBoundingBox());
				newmesh->addMeshBuffer(buf);
				buf->drop();

			}
			break;
			case video::EVT_TANGENTS:
			{
				video::S3DVertexTangents *v = (video::S3DVertexTangents *) mb->getVertices();

				scene::SMeshBufferTangents *buf = new scene::SMeshBufferTangents();
				buf->Material = mb->getMaterial();

				buf->Vertices.reallocate(vcount);
				buf->Indices.reallocate(icount);

				core::map<const video::S3DVertexTangents, const u16> sind; // search index for fast operation
				typedef core::map<const video::S3DVertexTangents, const u16>::Node snode;

				// Main algorithm
				u32 highest = 0;
				u32 drawcalls = 0;
				for (;;)
				{
					if (tc[highest].drawn)
					{
						bool found = false;
						float hiscore = 0;
						for (u32 t = 0; t < tcount; t++)
						{
							if (!tc[t].drawn)
							{
								if (tc[t].score > hiscore)
								{
									highest = t;
									hiscore = tc[t].score;
									found = true;
								}
							}
						}
						if (!found)
							break;
					}

					// Output the best triangle
					u16 newind = buf->Vertices.size();

					snode *s = sind.find(v[tc[highest].ind[0]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[0]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[0]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[1]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[1]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[1]], newind);
						newind++;
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					s = sind.find(v[tc[highest].ind[2]]);

					if (!s)
					{
						buf->Vertices.push_back(v[tc[highest].ind[2]]);
						buf->Indices.push_back(newind);
						sind.insert(v[tc[highest].ind[2]], newind);
					}
					else
					{
						buf->Indices.push_back(s->getValue());
					}

					vc[tc[highest].ind[0]].NumActiveTris--;
					vc[tc[highest].ind[1]].NumActiveTris--;
					vc[tc[highest].ind[2]].NumActiveTris--;

					tc[highest].drawn = true;

					for (u16 j = 0; j < 3; j++)
					{
						vcache *vert = &vc[tc[highest].ind[j]];
						for (u16 t = 0; t < vert->tris.size(); t++)
						{
							if (highest == vert->tris[t])
							{
								vert->tris.erase(t);
								break;
							}
						}
					}

					lru.add(tc[highest].ind[0]);
					lru.add(tc[highest].ind[1]);
					highest = lru.add(tc[highest].ind[2]);
					drawcalls++;
				}

				buf->setBoundingBox(mb->getBoundingBox());
				newmesh->addMeshBuffer(buf);
				buf->drop();
			}
			break;
		}

		delete [] vc;
		delete [] tc;

	} // for each meshbuffer

	return newmesh;
}


code:
/*
Minetest
Copyright (C) 2010-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 MESH_HEADER
#define MESH_HEADER

#include "irrlichttypes_extrabloated.h"
#include "nodedef.h"

/*!
 * Applies shading to a color based on the surface's
 * normal vector.
 */
void applyFacesShading(video::SColor &color, const v3f &normal);

/*
	Create a new cube mesh.
	Vertices are at (+-scale.X/2, +-scale.Y/2, +-scale.Z/2).

	The resulting mesh has 6 materials (up, down, right, left, back, front)
	which must be defined by the caller.
*/
scene::IAnimatedMesh* createCubeMesh(v3f scale);

/*
	Multiplies each vertex coordinate by the specified scaling factors
	(componentwise vector multiplication).
*/
void scaleMesh(scene::IMesh *mesh, v3f scale);

/*
	Translate each vertex coordinate by the specified vector.
*/
void translateMesh(scene::IMesh *mesh, v3f vec);

/*!
 * Sets a constant color for all vertices in the mesh buffer.
 */
void setMeshBufferColor(scene::IMeshBuffer *buf, const video::SColor &color);

/*
	Set a constant color for all vertices in the mesh
*/
void setMeshColor(scene::IMesh *mesh, const video::SColor &color);

/*!
 * Overwrites the color of a mesh buffer.
 * The color is darkened based on the normal vector of the vertices.
 */
void colorizeMeshBuffer(scene::IMeshBuffer *buf, const video::SColor *buffercolor);

/*
	Set the color of all vertices in the mesh.
	For each vertex, determine the largest absolute entry in
	the normal vector, and choose one of colorX, colorY or
	colorZ accordingly.
*/
void setMeshColorByNormalXYZ(scene::IMesh *mesh,
		const video::SColor &colorX,
		const video::SColor &colorY,
		const video::SColor &colorZ);

void setMeshColorByNormal(scene::IMesh *mesh, const v3f &normal,
		const video::SColor &color);

/*
	Rotate the mesh by 6d facedir value.
	Method only for meshnodes, not suitable for entities.
*/
void rotateMeshBy6dFacedir(scene::IMesh *mesh, int facedir);

/*
	Rotate the mesh around the axis and given angle in degrees.
*/
void rotateMeshXYby (scene::IMesh *mesh, f64 degrees);
void rotateMeshXZby (scene::IMesh *mesh, f64 degrees);
void rotateMeshYZby (scene::IMesh *mesh, f64 degrees);

/*
 *  Clone the mesh buffer.
 *  The returned pointer should be dropped.
 */
scene::IMeshBuffer* cloneMeshBuffer(scene::IMeshBuffer *mesh_buffer);

/*
	Clone the mesh.
*/
scene::SMesh* cloneMesh(scene::IMesh *src_mesh);

/*
	Convert nodeboxes to mesh. Each tile goes into a different buffer.
	boxes - set of nodeboxes to be converted into cuboids
	uv_coords[24] - table of texture uv coords for each cuboid face
	expand - factor by which cuboids will be resized
*/
scene::IMesh* convertNodeboxesToMesh(const std::vector<aabb3f> &boxes,
		const f32 *uv_coords = NULL, float expand = 0);

/*
	Update bounding box for a mesh.
*/
void recalculateBoundingBox(scene::IMesh *src_mesh);

/*
	Vertex cache optimization according to the Forsyth paper:
	http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
	Ported from irrlicht 1.8
*/
scene::IMesh* createForsythOptimizedMesh(const scene::IMesh *mesh);

#endif


code:
/*
Minetest
Copyright (C) 2013, 2017 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.
*/

#include "mesh_generator_thread.h"
#include "settings.h"
#include "profiler.h"
#include "client.h"
#include "mapblock.h"
#include "map.h"

/*
	CachedMapBlockData
*/

CachedMapBlockData::CachedMapBlockData():
	p(-1337,-1337,-1337),
	data(NULL),
	refcount_from_queue(0),
	last_used_timestamp(time(0))
{
}

CachedMapBlockData::~CachedMapBlockData()
{
	assert(refcount_from_queue == 0);

	if (data)
		delete[] data;
}

/*
	QueuedMeshUpdate
*/

QueuedMeshUpdate::QueuedMeshUpdate():
	p(-1337,-1337,-1337),
	ack_block_to_server(false),
	urgent(false),
	crack_level(-1),
	crack_pos(0,0,0),
	data(NULL)
{
}

QueuedMeshUpdate::~QueuedMeshUpdate()
{
	if (data)
		delete data;
}

/*
	MeshUpdateQueue
*/

MeshUpdateQueue::MeshUpdateQueue(Client *client):
	m_client(client)
{
	m_cache_enable_shaders = g_settings->getBool("enable_shaders");
	m_cache_use_tangent_vertices = m_cache_enable_shaders && (
		g_settings->getBool("enable_bumpmapping") ||
		g_settings->getBool("enable_parallax_occlusion"));
	m_cache_smooth_lighting = g_settings->getBool("smooth_lighting");
	m_meshgen_block_cache_size = g_settings->getS32("meshgen_block_cache_size");
}

MeshUpdateQueue::~MeshUpdateQueue()
{
	MutexAutoLock lock(m_mutex);

	for (std::map<v3s16, CachedMapBlockData *>::iterator i = m_cache.begin();
			i != m_cache.end(); ++i) {
		delete i->second;
	}

	for (std::vector<QueuedMeshUpdate*>::iterator i = m_queue.begin();
			i != m_queue.end(); ++i) {
		QueuedMeshUpdate *q = *i;
		delete q;
	}
}

void MeshUpdateQueue::addBlock(Map *map, v3s16 p, bool ack_block_to_server, bool urgent)
{
	DSTACK(FUNCTION_NAME);

	MutexAutoLock lock(m_mutex);

	cleanupCache();

	/*
		Cache the block data (force-update the center block, don't update the
		neighbors but get them if they aren't already cached)
	*/
	std::vector<CachedMapBlockData*> cached_blocks;
	size_t cache_hit_counter = 0;
	cached_blocks.reserve(3*3*3);
	v3s16 dp;
	for (dp.X = -1; dp.X <= 1; dp.X++)
	for (dp.Y = -1; dp.Y <= 1; dp.Y++)
	for (dp.Z = -1; dp.Z <= 1; dp.Z++) {
		v3s16 p1 = p + dp;
		CachedMapBlockData *cached_block;
		if (dp == v3s16(0, 0, 0))
			cached_block = cacheBlock(map, p1, FORCE_UPDATE);
		else
			cached_block = cacheBlock(map, p1, SKIP_UPDATE_IF_ALREADY_CACHED,
					&cache_hit_counter);
		cached_blocks.push_back(cached_block);
	}
	g_profiler->avg("MeshUpdateQueue MapBlock cache hit %",
			100.0f * cache_hit_counter / cached_blocks.size());

	/*
		Mark the block as urgent if requested
	*/
	if (urgent)
		m_urgents.insert(p);

	/*
		Find if block is already in queue.
		If it is, update the data and quit.
	*/
	for (std::vector<QueuedMeshUpdate*>::iterator i = m_queue.begin();
			i != m_queue.end(); ++i) {
		QueuedMeshUpdate *q = *i;
		if (q->p == p) {
			// NOTE: We are not adding a new position to the queue, thus
			//       refcount_from_queue stays the same.
			if(ack_block_to_server)
				q->ack_block_to_server = true;
			q->crack_level = m_client->getCrackLevel();
			q->crack_pos = m_client->getCrackPos();
			return;
		}
	}

	/*
		Add the block
	*/
	QueuedMeshUpdate *q = new QueuedMeshUpdate;
	q->p = p;
	q->ack_block_to_server = ack_block_to_server;
	q->crack_level = m_client->getCrackLevel();
	q->crack_pos = m_client->getCrackPos();
	m_queue.push_back(q);

	// This queue entry is a new reference to the cached blocks
	for (size_t i=0; i<cached_blocks.size(); i++) {
		cached_blocks[i]->refcount_from_queue++;
	}
}

// Returned pointer must be deleted
// Returns NULL if queue is empty
QueuedMeshUpdate *MeshUpdateQueue::pop()
{
	MutexAutoLock lock(m_mutex);

	bool must_be_urgent = !m_urgents.empty();
	for (std::vector<QueuedMeshUpdate*>::iterator i = m_queue.begin();
			i != m_queue.end(); ++i) {
		QueuedMeshUpdate *q = *i;
		if(must_be_urgent && m_urgents.count(q->p) == 0)
			continue;
		m_queue.erase(i);
		m_urgents.erase(q->p);
		fillDataFromMapBlockCache(q);
		return q;
	}
	return NULL;
}

CachedMapBlockData* MeshUpdateQueue::cacheBlock(Map *map, v3s16 p, UpdateMode mode,
			size_t *cache_hit_counter)
{
	std::map<v3s16, CachedMapBlockData*>::iterator it =
			m_cache.find(p);
	if (it != m_cache.end()) {
		// Already in cache
		CachedMapBlockData *cached_block = it->second;
		if (mode == SKIP_UPDATE_IF_ALREADY_CACHED) {
			if (cache_hit_counter)
				(*cache_hit_counter)++;
			return cached_block;
		}
		MapBlock *b = map->getBlockNoCreateNoEx(p);
		if (b) {
			if (cached_block->data == NULL)
				cached_block->data =
						new MapNode[MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE];
			memcpy(cached_block->data, b->getData(),
					MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE * sizeof(MapNode));
		} else {
			delete[] cached_block->data;
			cached_block->data = NULL;
		}
		return cached_block;
	} else {
		// Not yet in cache
		CachedMapBlockData *cached_block = new CachedMapBlockData();
		m_cache[p] = cached_block;
		MapBlock *b = map->getBlockNoCreateNoEx(p);
		if (b) {
			cached_block->data =
					new MapNode[MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE];
			memcpy(cached_block->data, b->getData(),
					MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE * sizeof(MapNode));
		}
		return cached_block;
	}
}

CachedMapBlockData* MeshUpdateQueue::getCachedBlock(const v3s16 &p)
{
	std::map<v3s16, CachedMapBlockData*>::iterator it = m_cache.find(p);
	if (it != m_cache.end()) {
		return it->second;
	}
	return NULL;
}

void MeshUpdateQueue::fillDataFromMapBlockCache(QueuedMeshUpdate *q)
{
	MeshMakeData *data = new MeshMakeData(m_client, m_cache_enable_shaders,
			m_cache_use_tangent_vertices);
	q->data = data;

	data->fillBlockDataBegin(q->p);

	int t_now = time(0);

	// Collect data for 3*3*3 blocks from cache
	v3s16 dp;
	for (dp.X = -1; dp.X <= 1; dp.X++)
	for (dp.Y = -1; dp.Y <= 1; dp.Y++)
	for (dp.Z = -1; dp.Z <= 1; dp.Z++) {
		v3s16 p = q->p + dp;
		CachedMapBlockData *cached_block = getCachedBlock(p);
		if (cached_block) {
			cached_block->refcount_from_queue--;
			cached_block->last_used_timestamp = t_now;
			if (cached_block->data)
				data->fillBlockData(dp, cached_block->data);
		}
	}

	data->setCrack(q->crack_level, q->crack_pos);
	data->setSmoothLighting(m_cache_smooth_lighting);
}

void MeshUpdateQueue::cleanupCache()
{
	const int mapblock_kB = MAP_BLOCKSIZE * MAP_BLOCKSIZE * MAP_BLOCKSIZE *
			sizeof(MapNode) / 1000;
	g_profiler->avg("MeshUpdateQueue MapBlock cache size kB",
			mapblock_kB * m_cache.size());

	// The cache size is kept roughly below cache_soft_max_size, not letting
	// anything get older than cache_seconds_max or deleted before 2 seconds.
	const int cache_seconds_max = 10;
	const int cache_soft_max_size = m_meshgen_block_cache_size * 1000 / mapblock_kB;
	int cache_seconds = MYMAX(2, cache_seconds_max -
			m_cache.size() / (cache_soft_max_size / cache_seconds_max));

	int t_now = time(0);

	for (std::map<v3s16, CachedMapBlockData*>::iterator it = m_cache.begin();
			it != m_cache.end(); ) {
		CachedMapBlockData *cached_block = it->second;
		if (cached_block->refcount_from_queue == 0 &&
				cached_block->last_used_timestamp < t_now - cache_seconds) {
			m_cache.erase(it++);
			delete cached_block;
		} else {
			++it;
		}
	}
}

/*
	MeshUpdateThread
*/

MeshUpdateThread::MeshUpdateThread(Client *client):
	UpdateThread("Mesh"),
	m_queue_in(client)
{
	m_generation_interval = g_settings->getU16("mesh_generation_interval");
	m_generation_interval = rangelim(m_generation_interval, 0, 50);
}

void MeshUpdateThread::updateBlock(Map *map, v3s16 p, bool ack_block_to_server,
		bool urgent)
{
	// Allow the MeshUpdateQueue to do whatever it wants
	m_queue_in.addBlock(map, p, ack_block_to_server, urgent);
	deferUpdate();
}

void MeshUpdateThread::doUpdate()
{
	QueuedMeshUpdate *q;
	while ((q = m_queue_in.pop())) {
		if (m_generation_interval)
			sleep_ms(m_generation_interval);
		ScopeProfiler sp(g_profiler, "Client: Mesh making");

		MapBlockMesh *mesh_new = new MapBlockMesh(q->data, m_camera_offset);

		MeshUpdateResult r;
		r.p = q->p;
		r.mesh = mesh_new;
		r.ack_block_to_server = q->ack_block_to_server;

		m_queue_out.push_back(r);

		delete q;
	}
}


code:
/*
Minetest
Copyright (C) 2013, 2017 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 MESH_GENERATOR_THREAD_HEADER
#define MESH_GENERATOR_THREAD_HEADER

#include "mapblock_mesh.h"
#include "threading/mutex_auto_lock.h"
#include "util/thread.h"

struct CachedMapBlockData
{
	v3s16 p;
	MapNode *data; // A copy of the MapBlock's data member
	int refcount_from_queue;
	int last_used_timestamp;

	CachedMapBlockData();
	~CachedMapBlockData();
};

struct QueuedMeshUpdate
{
	v3s16 p;
	bool ack_block_to_server;
	bool urgent;
	int crack_level;
	v3s16 crack_pos;
	MeshMakeData *data; // This is generated in MeshUpdateQueue::pop()

	QueuedMeshUpdate();
	~QueuedMeshUpdate();
};

/*
	A thread-safe queue of mesh update tasks and a cache of MapBlock data
*/
class MeshUpdateQueue
{
	enum UpdateMode
	{
		FORCE_UPDATE,
		SKIP_UPDATE_IF_ALREADY_CACHED,
	};

public:
	MeshUpdateQueue(Client *client);

	~MeshUpdateQueue();

	// Caches the block at p and its neighbors (if needed) and queues a mesh
	// update for the block at p
	void addBlock(Map *map, v3s16 p, bool ack_block_to_server, bool urgent);

	// Returned pointer must be deleted
	// Returns NULL if queue is empty
	QueuedMeshUpdate *pop();

	u32 size()
	{
		MutexAutoLock lock(m_mutex);
		return m_queue.size();
	}

private:
	Client *m_client;
	std::vector<QueuedMeshUpdate *> m_queue;
	std::set<v3s16> m_urgents;
	std::map<v3s16, CachedMapBlockData *> m_cache;
	Mutex m_mutex;

	// TODO: Add callback to update these when g_settings changes
	bool m_cache_enable_shaders;
	bool m_cache_use_tangent_vertices;
	bool m_cache_smooth_lighting;
	int m_meshgen_block_cache_size;

	CachedMapBlockData *cacheBlock(Map *map, v3s16 p, UpdateMode mode,
			size_t *cache_hit_counter = NULL);
	CachedMapBlockData *getCachedBlock(const v3s16 &p);
	void fillDataFromMapBlockCache(QueuedMeshUpdate *q);
	void cleanupCache();
};

struct MeshUpdateResult
{
	v3s16 p;
	MapBlockMesh *mesh;
	bool ack_block_to_server;

	MeshUpdateResult()
	    : p(-1338, -1338, -1338), mesh(NULL), ack_block_to_server(false)
	{
	}
};

class MeshUpdateThread : public UpdateThread
{
public:
	MeshUpdateThread(Client *client);

	// Caches the block at p and its neighbors (if needed) and queues a mesh
	// update for the block at p
	void updateBlock(Map *map, v3s16 p, bool ack_block_to_server, bool urgent);

	v3s16 m_camera_offset;
	MutexedQueue<MeshUpdateResult> m_queue_out;

private:
	MeshUpdateQueue m_queue_in;

	// TODO: Add callback to update these when g_settings changes
	int m_generation_interval;

protected:
	virtual void doUpdate();
};

#endif


code:
/*
Minetest
Copyright (C) 2010-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.
*/

#include "metadata.h"
#include "exceptions.h"
#include "gamedef.h"
#include "log.h"
#include <sstream>
#include "constants.h" // MAP_BLOCKSIZE
#include <sstream>

/*
	Metadata
*/

void Metadata::clear()
{
	m_stringvars.clear();
}

bool Metadata::empty() const
{
	return m_stringvars.size() == 0;
}

size_t Metadata::size() const
{
	return m_stringvars.size();
}

bool Metadata::contains(const std::string &name) const
{
	return m_stringvars.find(name) != m_stringvars.end();
}

bool Metadata::operator==(const Metadata &other) const
{
	if (size() != other.size())
		return false;

	for (StringMap::const_iterator it = m_stringvars.begin();
			it != m_stringvars.end(); ++it) {
		if (!other.contains(it->first) ||
				other.getString(it->first) != it->second)
			return false;
	}

	return true;
}

const std::string &Metadata::getString(const std::string &name, u16 recursion) const
{
	StringMap::const_iterator it = m_stringvars.find(name);
	if (it == m_stringvars.end()) {
		static const std::string empty_string = std::string("");
		return empty_string;
	}

	return resolveString(it->second, recursion);
}

/**
 * Sets var to name key in the metadata storage
 *
 * @param name
 * @param var
 * @return true if key-value pair is created or changed
 */
bool Metadata::setString(const std::string &name, const std::string &var)
{
	if (var.empty()) {
		m_stringvars.erase(name);
		return true;
	}

	StringMap::iterator it = m_stringvars.find(name);
	if (it != m_stringvars.end() && it->second == var) {
		return false;
	}

	m_stringvars[name] = var;
	return true;
}

const std::string &Metadata::resolveString(const std::string &str, u16 recursion) const
{
	if (recursion <= 1 && str.substr(0, 2) == "${" && str[str.length() - 1] == '}') {
		return getString(str.substr(2, str.length() - 3), recursion + 1);
	} else {
		return str;
	}
}


code:
/*
Minetest
Copyright (C) 2010-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 METADATA_HEADER
#define METADATA_HEADER

#include "irr_v3d.h"
#include <iostream>
#include <vector>
#include "util/string.h"

class Metadata
{
public:
	virtual ~Metadata() {}

	virtual void clear();
	virtual bool empty() const;

	bool operator==(const Metadata &other) const;
	inline bool operator!=(const Metadata &other) const
	{
		return !(*this == other);
	}

	//
	// Key-value related
	//

	size_t size() const;
	bool contains(const std::string &name) const;
	const std::string &getString(const std::string &name, u16 recursion = 0) const;
	virtual bool setString(const std::string &name, const std::string &var);
	const StringMap &getStrings() const
	{
		return m_stringvars;
	}
	// Add support for variable names in values
	const std::string &resolveString(const std::string &str, u16 recursion = 0) const;
protected:
	StringMap m_stringvars;

};

#endif


code:
/*
Minetest
Copyright (C) 2014-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2014-2017 paramat

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.
*/

#include "mg_biome.h"
#include "mg_decoration.h"
#include "emerge.h"
#include "server.h"
#include "nodedef.h"
#include "map.h" //for MMVManip
#include "util/numeric.h"
#include "porting.h"
#include "settings.h"

///////////////////////////////////////////////////////////////////////////////

BiomeManager::BiomeManager(Server *server) :
	ObjDefManager(server, OBJDEF_BIOME)
{
	m_server = server;

	// Create default biome to be used in case none exist
	Biome *b = new Biome;

	b->name            = "Default";
	b->flags           = 0;
	b->depth_top       = 0;
	b->depth_filler    = -MAX_MAP_GENERATION_LIMIT;
	b->depth_water_top = 0;
	b->depth_riverbed  = 0;
	b->y_min           = -MAX_MAP_GENERATION_LIMIT;
	b->y_max           = MAX_MAP_GENERATION_LIMIT;
	b->heat_point      = 0.0;
	b->humidity_point  = 0.0;

	b->m_nodenames.push_back("mapgen_stone");
	b->m_nodenames.push_back("mapgen_stone");
	b->m_nodenames.push_back("mapgen_stone");
	b->m_nodenames.push_back("mapgen_water_source");
	b->m_nodenames.push_back("mapgen_water_source");
	b->m_nodenames.push_back("mapgen_river_water_source");
	b->m_nodenames.push_back("mapgen_stone");
	b->m_nodenames.push_back("ignore");
	m_ndef->pendNodeResolve(b);

	add(b);
}

BiomeManager::~BiomeManager()
{
}

void BiomeManager::clear()
{
	EmergeManager *emerge = m_server->getEmergeManager();

	// Remove all dangling references in Decorations
	DecorationManager *decomgr = emerge->decomgr;
	for (size_t i = 0; i != decomgr->getNumObjects(); i++) {
		Decoration *deco = (Decoration *)decomgr->getRaw(i);
		deco->biomes.clear();
	}

	// Don't delete the first biome
	for (size_t i = 1; i < m_objects.size(); i++)
		delete (Biome *)m_objects[i];

	m_objects.resize(1);
}

////////////////////////////////////////////////////////////////////////////////

void BiomeParamsOriginal::readParams(const Settings *settings)
{
	settings->getNoiseParams("mg_biome_np_heat",           np_heat);
	settings->getNoiseParams("mg_biome_np_heat_blend",     np_heat_blend);
	settings->getNoiseParams("mg_biome_np_humidity",       np_humidity);
	settings->getNoiseParams("mg_biome_np_humidity_blend", np_humidity_blend);
}

void BiomeParamsOriginal::writeParams(Settings *settings) const
{
	settings->setNoiseParams("mg_biome_np_heat",           np_heat);
	settings->setNoiseParams("mg_biome_np_heat_blend",     np_heat_blend);
	settings->setNoiseParams("mg_biome_np_humidity",       np_humidity);
	settings->setNoiseParams("mg_biome_np_humidity_blend", np_humidity_blend);
}

////////////////////////////////////////////////////////////////////////////////

BiomeGenOriginal::BiomeGenOriginal(BiomeManager *biomemgr,
	BiomeParamsOriginal *params, v3s16 chunksize)
{
	m_bmgr   = biomemgr;
	m_params = params;
	m_csize  = chunksize;

	noise_heat           = new Noise(&params->np_heat,
									params->seed, m_csize.X, m_csize.Z);
	noise_humidity       = new Noise(&params->np_humidity,
									params->seed, m_csize.X, m_csize.Z);
	noise_heat_blend     = new Noise(&params->np_heat_blend,
									params->seed, m_csize.X, m_csize.Z);
	noise_humidity_blend = new Noise(&params->np_humidity_blend,
									params->seed, m_csize.X, m_csize.Z);

	heatmap  = noise_heat->result;
	humidmap = noise_humidity->result;
	biomemap = new biome_t[m_csize.X * m_csize.Z];
}

BiomeGenOriginal::~BiomeGenOriginal()
{
	delete []biomemap;

	delete noise_heat;
	delete noise_humidity;
	delete noise_heat_blend;
	delete noise_humidity_blend;
}

Biome *BiomeGenOriginal::calcBiomeAtPoint(v3s16 pos) const
{
	float heat =
		NoisePerlin2D(&m_params->np_heat,       pos.X, pos.Z, m_params->seed) +
		NoisePerlin2D(&m_params->np_heat_blend, pos.X, pos.Z, m_params->seed);
	float humidity =
		NoisePerlin2D(&m_params->np_humidity,       pos.X, pos.Z, m_params->seed) +
		NoisePerlin2D(&m_params->np_humidity_blend, pos.X, pos.Z, m_params->seed);

	return calcBiomeFromNoise(heat, humidity, pos.Y);
}

void BiomeGenOriginal::calcBiomeNoise(v3s16 pmin)
{
	m_pmin = pmin;

	noise_heat->perlinMap2D(pmin.X, pmin.Z);
	noise_humidity->perlinMap2D(pmin.X, pmin.Z);
	noise_heat_blend->perlinMap2D(pmin.X, pmin.Z);
	noise_humidity_blend->perlinMap2D(pmin.X, pmin.Z);

	for (s32 i = 0; i < m_csize.X * m_csize.Z; i++) {
		noise_heat->result[i]     += noise_heat_blend->result[i];
		noise_humidity->result[i] += noise_humidity_blend->result[i];
	}
}

biome_t *BiomeGenOriginal::getBiomes(s16 *heightmap)
{
	for (s32 i = 0; i != m_csize.X * m_csize.Z; i++) {
		Biome *biome = calcBiomeFromNoise(
			noise_heat->result[i],
			noise_humidity->result[i],
			heightmap[i]);

		biomemap[i] = biome->index;
	}

	return biomemap;
}

Biome *BiomeGenOriginal::getBiomeAtPoint(v3s16 pos) const
{
	return getBiomeAtIndex(
		(pos.Z - m_pmin.Z) * m_csize.X + (pos.X - m_pmin.X),
		pos.Y);
}

Biome *BiomeGenOriginal::getBiomeAtIndex(size_t index, s16 y) const
{
	return calcBiomeFromNoise(
		noise_heat->result[index],
		noise_humidity->result[index],
		y);
}

Biome *BiomeGenOriginal::calcBiomeFromNoise(float heat, float humidity, s16 y) const
{
	Biome *b, *biome_closest = NULL;
	float dist_min = FLT_MAX;

	for (size_t i = 1; i < m_bmgr->getNumObjects(); i++) {
		b = (Biome *)m_bmgr->getRaw(i);
		if (!b || y > b->y_max || y < b->y_min)
			continue;

		float d_heat     = heat     - b->heat_point;
		float d_humidity = humidity - b->humidity_point;
		float dist = (d_heat * d_heat) +
					 (d_humidity * d_humidity);
		if (dist < dist_min) {
			dist_min = dist;
			biome_closest = b;
		}
	}

	return biome_closest ? biome_closest : (Biome *)m_bmgr->getRaw(BIOME_NONE);
}

////////////////////////////////////////////////////////////////////////////////

void Biome::resolveNodeNames()
{
	getIdFromNrBacklog(&c_top,         "mapgen_stone",              CONTENT_AIR);
	getIdFromNrBacklog(&c_filler,      "mapgen_stone",              CONTENT_AIR);
	getIdFromNrBacklog(&c_stone,       "mapgen_stone",              CONTENT_AIR);
	getIdFromNrBacklog(&c_water_top,   "mapgen_water_source",       CONTENT_AIR);
	getIdFromNrBacklog(&c_water,       "mapgen_water_source",       CONTENT_AIR);
	getIdFromNrBacklog(&c_river_water, "mapgen_river_water_source", CONTENT_AIR);
	getIdFromNrBacklog(&c_riverbed,    "mapgen_stone",              CONTENT_AIR);
	getIdFromNrBacklog(&c_dust,        "ignore",                    CONTENT_IGNORE);
}


code:
/*
Minetest
Copyright (C) 2014-2016 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
Copyright (C) 2014-2017 paramat

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 MG_BIOME_HEADER
#define MG_BIOME_HEADER

#include "objdef.h"
#include "nodedef.h"
#include "noise.h"

class Server;
class Settings;
class BiomeManager;

////
//// Biome
////

typedef u8 biome_t;

#define BIOME_NONE ((biome_t)0)

// TODO(hmmmm): Decide whether this is obsolete or will be used in the future
enum BiomeType {
	BIOMETYPE_NORMAL,
	BIOMETYPE_LIQUID,
	BIOMETYPE_NETHER,
	BIOMETYPE_AETHER,
	BIOMETYPE_FLAT,
};

class Biome : public ObjDef, public NodeResolver {
public:
	u32 flags;

	content_t c_top;
	content_t c_filler;
	content_t c_stone;
	content_t c_water_top;
	content_t c_water;
	content_t c_river_water;
	content_t c_riverbed;
	content_t c_dust;

	s16 depth_top;
	s16 depth_filler;
	s16 depth_water_top;
	s16 depth_riverbed;

	s16 y_min;
	s16 y_max;
	float heat_point;
	float humidity_point;

	virtual void resolveNodeNames();
};

////
//// BiomeGen
////

enum BiomeGenType {
	BIOMEGEN_ORIGINAL,
};

struct BiomeParams {
	virtual void readParams(const Settings *settings) = 0;
	virtual void writeParams(Settings *settings) const = 0;
	virtual ~BiomeParams() {}

	s32 seed;
};

class BiomeGen {
public:
	virtual ~BiomeGen() {}
	virtual BiomeGenType getType() const = 0;

	// Calculates the biome at the exact position provided.  This function can
	// be called at any time, but may be less efficient than the latter methods,
	// depending on implementation.
	virtual Biome *calcBiomeAtPoint(v3s16 pos) const = 0;

	// Computes any intermediate results needed for biome generation.  Must be
	// called before using any of: getBiomes, getBiomeAtPoint, or getBiomeAtIndex.
	// Calling this invalidates the previous results stored in biomemap.
	virtual void calcBiomeNoise(v3s16 pmin) = 0;

	// Gets all biomes in current chunk using each corresponding element of
	// heightmap as the y position, then stores the results by biome index in
	// biomemap (also returned)
	virtual biome_t *getBiomes(s16 *heightmap) = 0;

	// Gets a single biome at the specified position, which must be contained
	// in the region formed by m_pmin and (m_pmin + m_csize - 1).
	virtual Biome *getBiomeAtPoint(v3s16 pos) const = 0;

	// Same as above, but uses a raw numeric index correlating to the (x,z) position.
	virtual Biome *getBiomeAtIndex(size_t index, s16 y) const = 0;

	// Result of calcBiomes bulk computation.
	biome_t *biomemap;

protected:
	BiomeManager *m_bmgr;
	v3s16 m_pmin;
	v3s16 m_csize;
};

////
//// BiomeGen implementations
////

//
// Original biome algorithm (Whittaker's classification + surface height)
//

struct BiomeParamsOriginal : public BiomeParams {
	BiomeParamsOriginal() :
		np_heat(50, 50, v3f(1000.0, 1000.0, 1000.0), 5349, 3, 0.5, 2.0),
		np_humidity(50, 50, v3f(1000.0, 1000.0, 1000.0), 842, 3, 0.5, 2.0),
		np_heat_blend(0, 1.5, v3f(8.0, 8.0, 8.0), 13, 2, 1.0, 2.0),
		np_humidity_blend(0, 1.5, v3f(8.0, 8.0, 8.0), 90003, 2, 1.0, 2.0)
	{
	}

	virtual void readParams(const Settings *settings);
	virtual void writeParams(Settings *settings) const;

	NoiseParams np_heat;
	NoiseParams np_humidity;
	NoiseParams np_heat_blend;
	NoiseParams np_humidity_blend;
};

class BiomeGenOriginal : public BiomeGen {
public:
	BiomeGenOriginal(BiomeManager *biomemgr,
		BiomeParamsOriginal *params, v3s16 chunksize);
	virtual ~BiomeGenOriginal();

	BiomeGenType getType() const { return BIOMEGEN_ORIGINAL; }

	Biome *calcBiomeAtPoint(v3s16 pos) const;
	void calcBiomeNoise(v3s16 pmin);

	biome_t *getBiomes(s16 *heightmap);
	Biome *getBiomeAtPoint(v3s16 pos) const;
	Biome *getBiomeAtIndex(size_t index, s16 y) const;

	Biome *calcBiomeFromNoise(float heat, float humidity, s16 y) const;

	float *heatmap;
	float *humidmap;

private:
	BiomeParamsOriginal *m_params;

	Noise *noise_heat;
	Noise *noise_humidity;
	Noise *noise_heat_blend;
	Noise *noise_humidity_blend;
};

////
//// BiomeManager
////

class BiomeManager : public ObjDefManager {
public:
	BiomeManager(Server *server);
	virtual ~BiomeManager();

	const char *getObjectTitle() const
	{
		return "biome";
	}

	static Biome *create(BiomeType type)
	{
		return new Biome;
	}

	BiomeGen *createBiomeGen(BiomeGenType type, BiomeParams *params, v3s16 chunksize)
	{
		switch (type) {
		case BIOMEGEN_ORIGINAL:
			return new BiomeGenOriginal(this,
				(BiomeParamsOriginal *)params, chunksize);
		default:
			return NULL;
		}
	}

	static BiomeParams *createBiomeParams(BiomeGenType type)
	{
		switch (type) {
		case BIOMEGEN_ORIGINAL:
			return new BiomeParamsOriginal;
		default:
			return NULL;
		}
	}

	virtual void clear();

private:
	Server *m_server;

};

#endif