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: 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
<adam.wulkiewicz_at_[hidden]>wrote:

>  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
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
>
>