Sign in to follow this  
Juliean

"Each vs. any" collision shape implementation

Recommended Posts

Hello,

 

not so much a math/physic than rather a code design oriented problem. Give a simple system for checking collisions, nothing fancy, only "does body A touch body B right now", whats a good solution for implementing a system where you can test any two shapes, without knowing what they are (so I can compare two ICollisionShape-Pointer e.g.)? Given that there is a known implementation for those two bodies, otherwise simply no collision is reported. I'm not very satisfied with my current solution, so I'm looking for ways to improve/totally new ways:

        class IVolume
        {
        public:
            
            virtual ~IVolume(void) {}

            virtual bool IsInside(const IVolume& volume) const = 0;

            virtual bool WithBox(const AABB& box) const { return false; }
            virtual bool WithOBB(const OBB& box) const { return false; }
            virtual bool WithSphere(const Sphere& sphere) const { return false; }
            virtual bool WithHeightfield(const Heightfield& field) const { return false; }
            virtual bool WithTriangle(const Triangle& triangle) const { return false; }
        };

So that is the actual interface I'm using, which has a lot of methods for certain shapes already defined. I'll show you why (let me add this is one of the points that annoy me the most):

            bool AABB::IsInside(const IVolume& volume) const
            {
                return volume.WithBox(*this);
            }        

Thats the poorly titled "IsInside" method, which checks collision between two shapes. Now thats the only way I found to being able to achieve such an each vs. any - collision: Overloading a generic method, which can be used on any shape and takes any shape, can call the correct method on the unkown shape, to pick the correct collision. Clever, huh? Well...

 

While this at least doesn't need RTTI, it still bums me. First of all, I have to implemented a new method in the interface for every implementation of it. Eww. Also, I potentially have to dublicate the collision implementation (AABB-OBB is different than OBB-AABB in that case, though I can get rid of that by a seperate file). So, any ideas or concrete examples how to implement this more extendable/faster (didn't I hear something about virtual being bad at this low level of "phyiscs" for caching behaviour? *ducks before getting hit for premature optimization-ism*)? Anything would be welcome!

Edited by Juliean

Share this post


Link to post
Share on other sites

This is one way to do it and actually has a name : Double Dispatch. Surprise, that page shows a collision sample. Yes, you need to write all the functions, but if you want to support all combinations you will do that anyway (or else throw a NotImplementedYetException or something wink.png).
 
