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

Subject: Re: [geometry] R-tree vs octomap
From: Andrew Hundt (athundt_at_[hidden])
Date: 2014-05-25 19:23:02

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.

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.

>
> 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.

Cheers!
Andrew Hundt