# Geometry :

Subject: Re: [geometry] Non-axis aligned bounding box collision in 3D
From: David Sauter (delwin_at_[hidden])
Date: 2014-03-28 16:39:02

You sir are amazing.

Thank you.

On Fri, Mar 28, 2014 at 1:12 PM, Adam Wulkiewicz

> 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
>
> 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
>
> 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
>
> #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;
>
> 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,