Sign in to follow this  
comdown

Structure for different kind of collision

Recommended Posts

In C++, I have three kind of object. rectangle, circle, triangle. and then i want to check collision from any kind versus any kind without considering what type of object they are. for example, class IObject; class Triangle : public IObject; class Rectangle : public IObject; class Circle : public IObject; IObject* pObject1 = blah blah; IObject* pObject2 = blah blah; bool bIsCollided = pObject1->IsCollided( pObject2 ); How should I make the structure to do like that? Thanks for your help. :)

Share this post


Link to post
Share on other sites
You have a couple of options. One could be to add new protected methods to your IObject interface: CollideTriangle, CollideRectangle and CollideCircle. Then, each of your classes implements the IsCollided like this:

// For Triangle class:
return CollideTriangle(pObject2);

// For Rectangle class
return CollideRectangle(pObject2);

// For Circle class
return CollideCircle(pObject2);

Then, you implement those three methods in all your classes. At that point, you know the type of both objects and you do the specific math computations.

Another way would be to provide a type id and make a switch case.

-Francis

Share this post


Link to post
Share on other sites
const int TRI = 0;
const int RECT = 1;
...
const int NUM_COLLISION_OBJECTS = ...

bool CollideTriTri(Triangle *, Triangle *)
bool CollideRectTri(Triangle *, Rect *)
bool CollideTriRect(...) NOTE it's a duplicate of the above function
ect...

class IObject
{
int type;
};

typedef (*bool CollisionFunc)(IObject *, IObject *);

CollisionFunc collisionFuncs[NUM_COLLISION_OBJECTS][NUM_COLLION_OBJECTS] =
{
CollideTriTri,
CollideRectTri,
...
};

and finally

bool Collide(IObject *p1, IObject *p2)
{
return collisionFuncs[p1->type][p2->type](p1, p2);
}

Share this post


Link to post
Share on other sites
Have a virtual function that returns possible axes in a specific direction, implement it for each shape then run a SAT test on the axes returned in the normalize(center_object_two - center_object_one) direction.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
Have a virtual function that returns possible axes in a specific direction, implement it for each shape then run a SAT test on the axes returned in the normalize(center_object_two - center_object_one) direction.


wow, it sounds very neat and simple, but is it really possible to apply to ANY kind object? like 2d, 3d objects, not fixed boundings(convex hull).

Share this post


Link to post
Share on other sites
Yes and no :) It's true for convex polytopes, not so much for spheres and such.

If you want a general algorithm no matter the actual shape properties, then you have GJK, and MPR.

In 2D, you can use .

Note the special case for circles and such.

in 3D, you can still apply that special case, but you'll also have to consider edges.

Also, it will not be as efficient as using bespoke algorithms.

To do that, you can use a visitor pattern, or a function table. I favour the second kind, as it solves a lot of dependency problems.

Here's the gist of it.


fluff...

struct Vector
{
float x, y, z;
};

void debug_output(const char* format, ...)
{}

void debug_assert(bool expression)
{}



collision objects.

namespace CollObject
{
// collision detection parameters and results.
struct Info
{
const Base* m_collider;
const Base* m_collidee;

bool m_intersected;
float m_intersection_depth;
Vector m_intersection_direction;

bool m_collided;
float m_collision_time;
Vector m_collision_normal;
};

enum
{
TYPE_TRIANGLE,
TYPE_SPHERE,
TYPE_AABB,
TYPE_OBB,
TYPE_SEGMENT,
TYPE_PARTICLE,
TYPE_CAPSULE,
TYPE_CYLINDER,
TYPE_CONVEX_HULL,
TYPE_ARBITRARY_MESH,
TYPE_COUNT,
};

class Base
{
public:
Base(const int type_id, const char* dbgType);
virtual ~Base(){}

int type_id() const { return m_type_id; }
const char* dbgType() const { return m_dbgType; }

const int m_type_id;
const char* m_dbgType;
};

class Triangle: public Base
{
public:
Triangle()
: Base(TYPE_TRIANGLE, "CollObject::Triangle")
{}

Vector m_vertices[3];
Vector m_normal;
};

class Sphere: public Base
{
public:
Sphere()
: Base(TYPE_SPHERE, "CollObject::Sphere")
{}

Vector m_centre;
float m_radius;
};

class AABBox: public Base
{
public:
AABBox()
: Base(TYPE_AABB, "CollObject::AABBox")
{}

Vector m_min;
Vector m_max;
};

class OBBox: public Base
{
public:
OBBox()
: Base(TYPE_OBB, "CollObject::OBBox")
{}

Vector m_centre;
Vector m_halfsize;
Vector m_axes[3];
};

// ect......
}


