Sign in to follow this  
jonwil

Looking for help with aab/tri collision

Recommended Posts

jonwil    157

I am working on collision detection for a custom game engine.

 

It has the following basic classes: (simplified to show only the relavent bits)

class Vector3
{
    float X;
    float Y;
    float Z;
};

class AABoxClass
{
    Vector3 Center;
    Vector3 Extent;
};

class TriClass
{
    const Vector3 *N;
    const Vector3 *V[3];
};

struct CastResultStruct
{
    bool        StartBad;        // was the inital configuration interpenetrating something?
    float        Fraction;        // fraction of the move up until collision
    Vector3    Normal;            // surface normal at the collision point
};

 

I need to create a function that looks like this.

bool Collide(const AABoxClass & box,const Vector3 & move,const TriClass & tri,CastResultStruct * result)

i.e. it collides a moving AABox against a triangle and returns a bool for whether it collided or not plus the 3 items in CastResultStruct.

 

Can anyone point me in the right direction on how to do this? I searched all over the internet and all over gamedev.net and elsewhere and cant find any kind of example of how to do this (I found a couple pointers to how to do it if all you care about is the "did these objects collide" flag and not the actual collision information but nothing on how to calculate the actual collision information (i.e. CastResultStruct above)

 

Share this post


Link to post
Share on other sites
Randy Gaul    2762

You can write a specialized routine for your AABB to tri case instead of using a more generalized algorithm.

 

I would compute the penetration depth of the triangle against the AABB by translating the AABB to the origin, and applying this translation to the triangle. Then it's straightforward to find out if any of the vertices of the triangle penetrate the AABB. It's also easy to see if the AABB intersects the plane of the triangle by using the dot product:

 

ax + by + cz - d = depth

 

I have to run, but I can write more later! Maybe someone else will post in the meantime.

Share this post


Link to post
Share on other sites
Randy Gaul    2762

You have to define the move vector for us, I have no idea what that is.

 

I suggest reading up on some SAT slides that Dirk Gregorius made for a recent GDC (I think 2015 one). He covers a lot about how to design collision routines like this one.

Share this post


Link to post
Share on other sites
jonwil    157

We are sweeping the box from its current position along that vector to the end and identifying if it collided and if so where.

The StartBad field indicates that its initial position was already colliding with the triangle.

The Fraction field indicates how far along the move vector the box actually moved before it collided.

The Normal field indicates the surface normal at the collision point.

Share this post


Link to post
Share on other sites
Randy Gaul    2762

Oh I see, I've never implemented any kind of box-cast stuff so I'm not immediately sure what the best approach would be. There are some swept collision routines in Ericson's Real-Time Collision Detection book, and I'm sure concepts there can be used to create your specific function.

 

Sweeping the box planes against the triangle would be easy, but I wouldn't be sure how to handle when edges on the box start hitting the triangle. I imagine this is where more skill would be required to come up with a solution.

 

Sorry I can't be of much more help unless I go an implement this myself, maybe someone else can give you more specific advice if you have specific questions.

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757

Oops, deleted my post as it slipped under the wrong topic:

 

For your problem you can do a couple of things:

1) Conservative advancement (see B. Mirtich's thesis here: http://www.kuffner.org/james/software/dynamics/mirtich/index.html)

2) Bracketed advancement (an extension of CA presented by E. Catto here 2013: http://box2d.org/downloads/)

3) You run a GJK-SAT between the swept AABB and the triangle. And then use a raycast in the direction of the relative moment to find your way out of the Minknowski sum. The intersection is your TOI. This is similar to Minkowski Portal Refinement (MPR).

 

The SAT based approaches might work as well, but I would not go through the hassle. For linear sweeps (translation only) I use 1). For non-linear sweeps (translation + rotation) I use 2)

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites
jonwil    157

Ugh, a PhD thesis. Seen enough of those in my time to know that actually turning whatever ideas, formulas and equasions they have in them into actual usable practial code is a real pain in the butt...

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757

Mirtich's Thesis is a fantastic piece of work, but I totally get what you mean and would agree in most cases! :) If this is too much work simply use Havok or PhysX. They have rich sweep APIs which you can run everything through. PhysX is free with source code available as well. I think it depends how important this is for you game. You would need a GJK implementation and then build the CA on top of this. It is actually not too bad. And I would help here of course!

 

I am not aware of any example code I would recommend. Maybe XNACollision.h/DirectXCollision.h might have something like this, but IIRC they implemented only the static tests there. Sorry!

Share this post


Link to post
Share on other sites
Randy Gaul    2762

Dirk do you guys actually do box-casts with an interative algorithm? I recall seeing in some of your GDC presentations (mainly Sergiy's debugging one) that box-casts were super common. For some reason I assumed this implied the existence of a more closed-form algorithm.

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