Geekly articles weekly

象限树和碰撞识别

图片

这个星期很短暂，在星期一和星期二，我继续研究2D照明系统 。 我剩下的时间都花在了四叉树的实现上。

在本文中，我将分享我的实现和在其设计过程中出现的想法。

首先，我需要说一下为什么决定实施象限树。

四叉树是一种空间分区数据结构 。 与其他数据结构相比，它的主要优点是适应性强。 在插入，删除和搜索时，它提供了良好的性能。 也就是说，我们可以在数据经常变化的动态上下文中使用该树。 而且，这种结构很容易理解和实现。

如果空间分区是您的新话题，那么我建议阅读Robert Nistrom的这篇文章 。 如果您想了解有关象限树的更多信息，请阅读本文或本文。

在我的游戏中，使用四叉树可立即带来收益：

  • 当检测到碰撞时，象限树比蛮力法（测试所有对）要有效得多。 但这不是最有效的方法，可以在本文中研究各种技术和基准。 但是，对于我的物理引擎的第一个版本，我使用它。 也许以后，如果需要的话，我会选择一种更专业的算法。
  • 在场景图中，执行裁剪时，我可以使用四叉树搜索所有可见节点。
  • 在照明系统中，您可以使用四叉树来查找与光源的可见多边形相交的墙。
  • 在AI系统中，您可以使用四叉树来搜索所有接近本质的对象或敌人。
  • 依此类推...

如您所见，象限树非常通用。 它们将是您工具箱中很好的补充。

文章中显示的所有代码都可以在GitHub上找到 。

初步准备


在详细说明四叉树代码之前，我们需要一些用于几何图元的Vector2 ：用于定义点的Vector2类和用于定义矩形的Box类。 两者都是样板。

矢量2


Vector2类Vector2简单。 它仅包含构造函数以及+和/运算符。 这就是我们所需要的：

 template<typename T> class Vector2 { public: T x; T y; constexpr Vector2<T>(TX = 0, TY = 0) noexcept : x(X), y(Y) { } constexpr Vector2<T>& operator+=(const Vector2<T>& other) noexcept { x += other.x; y += other.y; return *this; } constexpr Vector2<T>& operator/=(T t) noexcept { x /= t; y /= t; return *this; } }; template<typename T> constexpr Vector2<T> operator+(Vector2<T> lhs, const Vector2<T>& rhs) noexcept { lhs += rhs; return lhs; } template<typename T> constexpr Vector2<T> operator/(Vector2<T> vec, T t) noexcept { vec /= t; return vec; }

包装盒


Box类并不复杂：

 template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : left(Left), top(Top), width(Width), height(Height) { } constexpr Box(const Vector2<T>& position, const Vector2<T>& size) noexcept : left(position.x), top(position.y), width(size.x), height(size.y) { } constexpr T getRight() const noexcept { return left + width; } constexpr T getBottom() const noexcept { return top + height; } constexpr Vector2<T> getTopLeft() const noexcept { return Vector2<T>(left, top); } constexpr Vector2<T> getCenter() const noexcept { return Vector2<T>(left + width / 2, top + height / 2); } constexpr Vector2<T> getSize() const noexcept { return Vector2<T>(width, height); } constexpr bool contains(const Box<T>& box) const noexcept { return left <= box.left && box.getRight() <= getRight() && top <= box.top && box.getBottom() <= getBottom(); } constexpr bool intersects(const Box<T>& box) const noexcept { return !(left >= box.getRight() || getRight() <= box.left || top >= box.getBottom() || getBottom() <= box.top); } };

它包含一些有用的吸气剂。

更有趣的是，它包含用于检查矩形是否在另一个矩形内的contains方法和用于检查矩形是否与另一个矩形相交的intersects方法。

当插入和删除时，我们将使用contains ；在识别相交时，我们将使用相交。

四叉树


这是Quadtree类的Quadtree ：

 template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { static_assert(std::is_convertible_v<std::invoke_result_t<GetBox, const T&>, Box<Float>>, "GetBox must be a callable of signature Box<Float>(const T&)"); static_assert(std::is_convertible_v<std::invoke_result_t<Equal, const T&, const T&>, bool>, "Equal must be a callable of signature bool(const T&, const T&)"); static_assert(std::is_arithmetic_v<Float>); public: Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(), const Equal& equal = Equal()) : mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal) { } private: static constexpr auto Threshold = std::size_t(16); static constexpr auto MaxDepth = std::size_t(8); struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; }; Box<Float> mBox; std::unique_ptr<Node> mRoot; GetBox mGetBox; Equal mEqual; bool isLeaf(const Node* node) const { return !static_cast<bool>(node->children[0]); } };

