Geometry Boost List: Re: [geometry] R-tree vs octomap

Subject: Re: [geometry] R-tree vs octomap
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-26 08:35:50

Hi,

2014-05-26 1:23 GMT+02:00 Andrew Hundt <athundt_at_[hidden]>:

>
>
> On Fri, May 23, 2014 at 4:47 PM, Adam Wulkiewicz <
> adam.wulkiewicz_at_[hidden]> wrote:
>>
>>  Andrew Hundt wrote:
>>
>>> I was hoping to find out a bit about the similarities and differences in
>>> capability between R-tree and an octomap, which is a bit like a volumetric
>>> or voxel base octree.
>>>
>>> Octomap:
>>> https://octomap.github.io/
>>>
>>> Does anyone have thoughts on the use cases and overlapping
>>> advantages/disadvantages of an R-tree and octomap?
>>>
>>
>> AFAIU it's an octree. The difference between an octree and rtree is that
>> the first one partions space and stores the objects occupying some space in
>> a node, and the second one gathers some close objects together and encloses
>> them in nodes.
>>
>> I think that from a user-point of view all space-indexes could allow
>> doing the same things, not only those two.
>>
>> Since octomap is used in robotics to store measurements from various 3D
>> point-sample-based sensors it probably only allows to store Points. But
>> since it's specialized, it may be somehow optimized to work well with some
>> of the algorithms used in robotics/SLAM like the Iterative Closest Point
>> algorithm which AFAIK is used in 3D SLAM.
>>
>
>
> It does have optimizations to allow stuff like ray casting (tracing). Also
> I believe that instead of storing an actual point and the value of the
> sensor data at that point in a node, typically I believe just the sensor
> data value is stored there since the node represents a region of space.
> This makes it possible to do ray casting through the volume, which wouldn't
> be as effective with a simple point based model.
>
> Perhaps with the R-tree the way to get similar functionality would be to
> place an appropriate geometry like a box circle or perhaps an ellipse in an
> appropriate region, then use segment queries to simulate something like ray
> tracing.
>

Box regions aligned WRT a grid corresponding to the lowest level of the
octree could be stored in the Rtree, this way the same effect could be
achieved.

Ray queries are possible in the R-tree, they're even experimentally
supported in the Boost.Geometry rtree. E.g. see:
https://github.com/boostorg/geometry/blob/develop/index/example/benchmark_experimental.cppbut
it should also be available in the release 1.55. They're called path
queries because Segments and LineStrings can be passed as an argument.
This functionality isn't officially released yet because:
1. It gives correct results only in the cartesian CS
2. I'm not sure if this shouldn't be replaced by some more general
user-defined nearest predicate

Btw, why is the ray query needed? Wouldn't a spatial query be enough to get
the sample's corresponding voxel to update it?
Or maybe the closest voxel must be updated because on the obstacles' edges
samples distances may be noisy?

>
> I'm not sure how performance would compare, and I haven't tested it. It
> may vary a lot based on how sparse/dense the data is and the number of
> entries. I would hypothetically expect the octomap to have an advantage as
> density increases since with fixed voxels repeated entries at the same
> location would affect confidence levels rather than increasing the total
> amount of data stored. Perhaps there would also be a similar way to elide
> data with R-trees as well and thus mitigate that possible source of
> performance differences.
>

Yes, as I wrote above, the R-tree could be used to always store Boxes of a
grid of the lowest level of the quadtree - voxels. Since the R-tree is an
index and its interface doesn't allow the modification of the stored
values, voxels geometrical data (Box) should be stored with some ID, and
voxels data should be stored in some container outside the R-tree. Or some
custom updating visitor could be used for this, but this is not officially
supported.

>
>
>>
>> Did you check it out? E.g. did you do some benchmarking?
>>
>
>
> I know others who do actually use octomap and if I recall correctly the
> performance is reasonably good but could improve for situations with
> millions of data points, although I don't have more specific data.
>
>
Thanks for sharing this. It would be interesting to see how the R-tree
performs in such use-case.

Regards,
Adam