collision detection routines, implemented as functors


using namespace CollObject;
namespace CollFunctors
{

// functor used to resolve collision detection of two specific object types.
class Solve_Base
{
public:
virtual ~Solve_Base(){}

static int make_type_id(int collider_type, int collidee_type)
{
debug_assert(collider_type < TYPE_COUNT && collider_type >= 0);
debug_assert(collidee_type < TYPE_COUNT && collidee_type >= 0);
return (collider_type * TYPE_COUNT) + collidee_type;
}

const int collider_type() const { return m_collider_type; }
const int collidee_type() const { return m_collidee_type; }
const int type_id () const { return m_type_id; }
const char* dbg_type () const { return m_dbg_type; }

// implementation of the collisoin detection routine.
virtual bool solve(const Base* collider, const Base* collidee, Info* info)=0;

protected:
virtual bool dbg(const Base* collider, const Base* collidee)
{
debug_assert(collider->type_id() == m_collider_type);
debug_assert(collidee->type_id() == m_collidee_type);
debug_output("calling (%s)", m_dbg_type);

return (collider->type_id() == m_collider_type) &&
(collidee->type_id() == m_collidee_type);
}

Solve_Base(int collider_type, int collidee_type, const char* dbg_type)
: m_collider_type(collider_type)
, m_collidee_type(collidee_type)
, m_type_id(make_type_id(collider_type, collidee_type))
, m_dbg_type(dbg_type)
{}

const int m_collider_type;
const int m_collidee_type;
const int m_type_id;
const char* m_dbg_type;
};

// solve triangle - triangle test
class Solve_Triangle_Triangle: public Solve_Base
{
public:
Solve_Triangle_Triangle()
: Solve_Base(TYPE_TRIANGLE, TYPE_TRIANGLE, "CollDetection::Triangle_Triangle")
{}
virtual bool solve(const Base* collider, const Base* collidee, Info* info)
{
// debug check
dbg(collider, collidee);

// cast to objects.
const Triangle* a = (const Triangle*)(collider);
const Triangle* b = (const Triangle*)(collidee);

// do the test....
return true;
}
};

// solve triangle - sphere test
class Solve_Triangle_Sphere: public Solve_Base
{
public:
Solve_Triangle_Sphere()
: Solve_Base(TYPE_TRIANGLE, TYPE_SPHERE, "CollDetection::Triangle_Sphere")
{}
virtual bool solve(const Base* collider, const Base* collidee, Info* info)
{
// debug check
dbg(collider, collidee);

// cast to objects.
const Triangle* a = (const Triangle*)(collider);
const Sphere* b = (const Sphere*) (collidee);

// do the test....
return true;
}
};

// solve sphere - sphere test
class Solve_Sphere_Sphere: public Solve_Base
{
public:
Solve_Sphere_Sphere()
: Solve_Base(TYPE_SPHERE, TYPE_SPHERE, "CollDetection::Sphere_Sphere")
{}
virtual bool solve(const Base* collider, const Base* collidee, Info* info)
{
// debug check
dbg(collider, collidee);

// cast to objects.
const Sphere* a = (const Sphere*)(collider);
const Sphere* b = (const Sphere*)(collidee);

// do the test....
return true;
}
};

// ect........
}




