Complex collision detection/correction

First let me tell you a bit about how I do collisions, then I’ll get to the problem…

a quick look at http://home.earthlink.net/~ioquan will give you an idea of the context in which I am doing this.

My frame updates go something like this:

  1. Get Input.

  2. For each object that can move, calculate a velocity vector. The velocity vector is determined by various factors, including gravity, thrust, and previous velocity. The final vector is then scaled by time. Also calculate a rotation velocity and scale it by time.

  3. Now do collisions. For each moving object, test it against each other object. If the bounding spheres of the two objects collide, then do one of two things. If the object that it collided with is a model, correct the collision against the model’s bounding box (this works fine). If the object it collided with is terrain, then do a quad tree search. The quad tree does a few checks, then returns a small list of polygons with which to do more accurate tests. Now that I have a list of polygons, I take the “foot” of the moving object (a single point near the feet) plus the velocity vector. That gives me a line segment to test against each poly. If the poly is a floor, there is one kind of correction, if it’s a wall, there is another kind.

Note about collision correction: the purpose of the collision correction functions (Facet3D::RayCollide(pos,vel) and SmartBox::RayCollide(pos,vel)) is to change the velocity vector so that the collision doesnt happen. This is where most info on the web leaves off. They simply tell you how to determine if a collision happens, then assume you just want to STOP the player. In actuality, you need to slide the player.

The floor tests work fine. I simply solve for the y coordinate using the point the player is trying to move to and the plane equation of the polygon with which it collides. This results in the player being able to walk around the terrain, being raised with the floors.

The wall tests are the problem. If I just want to stop the player, that’s easy, I just find the intersection point, and change the velocity to (intersect - oldposition). Just stopping the player is not right though. I have tried many different methods of sliding the player. I have succeeded in sliding the player, but there are problems. Certain sliding methods result in the player bouncing erratically when he is colliding with both a wall and a floor. By tweaking some settings, I can reduce the bouncing in some places, but then it seems to appear in other places. I can also make it so the y coordinate of the final position to move to is the same as the intersection point; that reduces the bouncing greatly, but also means the player cant slide down a steep wall.

So ultimately what I want to know is, what is the right way to slide a player along a wall, and how can you eliminate the nasty bouncing side effects?

If anyone has done these types of collisions(like quake, doom, and just about any 3d game with floors and walls) , and can offer any insight, it would be much appreciated. Or if you have a URL that discusses this topic, that would be very helpful too.

[This message has been edited by ioquan (edited 05-31-2002).]

I just made an update to my site at http://home.earthlink.net/~ioquan

I put up two recent builds. One has the walls treated differently than the floors, and one doesnt. I also put up three .cpp files which have collision related code. (note: the code and exe in the zip are out of date.) (also note: I am using a 166 mhz cpu and an old cheap graphics card, so it will probably run MUCH faster on your system. At 150 fps or so, there may be some problems that I am not aware of.)

Please take a look. I have been trying to get the wall collision correction working for over 3 days now and its driving me crazy.

[This message has been edited by ioquan (edited 05-31-2002).]

>>So ultimately what I want to know is, what is the right way to slide a player along a wall<<

v = v - (N*(V.N))
v =velocity N=normal . = dotproduct

quake/doom cheat and treat the object as being a point/sphere which is ok for a game, then again if u have acees to q3a walk to a cliff edge then walk a bit further then look under your feet, youre doing a cartoon with the subtle difference with a cartoon the person will fall when they realise they are walking on nothing, in quake3 u can stand in mid air + have a polite conversation!, accurate collision detection is impossible. how impossible? u know the guys doing the nuclear explosion tests, well even them with there cray super computers can do a perfect time of collision. what does this tell u, hack my dear man, if its treating the person as a point that can walk in air so be it.
personally one thing ive started to do since a year or so, is to realise collision detection is not perfect, errors will occur, how to make the code hndle these errors without blowing up in your face is the task mate

There is such a thing as a perfect collision test, but not in real time. To do a perfect test, you would have to check every triangle against every triangle. Decide your action in the case of a collision, do that action, then retest (for instance bouncing off one wall into another in a corner) every triangle to every triangle, etc, etc, etc ad absurdum. Don’t bother for perfection, perfection isn’t. Hack as the man said. Choose your algorithms on speed and least case failures and you can live with the oddities.

Thats not true, you don’t need to check all triangles resulting in a O(m*n) complexity.

You can use a tree structure with your triangles (Octree, BSP or something else)

They give you an O(log n) complexity, so you can dramatically reduce the number of computations normaly to O(m log n) maybe less.
You can also combine this with hierachical bounding volumes, that tightly enclose the object.
You could have different meshes for collision detection and rendering.
The last two wouldn’t be that accurate anymore, but not as bad as a single bounding box.

Those all have the disadvantage, that it is more complicated to implement such structures and algorithms. But there has to be something in programming that is more fun then just doing double loops, or writing opengl state changes…to get back on topic :slight_smile:

Lars

Thanks for the help. I am not wanting to do perfect collision detection, I just want to eliminate the ickiness. I have tweaked it to the point where it works acceptably well, but there are still some erratic movements when the player is colliding with both a wall and a floor (especially if the floor is very steep - almost a wall).

By the way, I do use a hierarchical box, and I test lines against polygons. The problem is not so much the detection of collision (or speed), as it is the correction of collisions.

Anyway, I’m fairly happy with the way it works now, even though I would like it to be better.

[This message has been edited by ioquan (edited 06-09-2002).]

Try “comp.games.development.programming.algorithms” in netnews, where collision detection is frequently discussed. Very good algorithms for collision detection are known, and code is available. Search for “collision detection” in Google. V-Collide, V-Clip, and SOLID are all good. But collision detection isn’t the hard problem. Collision response, or what you
call “correction”, is.

You’re at the beginning of building a physics engine. That is a hard problem. I’ve done it; see “http://www.animats.com”. It took me two years. Admittedly I was focusing on the hard cases. There’s a sizable literature on the subject. The articles in Game Developer are a good start. Baraff’s tutorials in the SIGGRAPH proceedings are also useful, and you can find them on the web.

While you can find good collision code on the web, the free physics engines don’t get the hard cases right. Most of the people developing them get to the point where they hit the hard problems, then stop.
I recommend Havok for serious game work. It’s expensive, but if you have a budget and a schedule, it’s far cheaper than doing it yourself.

If you really want to work on this problem yourself, you’re going to end up knowing a lot about numerical solution of simultaneous differential equations and computational geometry. You get a choice of method - you can build a spring/damper system and struggle with stiff systems of differential equations, or you can try the Baraff impulse/constraint approach and struggle with linear complementarity problems.

Nobody who’s succeeded at this has spent less than two years on the problem.