This week was short, on Monday and Tuesday I continued to work on a 2D lighting system . The rest of the time I spent on the implementation of quadtree trees.



In this article I will share my implementation and thoughts that arose in the process of its design.



First, I need to say why I decided to implement a quadrant tree.



Quadtree is a space partition data structure . Its main advantage over other data structures is its adaptability. It provides good performance when inserting, deleting, and searching. That is, we can use this tree in a dynamic context where data often changes. Moreover, this structure is quite easy to understand and implement.



If space partitioning is a new topic for you, then I recommend reading this article by Robert Nistrom. If you want to learn more about quadrant trees, then read this or this article.



There are areas in my game in which using quadtree instantly pays off:

• When recognizing collisions, the quadrant tree is much more efficient than the brute-force method (testing all pairs). But this is not the most effective approach, an overview of various techniques and benchmarks can be studied in this article . However, for the first version of my physics engine, I use it. Perhaps later, if necessary, I will choose a more specialized algorithm.
• In the scene graph, when performing clipping, I can use quadtree to search for all visible nodes.
• In a lighting system, you can use quadtree to find walls that intersect the polygon of visibility of the light source.
• In the AI ​​system, you can use quadtree to search for all objects or enemies that are close to the essence.
• And so on...

As you can see, quadrant trees are pretty versatile. They will be a good replenishment in your toolkit.



All the code shown in the article can be found on GitHub .

Preliminary preparation

Before detailing the quadtree code, we need small classes for geometric primitives: the Vector2



class for specifying points and the Box



class for specifying rectangles. Both will be boilerplate.

Vector2

The Vector2



class Vector2



minimalistic. It contains only constructors, as well as the +



and /



operators. That's all we need:

 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

The Box



class is not much more complicated:

 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); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

It contains some useful getters.



What is more interesting is that it contains the contains method, which checks whether the rectangle is inside another, and the intersects



method, which checks whether the rectangle intersects with another.



We will use contains



when inserting and deleting, and intersects



when recognizing intersections.

Quadtree

Here is the Quadtree



class 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]); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

As you can see, Quadtree



is a template class. This will allow us to use the class for various purposes, which I talked about at the beginning.



Template Options:

• T
  
  
  
  : the type of values ​​that will be contained in quadtree. T
  
  
  
  should be a lightweight class because it will be stored inside a quadtree. Ideally, this should be a pointer or a small simple data structure (POD).
• GetBox
  
  
  
  : the type of the called object that will receive the value at the input and return a rectangle.
• Equal
  
  
  
  : the type of the called object to check if two values ​​are equal. By default, we use the standard equality operator.
• Float
  
  
  
  : The arithmetic type used in calculations. By default, we use float
  
  
  
  .

At the beginning of the class definition, there are three static assertions for checking the validity of the template parameters.



Let's take a look at the definition of a node. A node simply stores pointers to its four child nodes and a list of the values ​​contained in it. We do not store in it its bounding box or depth, they will be calculated on the fly.



I conducted benchmarks of both approaches (with preserving a rectangle with depth and without preservation) and did not find any performance degradation when calculating them on the fly. Moreover, it saves a little memory.



To be able to distinguish an internal node from a sheet, the isLeaf



method isLeaf



. It just checks that the first child is not null. Since null are either all child nodes, or none of them, it is enough to check only the first one.



Now we can look at the Quadtree



member Quadtree



:

• mBox
  
  
  
  is a global bounding box. All values ​​inserted into quadtree must be contained within it.
• mRoot
  
  
  
  is the root of quadtree.
• mGetBox
  
  
  
  is the called object, which we will use to get the rectangle from the value.
• mEqual
  
  
  
  is the called object, which we will use to verify the equality of the two values.

The constructor simply sets mBox



, mGetBox



and mEqual



, and also creates a root node.



The last two parameters that we have not talked about yet are Threshold



and MaxDepth



. Threshold



is the maximum number of values ​​that a node can contain before we divide it. MaxDepth



is the maximum depth of a node, we stop trying to split the nodes that are on MaxDepth



, because if you split too much, it can hinder performance. I gave these constants reasonable values ​​suitable for most cases. You can try to optimize them for your configuration.



Now we are ready to start more interesting operations.

Insert and delete

Before I show the insert code, we need to discuss which nodes will contain the values. There are two strategies:

• Values ​​are stored only in leaves. Since the bounding box of a value can interact with multiple leaves, the value will be stored in all of these leaves.
• Values ​​can be stored in all nodes. We save the value to the smallest node that completely contains its bounding box.

If the bounding rectangles are small and approximately the same size, then the first strategy is more effective when looking for intersections. However, if large rectangles exist, degenerate cases may occur in which performance will be very poor. For example, if we insert a value whose rectangle is in the global bounding box, it will be added to all leaves. And if we insert a Threshold



