Structure for different kind of collision
Author
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. :)
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
// 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
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);
}
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);
}
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.
Author
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).
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...
collision objects.
[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]
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 functorsusing 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]
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.
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.
I suppose they are all sides of the same coin. I was referring to implementations such as these :
Which may look neater, but introduces more dependencies, and not as flexible when you want to introduce new types.
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.
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.
>:|
>:|
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
