Improve getPointedThing() (#4346)

* Improved getPointedThing()

The new algorithm checks every node exactly once.
Now the point and normal vector of the collision is also returned in the
PointedThing (currently they are not used outside of the function).
Now the CNodeDefManager keeps the union of all possible nodeboxes, so
the raycast won't miss any nodes. Also if there are only small
nodeboxes, getPointedThing() is exceptionally fast.
Also adds unit test for VoxelLineIterator.

* Cleanup, code move

This commit moves getPointedThing() and
Client::getSelectedActiveObject() to ClientEnvironment.
The map nodes now can decide which neighbors they are connecting to
(MapNode::getNeighbors()).

2 files changed, 73 insertions, 42 deletions

diff --git a/src/util/pointedthing.cpp b/src/util/pointedthing.cpp
index cd13000b5..ed3d4bb67 100644
--- a/src/util/pointedthing.cpp
+++ b/src/util/pointedthing.cpp
@@ -27,29 +27,25 @@ PointedThing::PointedThing():
 	type(POINTEDTHING_NOTHING),
 	node_undersurface(0,0,0),
 	node_abovesurface(0,0,0),
+	node_real_undersurface(0,0,0),
+	intersection_point(0,0,0),
+	intersection_normal(0,0,0),
 	object_id(-1)
 {}
 
 std::string PointedThing::dump() const
 {
 	std::ostringstream os(std::ios::binary);
-	if(type == POINTEDTHING_NOTHING)
-	{
+	if (type == POINTEDTHING_NOTHING) {
 		os<<"[nothing]";
-	}
-	else if(type == POINTEDTHING_NODE)
-	{
+	} else if (type == POINTEDTHING_NODE) {
 		const v3s16 &u = node_undersurface;
 		const v3s16 &a = node_abovesurface;
 		os<<"[node under="<<u.X<<","<<u.Y<<","<<u.Z
 			<< " above="<<a.X<<","<<a.Y<<","<<a.Z<<"]";
-	}
-	else if(type == POINTEDTHING_OBJECT)
-	{
+	} else if (type == POINTEDTHING_OBJECT) {
 		os<<"[object "<<object_id<<"]";
-	}
-	else
-	{
+	} else {
 		os<<"[unknown PointedThing]";
 	}
 	return os.str();
@@ -59,61 +55,56 @@ void PointedThing::serialize(std::ostream &os) const
 {
 	writeU8(os, 0); // version
 	writeU8(os, (u8)type);
-	if(type == POINTEDTHING_NOTHING)
-	{
-		// nothing
-	}
-	else if(type == POINTEDTHING_NODE)
-	{
+	switch (type) {
+	case POINTEDTHING_NOTHING:
+		break;
+	case POINTEDTHING_NODE:
 		writeV3S16(os, node_undersurface);
 		writeV3S16(os, node_abovesurface);
-	}
-	else if(type == POINTEDTHING_OBJECT)
-	{
+		break;
+	case POINTEDTHING_OBJECT:
 		writeS16(os, object_id);
+		break;
 	}
 }
 
 void PointedThing::deSerialize(std::istream &is)
 {
 	int version = readU8(is);
-	if(version != 0) throw SerializationError(
+	if (version != 0) throw SerializationError(
 			"unsupported PointedThing version");
 	type = (PointedThingType) readU8(is);
-	if(type == POINTEDTHING_NOTHING)
-	{
-		// nothing
-	}
-	else if(type == POINTEDTHING_NODE)
-	{
+	switch (type) {
+	case POINTEDTHING_NOTHING:
+		break;
+	case POINTEDTHING_NODE:
 		node_undersurface = readV3S16(is);
 		node_abovesurface = readV3S16(is);
-	}
-	else if(type == POINTEDTHING_OBJECT)
-	{
+		break;
+	case POINTEDTHING_OBJECT:
 		object_id = readS16(is);
-	}
-	else
-	{
-		throw SerializationError(
-			"unsupported PointedThingType");
+		break;
+	default:
+		throw SerializationError("unsupported PointedThingType");
 	}
 }
 
 bool PointedThing::operator==(const PointedThing &pt2) const
 {
-	if(type != pt2.type)
+	if (type != pt2.type)
+	{
 		return false;
-	if(type == POINTEDTHING_NODE)
+	}
+	if (type == POINTEDTHING_NODE)
 	{
-		if(node_undersurface != pt2.node_undersurface)
-			return false;
-		if(node_abovesurface != pt2.node_abovesurface)
+		if ((node_undersurface != pt2.node_undersurface)
+				|| (node_abovesurface != pt2.node_abovesurface)
+				|| (node_real_undersurface != pt2.node_real_undersurface))
 			return false;
 	}
-	else if(type == POINTEDTHING_OBJECT)
+	else if (type == POINTEDTHING_OBJECT)
 	{
-		if(object_id != pt2.object_id)
+		if (object_id != pt2.object_id)
 			return false;
 	}
 	return true;
diff --git a/src/util/pointedthing.h b/src/util/pointedthing.h
index 2b2703e98..f695a4ebd 100644
--- a/src/util/pointedthing.h
+++ b/src/util/pointedthing.h
@@ -32,17 +32,57 @@ enum PointedThingType
 	POINTEDTHING_OBJECT
 };
 
+//! An active object or node which is selected by a ray on the map.
 struct PointedThing
 {
+	//! The type of the pointed object.
 	PointedThingType type;
+	/*!
+	 * Only valid if type is POINTEDTHING_NODE.
+	 * The coordinates of the node which owns the
+	 * nodebox that the ray hits first.
+	 * This may differ from node_real_undersurface if
+	 * a nodebox exceeds the limits of its node.
+	 */
 	v3s16 node_undersurface;
+	/*!
+	 * Only valid if type is POINTEDTHING_NODE.
+	 * The coordinates of the last node the ray intersects
+	 * before node_undersurface. Same as node_undersurface
+	 * if the ray starts in a nodebox.
+	 */
 	v3s16 node_abovesurface;
+	/*!
+	 * Only valid if type is POINTEDTHING_NODE.
+	 * The coordinates of the node which contains the
+	 * point of the collision and the nodebox of the node.
+	 */
+	v3s16 node_real_undersurface;
+	/*!
+	 * Only valid if type isn't POINTEDTHING_NONE.
+	 * First intersection point of the ray and the nodebox.
+	 */
+	v3f intersection_point;
+	/*!
+	 * Only valid if type isn't POINTEDTHING_NONE.
+	 * Normal vector of the intersection.
+	 * This is perpendicular to the face the ray hits,
+	 * points outside of the box and it's length is 1.
+	 */
+	v3s16 intersection_normal;
+	/*!
+	 * Only valid if type is POINTEDTHING_OBJECT.
+	 * The ID of the object the ray hit.
+	 */
 	s16 object_id;
 
 	PointedThing();
 	std::string dump() const;
 	void serialize(std::ostream &os) const;
 	void deSerialize(std::istream &is);
+	/*!
+	 * This function ignores the intersection point and normal.
+	 */
 	bool operator==(const PointedThing &pt2) const;
 	bool operator!=(const PointedThing &pt2) const;
 };