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/nodedef.cpp | 141 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 141 insertions(+) (limited to 'src/nodedef.cpp') diff --git a/src/nodedef.cpp b/src/nodedef.cpp index 92cdf738e..dbbdf95d2 100644 --- a/src/nodedef.cpp +++ b/src/nodedef.cpp @@ -790,9 +790,18 @@ public: virtual void resetNodeResolveState(); virtual void mapNodeboxConnections(); virtual bool nodeboxConnects(MapNode from, MapNode to, u8 connect_face); + virtual core::aabbox3d getSelectionBoxIntUnion() const + { + return m_selection_box_int_union; + } private: void addNameIdMapping(content_t i, std::string name); + /*! + * Recalculates m_selection_box_int_union based on + * m_selection_box_union. + */ + void fixSelectionBoxIntUnion(); // Features indexed by id std::vector m_content_features; @@ -819,6 +828,14 @@ private: // True when all nodes have been registered bool m_node_registration_complete; + + //! The union of all nodes' selection boxes. + aabb3f m_selection_box_union; + /*! + * The smallest box in node coordinates that + * contains all nodes' selection boxes. + */ + core::aabbox3d m_selection_box_int_union; }; @@ -849,6 +866,8 @@ void CNodeDefManager::clear() m_name_id_mapping_with_aliases.clear(); m_group_to_items.clear(); m_next_id = 0; + m_selection_box_union.reset(0,0,0); + m_selection_box_int_union.reset(0,0,0); resetNodeResolveState(); @@ -1007,6 +1026,123 @@ content_t CNodeDefManager::allocateId() } +/*! + * Returns the smallest box that contains all boxes + * in the vector. Box_union is expanded. + * @param[in] boxes the vector containing the boxes + * @param[in, out] box_union the union of the arguments + */ +void boxVectorUnion(const std::vector &boxes, aabb3f *box_union) +{ + for (std::vector::const_iterator it = boxes.begin(); + it != boxes.end(); ++it) { + box_union->addInternalBox(*it); + } +} + + +/*! + * Returns a box that contains the nodebox in every case. + * The argument node_union is expanded. + * @param[in] nodebox the nodebox to be measured + * @param[in] features used to decide whether the nodebox + * can be rotated + * @param[in, out] box_union the union of the arguments + */ +void getNodeBoxUnion(const NodeBox &nodebox, const ContentFeatures &features, + aabb3f *box_union) +{ + switch(nodebox.type) { + case NODEBOX_FIXED: + case NODEBOX_LEVELED: { + // Raw union + aabb3f half_processed(0, 0, 0, 0, 0, 0); + boxVectorUnion(nodebox.fixed, &half_processed); + // Set leveled boxes to maximal + if (nodebox.type == NODEBOX_LEVELED) { + half_processed.MaxEdge.Y = +BS / 2; + } + if (features.param_type_2 == CPT2_FACEDIR) { + // Get maximal coordinate + f32 coords[] = { + fabsf(half_processed.MinEdge.X), + fabsf(half_processed.MinEdge.Y), + fabsf(half_processed.MinEdge.Z), + fabsf(half_processed.MaxEdge.X), + fabsf(half_processed.MaxEdge.Y), + fabsf(half_processed.MaxEdge.Z) }; + f32 max = 0; + for (int i = 0; i < 6; i++) { + if (max < coords[i]) { + max = coords[i]; + } + } + // Add the union of all possible rotated boxes + box_union->addInternalPoint(-max, -max, -max); + box_union->addInternalPoint(+max, +max, +max); + } else { + box_union->addInternalBox(half_processed); + } + break; + } + case NODEBOX_WALLMOUNTED: { + // Add fix boxes + box_union->addInternalBox(nodebox.wall_top); + box_union->addInternalBox(nodebox.wall_bottom); + // Find maximal coordinate in the X-Z plane + f32 coords[] = { + fabsf(nodebox.wall_side.MinEdge.X), + fabsf(nodebox.wall_side.MinEdge.Z), + fabsf(nodebox.wall_side.MaxEdge.X), + fabsf(nodebox.wall_side.MaxEdge.Z) }; + f32 max = 0; + for (int i = 0; i < 4; i++) { + if (max < coords[i]) { + max = coords[i]; + } + } + // Add the union of all possible rotated boxes + box_union->addInternalPoint(-max, nodebox.wall_side.MinEdge.Y, -max); + box_union->addInternalPoint(max, nodebox.wall_side.MaxEdge.Y, max); + break; + } + case NODEBOX_CONNECTED: { + // Add all possible connected boxes + boxVectorUnion(nodebox.fixed, box_union); + boxVectorUnion(nodebox.connect_top, box_union); + boxVectorUnion(nodebox.connect_bottom, box_union); + boxVectorUnion(nodebox.connect_front, box_union); + boxVectorUnion(nodebox.connect_left, box_union); + boxVectorUnion(nodebox.connect_back, box_union); + boxVectorUnion(nodebox.connect_right, box_union); + break; + } + default: { + // NODEBOX_REGULAR + box_union->addInternalPoint(-BS / 2, -BS / 2, -BS / 2); + box_union->addInternalPoint(+BS / 2, +BS / 2, +BS / 2); + } + } +} + + +inline void CNodeDefManager::fixSelectionBoxIntUnion() +{ + m_selection_box_int_union.MinEdge.X = floorf( + m_selection_box_union.MinEdge.X / BS + 0.5f); + m_selection_box_int_union.MinEdge.Y = floorf( + m_selection_box_union.MinEdge.Y / BS + 0.5f); + m_selection_box_int_union.MinEdge.Z = floorf( + m_selection_box_union.MinEdge.Z / BS + 0.5f); + m_selection_box_int_union.MaxEdge.X = ceilf( + m_selection_box_union.MaxEdge.X / BS - 0.5f); + m_selection_box_int_union.MaxEdge.Y = ceilf( + m_selection_box_union.MaxEdge.Y / BS - 0.5f); + m_selection_box_int_union.MaxEdge.Z = ceilf( + m_selection_box_union.MaxEdge.Z / BS - 0.5f); +} + + // IWritableNodeDefManager content_t CNodeDefManager::set(const std::string &name, const ContentFeatures &def) { @@ -1037,6 +1173,8 @@ content_t CNodeDefManager::set(const std::string &name, const ContentFeatures &d verbosestream << "NodeDefManager: registering content id \"" << id << "\": name=\"" << def.name << "\""<