如您所见， Quadtree是模板类。 这将使我们能够将类用于各种目的，这是我在开始时谈到的。

模板选项：

  • T ：将包含在四叉树中的值的类型。 T应该是一个简单的类，因为它将存储在四叉树中。 理想情况下，这应该是指针或小型简单数据结构（POD）。
  • GetBox ：将在输入处接收值并返回一个矩形的被调用对象的类型。
  • Equal ：检查两个值是否相等的被调用对象的类型。 默认情况下，我们使用标准的相等运算符。
  • Float ：计算中使用的算术类型。 默认情况下，我们使用float 。

在类定义的开头，有三个静态断言用于检查模板参数的有效性。

让我们看一下节点的定义。 一个节点仅存储指向其四个子节点的指针以及其中包含的值的列表。 我们不会在其中存储其边界框或深度，它们会即时计算出来。

我对这两种方法进行了基准测试（保留具有深度的矩形而没有保留矩形），并且在进行动态计算时未发现任何性能下降。 而且，它节省了一点内存。

为了能够将内部节点与工作表区分开， isLeaf方法。 它只是检查第一个孩子不为空。 由于null要么是所有子节点，要么都不是，因此仅检查第一个就足够了。

现在我们来看一下Quadtree成员Quadtree ：

  • mBox是一个全局边界框。 插入四叉树的所有值都必须包含在其中。
  • mRoot是四叉树的根。
  • mGetBox是被调用的对象，我们将使用该对象从值中获取矩形。
  • mEqual是被调用的对象，我们将使用它来验证两个值的相等性。

构造函数只需设置mBox ， mGetBox和mEqual ，并创建一个根节点。

我们尚未讨论的最后两个参数是Threshold和MaxDepth 。 Threshold是节点除以之前可以包含的最大值数。 MaxDepth是节点的最大深度，我们将停止尝试拆分MaxDepth上的节点，因为如果拆分过多，则会影响性能。 我为这些常数提供了适合大多数情况的合理值。 您可以尝试针对您的配置优化它们。

现在我们准备开始更多有趣的操作。

插入和删除


在显示插入代码之前，我们需要讨论哪些节点将包含值。 有两种策略：

  • 值仅存储在叶子中。 由于值的边界框可以与多个叶子交互，因此该值将存储在所有这些叶子中。
  • 值可以存储在所有节点中。 我们将值存储在完全包含其边界框的最小节点中。

如果边界矩形很小并且大小近似相同，则在寻找相交点时第一种策略会更有效。 但是，如果存在较大的矩形，则可能会出现性能下降的简并情况。 例如，如果我们插入一个矩形在全局边界框中的值，它将被添加到所有叶子中。 而且，如果我们为这些值插入Threshold值，则所有节点将被分割，直到达到MaxDepth且值不在所有叶子中为止。 因此，四叉树将包含  texttt阈值\乘以4 textttMaxDepth意思，这……很多。

此外，采用第一种策略时，插入和删除操作会稍慢一些，因为我们必须插入（或删除）与该值相交的所有节点。

因此，我将使用第二种策略，其中没有简并的案例。 由于我计划在各种情况下使用四叉树，因此会更加方便。 另外，此策略更适用于动态上下文，在该上下文中，例如，在移动实体的物理引擎中，执行了许多插入和删除操作以更新值。

为了找出要在哪个节点中插入或删除值，我们将使用两个辅助函数。

