Boost logo

Geometry :

Subject: Re: [geometry] Adapters at the point and/or box abstraction level?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-28 07:22:45

Hi Patrick,

Patrick J. Lopresti wrote:
> I have an existing library of code dealing with 2D points, boxes,
> etc., and I am looking for a good spatial index. I believe
> boost::geometry::rtree might fit the bill.
> However...
> My library uses SSE registers to represent 2D points/vectors. This
> makes the operations I care about very fast (e.g. vector arithmetic,
> box union/intersection), but accessing the components of a point is a
> bit painful.

This is very interesting. Some time ago I thought about using SEE or AVX
in algorithms if those operations were supported. I tought the release
of Boost.SIMD would be a good time to do it, assuming it will be released.

Correct me if I'm wrong. The coordinates must be loaded to the SSE
register to perform some vector operation but normally they should be
stored in memory (in C-array) so you should expect no penalty accessing
single coordinate WRT e.g. the geometry::model::point<>. But I'm
guessing that you're comparing the performance of higher level
operations which indeed is probably worse.

> Is there any way to teach boost::geometry -- and especially
> boost::geometry::rtree -- to use my functions for these operations,
> avoiding get<0> and get<1> as much as possible?

As Barend mentioned in an other email you could:
1. specialize algorithms on the geometry::dispatch level
2. you could overload the algorithm's main function for your Geometry
type only

If done properly 1. could be used with any user-defined type to perform
SIMD calculation. We'd probably need to develop SIMD Point Concept. This
could be something like:
- geometry::use_simd<Point>::value equal to true
- and/or geometry::is_contigeous<Point>::value equal to true - this
could give use benefits even if SIMD were not used
- some access to the vectorised data - e.g. data() and size() (similar
to the C++11 std::vector, std::array), they should probably be free

But back to the question. R-tree is using various algorithms, some of
them are the ones released officially in the namespace boost::geometry,
- intersection(),
- expand(),
- intersects()
- all other spatial relation operations used in spatial queries,
- comparable_distance() used in kNN queries,
- maybe more?
Some of them are only in the details of the R-tree, in the namespace
boost::geometry::index::detail, e.g.:
- content() - a function calculating a hypervolume of an n-dimensional box
- margin() - a function calculating something close to the comparable
hyperperimeter of an n-dimensional box

There are also an arithmetic operations
which are used internally in many algorithms. Writing those algorithms
using SIMD could give some speed up in many places of Boost.Geometry.

So if you wanted to implement some algorithm using SIMD we could guide
you how to do it.


Geometry list run by mateusz at