Encapsulation and Collision detection

OpenGL OpenGL: Advanced Coding
1

This is not really an OpenGL question, but I wanted to see what some of the people have to say about this.

What I want to know is what is the best way to implement collision detection in c++ with as little violation of encapsulation as possible? I want to avoid having to rewrite collision code for all of my existing objects when a new type of collidable geometry is introduced to the engine.

Since collision detection neccessarily involves at least two objects, it becomes very difficult to encapsulate the functionality into a single object.
It seems there is no way to implement collision detection without having every type of collidable object know the details of every other type of collidable object, and as an OO c++ programmer, this troubles me greatly.

I guess the best solution would involve abstracting away the data neccessary for collisions. For instance, have a class that handles box collisions, another that handles cylinder collisions, and another that handles polygonal collisions. The hope would be that each new type of geometry would fall into one of these categories, and be derived from the appropriate object. This way there would be a limited number of cases that would have to be acounted for. I have a lot of unanswered questions about how this could best work though.

Anyway, if anyone has any ideas or suggestions at all, I would really appreciate your input.

2

It all depends on how accurate you want to be.

It also depends on how you envision your engine design. Since you said you prefer OO and doing encapsulation (minimized coupling), then I think you’re gone be unhappy with what you are thinking right now.

Personally, I would have some external functions (insided a class perhaps) to which you feed your geometry. You have to decide on how to do some quick rejections (1 bounding sphere per object test, if it passes, test sub parts, …) and tell that class on how to process the geometry.

Anywhoo, everyone has a unique approach.

V-man

3

It troubles me greatly that people think being an OO C++ programmer means EVERYTHING has to be object-oriented. No one tool works for every job, use the appropriate tool. As Einstein said (with slight paraphrase due to my fallible memory), “Make everything as simple as possible, but no simpler”.

In other words, if object-oriented programming doesn’t work, feel free to use something else that does work.

4

One of the main reasons I have decided to start work on a new engine is because I am unhappy with the design of the collision system in my previous engine.

I’d like to keep it as OO as possible, for several reasons. I want to build a general purpose engine that is reusable and extensible. I would also like to be able to compile it into a library. The people who use the library should be able to derive a new class from my classes without having to worry that the derived class wont be accounted for in the collision system.

Cameras, characters, projectiles, etc. all share common collision code. And for static geometry, terrain meshes, buildings, and even bsp trees share some common collision code. Since many different types of entities in the 3D world share common collision code, I would like to reap the benefits of inheritance and polymorphism as much as possible.

5

I want to build a general purpose engine that is reusable and extensible.

Which can be done just as well without an OOP approach.

I would also like to be able to compile it into a library.

Libraries existed long before OOP.

Since many different types of entities in the 3D world share common collision code, I would like to reap the benefits of inheritance and polymorphism as much as possible.

Unfortunately, collision code commonly has an OOP-breaking problem: it needs fundamental knowledge of 2 objects to work. You just aren’t going to get around this. As such, adding new objects will always pose a problem.

The best method I can come up with is to separate objects and their collision volumes. That is, you have a library of collision-detection functions (not class members, but actual functions. If it makes you feel better, make them static members, but I wouldn’t suggest it, as you will see below) that take two collision volumes and tell if (and where) they collide.

When you iterate through your objects list to see who collides with what, you ask each object for their collision volumes. Then, you take these two sets of volumes and call the pair-wise collision detection functions on them.

This way, when someone introduces a new object into the scene, all he needs to do is describe it in terms of a set of pre-defined collision volumes. You should, also, have some way of adding to this list of collision volumes, but this must require the programmer to write new volume collision detection functions.

Precisely how you integrate these new functions into your code is up to you. I might try a physics initialization routine that gathers up the possible collision volumes and collision function-pointers. The user can add new volumes and function-pointers to the libraries list during initialization. It may look kind of hack-ish, but it is a good solution to the problem.

6

You can implement multiple-dispatch (which is basically like what Korval was saying you should do by hand) automatically so that you can keep a nice object oriented structure without having to have people edit your original code for new cases.

The beginner’s reference for this sort of thing is Meyer’s “More Effective C++” and the more advanced reference is Alexandrescu’s “Modern C++ design”.

I’ve implemented the latter, but just as a warning, MS Visual C++ 6.0 compiler is not up to it. You’ll have to use a different one.

– Zeno

7

Originally posted by Zeno:
[b]I’ve implemented the latter, but just as a warning, MS Visual C++ 6.0 compiler is not up to it. You’ll have to use a different one.

– Zeno[/b]

You have encountered a bug? and what was it.

V-man

8

Function overloading. Functions don’t need to be members of any class to be OOP. If it satisfies you, write a ‘collision factory’ class or something.

Just a small snippet, I don’t want to completely spoil the fun.

inline bool collision(const Sphere& sphere,const Cylinder& cylinder)
{
   return(collision(cylinder,sphere));
}
9