for such values, then all nodes will be divided until MaxDepth



reached and the values ​​are not in all leaves. Therefore, quadtree will contain $$$\ texttt {Threshold} \ times 4 ^ {\ texttt {MaxDepth}}$ values, and that’s ... a lot.



Moreover, in the first strategy, inserting and deleting will be a little slower, because we have to insert (or delete) all nodes that intersect the value.



Therefore, I will use the second strategy, in which there are no degenerate cases. Since I plan to use quadtree in various contexts, it will be more convenient. In addition, this strategy is more suitable for dynamic contexts in which a lot of insertions and deletions are performed to update values, for example, in a physical engine where entities are moved.



To find out in which node we will insert or delete a value, we will use two auxiliary functions.



The first, computeBox



, computes the rectangle of the child node from the rectangle of the parent node and the index of its quadrant.

 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>(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

The second, getQuadrant



, returns the quadrant in which the value is located:

 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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

It returns -1



if it is not contained in any of the quadrants.



Now we are ready to consider insert and delete methods.

Insert

The add



method simply calls a private helper method:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Here is the helper method code:

 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); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

At the beginning there are a couple of assumptions that verify that we are not doing anything illogical, for example, we are not inserting a value into a node that does not contain its bounding box.



Then, if the node is a sheet, and we can insert a new value into it, i.e. we have not reached MaxDepth



or Threshold



, perform the insert. Otherwise, we share this node and try again.



If the node is internal, then we compute the quadrant that contains the bounding box of the value. If it is completely contained in the child node, we make a recursive call. Otherwise, insert into this node.



Here is the separation procedure:

 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); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We create four child nodes, and then for each value of the parent node we decide in which node (child or parent) the value should be stored.

Delete

The remove



method also simply calls a helper method:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Here is the helper method code, it is very similar to the insert code:

 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); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

If the current node is a sheet, then we remove the value from the list of values ​​of the current node

and try to combine this node with the sister nodes and its parent. Otherwise, we determine in which quadrant the bounding box of the value is located. If it is completely contained in the child node, then we make a recursive call. Otherwise, delete from the values ​​of the current node.



Since we don’t care about the order of the values ​​stored in the node, when I erase, I use a little optimization: I just change the erased value with the last one and delete it:

 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(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

We also need to take a look at 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



verifies that all child nodes are leaves and that the total number of its values ​​and the values ​​of the child nodes is less than threshold. If so, then we copy all the values ​​from the child nodes to the current node and delete the child nodes.

Intersection search

Intersection with rectangle

Finally, we got to the most interesting: to the search for intersections. The first way to use it is to get all values ​​intersecting a given rectangle. For example, this is necessary to perform clipping.



This will be query



:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

In this method, we simply select std::vector



, which will contain the values ​​that intersect the bounding box, and call the helper method:

 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); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

First, we add up all the values ​​stored in the current node that intersect with the requested rectangle. Then, if the current node is internal, we make a recursive call for each child node whose bounding rectangle intersects with the requested rectangle.

All pairwise intersections

The second supported use case is to search for all pairs of values ​​stored in the quadrant tree that intersect. This is especially useful when creating a physical engine. This problem can be solved using the query



method. And in fact, we can call query



on the bounding box of all values. However, this can be done more efficiently by adding only one intersection for a pair (with query



we will find them twice).



To realize this, we need to consider that the intersection can only occur

• between two values ​​stored in one node

or

• between the value stored in the node and another value stored in the descendant of this node.

Due to this, we need to check only the intersection between:

• value and the following values ​​stored in the same node

and

• value and values ​​stored in the descendant.

Thus, we will definitely not report the same intersection twice.



Here is the findAllIntersections



code:

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Again, we simply allocate std::vector



to store the intersections and call the helper function:

 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); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

At the first stage, intersections between the values ​​stored in the current node are checked. Then, if the current node is internal, findIntersectionInDescendants



checks for intersections between the values ​​stored in this node and the values ​​stored in its descendants. Finally, we make recursive calls.



findIntersectionsInDescendants



recursively finds intersections between the given value and all values ​​stored in the subtree:

 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); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

That's all! I repeat, all the code is posted on GitHub .

Useful resources

If you want to learn more about collision recognition and partitioning data structures, I recommend reading the book by Christer Erickson Real-Time Collision Detection . Many topics are deeply revealed in it, and at the same time the book is written in a very understandable language. Moreover, chapters can be read separately. This is a great reference source.

Conclusion

This completes the work with collision recognition. However, it is only half the physical engine. The second half is the resolution of collisions .