Game Development Reference
In-Depth Information
same, it will continue partitioning the space horizontally until the object fits, or until it de-
termines that it cannot fit.
We will start by defining the node, a node will represent an area of space, it may be empty,
in which case it may be partitioned if necessary, or it may be in use, which means there is
a texture in it. A node may also be a leaf, this means it is un-partitioned space (it has no
children nodes).
class node
{
public:
node() : m_isEmpty(true) { }
std::shared_ptr<node>& Child(int i) { return m_children[i]; }
const bool IsLeaf() const
{
return m_children[0] == nullptr &&
m_children[0] == m_children[1];
}
bool& IsEmpty() { return m_isEmpty; }
math::rectangle& Rectangle() { return m_rectangle; }
private:
bool m_isEmpty;
std::shared_ptr<node> m_children[2];
math::rectangle m_rectangle;
};
The entry point for the algorithm is inserting a new rectangle into the texture, it is a recurs-
ive process that begins by creating the root partition if one does not yet exist.
std::shared_ptr<node> Insert(const math::rectangle& rectangle)
{
if ( m_root == nullptr )
{
m_root = std::shared_ptr<node>(new node() );
m_root->Rectangle() = rectangle;
return m_root;
}
return Insert(m_root, rectangle);
}
The algorithm lives within the private Insert function which takes two parameters, a node
and the area that is being added, if successful, the algorithm will return the node in which
the rectangle was added, if it fails it will return
nullptr
and it will be up to the caller to
handle the error case.