I think that how are performed the encapsulated features is not the main problem : in most case, by writing something in a more C manner, you optain better performances than when you use operator or other complex mechanisms.
But the main goal is to optain an easy to understand class hirarchy, an OO only API, and no limitations like fixed table or global variables. You can build tables and references in background wich will make your objects interact as “magic” : when constructing an object, all other objects can interact with the new one thru recording table and direct pointer reference. So, each class can, internally, have his “tips” to perform more efficiently features.

That’s how Y work.

For pair object collision, I think the only strategy to optain an efficient but progressive test code is to transform complexe object in a more generic one, for exemple a mesh-mesh collider or sphere-sphere collider, because every geometry can be transformed in common geometry (by inheritance, every object are the base geometry). With time, you will surcharge your pair test to obtain better performance with the most used geometry types. You know, at loading, for first test, you have to compuste Bounding Sphere or box. You should transform it in poor mesh. With time, you will write new collision test methods for more accurate and faster test to satisfy users.

What I want to say to you is that with C++ you can start with really small but feature rich core, that will grow with time. The most importante thing is to have all features, the right architecture and an extensible structure at start : for that, I all time write ALL my headers file after every line of code. For each class components, I describe the usage of all others and how classes aterract to avoid conception errors.

regards,

Gaby

10

Originally posted by V-man:
[b] You have encountered a bug? and what was it.

V-man[/b]

The double-dispatch helper that I was talking about is heavily dependent on templates. MSVC6 is notoriously bad with templates. Specifically, it doesn’t support templated member functions and it can’t correctly deduce template arguments from function parameters. Intel’s compiler is good enough to get things to work, though it’s template support isn’t 100% either (at least in version 5.0).

11

It is really difficult to seperate collision code into classes without breaking encapsulation. So don’t think in terms of classes, think in terms of components.

Taking zeckensack’s example, throw all your collision code into a namespace.

namespace collide
{
inline bool collision(…)
{
…
}
}

Namespaces are really underutilized. I have been trying to get into the habit of not puting anything into the global namespace. And then selectively use “using namespace foo;” declarations to make code look prettier.

Everything just starts making more sense and looking cleaner.

[This message has been edited by PK (edited 12-18-2002).]

12

For pair object collision, I think the only strategy to optain an efficient but progressive test code is to transform complexe object in a more generic one, for exemple a mesh-mesh collider or sphere-sphere collider, because every geometry can be transformed in common geometry (by inheritance, every object are the base geometry). With time, you will surcharge your pair test to obtain better performance with the most used geometry types. You know, at loading, for first test, you have to compuste Bounding Sphere or box. You should transform it in poor mesh. With time, you will write new collision test methods for more accurate and faster test to satisfy users.

I’m not sure I understand your idea fully, but it seems like all you’re doing is forcing objects to describe themselves in similar terms. That is, if I have a sphere and a cylinder, the sphere must be written to describe itself as a cylinder.

This is unacceptable for good physics (and if you’re not interested in good physics, why are you bothering with this at all?). If I really wanted sphere-cylinder collision, doing sphere-sphere isn’t going to get the job done; a sphere isn’t a cylinder. And doing mesh-mesh (transforming them into meshes) is going to be atrociously slow.

In short, this will only lead to an approximation of the right thing, not the actual right thing.

But the main goal is to optain an easy to understand class hirarchy, an OO only API, and no limitations like fixed table or global variables. You can build tables and references in background wich will make your objects interact as “magic” : when constructing an object, all other objects can interact with the new one thru recording table and direct pointer reference. So, each class can, internally, have his “tips” to perform more efficiently features.
That’s how Y work.

That is a rather immature attitude towards both design and programming. Yes, you like OOP; that’s fine. But it is not always the appropriate method for programming a section of code. OOP is a means to an end; it is just a tool. You don’t use a hammer on a screw; you use a screwdriver. Just the same, you don’t use OOP for every problem that comes along. You use the tool that is most apporpriate. And the most appropriate tool looks more like my initial suggestion than C++ OOP.

13

Here’s a suggestion you might want to digest. When dealing with classes, try to only use the class to modify it’s own data. In all other cases, yours for example, pass the class into a regular function just like you would a struct. Not following these guidlines can cause confusion.

[This message has been edited by WhatEver (edited 12-18-2002).]

14

So I thougth that I should offer my two cents. My observation up to this point is that if I create a new object you can do two things. One is to define it in terms of some derivitive more general thing, for instance making it into triangle etc. Or you have to define how this new object interacts with all the other objects otherwise it will not know how to. That means each class I add has to have one more collision test than the last. This bad however because I can not merge different peoples sets of new classes together.
So maybe the thing to do is to write both of these approaches. Have a base object that collides the triangles that make the object up. Then allow the user to also add code that enables them to write specific collision events bewteen objects if they wish. Could you do this with a base class for objects then overload a collide function with the correct types. SO when compiled the collide deals with everything unless the specific overloaded case is used.

I hope this post is not just craziness I am a little tired,

fringe