using namespace CollObject;
using namespace CollFunctors;
namespace CollDetection
{
// solve collision detection between arbitrary object types.
class Solver
{
public:
Solver()
{
// wipe the collision table clean.
memset(m_function_table, 0, sizeof(m_function_table));

// fill in the function table.
// -> create new functors for each collision object types.
register_function(new Solve_Triangle_Triangle);
//register_function(new Solve_Triangle_AABB);
//register_function(new Solve_Triangle_OBB);
register_function(new Solve_Sphere_Sphere);
//register_function(new Solve_Sphere_AABBox);
//register_function(new Solve_Sphere_OBBox);
//register_function(new Solve_AABBox_AABBox);
//register_function(new Solve_AABBox_OBBox);
//register_function(new Solve_OBBox_OBBox);
}

~Solver()
{
// cleanup the collision function table.
for(int i = 0; i < (TYPE_COUNT * TYPE_COUNT); i ++)
unregister_function(i);
}

// unregister a collision detection routine.
bool unregister_function(int type_id)
{
// sanity check
debug_assert(type_id < (TYPE_COUNT * TYPE_COUNT) && (type_id >= 0));
if(type_id < 0 || type_id > (TYPE_COUNT * TYPE_COUNT))
return false;

// destroy functor.
if(m_function_table[type_id] != NULL)
delete m_function_table[type_id];
m_function_table[type_id] = NULL;
}

bool register_function(Solve_Base* function)
{
// sanity check
if(!function)
return false;

// the function slot in the table.
int type_id = function->type_id();

// sanity check
debug_assert(type_id < (TYPE_COUNT * TYPE_COUNT) && (type_id >= 0));
if(type_id < 0 || type_id > (TYPE_COUNT * TYPE_COUNT))
return false;

// destroy functor.
if(m_function_table[type_id] != NULL)
delete m_function_table[type_id];

// insert new one in its place.
m_function_table[type_id] = function;
return true;
}

// compute collision detection info for two objects.
bool resolve(const Base* collider, const Base* collidee, Info* info, bool allow_reflect_call=true)
{
// type identifiers of the objects.
int type_a = collider->type_id();
int type_b = collidee->type_id();

// the function identifier for those specific two object types.
int function_type_id = Solve_Base::make_type_id(type_a, type_b);

// sanity check.
if(function_type_id < 0 || function_type_id >= (TYPE_COUNT * TYPE_COUNT))
return false;

// the function lookup.
Solve_Base* solver = m_function_table[function_type_id];

// coll detection function available, call it.
if(solver != NULL)
{
// clean up the collision detection info.
info->m_collider = collider;
info->m_collidee = collidee;
info->m_intersected = false;
info->m_collided = false;

// call the collison solver routine.
return solver->solve(collider, collidee, info);
}
// collision detection routine unavailable.
// try the reflective routine, if allowed.
if(allow_reflect_call)
{
// dont allow 'reflection', to avoid infinite loop.
return resolve(collidee, collider, info, false);
}
else
{
return false;
}
}

private:
// table of collision detection routine (functors) for various object types.
Solve_Base* m_function_table[TYPE_COUNT * TYPE_COUNT];
};
}



[Fixed so as not to make the baby Zahlman cry. - Zahlman]

It's a bit long winded, but it has some cool advantages over the visitor pattern.

Mainly, it's modular (replace, adding a new algorithm is just creating a new functor that will handle those specific types of objects), less dependencies (only dependencies are inside each functor's solve() function)

Main problem is type safety. With the visitor pattern, you are guaranteed to be type safe, but for it's no biggy.

Also, your object types are explicit and depend on an enum list. That's not the best solution, what you could do is have a hash for each object types, and use a hash table for your function table instead of an array.

[Edited by - Zahlman on April 8, 2010 1:40:35 PM]

Share this post


