Geometry Boost List: Re: [geometry] Adapters at the point and/or box abstraction level?

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 
functions

But back to the question. R-tree is using various algorithms, some of 
them are the ones released officially in the namespace boost::geometry, 
like:
- 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 
(http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/reference/arithmetic.html) 
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.

Regards,
Adam