6
\$\begingroup\$

I've been working on a recursive quadtree in C++. How can I improve my code? My primary goals are improving the performance/speed, as well as practice.

QuadTree.h

#pragma once

#include <vector>
#include <algorithm>
#include <functional>

struct AABB {
    double left, top, right, bottom;

    AABB() { }
    AABB(const double &l, const double &t, const double &r, const double &b);
    bool within(const AABB&) const;
    bool intersects(const AABB&) const;
};

struct Object {
    friend class QuadTree;
public:
    AABB _bound;

    Object() { };
    Object(const AABB&, void *data = nullptr);
    void setData(void *data);
    void *getData() const;
private:
    void     *_data = nullptr;
    QuadTree *_qt   = nullptr;
};

class QuadTree {
public:
    QuadTree(const AABB&, const unsigned &capacity, const unsigned &maxLevel, 
        const unsigned &level = 0, QuadTree *parent = nullptr);

    bool insert(Object*);
    bool remove(Object*);
    void update(Object*);
    bool contains(Object*) const;
    void search(const AABB&, const std::function<void(Object*)> &callback) const;
    void query(const AABB&, std::vector<Object*> &returnObjects) const;
    bool any(const AABB&, const std::function<bool(Object*)> &condition = nullptr) const;
    unsigned getTotalChildren() const;
    unsigned getTotalObjects() const;
    void clear();

    QuadTree() { }
    ~QuadTree();
private:
    AABB                 _bound;
    QuadTree*            _parent;
    QuadTree*            _children[4];
    bool                 _isLeaf = true;
    double               _centerX;
    double               _centerY;
    unsigned             _level;
    unsigned             _maxLevel;
    unsigned             _capacity;
    std::vector<Object*> _objects;

    void subdivide();
    void discardEmptyBuckets(QuadTree *node);
    QuadTree *getChild(const AABB&) const;
};

QuadTree.cpp

#include "QuadTree.h"

//** AABB **//
AABB::AABB(const double &l, const double &t, const double &r, const double &b) :
    left(l),
    top(t),
    right(r),
    bottom(b) {
}
bool AABB::within(const AABB &bound) const {
    return left > bound.left && bottom > bound.bottom
        && right < bound.right && top < bound.top;
}
bool AABB::intersects(const AABB &bound) const {
    if (bound.right <= left) return false;
    if (bound.left >= right) return false;
    if (bound.top <= bottom) return false;
    if (bound.bottom >= top) return false;
    return true; // intersection
}

//** Object **//
Object::Object(const AABB &bound, void *data):
    _bound(bound), 
    _data(data) {
};
void Object::setData(void *data) {
    _data = data;
}
void *Object::getData() const { 
    return _data;
}

//** QuadTree **//
QuadTree::QuadTree(const AABB &bound, const unsigned &capacity, const unsigned &maxLevel, 
    const unsigned &level, QuadTree *parent):
    _capacity(capacity),
    _maxLevel(maxLevel),
    _level(level), 
    _parent(parent),
    _centerX((bound.left + bound.right) * 0.5f),
    _centerY((bound.bottom + bound.top) * 0.5f),
    _bound(bound) {
}

// Inserts an object into this quadtree
bool QuadTree::insert(Object *obj) {
    // Item already exists
    if (obj->_qt != nullptr)
        return false;

    // insert object at the lowest level
    if (!_isLeaf) {
        if (QuadTree *child = getChild(obj->_bound))
            return child->insert(obj);
    }
    _objects.push_back(obj);
    obj->_qt = this; // used for quick search by quadtree

    // Subdivide if required
    if (_isLeaf && _level < _maxLevel && _objects.size() >= _capacity) {
        subdivide();

        // Re-insert objects into new quadrant
        for (unsigned i = 0; i < _objects.size();) {
            Object *object = _objects[i];
            if (QuadTree *child = getChild(object->_bound)) {
                _objects.erase(_objects.begin() + i);
                object->_qt = nullptr;
                child->insert(object);
            }
            else ++i;
        }
    }
    return true;
}

// Removes an object from this quadtree
bool QuadTree::remove(Object *obj) {
    if (obj->_qt == nullptr)
        return false;
    if (obj->_qt != this)
        return obj->_qt->remove(obj);

    _objects.erase(std::find(_objects.begin(), _objects.end(), obj));
    obj->_qt = nullptr;
    discardEmptyBuckets(this);
    return true;
}

