Sign in to follow this  

Nasty one for OO to handle

This topic is 4701 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

Assume we have for example a collision detection engine, that supports various kinds of Objects to collide with each other. I.e. we have something like: class Object {}; class Mesh : public Object {}; class Sphere : public Object {}; and so on. Now, we want to develop a function like this: bool DoTheyCollide( const Object& o1, const Object& o2 ) { ... }; That checks if two collision objects collide. Of course, this kind of function would be defined for each pair, for example: bool DoTheyCollide( const Mesh& o1, const Mesh& o2 ) { ... }; bool DoTheyCollide( const Mesh& o1, const Sphere& o2 ) { ... }; I wonder if this is possible to do Elegantly (i.e. so that the correct DoTheyCollide is called automatically, as in all virtual-call mechanisms)? -- Mikko

Share this post


Link to post
Share on other sites
Whats wrong with simply doing...

class Object
{
virtual bool DoTheyCollide(Object &rhs) = 0;
public:
float x,y,z; // etc
}

class Mesh
{
bool DoTheyCollide(Object &rhs) { // test rhs against this.x/y/z some code }
}

class Sphere
{
bool DoTheyCollide(Object &rhs) { // test rhs against this.x/y/z some code }
}

Mesh Obj;
Sphere.DoTheyCollide(Obj)

Share this post


Link to post
Share on other sites
This is called double dispatch, and isn't something "nasty" for OO to handle, since some languages support multiple dispatch natively. On the other hand, C++ isn't one of them. Some good discussions of how to handle this in C++ can be found in "More Effective C++" by Scott Meyers or "Modern C++ Design" by Andrei Alexandrescu.

Share this post


Link to post
Share on other sites
I cooked up a quick example that demonstrates the behaviour you are looking for:

btw. the reason it is called double dispatching is because the virtual call mechanism has to be used two times.
You can see that happen in the code: when the virtual method 'collidesWith' is called (first dispatch). And then from within that method another virtual call is made (second dispatch).


#include <iostream>

using namespace std;

class Mesh;
class Sphere;

class Object {
public:
virtual bool collidesWith(Object &object)=0;

virtual bool test(Mesh &object)=0;
virtual bool test(Sphere &object)=0;
};

class Mesh : public Object {
public:
bool collidesWith(Object &object)
{
return object.test(*this);
}

bool test(Mesh &object)
{
// test Mesh against Mesh
cout << "testing Mesh against Mesh\n";
return false;
}

bool test(Sphere &object)
{
// test Sphere against Mesh
cout << "testing Sphere against Mesh\n";
return false;
}
};

class Sphere : public Object {
public:
bool collidesWith(Object &object)
{
return object.test(*this);
}

bool test(Mesh &object)
{
// test Mesh against Sphere
cout << "testing Mesh against Sphere\n";
return false;
}

bool test(Sphere &object)
{
// test Sphere against Sphere
cout << "testing Sphere against Sphere\n";
return false;
}
};

int main(int argc, const char argv[])
{
Mesh m;
Sphere s;

Object &obj1 = m; // mesh object
Object &obj2 = s; // sphere object

obj1.collidesWith(obj1); // mesh - mesh
obj1.collidesWith(obj2); // mesh - sphere
obj2.collidesWith(obj1); // sphere - mesh
obj2.collidesWith(obj2); // sphere - sphere

system("PAUSE");
return 0;
}

Share this post


Link to post
Share on other sites
Well, I take the approach of making the objects / characters and so on check themselves. Give each object class a function to see if it is colliding with something else. That way every object can call the AmIColliding(), and if it is adjust its own internal paramerters direction, velocity, and all that on itself. That is just the way I would approach it instead of making some external entity check all the objects and then have to tell the objects to update all the info about position and such. Just make the objects handle themselves.

Share this post


Link to post
Share on other sites

class baseObj
{
private:
face *trianglesInThisObject;

public:
virtual bool collidesWith ( baseObj * );
virtual bool collidesWith ( face * ); //could be non-virtual, or could have other types of collisions, like a ray, or a point/radius.
};

class sphere : public baseObj
{
public:
bool collidesWith ( face *f )
{
//do something to see if this face collides with my geometry.
}
bool collidesWith ( baseObj *b )
{
//for each face in the sphere, see if b collided with it.
if ( b->collidesWith(curface) )
{
//do something, we collided
}
}
}

int main ()
{
sphere S1;
sphere S2;
S1.collidesWith ( (baseObj*)&S2 );//ugly typecast, but gets the job done.
}





Thus the sphere is passing geometry into the base object, and the object checks the collions, so the objects pass geometry pointers around, and don't have to know the internals of the other object. Thus removing the need for many
collide ( sphere ) collide ( tri ) collide ( box ). Only a couple like Ray-Tri, and Tri-Tri collion types need to be added (like the triangle faces above.).

PS. Code is definatly not complete, its just there to show another idea.

Share this post


Link to post
Share on other sites
I'm actually finishing up a solution at this time that should handle your problem completely with compile-time resolution (no inheritance required, no virtual functions) using a heterogenous containment library I'm developing. The reason I started developing it was actually because of a problem very similar to this. It avoids any runtime polymorphism in favor of regular function calls and no type enumeration.

Multi-dispatch works okay with a small number of object types, but having to keep adding functions to the base class is a hassle and can potentially break code. Other solutions directly involving RTTI can also be nasty and force switch-like logic inside of your collision function (which also requires recompilation every time you add or remove a collision type). My proposed solution, which is currently hitting a rough spot because of lack of compliance in some areas with VC++ 7.1 is:


//Define all of your collision functions (each one completely separately)
void collide( sphere const& left
, sphere const& right
);

void collide( sphere const& left
, mesh const& right
);

void collide( sphere const& left
, box const& right
);

void collide( mesh const& left
, mesh const& right
);

void collide( mesh const& left
, box const& right
);

void collide( box const& left
, box const& right
);

// Collision function object passed to the algorithm
// (would in practice most-likely call a callback
// function object passed to the constructor on collisions)
class collision_function_object
{
public:
template< typename LeftType
, typename RightType
>
void operator ()( LeftType const& left
, RightType const& right
) const
{
// Call the appropriate collision function
// With types resolved at compile time
collide( left, right );
}
};


int main()
{
// Can contain spheres, meshes and boxes,
// and more or less types as you choose
::surge::cauldron::vector< ::boost::mpl::deque< sphere
, mesh
, box
>
> your_container;

// Add your objects (adds them to separate internal vectors)
your_container.push_back( your_sphere );
your_container.push_back( your_box );
your_container.push_back( your_mesh );
your_container.push_back( your_mesh2 );
your_container.push_back( your_sphere2 );

// Test collision -- 2 means each combination of 2,
// since you collide 2 objects at a time. This
// template can also be used for 3, 4, etc.
// objects per combination, which would require
// a function object taking that many parameters
::surge::cauldron::for_each_combination_in< 2 >( your_container
, collision_function_object()
);
}





This removes any and all RTTI and inheritance requirements and potentially even brings about a speed increase, particularly noticeable for large groups whose collision functions may not be too complex compared to the overhead of multiple virtual function calls for multi-dispatch. Perhaps more notably, it also successfully detaches the requirement for your collision functions to be member functions. This is very good since you can now, for instance, use figures (spheres, boxes, cones, capsules etc) from a premade math library, and you can add the collision functions as nonmember functions, not requiring you to inherit from or encapsulate the original types.

The only "problem" with the solution is that since internally there are 3 separate containers, order in the overall container goes all spheres, all meshes, then all boxes (each requiring different iterator types). Since order between types is often not a problem, as in this situation, the solution is generally optimal.

I may eventually also develop a dynamic version which synchronizes this type of container with one of polymorphic elements (providing the best of both worlds, common order and stl-style iteration as well as separate access by type with compile-time resolution).

Share this post


Link to post
Share on other sites

This topic is 4701 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.

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