SpatialQuery, -Index and 3D-support

[niniemann]

I feel a little bit lost while implementing a spatial index and spatial queries, so I'll just write down some thoughts...

What do I want?

• "sempr, give me all geometries which are roughly within this area" (relaxed bounding-box-query on e.g. an RTree)
• "sempr, give me all geometries which really do intersect this volume" (exact query)
• ...

First approach

First of all, we need a spatial index to work with bounding boxes and thus speed things up, and a query object. How's the query processed? Well, it has a geometry, a coordinate system and a flag for exact or relaxed, and the SpatialIndex uses the AABB of the geometry for a first & fast lookup. After that it has pointers to other geometries, candidates, and can call candidate->within(queryGeometry);, right?

No. Problems:

It all comes down to the question: How do we represent (and work with) volumes?

An AABB is simple as it only consists of two points, but as soon as we transform it into another coordinate system (and this we have to do, definitely!) it becomes an OBB, something rotated and difficult. Well okay, we can still take the AABB of the OBB within the correct reference frame, so the sole indexing thing seems okay. But what now? If we want the SpatialIndex to answer exact queries we need a way to do 3D-intersection/containment tests. The GDAL/GEOS documentation is a bit thin on this, but certainly does not support it. The PostGIS documentation tells us not to call functions like ST_Within on GeometryCollections.

The only thing I personally know of being able to do this is CGAL... which is GPL. :( (When working with PostGIS and SFCGAL you can use a PolyhedralSurface, call ST_MakeSolid on it and then use ST_3DIntersects etc.).

So, what to do?

Let's keep the SpatialIndex simple for now: Only compare (3D-)BoundingBoxes, and keep them axis aligned. Just plain simple SpatialIndex-Queries.

We need a way to represent and work with 3D geometries. At least 3D oriented boxes and containment/intersection tests. How can we stay compatible to the GDAL-types? They allow iterating on their vertices, so containment-in-a-3D-box should be not too hard. The same goes for an incomplete intersection-test: Just check if some vertices are inside the box, though this fails for long line segments or big surface-polygons.

Maybe the GeometricTools-library can come in handy, as it implements e.g. OBB & triangle-intersection-tests. We could use this in an extension to provide 3D-spatial-queries? And maybe combine this with the AssetImporter to create a "3D-extension-layer" for sempr?

[Kynneb]

Okay this are in fact two problems, right?

What to do with bounding boxes: I would say we cache the minimum OOBB in the original frame, run it through the transformation chain and only then calculate the axis aligned BB. Or at least in 2D we could use convex hulls instead of OOBBs. All this has to be done each time the original geometry changes.

What to do with intersection. Well, if we don't find a tool to support that we should have a look wether to do it ourselves. This would obviously require a lot more of investigation.

[niniemann]

BoundingBoxes: I can just repeat myself: If you know how to calculate a minimal oriented bounding box, please do. :) I think the rest of the rest of the procedure is already implemented as you said, i.e., taking some kind of BB, apply the transformations, and create an AABB of it in the end.

All the rest of the geometric processing stuff depends on the datatypes we choose for 3D representation and the algorithms/libraries we include for 3D processing. Libraries do exist, even free and non-GPL ones. But we have to choose and live with the consequences. :wink:

[Kynneb]

Is this a conceptual problem or a technical one because of the datatypes?

[niniemann]

I'd rather say it's a technical one... on the concept-side of things we just need to discuss which operations we want to support in general. We've already said that we want to support 2D representation & processing first, and extend this to 3D later on -- but what kind of "interaction" between 2D and 3D do we want to implement? Do we ever want to combine the 2D and 3D types directly, if yes, how? Or will we keep them separated, work on 2D with 2D, and 3D with 3D, and project 3D stuff into 2D if we want to combine things?

But let's not drift away too far. Those are questions to be answered later, I think, though they are directly affected by our choice of 3D representation datatypes and algorithms. :wink:

So... I think the main problem is to choose a combination of 3D representation datatypes and algorithms that match well. Right?

[Kynneb]

Well for BBing: mainly you have to have the possibility of iterating through the points of a mesh/ point cloud / geometric figure. Then you do either the AABB in the object frame (really quick) or an approx minimum BB e.g. by using PCA approach (this is obviously a bit more costly but we would not have to do it that often, I think.

At the rest: agree, perhaps let's discuss this separately

[Kynneb]

Question on a side note: Why always Boxes? In a conversation with Martin the idea came up to maybe use Spheroid approximation instead of BBs. Those would have the charming advantage of being rotation invariant. Also Collision checking would be pretty straight forward.

[niniemann]

Because bounding boxes are an easy abstraction, but still a better approximation to the original object than spheres. If we don't need the accuracy and really consider spheres we won't need to think about this at all and can just use the AABB as we do right now. Plus, the spatial index I use works with axis aligned bounding boxes. :wink:

For the record: Martin mentioned pcl to compute small oriented bounding boxes or even convex hulls:

https://github.com/mintar/correspondence_grouping/blob/master/bbox.cpp https://github.com/mintar/correspondence_grouping/blob/master/bb_hull.cpp

[Kynneb]

Ah, sorry. Not 1 object 1 sphere, but several spheres to approximate an object. Spheres have the nice advantage of being rotation invariant. Martin linked some nice slides as a starting point. (Also for OBBs and other stuff)

http://www.informatik.uni-bremen.de/~zach/talks/vr05_colldet_tut/bounding_volume_hierarchies.pdf

[niniemann]

That sounds really nice for collision checks etc, but a bit overkill for a simple spatial index. ^^

[Kynneb]

surely would be more work, perhaps as an alternative module later on then.

[ctieben]

If you only like to check the intersection of a box and a point or another box its not so difficult to do it on your own without instead of more dependencies or licence issues. See: http://www.realtimerendering.com/intersections.html

There is simple operations to found a valid (not the best) OOBB by iteration over each point in the local CS of the geometry and found the min/max for each axis. O(n) = n You can calculate this once and apply the transformation to it.

You could use the same operation to get a AABB out of a OOBB with an constant effort.

The tricky part is to combine it with GDAL (or GOES).

[ctieben]

I have extend the SpatialQuery and Index on the Spatial Conclusion branch up to d27e690f60b54255a57182ee1cf6fa81be32e8a6 to check the intersection based on the geometry and not only based on boxes. In there fist place there is a box based test now and these results get tested by the geometry based constrained by GEOS.

But so far there are still only planar geometries that could lay in a 3D or 2D space.

[niniemann]

The reference commit only fixes a bug (wrongly used iterator++ & erase).

My intention with the SpatialIndex was exactly this reduced functionality: Something that can easily be computed on any geometry, the axis aligned bounding boxes. If you make checks that take the actual geometry into account, you introduce a dependency on the geometry-type in the spatial index.