Geometry Boost List: Re: [geometry] Non-axis aligned bounding box collision in 3D

Subject: Re: [geometry] Non-axis aligned bounding box collision in 3D
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-03-28 14:12:32

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