> I'd like to understand every aspect of your
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.
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
3) A sun vector
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
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
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
> 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
> 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.