// Removes and re-inserts object into quadtree (for objects that move)
void QuadTree::update(Object *obj) {
    QuadTree *node = obj->_qt;
    if (node->_parent == nullptr || obj->_bound.within(node->_bound))
        return;
    // Re-insert object at the highest level
    node->remove(obj);
    do {
        node = node->_parent;
        if (obj->_bound.within(node->_bound))
            break;
    } while (node->_parent != nullptr);
    node->insert(obj);
}

// Checks if object exists in this quadtree
bool QuadTree::contains(Object *obj) const {
    if (obj->_qt == nullptr)
        return false;
    if (obj->_qt != this)
        return obj->_qt->contains(obj);

    return std::find(_objects.begin(), _objects.end(), obj) != _objects.end();
}

// Searches quadtree for objects within the provided boundary and returns them in callback
void QuadTree::search(const AABB &bound, const std::function<void(Object*)> &callback) const {
    // Search children first
    if (!_isLeaf) {
        if (QuadTree *child = getChild(bound)) {
            child->search(bound, callback);
        } else {
            for (auto&& node : _children) {
                if (node->_bound.intersects(bound))
                    node->search(bound, callback);
            }
        }
    }
    // Now search objects
    for (auto&& obj : _objects) {
        if (obj->_bound.intersects(bound))
            callback(obj);
    }
}

// Searches quadtree for objects within the provided boundary and adds them to provided vector
void QuadTree::query(const AABB &bound, std::vector<Object*> &returnObjects) const {
    search(bound, [&returnObjects](Object *obj) {
        returnObjects.push_back(obj);
    });
}

// Checks if any object exists in the specified bounds (with optional filter)
bool QuadTree::any(const AABB &bound, const std::function<bool(Object*)> &condition) const {
    bool found = false;
    search(bound, [&condition, &found](Object *obj) {
        if (condition == nullptr || condition(obj)) {
            found = true;
            return;
        }
    });
    return found;
}

// Returns total children count for this quadtree
unsigned QuadTree::getTotalChildren() const {
    unsigned count = 0;
    if (!_isLeaf) {
        for (auto&& child : _children)
            count += child->getTotalChildren();
    }
    return (_isLeaf? 0 : 4) + count;
}

// Returns total object count for this quadtree
unsigned QuadTree::getTotalObjects() const {
    unsigned count = 0;
    if (!_isLeaf) {
        for (auto&& node : _children)
            count += node->getTotalObjects();
    }
    return _objects.size() + count;
}

// Removes all objects and children from this quadtree
void QuadTree::clear() {
    if (!_objects.empty()) {
        for (auto&& obj : _objects)
            remove(obj);
        _objects.clear();
    }
    if (!_isLeaf) {
        delete _children[0];
        delete _children[1];
        delete _children[2];
        delete _children[3];
        _isLeaf = true;
    }
}

// Subdivides into four quadrants
void QuadTree::subdivide() {
    // Bottom right
    _children[0] = new QuadTree(
        { _centerX, _centerY, _bound.right, _bound.bottom },
        _capacity, _maxLevel, _level + 1, this
    );
    // Bottom left
    _children[1] = new QuadTree(
        { _bound.left, _centerY, _centerX, _bound.bottom },
        _capacity, _maxLevel, _level + 1, this
    );
    // Top left
    _children[2] = new QuadTree(
        { _bound.left, _bound.top, _centerX, _centerY },
        _capacity, _maxLevel, _level + 1, this
    );
    // Top right
    _children[3] = new QuadTree(
        { _centerX, _bound.top, _bound.right, _centerY },
        _capacity, _maxLevel, _level + 1, this
    );
    _isLeaf = false;
}

// Discards buckets if all children are leaves and contain no objects
void QuadTree::discardEmptyBuckets(QuadTree *node) {
    if (!node->_objects.empty())
        return;
    if (!node->_isLeaf) {
        for (auto &&child : node->_children) {
            if (!child->_isLeaf || !child->_objects.empty())
                return;
        }
        node->clear();
    }
    if (node->_parent != nullptr)
        discardEmptyBuckets(node->_parent);
}

