From 3f8261830e0503cd59d8713d5c9aab12fc1491db Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?D=C3=A1niel=20Juh=C3=A1sz?= Date: Wed, 4 Jan 2017 19:18:40 +0100 Subject: 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()). --- src/environment.cpp | 241 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 241 insertions(+) (limited to 'src/environment.cpp') diff --git a/src/environment.cpp b/src/environment.cpp index ac9b5b079..8c0daf87b 100644 --- a/src/environment.cpp +++ b/src/environment.cpp @@ -43,8 +43,11 @@ with this program; if not, write to the Free Software Foundation, Inc., #include "daynightratio.h" #include "map.h" #include "emerge.h" +#include "raycast.h" +#include "voxelalgorithms.h" #include "util/serialize.h" #include "util/basic_macros.h" +#include "util/pointedthing.h" #include "threading/mutex_auto_lock.h" #define LBM_NAME_ALLOWED_CHARS "abcdefghijklmnopqrstuvwxyz0123456789_:" @@ -2848,4 +2851,242 @@ ClientEnvEvent ClientEnvironment::getClientEvent() return event; } +ClientActiveObject * ClientEnvironment::getSelectedActiveObject( + const core::line3d &shootline_on_map, v3f *intersection_point, + v3s16 *intersection_normal) +{ + std::vector objects; + getActiveObjects(shootline_on_map.start, + shootline_on_map.getLength() + 3, objects); + const v3f line_vector = shootline_on_map.getVector(); + + // Sort them. + // After this, the closest object is the first in the array. + std::sort(objects.begin(), objects.end()); + + /* Because objects can have different nodebox sizes, + * the object whose center is the nearest isn't necessarily + * the closest one. If an object is found, don't stop + * immediately. */ + + f32 d_min = shootline_on_map.getLength(); + ClientActiveObject *nearest_obj = NULL; + for (u32 i = 0; i < objects.size(); i++) { + ClientActiveObject *obj = objects[i].obj; + + aabb3f *selection_box = obj->getSelectionBox(); + if (selection_box == NULL) + continue; + + v3f pos = obj->getPosition(); + + aabb3f offsetted_box(selection_box->MinEdge + pos, + selection_box->MaxEdge + pos); + + if (offsetted_box.getCenter().getDistanceFrom( + shootline_on_map.start) > d_min + 9.6f*BS) { + // Probably there is no active object that has bigger nodebox than + // (-5.5,-5.5,-5.5,5.5,5.5,5.5) + // 9.6 > 5.5*sqrt(3) + break; + } + + v3f current_intersection; + v3s16 current_normal; + if (boxLineCollision(offsetted_box, shootline_on_map.start, line_vector, + ¤t_intersection, ¤t_normal)) { + f32 d_current = current_intersection.getDistanceFrom( + shootline_on_map.start); + if (d_current <= d_min) { + d_min = d_current; + nearest_obj = obj; + *intersection_point = current_intersection; + *intersection_normal = current_normal; + } + } + } + + return nearest_obj; +} + +/* + Check if a node is pointable +*/ +static inline bool isPointableNode(const MapNode &n, + INodeDefManager *ndef, bool liquids_pointable) +{ + const ContentFeatures &features = ndef->get(n); + return features.pointable || + (liquids_pointable && features.isLiquid()); +} + +PointedThing ClientEnvironment::getPointedThing( + core::line3d shootline, + bool liquids_pointable, + bool look_for_object) +{ + PointedThing result; + + INodeDefManager *nodedef = m_map->getNodeDefManager(); + + core::aabbox3d maximal_exceed = nodedef->getSelectionBoxIntUnion(); + // The code needs to search these nodes + core::aabbox3d search_range(-maximal_exceed.MaxEdge, + -maximal_exceed.MinEdge); + // If a node is found, there might be a larger node behind. + // To find it, we have to go further. + s16 maximal_overcheck = + std::max(abs(search_range.MinEdge.X), abs(search_range.MaxEdge.X)) + + std::max(abs(search_range.MinEdge.Y), abs(search_range.MaxEdge.Y)) + + std::max(abs(search_range.MinEdge.Z), abs(search_range.MaxEdge.Z)); + + const v3f original_vector = shootline.getVector(); + const f32 original_length = original_vector.getLength(); + + f32 min_distance = original_length; + + // First try to find an active object + if (look_for_object) { + ClientActiveObject *selected_object = getSelectedActiveObject( + shootline, &result.intersection_point, + &result.intersection_normal); + + if (selected_object != NULL) { + min_distance = + (result.intersection_point - shootline.start).getLength(); + + result.type = POINTEDTHING_OBJECT; + result.object_id = selected_object->getId(); + } + } + + // Reduce shootline + if (original_length > 0) { + shootline.end = shootline.start + + shootline.getVector() / original_length * min_distance; + } + + // Try to find a node that is closer than the selected active + // object (if it exists). + + voxalgo::VoxelLineIterator iterator(shootline.start / BS, + shootline.getVector() / BS); + v3s16 oldnode = iterator.m_current_node_pos; + // Indicates that a node was found. + bool is_node_found = false; + // If a node is found, it is possible that there's a node + // behind it with a large nodebox, so continue the search. + u16 node_foundcounter = 0; + // If a node is found, this is the center of the + // first nodebox the shootline meets. + v3f found_boxcenter(0, 0, 0); + // The untested nodes are in this range. + core::aabbox3d new_nodes; + while (true) { + // Test the nodes around the current node in search_range. + new_nodes = search_range; + new_nodes.MinEdge += iterator.m_current_node_pos; + new_nodes.MaxEdge += iterator.m_current_node_pos; + + // Only check new nodes + v3s16 delta = iterator.m_current_node_pos - oldnode; + if (delta.X > 0) + new_nodes.MinEdge.X = new_nodes.MaxEdge.X; + else if (delta.X < 0) + new_nodes.MaxEdge.X = new_nodes.MinEdge.X; + else if (delta.Y > 0) + new_nodes.MinEdge.Y = new_nodes.MaxEdge.Y; + else if (delta.Y < 0) + new_nodes.MaxEdge.Y = new_nodes.MinEdge.Y; + else if (delta.Z > 0) + new_nodes.MinEdge.Z = new_nodes.MaxEdge.Z; + else if (delta.Z < 0) + new_nodes.MaxEdge.Z = new_nodes.MinEdge.Z; + + // For each untested node + for (s16 x = new_nodes.MinEdge.X; x <= new_nodes.MaxEdge.X; x++) { + for (s16 y = new_nodes.MinEdge.Y; y <= new_nodes.MaxEdge.Y; y++) { + for (s16 z = new_nodes.MinEdge.Z; z <= new_nodes.MaxEdge.Z; z++) { + MapNode n; + v3s16 np(x, y, z); + bool is_valid_position; + + n = m_map->getNodeNoEx(np, &is_valid_position); + if (!(is_valid_position && + isPointableNode(n, nodedef, liquids_pointable))) { + continue; + } + std::vector boxes; + n.getSelectionBoxes(nodedef, &boxes, + n.getNeighbors(np, m_map)); + + v3f npf = intToFloat(np, BS); + for (std::vector::const_iterator i = boxes.begin(); + i != boxes.end(); ++i) { + aabb3f box = *i; + box.MinEdge += npf; + box.MaxEdge += npf; + v3f intersection_point; + v3s16 intersection_normal; + if (!boxLineCollision(box, shootline.start, shootline.getVector(), + &intersection_point, &intersection_normal)) { + continue; + } + f32 distance = (intersection_point - shootline.start).getLength(); + if (distance >= min_distance) { + continue; + } + result.type = POINTEDTHING_NODE; + result.node_undersurface = np; + result.intersection_point = intersection_point; + result.intersection_normal = intersection_normal; + found_boxcenter = box.getCenter(); + min_distance = distance; + is_node_found = true; + } + } + } + } + if (is_node_found) { + node_foundcounter++; + if (node_foundcounter > maximal_overcheck) { + break; + } + } + // Next node + if (iterator.hasNext()) { + oldnode = iterator.m_current_node_pos; + iterator.next(); + } else { + break; + } + } + + if (is_node_found) { + // Set undersurface and abovesurface nodes + f32 d = 0.002 * BS; + v3f fake_intersection = result.intersection_point; + // Move intersection towards its source block. + if (fake_intersection.X < found_boxcenter.X) + fake_intersection.X += d; + else + fake_intersection.X -= d; + + if (fake_intersection.Y < found_boxcenter.Y) + fake_intersection.Y += d; + else + fake_intersection.Y -= d; + + if (fake_intersection.Z < found_boxcenter.Z) + fake_intersection.Z += d; + else + fake_intersection.Z -= d; + + result.node_real_undersurface = floatToInt(fake_intersection, BS); + result.node_abovesurface = result.node_real_undersurface + + result.intersection_normal; + } + return result; +} + #endif // #ifndef SERVER -- cgit v1.2.3