
Geometry : 
Subject: Re: [geometry] Adapters at the point and/or box abstraction level?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20140528 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 Carray) 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 userdefined 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. Rtree 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 Rtree, in the namespace
boost::geometry::index::detail, e.g.:
 content()  a function calculating a hypervolume of an ndimensional box
 margin()  a function calculating something close to the comparable
hyperperimeter of an ndimensional 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
Geometry list run by mateusz at loskot.net