第一个是computeBox ，它通过父节点的矩形及其象限的索引来计算子节点的矩形。

 Box<Float> computeBox(const Box<Float>& box, int i) const { auto origin = box.getTopLeft(); auto childSize = box.getSize() / static_cast<Float>(2); switch (i) { // North West case 0: return Box<Float>(origin, childSize); // Norst East case 1: return Box<Float>(Vector2<Float>(origin.x + childSize.x, origin.y), childSize); // South West case 2: return Box<Float>(Vector2<Float>(origin.x, origin.y + childSize.y), childSize); // South East case 3: return Box<Float>(origin + childSize, childSize); default: assert(false && "Invalid child index"); return Box<Float>(); } }

第二个getQuadrant返回值所在的象限：

 int getQuadrant(const Box<Float>& nodeBox, const Box<Float>& valueBox) const { auto center = nodeBox.getCenter(); // West if (valueBox.getRight() < center.x) { // North West if (valueBox.getBottom() < center.y) return 0; // South West else if (valueBox.top >= center.y) return 2; // Not contained in any quadrant else return -1; } // East else if (valueBox.left >= center.x) { // North East if (valueBox.getBottom() < center.y) return 1; // South East else if (valueBox.top >= center.y) return 3; // Not contained in any quadrant else return -1; } // Not contained in any quadrant else return -1; }

如果未包含在任何象限中，则返回-1 。

现在，我们准备考虑插入和删除方法。

插入


add方法只是调用一个私有帮助器方法：

 void add(const T& value) { add(mRoot.get(), 0, mBox, value); }

这是辅助方法代码：

 void add(Node* node, std::size_t depth, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Insert the value in this node if possible if (depth >= MaxDepth || node->values.size() < Threshold) node->values.push_back(value); // Otherwise, we split and we try again else { split(node, box); add(node, depth, box, value); } } else { auto i = getQuadrant(box, mGetBox(value)); // Add the value in a child if the value is entirely contained in it if (i != -1) add(node->children[static_cast<std::size_t>(i)].get(), depth + 1, computeBox(box, i), value); // Otherwise, we add the value in the current node else node->values.push_back(value); } }

最初，有两个假设可以验证我们没有做任何不合逻辑的事情，例如，我们没有在不包含边界框的节点中插入值。

然后，如果节点是一个工作表，我们可以在其中插入一个新值，即 我们尚未达到MaxDepth或Threshold ，执行插入。 否则，我们共享此节点，然后重试。

如果节点在内部，则我们将计算包含该值边界框的象限。 如果它完全包含在子节点中，则进行递归调用。 否则，请插入该节点。

这是分离过程：

 void split(Node* node, const Box<Float>& box) { assert(node != nullptr); assert(isLeaf(node) && "Only leaves can be split"); // Create children for (auto& child : node->children) child = std::make_unique<Node>(); // Assign values to children auto newValues = std::vector<T>(); // New values for this node for (const auto& value : node->values) { auto i = getQuadrant(box, mGetBox(value)); if (i != -1) node->children[static_cast<std::size_t>(i)]->values.push_back(value); else newValues.push_back(value); } node->values = std::move(newValues); }

我们创建四个子节点，然后对于父节点的每个值，我们决定应将值存储在哪个节点（子节点或父节点）中。

删掉


remove方法还简单地调用一个辅助方法：

 void remove(const T& value) { remove(mRoot.get(), nullptr, mBox, value); }

这是帮助程序方法代码，它与插入代码非常相似：

 void remove(Node* node, Node* parent, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Remove the value from node removeValue(node, value); // Try to merge the parent if (parent != nullptr) tryMerge(parent); } else { // Remove the value in a child if the value is entirely contained in it auto i = getQuadrant(box, mGetBox(value)); if (i != -1) remove(node->children[static_cast<std::size_t>(i)].get(), node, computeBox(box, i), value); // Otherwise, we remove the value from the current node else removeValue(node, value); } }

如果当前节点是一个工作表，那么我们将从当前节点的值列表中删除该值
并尝试将此节点与姐妹节点及其父节点合并。 否则，我们确定该值的边界框位于哪个象限中。 如果它完全包含在子节点中，则我们进行递归调用。 否则，从当前节点的值中删除。

由于我们不在乎节点中存储的值的顺序，因此在擦除时，我会进行一些优化：我只更改了最后一个值，然后将其删除：

 void removeValue(Node* node, const T& value) { // Find the value in node->values auto it = std::find_if(std::begin(node->values), std::end(node->values), [this, &value](const auto& rhs){ return mEqual(value, rhs); }); assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); // Swap with the last element and pop back *it = std::move(node->values.back()); node->values.pop_back(); }

我们还需要看一下tryMerge ：

 void tryMerge(Node* node) { assert(node != nullptr); assert(!isLeaf(node) && "Only interior nodes can be merged"); auto nbValues = node->values.size(); for (const auto& child : node->children) { if (!isLeaf(child.get())) return; nbValues += child->values.size(); } if (nbValues <= Threshold) { node->values.reserve(nbValues); // Merge the values of all the children for (const auto& child : node->children) { for (const auto& value : child->values) node->values.push_back(value); } // Remove the children for (auto& child : node->children) child.reset(); } }

tryMerge验证所有子节点都是叶子，并且其值的总数和子节点的值均小于阈值。 如果是这样，则我们将所有值从子节点复制到当前节点并删除子节点。

交叉口搜索


矩形相交


最后，我们得到了最有趣的东西：寻找相交点。 第一种使用方法是获取与给定矩形相交的所有值。 例如，需要执行裁剪。

这将query来query ：

 std::vector<T> query(const Box<Float>& box) const { auto values = std::vector<T>(); query(mRoot.get(), mBox, box, values); return values; }

在此方法中，我们只需选择std::vector ，它将包含与边界框相交的值，然后调用helper方法：

 void query(Node* node, const Box<Float>& box, const Box<Float>& queryBox, std::vector<T>& values) const { assert(node != nullptr); assert(queryBox.intersects(box)); for (const auto& value : node->values) { if (queryBox.intersects(mGetBox(value))) values.push_back(value); } if (!isLeaf(node)) { for (auto i = std::size_t(0); i < node->children.size(); ++i) { auto childBox = computeBox(box, static_cast<int>(i)); if (queryBox.intersects(childBox)) query(node->children[i].get(), childBox, queryBox, values); } } }

首先，我们将存储在当前节点中与所请求矩形相交的所有值相加。 然后，如果当前节点在内部，则对边界矩形与请求的矩形相交的每个子节点进行递归调用。

所有成对相交


第二个受支持的用例是搜索相交的象限树中存储的所有值对。 这在创建物理引擎时特别有用。 可以使用query方法解决此问题。 实际上，我们可以在所有值的边界框上调用query 。 但是，通过为一对仅添加一个交叉点可以更有效地完成此操作（通过query我们将发现它们两次）。

要实现这一点，我们需要考虑相交只能发生

  • 一个节点中存储的两个值之间

或

  • 在节点中存储的值和此节点的后代中存储的另一个值之间。

因此，我们只需要检查以下项之间的交集：

  • 值和以下值存储在同一节点中

和

  • 值和存储在后代中的值。

因此，我们绝对不会两次报告​​同一路口。

这是findAllIntersections代码：

 std::vector<std::pair<T, T>> findAllIntersections() const { auto intersections = std::vector<std::pair<T, T>>(); findAllIntersections(mRoot.get(), intersections); return intersections; }

同样，我们只需分配std::vector来存储交集并调用helper函数：

 void findAllIntersections(Node* node, std::vector<std::pair<T, T>>& intersections) const { // Find intersections between values stored in this node // Make sure to not report the same intersection twice for (auto i = std::size_t(0); i < node->values.size(); ++i) { for (auto j = std::size_t(0); j < i; ++j) { if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) intersections.emplace_back(node->values[i], node->values[j]); } } if (!isLeaf(node)) { // Values in this node can intersect values in descendants for (const auto& child : node->children) { for (const auto& value : node->values) findIntersectionsInDescendants(child.get(), value, intersections); } // Find intersections in children for (const auto& child : node->children) findAllIntersections(child.get(), intersections); } }

在第一阶段，检查存储在当前节点中的值之间的交集。 然后，如果当前节点是内部节点，则findIntersectionInDescendants检查此节点中存储的值与其后代中存储的值之间的交集。 最后，我们进行递归调用。

findIntersectionsInDescendants递归查找给定值与子树中存储的所有值之间的交点：

 void findIntersectionsInDescendants(Node* node, const T& value, std::vector<std::pair<T, T>>& intersections) const { // Test against the values stored in this node for (const auto& other : node->values) { if (mGetBox(value).intersects(mGetBox(other))) intersections.emplace_back(value, other); } // Test against values stored into descendants of this node if (!isLeaf(node)) { for (const auto& child : node->children) findIntersectionsInDescendants(child.get(), value, intersections); } }

仅此而已！ 我重复一遍，所有代码都发布在GitHub上 。

有用的资源


如果您想了解有关碰撞识别和分区数据结构的更多信息，建议阅读Christer Erickson 实时碰撞检测的书 。 书中深刻地揭示了许多主题，同时，本书以一种非常易懂的语言编写。 此外，各章可以单独阅读。 这是一个很好的参考资料。

结论


这样就完成了碰撞识别的工作。 但是，它只是物理引擎的一半。 后半部分是解决冲突的方法 。

Source: https://habr.com/ru/post/zh-CN473066/

More articles:


All Articles