// Returns child/quadrant that the provided boundary is in
QuadTree *QuadTree::getChild(const AABB &bound) const {
    bool bottom = bound.bottom > _centerY;
    bool left   = bound.left < _centerX;
    bool top    = !bottom && bound.top < _centerY;
    if (left && bound.right < _centerX) {
        if (top)    return _children[1]; // top left
        if (bottom) return _children[2]; // bottom left
    }
    else if (!left) {
        if (top)    return _children[0]; // top right
        if (bottom) return _children[3]; // bottom right
    }
    return nullptr;
}

QuadTree::~QuadTree() {
    clear();
}

I've done some profiling in VS2017 and I have found that the insert method takes the longest (i'm guessing due to the recursion), followed by AABB::intersects, then search. I have no clue on what I can do to make those methods faster. I'm curious to see what you guys have to say about it :)

\$\endgroup\$
  • \$\begingroup\$ I'm a little confused reading this. If my root-level QuadTree has bounds from, say, -1 to +1 in both directions, it will be subdivided into 4 quads from 0 to ±1, etc. If I have an object that's centered at the origin, it looks to me like it will only end up in one of the second-level quads, not all 4, which is where it needs to be. Am I misunderstanding that? \$\endgroup\$ – user1118321 May 21 '18 at 3:00
  • \$\begingroup\$ It depends on the size of the object. It will only be re-inserted into one of the second-level quadrants if its boundaries can fit inside of one (aka if getChild does not return nullptr), otherwise, it is skipped and remains inside all four quadrants. I should probably make that more clear :P \$\endgroup\$ – m-byte May 21 '18 at 3:51
  • \$\begingroup\$ remember to upvote helpful answers! \$\endgroup\$ – JDługosz May 23 '18 at 0:46
  • \$\begingroup\$ What are you using this quadtree for ? collision detection, finding closest pairs ?? \$\endgroup\$ – Harald Scheirich May 23 '18 at 1:01
  • \$\begingroup\$ @HaraldScheirich I'm using it mainly for collision detection. \$\endgroup\$ – m-byte May 23 '18 at 1:40
3
\$\begingroup\$
AABB() { }
Object() { };
QuadTree() { }

What does this do, compared with not mentioning it at all? I notice you add an empty default constructor to all your classes. Look up “the rule of five”. In the case of AABB, you can remove the other constructor and then aggregate initialization takes hold, which is the same thing you wanted. Getting rid of it means I don’t have to wonder why you are passing double by const ref instead of value.

And you have a stray ; .


Writing identifiers with a leading underscore is a bad idea, and is generally dissuaded as a style. Note that it is legal for member names if (and only if) the next character is not a capital letter or another underscore.


The Object default constructor simply allows the default data initializers to apply, so it is not necessary (and can be worse) to write it explicitly. You can use =default if you need to mention it, but leaving it off completely is best.

OTOH, you did not define a copy constructor etc. What happens when an instance is copied? The pointer members get shallow copied, which generally is not right.

Raw pointers? what is the ownership/relationship/lifetime of these data members?

A void* data member? Don’t do that. There are safe ways to do type erasure in C++, or templates to customize the payload type, std::any, etc.


QuadTree(const AABB&, const unsigned &capacity, const unsigned &maxLevel, 
    const unsigned &level = 0, QuadTree *parent = nullptr);

Why would you pass an unsigned as a const ref?

void search(const AABB&, const std::function<void(Object*)> &callback) const;

How do you use this? Normally a search takes a predicate but you have it labeled callback, and the first parameter is unnamed. I think it would be clearer to call it enumerate (If I understand what it does) and name the searched-for rectangle to be clear that’s what it is for.

void query(const AABB&, std::vector<Object*> &returnObjects) const;

Don’t use “out” parameters. Return values (⧺F.20).

std::vector<Object*> query (const AABB&) const;

You might get faster code if you declared within, intersects and whatever else you can as noexcept.

It’s odd that within and intersects are written in totally different styles when they work in the identical manner.


speed of insert

Look at branch prediction. If an if statement will go one way or the other at random (as when traversing a tree) the predictor will never get it right and you have a huge latency.


