Hi,

Cyber Momo Via Geometry wrote:

Hi,

I will try to explain clearly my performence issue.
The following code work great and result is as expected.
Idea is to store on my RTree position and pointer of the WorldObject.
I can so use RTree for spacial queries and do required check on element before returning the result.

My RTree is filled by approximatly 50k elements.
The queries by the core have to be done 100k times every 100ms (about 2 times per object with differents check)

I should mention that my cpu is not obsolete with 4core/8T at 3.6Ghz.
So i used that code for testing it.
It look like that nearest predicate is pretty slow on my system. I got the min return time between 600-700ms after 100k queries.
Do not consider the check in the loop time as the result of within and nearest predicate contain never more than 20 objects and check is pretty fast.

Is that normal? Maybe i made some mistake or there is something that i can do to optimize that.
I would love to have your opinion.

So as a start the compiler optimization should be enabled, but you know that for sure.
There are also many assertions in the R-tree so you could disable them by defining NDEBUG.

typedef boost::geometry::model::point<float, 3, boost::geometry::cs::cartesian> Point3D;
typedef std::pair<Point3D, WorldObject*> RTreeElement;

// define custom equal comparison is needed for pointer type
struct WObjEqualTo
{
    bool operator()(RTreeElement const& v1, RTreeElement const& v2) const
    {
        return boost::geometry::equals(v1.first, v2.first)
            && v1.second == v2.second;
    }
};

// finally we can define our RTree type
typedef boost::geometry::index::rtree< RTreeElement, boost::geometry::index::quadratic<16>, boost::geometry::index::indexable<RTreeElement>, WObjEqualTo > WorldRTree;

You could experiment with the balancing algorithm, rstar should generate a better tree for querying. You could also play with the Max number of elements and set it to something lower than 16, so e.g. rtree<4>. Setting lower value could speed up balancing algorithm in cases when there was no overlap between objects but slow down querying if there was overlap. And if it was possible you should pass all of the points in the constructor of the R-tree in order to use packing algorithm.

// method to do queries
template<typename CheckType, class ObjectType>
void Map::GetNearObject(ObjectType& resultObj, CheckType& check, Point3D centerPoint, float radius, TypeMask typeMask /*= TYPEMASK_WORLDOBJECT*/) const
{
    namespace bg = boost::geometry;
    namespace bgi = boost::geometry::index;

    typedef bg::model::box<Point3D> box;
    box visibleBox(Point3D(centerPoint.get<0>() - radius, centerPoint.get<1>() - radius, centerPoint.get<2>() - radius), Point3D(centerPoint.get<0>() + radius, centerPoint.get<1>() + radius, centerPoint.get<2>() + radius));
    for (WorldRTree::const_query_iterator it = m_worldRtree.qbegin(bgi::within(visibleBox) && bgi::nearest(centerPoint, 1000)); it != m_worldRtree.qend(); ++it)

Ok I'm slightly confused, k in nearest predicate is pretty big (1000) and you mentioned above that there should be max 20 objects there so my guess is that you want to get all of them. From the code I see that you want to get only 1 closest object meeting some additional criteria (condition below). So I'm not sure what is the endgoal. I'm guessing that in a game probably all of the objects within some effective range should be handled so I'll start from that.

1. Assuming you want to handle all of the objects within a range.

This would not be knn query, it'd be spatial query because you'd want to get all of the objects, not some number of the closest ones. So:
- nearest predicate woudln't be needed at all
- the additional checks could be done at the querying stage, even before the object is returned from the R-tree by using bgi::satisfies() predicate
- the squared distance could be used to avoid square root

So using the conditions below it could look like this (in C++03 because you seem to use it):
struct MyPred{    MyPred(Point3D const& p, float r, TypeMask m) : mask(m), radius(r), point(p) {}    template <typename ValueType>    bool operator(ValueType const& v) const    {        // or replace distance check with squared distance check        // e.g. CARTESIAN ONLY! bg::comparable_distance(v.first, point) < radius*radius        // and of course faster checks should be done first        // e.g. if check() was faster than distance it should be done earlier        return v.second->isType(mask) && bg::distance(v.first, point) < radius && check(v.second);    }private:    TypeMask mask;    float radius;    Point3D point; // or const& if you know that MyPred object will always be temporary object};// ...// iterator iterating through all objects of type defined by typeMask in radius around centerPoint// and this is iterator since you might want to pause the query at some point, until all of the objects are foundm_worldRtree.qbegin(bgi::within(visibleBox)                  && bgi::satisfies(MyPred(centerPoint, radius, typeMask))

2. In case you wanted to return only one closest object meeting the criteria then this is knn query with k = 1 and query iterator is not needed for that. Instead you could use query() method, but then indeed additional within() predicate should be passed to not search the whole tree, so:

std::vector<RTreeElement> results;size_t found_count = rtree.query(bgi::within(visibleBox)                               && bgi::nearest(centerPoint, 1)                               && bgi::satisfies(MyPred(centerPoint, radius, typeMask)),                                  std::back_inserter(results));
or less safer, passing a pointer as OutputIterator because you know that max 1 element will be returned:

RTreeElement result;size_t found_count = rtree.query(bgi::within(visibleBox)                               && bgi::nearest(centerPoint, 1)                               && bgi::satisfies(MyPred(centerPoint, radius, typeMask)),                                  &result);
though I'm not sure if this will speed things up dramatically.

Maybe if you described a bigger picture, what you're trying to do in general, etc. it could be possible to find a better solution. E.g. why are you creating the query iterators each time when they could be stored, the query could be paused and resumed after doing something else. Otherwise there is no need to use them, because query() method is sufficient.

    {
        if (it->second->isType(typeMask) && bg::distance(it->first, centerPoint) < radius && check(it->second))
        {
            resultObj = static_cast<ObjectType>(it->second);
            break;
        }
    }
};

<snip>

Adam