PDA

View Full Version : C++ question on "clean code design"



rhmazza
06-19-2002, 10:38 AM
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.

gumby
06-19-2002, 11:02 AM
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.

sqrt[-1]
06-19-2002, 04:43 PM
The visitor design pattern in this case would look like this:

class Sphere;
class Cylinder;

class Geometry
{
//General collision
virtual bool TestCollision(Geometry *)=0;

//Specific collisions
virtual bool TestCollisionSphere(Sphere *)=0;
virtual bool TestCollisionCylinder(Cylinder *)=0;
}

class Sphere : public Geometry
{
bool TestCollision(Geometry *g){
return g->TestCollisionSphere(this);
}

//Specific collisions
bool TestCollisionSphere(Sphere *){
//Code for sphere-sphere collision
}
bool TestCollisionCylinder(Cylinder *){
//Code for sphere-cylinder collision
}
}

class Cylinder : public Geometry
{
bool TestCollision(Geometry *g){
return g->TestCollisionCylinder(this);
}

//Specific collisions
bool TestCollisionSphere(Sphere *){
//Code for cylinder-sphere collision
}
bool TestCollisionCylinder(Cylinder *){
//Code for cylinder-cylinder collision
}
}


Then to simply test the collision between two Geometry objects, simply call
geometryArray[0]->TestCollision(geometryArray[1]);

Edit: Forgot the virtuals..

[This message has been edited by sqrt[-1] (edited 06-20-2002).]

rhmazza
06-19-2002, 04:49 PM
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!

Miguel_dup1
06-19-2002, 08:00 PM
I prepared a simple sample of base classes... Check it out.
http://a502j271.tower.wayne.edu/BaseClass.zip

I hope it helps.

nickels
06-20-2002, 08:36 AM
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).]

rhmazza
06-20-2002, 09:49 AM
The plot thickens...
but I enjoy different opinions on things. I see...

sqrt[-1]
06-20-2002, 04:59 PM
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).]

nickels
06-21-2002, 06:44 AM
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).]

gking
06-21-2002, 10:30 AM
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 Geometry class would look something like:




enum { NO, MAYBE, YES };

class Geometry {
public:
static bool TestCollision(Geometry*, Geometry*);
protected:
virtual void GenerateRays(std::vector<Ray>&amp;) = 0;
virtual void RayIntersection(const std::vector<Ray>&amp;, std::vector<float>&amp;) = 0;
virtual unsigned int TestIntersection(const std::vector<Ray>&amp;, const std::vector<float>&amp;) = 0;
};


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).

sqrt[-1]
06-23-2002, 03:11 PM
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?)

ioquan
06-24-2002, 04:56 PM
In case you're interested, I have a complete engine in c++ at http://home.earthlink.net/~ioquan. (Click on x3d ).

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).]

ioquan
06-24-2002, 06:11 PM
Here's a quick explanation of how I do this.

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.

fringe
06-25-2002, 06:59 AM
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.

Just an idle idea really

fringe

rhmazza
06-25-2002, 09:14 AM
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):

bool CollisionManager::hits(BGeo *g1, BGeo *g2)
{
bool answer = false;
// check all cases:

if(dynamic_cast<Sphere *>(g1)){
if(dynamic_cast<Sphere *>(g2)){
return hitsSphereSphere((Sphere *)g1, (Sphere *)g2);
}
else if(dynamic_cast<Cylinder *>(g2)){
// Not Needed Yet
}
else if(dynamic_cast<Poly *>(g2)){
return hitsPolySphere((Poly *)g2, (Sphere *)g1);
}
}
else if(dynamic_cast<Cylinder *>(g1)){
if(dynamic_cast<Sphere *>(g2)){
// Not Needed Yet
}
else if(dynamic_cast<Cylinder *>(g2)){
return hitsCylinderCylinder((Cylinder *)g1, (Cylinder *)g2);
}
else if(dynamic_cast<Poly *>(g2)){
return hitsPolyCylinder((Poly *)g2, (Cylinder *)g1);
}
}
else if(dynamic_cast<Poly *>(g1)){
if(dynamic_cast<Sphere *>(g2)){
return hitsPolySphere((Poly *)g1, (Sphere *)g2);
}
else if(dynamic_cast<Cylinder *>(g2)){
return hitsPolyCylinder((Poly *)g1, (Cylinder *)g2);
}
else if(dynamic_cast<Poly *>(g2)){
// Not Needed Yet
}
}

return answer;
}

rhmazza
06-25-2002, 09:25 AM
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.

Thanks,
Ray

Iceman
06-25-2002, 11:35 AM
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.

Iceman
06-25-2002, 11:38 AM
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).]

ioquan
06-25-2002, 12:11 PM
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).]

ioquan
06-25-2002, 12:27 PM
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.

rhmazza
06-25-2002, 12:52 PM
I knew I was thinking about the instance->memberFunction() too hard. Whoops. And I have actually already downloaded your code but have not had a chance to look through it yet.

As for having spheres, cylinders, and plain polygons (usually just for terrain), I find all objects are approximated well, reactions are easy and feel natural, and it is very efficient.

Thanks again everyone's responses.

sqrt[-1]
06-25-2002, 02:24 PM
I really did not want to continue this thread but any how...

Iceman - how does macha's code solve this problem? All it does is print the object you are colliding against. The problem here is to get 3 things: -The object you are colliding against
-The object you are colliding with
-A way to access a method to perform the collision between the two objects of known types.

With macha's code all we can get is one of the collision objects, not the other object or how to collide against it. Or perhaps I am reading the code wrong? (elighten me please)

Thug
06-26-2002, 06:03 AM
If you do write the code the way sqrt[-1]
listed you will have to watch out that you have a TestCollisionSphere(...) method for every type of collision. I used this type of code for handeling collisions. What happens when Object A collids into object B. Do they explode, Enter the structure, etc. Anyway the part that you have to watch out for is if you happen to forget a collision method, it will crash the program. Believe me, I had my share of "Program has performed illeagal operaton..." plenty of times until I found what was crashing the program.

There are two great c++ books out there written by Scott Meyers
called "Effective C++: 50 Specific Ways to Improve Your Programs and Design" and "Effective C++ Cd: 85 Specific Ways to Improve Your Programs and Designs". One of these books, I forget which one, decribes using virtual functions to handle the collisions and you have the opprotunity to catch any collisions that you do not have registered and display a message telling you that you need to impliment this collision code as well. Trust Me. It is worth the money to read these books. The best thing is that you do NOT have to read the book from cover to cover.

sqrt[-1]
06-26-2002, 02:55 PM
Uh.. Thug how can you forget to implement TestCollisionSphere? It is a pure virtual method in the base class. If you forget to implement it, the compiler will complain.

Also what you do with the result of the collision is not (and should not be) part of this code, it only determines if a collision occured between two objects (and if you wish the position of the collision)

I also fail to see how this design could crash your program. Could you elaborate more?

Nutty
06-28-2002, 03:01 PM
You could use a slightly modified version of sqrt[-1]'s code, and you wouldn't need to modify the derived types to add a new collision type.

Simply make the base class functions virtual, but not pure virtual, and implment an empty function for each one, or put an assert in.

Then when you add TestCollisionCube(Cube*) {} to the base class, you just implement it in the cube geometry class.

Some ppl will probably say thats really dirty but it gets around the problem nickels pointed out, with no ugly casts involved.

Nutty