So there’s no OpenGL problem here, but many of you I know are great C++ programmers, so here’s my question:
Say I have a base class “Geometry” and two derived classes “Sphere” and “Cylinder”. (This is a simplified version of how I have collision detection/reaction working right now).
Okay, so I have a vector of a bunch of these objects. So I drop them all in but have to cast them to their base class “Geometry” since it’s a vector of <Geometry *>.
Now, each game loop I’m testing items in the vector against other for collisions. But there are different tests to do depending on what kind of geometry they are. Sphere-Sphere collisions are different from Sphere-Cylinder, etc.
So I need to know what kind of objects they are, so I’m using RTTI’s typeid(). But I’m told basing code logic on RTTI or dynamic_cast is poor design, and I agree.
Is there a cleaner way that anyone can think of to do this? If my explanation isn’t clear enough I can post some code.
What you want to do is known as “double dispatching”. You want to call the appropriate version of some virtual function based on the types of two objects. Look at the “visitor” design pattern. I use this for my collision detection and it works nicely.
Thanks gumby, thanks sqrt[-1], that’s exactly the sort of solution I was looking for to make my code more “elegant”… We must have elegant code nowadays, mustn’t we?
Heh heh. It’ll certainly clean things up on my end. Thanks again guys!
I would have to argue that using the dynamic cast is less bad than the answer proposed by i.
Reason:
You should avoid using dynamic cast when possible, but there are appropriate times. When you implement a container (which your geometry array is) you have to allow casting to recover the base type, and this is an appropriate use of dynamic cast. Don’t let other people tell you never to use it; they probably don’t know how, that is why they tell you that.
The i solution has problems, because to add a new derived class you have to go edit every other derived class. This violates extensibility in a very bad way.
Remember, don’t believe everything people tell you; whoever told you dynamic cast is poor design is ignorant likely ignorant. This is the same phenomenon as when
the baptists (or muslims) say you shouldn’t dance because it will corrupt you. It is the product of weak-mindedness.
From Bjarney Soupstrap:
“…(use of dynamic cast) allows us to wrap a concrete type in a polymorphic type, say for transmission through an object I/O system (or container) and the unwrap the concrete type later.”
[This message has been edited by nickels (edited 06-20-2002).]
nickels, Yes I do agree that dynamic casting has a place in code. (weither or not this belongs in this case is up to debate)
Just out of couriousity, how would you add a new collision type like Box? It seems to me you would need to add box-box collision, box-sphere collision and box-cylinder collision. The logical place to put these new methods would be in the Box, Sphere and Cylinder classes. Since you are updating the other derived methods you may as well insert a TestCollisionBox into the Geometry class.
The other advantage of making the base class contain abstract methods for collision is that and new descendant class MUST implement all the collision types to be valid (or you will get a compile error) This prevents you accedently “forgetting” to implement a collision against two different types of geometry.
But I’m curious nickels, how would you implement this problem?
Edit: In the above code I origionaly forgot the virtuals, OK now
[This message has been edited by sqrt[-1] (edited 06-20-2002).]
i : I don’t mean to put down on the usefullness of your solution, certainly. But as far as C++ coding conventions go I have the concerns above.
Is there no way to truly abstract the TestCollision? Store the geometry in some way so that you really can test for a collision without even consulting the derived class. Can this function be implemented entirely in the base class by storing the vertices in the base class.
Otherwise having a class heirarchy really doesn’t help (at least in this respect). You are trying to milk polymorphism from things that don’t really have anything in common, it seems.
This is the direction I would head, though I would have to be more familiar with the internals.
I admit, I am the critic without a solution…
But, a word on why I don’t like the above solution. A user should be able to implement a new derived class without knowing anything about the siblings. A derived class is simply an extension of the base interface and should not rely on siblings. Also, now the dependancies are extremelly circular among siblings, with everyone knowing about everyone else; very messy and not even possible in some languages (F90, for instance). Also, now everytime someone adds a new class the entire library has to be recompiled. If your code was a library and users were supposed to be able to extend your code by creating their own geometry types, it wouldn’t work because they would have to have your source to add these collision functions to the siblings and they would have to compile your code.
There has to be a better model for this. However, sometimes what works is the best design (especially for home projects).
[This message has been edited by nickels (edited 06-21-2002).]
Unfortunately, I don’t think a fully generic solution could be implemented using just geometry, unless you wanted to force all derived geometry classes to provide a hyperquadric representation of themselves (or something similar) to the base class, so all collision tests could be handled in the same way.
However, you could generate a completely abstracted TestCollision with ray-casting; however, you can’t guarantee that collisions will always be detected.
The pseudo-code for TestCollision would look like:
bool TestCollision(A, B) {
status ← MAYBE
while (status==MAYBE) {
rayVector ← A.GenerateRays;
floatVec ← B.RayIntersection(rayVector);
status ← A.TestIntersection(rayVector, floatVec);
}
if (status==NO) return false;
else return true;
}
GenerateRays generates a number of random rays from the piece of geometry (the number of rays generated can vary from class to class), RayIntersection computes the distance from the RayOrigin to the closest intersection point of the geometry, and TestIntersection determines if the nearest intersection point with a different geometry is also inside the current geometry.
However, this solution will probably be noticeably slower than special-casing every type of geometry you create, since you’ll want to perform a number of ray/geometry intersection tests to ensure that you aren’t undersampling (and returning false negatives).
nickels, yes I agree that my “solution” would be horrible for extensibility, but like you said, it may be hard to implement it in a generic way. (As each new type would require collisions for all the other currently existing types, some of which may not be known with arbitary inheritance) (Other generic way would be to use a approximate mesh in the base class for the solution -but as stated you would lose a greate deal of speed. (sphere-sphere collision is very fast and other collisions can be short circuited)
But I still think my above solution still has bearing in a polymorphic type scenerio (not with inheritance of course).
Consider meshes in a scene using bounding volumes. Each mesh could decide for itself what geoemtry type best fits the mesh and store the geoemtry pointer. Then quick collisions could then be performed when two meshes got near each other without knowing what the bounding geometry types were.
I think we can safely close this thread and agree there is no (known) perfect solution. (Unless someone else would like to propose something?)
It features a complex class hierarchy, with collisions, physics and drawing being done at the most general level possible. I also use a CollisionObject instead of using the actual vertices of the object. The CollisionObject can have a sphere, a hierarchical bounding box, and in cases where polygon collisions are needed, it has a collection of facets and vertices that point to the actual facets and vertices of the object.
Btw, i dont think there’s a problem with using typeid’s in some situations, but if you can use a virtual function, it is preferrable.
[This message has been edited by ioquan (edited 06-24-2002).]
All of my geometric types are derived from Object3D (Object3D is also derived from Entity3D which can be any physical entity such as models, terrain, lights, cameras, projectiles, etc.). Each Object has a virtual collide function which accepts another object as the parameter.
As of right now, I’m using typeid’s inside the virtual collision function. For example, in Mesh3D::Collide(Entity3D * entity), I will check the typeid of entity to decide if it is a model, projectile, etc.
This is really a temporary solution though. The idea is to eventually make a list of valid collision tests for each object, and then for the virtual collide function to access that list and have no knowledge of the actual type of the object.
Not ever done anything like this but why not start by defining an object, a sphere, and how it will collide with itself, i.e. other spheres.
Next object is a plane, define how it collides with planes and spheres. Then a cube how does it collide with cubes, planes and spheres.
This makes adding new objects easy, but you have to chose what collides with what, this requires ordering the list of objects by complication rather than by time of creation.
This thread has been getting a bunch of replies, so I thought I might as well share the original snippet of code that caused me to ask the initial question about design.
I haven’t changed anything major yet, and I don’t know that I’m going to, because it is apparent that there is no one perfect way to do this. And the more I look at the method I’m using, the more it looks all right, and manageable all from the collision class.
So here’s what I’ve got:
1 vector of dynamic objects which is tested each loop agains itself, and against the other vector which contains static objects.
Then I have
Class BGeo // for “Bounding Geometry”
|- Class Sphere
|- Class Cylinder
|- Class Poly
Here is the original questionable code (compacted):
Which brings up another question I have as a result of changing another aspect of my collision class. (Maybe it would be better off in a new thread, but I’ll toss it in here for now anyway since it’s C++ oriented).
Is there a way to store a reference to a member function without storing its corresponding instance of whatever class it belongs to? And if not, is there a way to store some sort of handle to the instance of its class in a generic way so that one can simply call “instance->memberFunction()” without needing to know the Class of the instance? I haven’t been able to look up a clear answer to this.
Looks to me like you guys are making the problem harder than it has to be. All of these design techniques are fun to explore but the problem at hand is really a simple one, with a simple solution. I suggest you download Mancha’s code linked above and check it out, it solves this problem in a very simple manner.
rhmazza, member functions are meaningless without a reference to the class they belong to. You can use a ‘pointer to member function’ but that pointer is associated with an instance of an instantiated class. I believe the answer to your question is no.
[This message has been edited by Iceman (edited 06-25-2002).]
You cant work with member function pointers the way you are wanting to, unless you explicitly pass the this pointer to it, which kind of defeats the purpose.
However, your question about instance->MemberFunction() has a simple answer. This is precisely what a virtual function is. You declare the function as virtual in the base class, then you override it in the derived classes. Then no matter what kind of reference to the class you have, the proper function will be called.
I posted a link to my engine above. If you download it, check out World3D::Collide(void), and all of the virtual object collide functions like MD2Model::Collide(Entity3D * entity), Mesh3D::Collide(Entity3D * entity), etc.
Here is the direct download link for the lazy: http://home.earthlink.net/~ioquan/x3d014.zip
[This message has been edited by ioquan (edited 06-25-2002).]
One more thing…do you really want to have separate collision functions for all these different shapes? Are you going to do collision functions for trapezoids, parallelograms, ovals, etc.? Most engines use a sphere test first, then do the final collision detection/correction against either a sphere, box, or a polygon. For each object, you are probably going to have a combination of tests.