Hi David,

David Sauter wrote:
> I'd like to understand every aspect of your use-case.

It would probably be easiest for me to just describe the full use case.  It is very possible that I'm missing a simple solution somewhere.

My inputs:
1) Very large height map (multiple gigs) that has been partitioned into computable chunks.
2) A few tens of millions of shadow maps to apply to the terrain
3) A sun vector

Limitations:
Do this on a single computer (using the GPU)
No viewport - I have to compute the entire terrain

Needless to say I'm not even attempting to do this in realtime but it is by far the slowest part of a much larger process.

Right now what I'm doing is taking each shadow map (which is a square facing down and axis aligned but offset in x, y and z) and putting it into an r-tree spacial index.  I then cull the entire list by the extents of the chunk I'm on projected straight up and stack them up.  From there I pass them to the GPU to stamp the entire list down on the terrain to form the final shadow map.

note - the shadow map is binary (shadow or no shadow) so I don't need to deal with additive shadows etc and can early-out when I detect that a given post is shadowed.

The problem with this is that I stamp them vertically and thus they're not actually in the right places.  A tree on top of a hill will project a very different shadow than one on a flat plane.

Thus in the new version I'm projecting the sun vector through the shadow map at the proper height and marking the ground collision as shadowed.  The problem is that now my initial culling of the shadow maps is basically useless as for some of the worst case chunks I'm getting almost the whole list as an AABB will comprise about the whole map.

What I really need is a collision with the chunk plate projected along the sun vector.  That's not a box anymore as it's really a square extruded in a vector that is offset in all three axis.

Am I missing something?  Should I be doing my collision detection in three passes (2 CPU 1 GPU) instead of the current two passes (1 CPU 1 GPU)?  Should I split up my collision along the Z axis into a series of AABB's that are stair-stepping up along the vector?  I've got a few ideas on this but I'm shooting blind right now.

Now to answer the other questions:
> But should this index be able to store OBBs as well or AABBs (like the one we have right now)? Or maybe to also use OBBs for tree nodes?

I only need to store AABB's.  Actually I'm storing 2D polygons that are scattered in 3D space.  They're all facing the ground and axis-aligned.  The issue is what I'm trying to cull them with.  That means I don't need to deal with the overhead of trying to store OBBs (and thus answers your entire next paragraph...)

> I assume that you tried to index and search using AABBs and those queries return many Values which you must then check again using OBBs? Or are you then checking for the intersection of some more detailed objects or aren't preforming any additional checks?

I'm not performing additional checks until I actually project the ray through the stack to see what hits what.  Maybe this is my issue?  A second CPU culling before I hand the stack to the GPU?

> 1. For performing the query on an existing implementation of the rtree using the OBB
> a) The definition of concept and access to data stored in the OBB
> b) The implementation of the spatial relation function used in the query, e.g. bg::intersects(OBB, AABB)

I think that's what I need.  How much work do you think it would be to add the ability to do an intersection with an OBB?  I could add it myself if there's no one else working on that but I'm hoping for an existing solution.


Ok, I now understand your case. Yes, indeed you could create a OBB as a projection of some terrain rectangle in the direction of sun vector. OBB probably expanded up, by the highest point of the terrain in the fragment.

Your case is very similar to Michael's described in the thread "[geometry] Querying index using intersection with custom geometry".
Since the rtree is using the bg::intersects() function internally you could try to implement it for a Box/MyOBB pair and then just pass MyOBB into the bgi::intersects() predicate.

In your case it would be even simpler since your OBBs would have X and Y axes aligned (assuming the Z in up/down). So you could not implement the AABB/OBB intersection test. Instead of OBB you could use something like a skewed Prism. Store a base, horizontal Box corresponding to the terrain fragment and the sun vector. In your implementation of bg::intersects(Box, MyPrism) you could just calculate 2 AABBs out of the Prism (for the MINZ and MAXZ of the Box), expand them by the X,Y values of each other and then check for the intersection with the Box. Expanding is needed because the Box might fall somewhere between those flat AABBs.

You could also just get XY coordinates and create one expanded AABB with a Z coordinate of the center/centroid of the Box. Then just test for Box/AABB intersection. Like on the picture below:



The support for "proper" Boxes is unfortunately needed because rtree nodes are non-flat, not like your shadow maps, otherwise you could just move the base Box of a terrain fragment and check the intersection of 2 flat Boxes.

Have in mind that your type will work with only this one overload of intersects(Box, MyPrism)

Here is a skeleton of a program for this. Nearly the same as in the other thread mentioned before:

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>

struct MyPrism
{
    MyPrism(int d) : dummy(d) {}
    int dummy;
};

namespace boost { namespace geometry {

// This will be called for Nodes Bounds and Indexables!

template <typename Box> inline
bool intersects(Box const& b, MyPrism const& p)
{
    std::cout << "checking the intersection with " << p.dummy << std::endl;
    return true; // always intersects
}

}}

int main()
{
    namespace bg = boost::geometry;
    namespace bgi = bg::index;
    namespace bgm = bg::model;
    typedef bgm::point<float, 3, bg::cs::cartesian> pt;
    typedef bgm::box<pt> box;

    // check your implementation
    bool ok = bg::intersects(box(pt(0, 0, 0), pt(1, 1, 1)), MyPrism(5));

    std::cout << "-------------------" << std::endl;

    // now use the rtree
    bgi::rtree<box, bgi::rstar<8> > rt;
    // insert some values
    rt.insert(box(pt(0, 0, 0), pt(1, 1, 1)));
    rt.insert(box(pt(2, 2, 2), pt(3, 3, 3)));

    // performa a query
    std::vector<box> vec;
    rt.query(bgi::intersects(MyPrism(10)), std::back_inserter(vec));

    std::cout << vec.size() << std::endl;
}

Regards,
Adam