Link to post
Share on other sites
Could you not also implement custom RTTI so you do not have to use a hash table?
Just to be clear this solution is known as double-dispatch, correct?
I usually see this implmented with the stl map for the function table, which requires less code. Scott Meyer's Effective C++ ( or is it More Effective C++ ) has a good explanation of double-dispatching.

Share this post


Link to post
Share on other sites
I suppose they are all sides of the same coin. I was referring to implementations such as these :

Quote:


class CollObject
{
virtual bool collide(const CollObject& other) const=0;
virtual bool collide(const CollSphere& other) const=0;
virtual bool collide(const CollTriangle& other) const=0;
};

class CollTriangle
{
virtual bool collide(const CollObject& other) const { return other.collide(*this); }
virtual bool collide(const CollSphere& other) const { /* implement code */; }
virtual bool collide(const CollTriangle& other) const { /* implement code */; };

class CollSphere
{
virtual bool collide(const CollObject& other) const { return other.collide(*this); }
virtual bool collide(const CollSphere& other) const { /* implement code */; }
virtual bool collide(const CollTriangle& other) const { return other.collide(*this); }
};



Which may look neater, but introduces more dependencies, and not as flexible when you want to introduce new types.

Share this post


Link to post
Share on other sites
God damn it, oliii, you've been here longer than I have. Learn to use the proper code formatting tags already, would you? I already posted a sticky about this.

>:|

Share this post


Link to post
Share on other sites
Well, the reason I suggested axes in a specific direction (support point?) is because of spheres, I didn't implement it, of course, but assuming you use the normalized distance vector from the centers of the shapes as directions, you can get a circle/sphere axis which you can test against the ones returned from the other shape, other shapes can add axes on a per vertex basis too, so you could check a square's corner against a head on circle collision by using the axis from a normal located at the vertex pointing at the circle's center.

To me it makes sense on paper [smile], its an idea I have had for some time which I would like to implement in ODE since adding a new primitive there grows the amount of code needed to handle collisions exponentially a lot [lol] since for each new one you have to add a function for the others to check against the new one, luckily they don't have to be reciprocal (IE: Triangle-Square can handle Square-Triangle by switching arguments), otherwise, it would be exponential... I think.

Share this post


Link to post
Share on other sites
The circle SAT has been demonstrated here.

It's in 2D, the problem with 3D is you get an explosion of tests to perform. You will have to test the sphere against the vertices, the sphere against the edges (I would say, the closest point on the edge to the sphere centre will give you an axis).

Of course you can optimise the test to reduce the features that could give a potential separating axis (there is no reason to test the 'back' features). Then in the end, the SAT sphere test becomes really close to the standard sphere-convex hull test anyway.

IIRC, the standard way of checking a sphere with a convex hull for intersection if finding the point on the hull the closest to the sphere centre, which basically involve some form of Voronoi diagram (partitioning space to find the closest features) to identify the potential parts needed for the tests (vertices, edges, faces).

V-Clip does this for polytopes vs polytopes iirc, but imo there is no reason why it wouldn't work for spheres as well.

Share this post


Link to post
Share on other sites
Correct, the advantage in the way I am proposing is in the abstraction, you forget about shapes and test only axes and intervals, thus, you can have a single collision test function instead of one for each pair of shapes, the complexity then becomes providing an optimized set of axes for each shape based on the rough position of a second shape.

Or at least that's my idea [smile].

Share this post


Link to post
Share on other sites
Thanks guys for sharing good ideas. So I think it's possible to make the test by one function but it's too complex and not optimized. right?

I think I should use different optimized ways to check collisions in practice.

Share this post


Link to post
Share on other sites
Quote:
Original post by comdown
So I think it's possible to make the test by one function but it's too complex and not optimized. right?


Not really, all things being equal, implementing either solution would yield roughly the same performance (plus/minus a virtual call), the difference is in the code structure and volume (that's my hypothesis anyway).

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