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 10:28:09

> 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.

David Sauter