Jump to content
  • Advertisement
Sign in to follow this  
jonwil

Looking for help with aab/tri collision

This topic is 1024 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement

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

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

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

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

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

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!