Sign in to follow this  
dv

Using GJK for frustum <-> bounding volume tests

Recommended Posts

dv    124
Hi,

I have a list of bounding volumes of various types, AABBs, OBBs, polytopes, spheres .. given that regular testing requires N*N/2 collision detection functions, and does not work that well with polymorphism in static languages like C++ (double dispatch is a workaround, but a very ugly one), I am thinking about using GJK.

I wonder though how GJK can deal with "open" volumes. For example, a frustum is a polytope. However, what if I omit the far plane? Then the frustum extends to infinity. How would one deal with this?
Also, whenever I look up polytopes and GJK, a transformation into a convex hull is done first. It would be beneficial to be able to use a list of planes as a representation instead of the convex hull. (This is convenient for the frustum - just pass on the list of frustum planes.)

Another example of "open" volumes would be the half-spaces of a kd-tree. I have no idea how to use GJK there. With octrees, I typically have finite extents, that is, the octree nodes do not extend into infinity. I could perform GJK tests between a volume and an implicit octree node AABB.

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757
GJK only works with extreme points so an open shape will be closed. So for your frustum you would either use the vertices or come up with a simple support function. I recommend looking into this video here. I think Casey uses his method for scene culling as well: [url="http://mollyrocket.com/849"]http://mollyrocket.com/849[/url]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this