Geometry Boost List: Re: [geometry] Performence issue with RTree

Subject: Re: [geometry] Performence issue with RTree
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2017-03-30 12:48:40

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 found
m_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