To get rid of the virtuals (if that's a problem) you could sort/filter your lists by type - or have uniform lists to begin with.

Share this post


Link to post
Share on other sites

This is a good question.  I've never seen it solved in a particularly satisfactory way.  This is what I do:

enum ShapeType
{
    Shape_Null   = 0,
    Shape_AABB   = 1,
    Shape_OOBB   = 2,
    Shape_Hull   = 4,
    Shape_Sphere = 8,
};

#define ShapeTypeMash(a, b) (((uint32)a << 16) | (uint32)b)

class IShape
{
public:

    virtual ShapeType GetType(void) const = 0;
};

bool CollideShapes(const IShape* a_pShapeA, const IShape* a_pShapeB)
{
    ShapeType eTypeA = a_pShapeA->GetType();
    ShapeType eTypeB = a_pShapeB->GetType();

    if(eTypeA > eTypeB)
    {
        swap(eTypeA, eTypeB);
        swap(a_pShapeA, a_pShapeB);
    }

    bool bResult = false;

    switch(ShapeTypeMash(eTypeA, eTypeB))
    {

    case ShapeTypeMash(Shape_AABB, Shape_AABB):
        bResult = CollideShapes_AABB_AABB((const AABB*)a_pShapeA, (const AABB*)a_pShapeB);
	break;

    case ShapeTypeMash(Shape_AABB, Shape_OOBB):
        bResult = CollideShapes_AABB_OOBB((const AABB*)a_pShapeA, (const OOBB*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_AABB, Shape_Hull):
        bResult = CollideShapes_AABB_Hull((const AABB*)a_pShapeA, (const Hull*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_AABB, Shape_Sphere):
        bResult = CollideShapes_AABB_Sphere((const AABB*)a_pShapeA, (const Sphere*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_OOBB, Shape_OOBB):
        bResult = CollideShapes_OOBB_OOBB((const OOBB*)a_pShapeA, (const OOBB*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_OOBB, Shape_Hull):
        bResult = CollideShapes_OOBB_Hull((const OOBB*)a_pShapeA, (const Hull*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_OOBB, Shape_Sphere):
        bResult = CollideShapes_OOBB_Sphere((const OOBB*)a_pShapeA, (const Sphere*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_Hull, Shape_Hull):
        bResult = CollideShapes_Hull_Hull((const Hull*)a_pShapeA, (const Hull*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_Hull, Shape_Sphere):
        bResult = CollideShapes_Hull_Sphere((const Hull*)a_pShapeA, (const Sphere*)a_pShapeB);
        break;

    case ShapeTypeMash(Shape_Sphere, Shape_Sphere):
        bResult = CollideShapes_Sphere_Sphere((const Sphere*)a_pShapeA, (const Sphere*)a_pShapeB);
        break;

    default:
        bResult = false;
        break;
    }

    return bResult;
}

It works okay and keeps the shape vs shape collision code out of the actual shape class which I have found to be beneficial.  It keeps you from modifying all of your shape classes each time you add a new type.  You can leverage template specialization to clean up the syntax a bit.  I'm hoping someone replies with a better solution though.

Share this post


Link to post
Share on other sites
You may be able to create a generic does collide function around the Axis separation theorem. The basic approach would be to create project function for each shape that calculates the range of a shape along an axis. To further explain what I mean imagine you have a shape and a line. You then slide a flat surface on both ends of the line and have each surface perpendicular to the line and together they clamp down on the shape. The distance each flat surface is along the line determines the max and min for the range. If you want to see if two shapes overlap you simply calculate that range for both shapes. If their ranges don't overlap then you know for sure that they don't overlap. If the ranges do overlap they the shapes might or might not overlap, but there may an axis where they don't. So the trick is to find an axis where they don't overlap, then you have proven that the shapes don't overlap.

The other part of the algorithm would be for each shape to generate a list of axis to test to check to see if the shapes overlap. This is where the algorithm gets tricky because the axis you choose to test that will thoroughly verify of two shapes overlap depends on the features of both shapes. For example, a sphere on sphere can be verified with a single axis that goes between the centers of each. A sphere on a triangle has to have an axis for the flat side of the triangle, three edges, and the three points. More complicated shapes will have many axis to test.

Finding a way to generalize collision is possible, it is just tricky and the generalized version will likely be much slower. Also, the algorithm I described above only works for convex objects, so the heightfield collision wont work using this. You will probably have to create a separate generalized collision function for that. You would probably also want to create a bounding box function that can be used to filter out collision using a simple bounding box to bounding box collision before the more expensive generalized form.

However, I think your current implementation is a good one. It may not be very elegant to add addition shape types because that means you have to update the base interface as well as every other shape already added, but the double dispatch method still works pretty well especially when there aren't many different shape types.

Share this post


Link to post
Share on other sites

I have misgivings about the double dispatch method.  I feel like it's a form of spaghetti code that forms over and over again in response to a particular type of problem so we gave it a name and sanctioned it as a design paradigm.  My biggest problems with it is that it obliterates the open/closed principle and is hard to maintain.  Admittedly this is an opinion many will take issue with.

 

HappyCoder is onto something about giving your IVolume interface the necessary methods so that they can be used by a separating axis detector for collision.  I've done this before and it's workable but still awkward.  Also: performance!  An AABB to AABB detector can be made very fast but if when you generalize to a separating axis test you'll pay a price.  It will be slightly faster than if you had stored your AABBs as convex hulls and used a vanilla separating axis detector but only slightly.  Bounding volumes with curved boundaries (capsules, cylinders etc) are problematic as well.  In any case it is a fun academic experiment and may suit your needs.

Share this post


Link to post
Share on other sites
My personal favorite, one that satisfies your requirement for abstraction, is the GJK algorithm. There's a good write-up I found once, but I can't seem to find it. This one seems fine, though: http://www.codezealot.org/archives/88

Basically, the magic is in the support function. In the GJK algorithm, the only piece of information used to determine collision is the furthest point along a ray for any given shape .

class Shape 
{
  virtual void furthestPointAlongRay(vec3 ray) ;
... 
};
All you have to do is overload the function for any convex hull. This method is extremely versatile and fast, far worth whatever evils you may have heard about virtual function calls ;)

Best wishes on your physics engine!
~CulDeVu

Share this post


Link to post
Share on other sites

I have misgivings about the double dispatch method.  I feel like it's a form of spaghetti code that forms over and over again in response to a particular type of problem so we gave it a name and sanctioned it as a design paradigm.  My biggest problems with it is that it obliterates the open/closed principle and is hard to maintain.  Admittedly this is an opinion many will take issue with.


Somewhat agreed. A name and idea is one thing. The implementation the other. I always felt that almost all GoF patterns came down this double dispatch. I haven't used a language which supports multitype dispatch (functional programmers anyone?), so if you want to use the language provided single dispatch (C++, C#, likely Java) you need to "serialize" them, which can get awkward. I like your approach though, it is sort of a two type vtable and keeps the key idea in one place.

@HappyCoder. Now that you mention it I think that's idea about the support function in the GJK algorithm.

Edit: And beaten. Edited by unbird

Share this post


Link to post
Share on other sites

Thanks all for the feedback,

 

as for the "advanced" techniques like GJK, axis seperation etc, while they do sound interesting, I'll skip them for now and wait until I integrate a "real" physics engine in the version 2 of my game engine. Page is bookmarked, will do a great job when I start to get serious with physics, not like my simple collision libary I have right now :)

For now, I've gone with nonoptimalrobots approach, this at least eliminates the need for changing the interface and all classes every time I add a new shape. I'll experiment with it and see if I can clean up the syntax, if so, I'll edit the code here for you to see. Thanks so far!

Share this post


Link to post
Share on other sites

Note that you can also have a simple matrix of function pointers. 

typedef void (*rnCollideFunc)( rnManifold&, const rnTransform&, const rnShape*, const rnTransform&, const rnShape* );
static const rnCollideFunc CollisionMatrix[ RN_SHAPE_COUNT ][ RN_SHAPE_COUNT ] =
{
	{ rnCollideSpheres, rnCollideSphereCapsule,  rnCollideSphereHull,  },
	{ NULL,             rnCollideCapsules,       rnCollideCapsuleHull, },
	{ NULL,             NULL,                    rnCollideHulls,  NULL },
	{ NULL,		    NULL,		     NULL,		   }
};

And then you simply call the function like this:

RN_ASSERT( Shape1->GetType() <= Shape2->GetType() );
rnCollideFunc Collide = CollisionMatrix[ Shape1->GetType() ][ Shape2->GetType() ];
Collide( Out, Transform1, Shape1, Transform2, Shape2, Cache );

You usually have a contact class which holds the pointers to the shapes. If you sort them on construction such that Shape1->GetType() <= Shape2->GetType() you don't need to deal with the lower collision matrix. I am using this for years and always liked its simplicity. IIRC I took this idea from the ODE.

 

As a side note: Someone above suggested to swap the pointers. You usually have the convention that the contact normal points from A -> B (or vice versa). So don't forget to invert the orientation of the normal as well when you flipped pointers.

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

Note that you can also have a simple matrix of function pointers.

Yep, that's what I do. 2D array of function pointers for intersection tests, and another for slide normal calculation. Call the intersection test with the collider's position+velocity. and If you hit something, call the normal calculation with position and velocity as separate arguments. Assuming you're not doing continuous collision detection, the normal vector is just a guess, and usually works best when the things aren't already intersecting, and some shape combos can make a more accurate (or even perfect) guess if they have the velocity too.

 

Shape types can either be a virtual function like nonoptimalrobot's example, or a member variable that's set when the shape is initialized. I prefer variable since the shape class doesn't usually need any other virtuals, so it saves the vtable pointer, and is a little bit faster to read a variable than call a virtual function. Plus then I don't need to make separate classes for each shape type. All shapes have a position vector and a scale vector. Spheres only actually use scale.x as the radius. Cylinders use x for radius, y for length, and don't need z. Boxes use all 3.

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