_children[0] = new QuadTree(

⧺C.149 — no naked new or delete.

I also think that allocating nodes as part of insert is why it is slow! That is inherently a slow operation. You might time the subdivide function separately and compare that to the insert time, and see what percentage it accounts for.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your feedback :) In the case of Object, I decided to just disable the copy constructor all together, since QuadTree stores a vector of pointers to Objects, copying them to other objects would render functions like remove() and contains() useless. Also that makes sense why insert is slow, I'll just make it so that they are not allocated on the heap and I add them to the array by reference instead. \$\endgroup\$ – m-byte May 22 '18 at 20:32
  • \$\begingroup\$ Also, would return values really work better than out parameters in this case? I read somewhere that returning vectors from functions is not a good idea, because the vector has a chance of being copied on the way back. For example, if I have a quadtree with 100,000 objects, and the query returns about 10,000 objects pointers, something like std::vector<Object*> foundObjects = quadTree.query(bound); could copy all 10,000 pointers to foundObjects. Or is this not the case with modern compilers? \$\endgroup\$ – m-byte May 22 '18 at 20:41
  • \$\begingroup\$ The vector will not be copied! Even if you don’t do things just right to allow NRVO, since C++11 we have move semantics. Returning the vector will just copy the pointer to the guts. \$\endgroup\$ – JDługosz May 23 '18 at 0:30
  • \$\begingroup\$ ⟪I'll just make it so that they are not allocated on the heap and I add them to the array by reference instead.⟫ I don’t know what you mean by that. \$\endgroup\$ – JDługosz May 23 '18 at 0:32
  • \$\begingroup\$ See this video from four years ago. Returning large values starts at 14:30. A minute farther, “returning a potentially large matrix by value … and it’s OK, because we automatically move from temporary objects; we don’t do deep copies — so you get the clean semantics of value types and the efficiency of reference types” \$\endgroup\$ – JDługosz May 23 '18 at 0:44
3
\$\begingroup\$

Quadtrees are very useful, so this is a good exercise to implement your own. I think you've done a reasonable job here, but I see some things that could be improved.

Naming

Always name all of your parameters in your header. It makes it so much easier for another programmer that's trying to call the methods in a class if the parameters have useful, descriptive names. For example, in the Object constructor, what is the AABB parameter? Is it the bounds of the object? Is it the bounds of the quad in a QuadTree in which the object is found? Please clarify!

Speaking of the Object class, the name Object is meaningless. Every single thing in your program (other than PODT) are objects, yet they can't all be inserted into a QuadTree. Usually quad trees are used for things like collision-detection or finding the distance to neighbors. I would rename the Object class to Collidable or something along those lines.

What is the difference between contains(), search() and query()? Just looking at the names, they all sound like the same thing. You should give them more distinct names that clarify what they actually do. Looking at the code, it seems that contains() does a shallow search of the object's QuadTree for the existence of the object. (Isn't that a tautology? Shouldn't you never be allowed to have an object's _qt be a QuadTree to which it does not belong?) search() calls a callback for every object in a bounding box. So maybe a better name would be performTaskOnObjectsInRegion() or something like that. And query() appears to collect all objects within a bounding box, so I'd call it collectObjectsInRegion() or something along those lines.

Default Constructors

All 3 of your classes have default constructors that do nothing and leave their member variables in an undefined state. Why? It would be better to disallow creating these objects in an unusable state. Instead of an axis-aligned bounding box that contains random (possibly nonsensical) values for its bounds, simply disallow creating one without bounds by using:

AABB() = delete;

This removes the default constructor and solves the problem of an invalid object being created. Likewise, if you do the same for Object, then you never need for its _bound to be invalid. You can then also remove the setData() method as its data will always be set in the constructor. (I'd also remove the default nullptr value as there's no use in having an Object with no data.) Likewise with QuadTree. Doing this eliminates a huge class of bugs that crop up from badly initialized instances of objects.

Performance

I ran a profile of inserting 100,000 objects into a QuadTree. The slowest part (84% of runtime in my experiment) is the call to vector::erase(). The reason is that this causes the rest of the elements in the vector to be moved back 1 spot. It ends up being a bunch of calls to memmove(). It might be worth trying other containers instead of std::vector. One that has O(1) removal would fix this problem. Or, you could swap the object that you're currently working on with the last object in the vector and then erase only the last object. Doing this removed insert() from even showing up in my traces. (I didn't do much verification of the resulting QuadTree because there are no tests here, and no examples of how to use it, so make sure you do a lot of tests before going with that method.) It looked like this:

    // Re-insert objects into new quadrant
    for (unsigned i = 0; i < _objects.size();) {
        Object *object = _objects[i];
        if (QuadTree *child = getChild(object->_bound)) {
            std::swap(*(_objects.begin() + i), *(_objects.end() - 1));
            _objects.erase(_objects.end() - 1);
            object->_qt = nullptr;
            child->insert(object);
        }
        else ++i;
    }
