Geometry Boost List: [geometry] Performence issue with RTree

Subject: [geometry] Performence issue with RTree
From: Cyber Momo (cybermomo_at_[hidden])
Date: 2017-03-30 07:48:13

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.

Thank you.

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;

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

// loop i used for testing
    foundUnit = nullptr;
    std::chrono::steady_clock::time_point begin7 =
std::chrono::steady_clock::now();
    for (uint32 i = 0; i < 100000; ++i)
    {
        player->GetMap()->GetNearObject(foundUnit,
AnyAliveUnitInObjectRangeCheck, player->GetPosition(), 100,
TYPEMASK_PLAYER_OR_UNIT);
    }
    std::chrono::steady_clock::time_point end7 = std::chrono::steady_clock::
now();
    auto mtdiff7 = std::chrono::duration_cast<std::chrono::microseconds>(end7
- begin7).count();