\$\endgroup\$
  • \$\begingroup\$ stackoverflow.com/q/347441/5416291 there's a term for that. \$\endgroup\$ – bruglesco May 22 '18 at 13:52
  • \$\begingroup\$ Thank you! I'm in the process of renaming most of the program now. I thought that contains() would be a useful since an object's qt isn't meant to be accessed by anything other than the QuadTree itself, so anyone who would like to check can just use that instead of the if statement. Also the reason why I had default constructors for every class is so I could initialize them later before I insert them into the quadtree.. but I see now that it was a bad idea haha. I'll make sure that isn't possible. \$\endgroup\$ – m-byte May 22 '18 at 20:06
  • \$\begingroup\$ Also why insert was slow makes a lot of sense now. I didn't realize how muchvector::erase() was bottle necking my code until I actually thought about what it was doing. I'll try your method and see if it holds up, if not Ill try your suggestion of using another container. Which one would you suggest would work best in this scenario? \$\endgroup\$ – m-byte May 22 '18 at 20:18
  • \$\begingroup\$ My first thought was to use a std::set instead of std::vector, since you don't care about the order of the elements. But there's a tradeoff in that insertions are O(log(n)). If the above swap and delete works, I'd just keep that. \$\endgroup\$ – user1118321 May 23 '18 at 3:22
1
\$\begingroup\$

Some things I haven't seen in the previous reviews, or I just plain missed ...

Quadtree

With moving object the quadtree might not be your best choice, at best an object will move from one child into the next but at worst you could have to delete a whole bunch as the path that the item is on might become empty and you have to remove all the children. Having multiple objects per node also forces you to keep a dynamic data structure in the node, that is not ideal. An alternative solution is the AABB Tree, (http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/) has a good description. As this tree only has one object per leaf at max and has a max number of nodes you can preallocate the memory and you can use a linear store for all the nodes. Additionally it is possible to change the object AABBs and update the structure with new bounding boxes. If updating the tree usually you'll check for an amount of change that will trigger a rebuild.

Depending on the number of objects, you might just be quicker doing a pairwise AABB test, did you do the timing ?

Allocations

Each insertion and removal incurs a good number of deallocations and allocations, if you want to stick with the quad-tree you can save on allocations by preserving children that you have already allocated and only allocating when needed.

update()

Your update calls remove() and insert() which updates the array twice, that is not optimal. If you're doing collision detection, in most cases you'll probably have a bunch of updates to do at the same time. If you can utilize this you might be able to improve your performance.

Do you really need it ?

  • _maxLevel and _level are never read in the code, do you really need it ?
  • contains() are you sure you ever need to test if a specific object is in the tree ? Meaning are you ever in a state where there are objects that might be in the tree ? If you can get rid of that function, you can get rid of the tracking std::vector<> the maintainance of which cost a lot of time.

_children

_children could be a std::array rather than a c-array;

Formatting

I'm not a fan of use of braces like this

if (!_isLeaf) {
    if (QuadTree *child = getChild(obj->_bound))
        return child->insert(obj);
}

What made you put the first pair of brace in ? Just because it looks complicated ? A rule of thumb I use is, "you can skip the braces if it fits in one line, e.g.

if (obj->_qt != nullptr) return false;

Naming

contains, query, search, any do very similar things, contains, getObjectsInBound, search could be labeled as forEachObjectInBound (similar to std::for_each with bounds), and any is findEachObjectInBoundIf (similar to std::find_if with bounds)

Consider std::algorithm

Your trio of query, search and any could be replaced by always using the following search()

void QuadTree::query(const AABB &bound, std::vector<Object*> &returnObjects) const {
    if (!_isLeaf) {
        if (QuadTree *child = getChild(bound)) {
            child->search(bound, returnObjects);
        } else {
            for (auto&& node : _children) {
                if (node->_bound.intersects(bound))
                    node->search(bound, returnObjects);
            }
        }
    }
    // Now search objects
    for (auto&& obj : _objects) {
        if (obj->_bound.intersects(bound))
            returnObjects.push_back(obj);
    }
}

And then use std::foreach or std::find_if on it. Although if you use any() a lot you would want to implement it in a way it exits as sound as the condition is satisfied, your implementation finds all objects no matter if the condition is true early.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.