Archived

This topic is now archived and is closed to further replies.

Zealot

3D Collision Response

Recommended Posts

I just can''t get this out of my head - how do 3D games pull off collision response with the environment? It is fairly simple to do collision detection, but, how do first person games pull off gravity and the like? Simply put, how does the game engine differ between floors, walls, and the ceiling? It sounds simple, but it is by no means such. Do they first see if the character collides with a polygon, then determine the slope, and if it conforms to certain guidelines (such as friction and maximum slope climbable) it is considered a floor poly? That seems possible if the person is rather small, but how do games do it if it is a large character, such as a giant bot? Games like Genome did it by not having steep slopes, and storing the ground and rocks and such in different ways. But, what if I have a polygon soup level? Is it possible to make realistic looking colllisions and response using large objects? Those last few paragraphs may have sounded like a large mess, but bear with me. En taro Adun! Doom to all who threaten the homeworld! *Protoss Zealot - Starcraft*

Share this post


Link to post
Share on other sites
It is possible that a large figure could have collided with a large number of polygons along a given travel path. I think the best engines will deal with the first collision and handle the rest one by one as the object encounters them..

The geometry of the polygon being collided with allows the new travel direction to be calculated based off the previous travel direction.

Gravity is just another way the travel direction is affected. It''s just added to the object''s velocity frame by frame (if not standing on a surface)

I think the trick with complex figures is to perform collision detection quickly, and not check against a bunch of polygons every frame. It can be done, but it would be a calculation hog. There are ways to limit which polygons are checked (by approximating the figure as a simpler body first, and if that collides, then do a more detailed check for actual collision, etc.)

Share this post


Link to post
Share on other sites
With your collision detector you may be able to get the collision tringle, with this you can get the face normal and response with bounce, slide or whatever you want.

Share this post


Link to post
Share on other sites
For 100 games, there are probably 100 different ways that physics are implemented.

As far as collision goes (and I did not work on the physics/collision in our games, so I can''t say for sure), it ranges from total "fake" physics, to real simulated, per-polygon colliison stuff.

A really cool thing to do if you have $20 is to go out and buy "The Document Of Metal Gear Solid 2". It is a super cool DVD for Playstation2 that shows how they did a lot of their stuff. Considering that this is one of the best games ever made and the level of sophistication that it seems to have, I was amazed to see how many things in their game that were pulled off 100% convincingly were completely faked. For example, they had some pretty cool geometry, yet for physics and collision, they had a totally separate "invisible" level geometry underneath that was basically made out of boxes, and simple ones at that. So it did 1% of the work it would have had to do had they used their rendering level geometry for their physics. Yet the player never knows the difference.



Marc Hanson
Programmer on "Alter Echo"
Outrage Games - THQ

Share this post


Link to post
Share on other sites
Read, read, read, and then read more. I'm still learning a lot about collision detection.

To most collision/physics engines, gravity is just another force. It acts on the player and on other dynamic objects. The player tries to fall through the floor, but the floor blocks the way.

This is exactly the same as running a player into a wall. You apply a force to the player and make them move forward. The player tries to move through the wall, but the wall blocks the way.

The fact that gravity points down or that the floor is the floor really isn't too special. Gravity is just another force and the floor is just another polygon to be collision tested against.

There are many ways of doing collision testing. Most approaches use some kind of heirarchical collision testing - using BSPs, AABB trees, OBB trees, kd-trees, octrees, and quadtrees. These methods are all designed to reduce the number of object-object tests that one has to make using the power of recursive subdivision. Then there are other approaches like Sweep & Prune, and collision hashing.

Yes, its possible to do robust collision for a polygon soup level using something like AABB trees or octrees. BSPs don't work so well here, but there are tradeoffs involved with nearly every approach. (BSPs however are very fast for ray collisions and work well in closed bounded indoor environments.)

Most of the time you end up bounding your objects by an invisible bounding volume that is used for collision detection. An AABB, OBB, sphere, or cylinder usually. Testing the bounding volume is much faster than testing versus each polygon. If the bounding volumes of two objects intersect and you need more detailed information about the collision, usually, the objects themselves are divided up into to a heirachy of bounding volumes, so you can narrow quickly on the collision point using recursive subdivision. The very last thing you want to do is test triangle versus triangle. The only time that a collision engines end up testing triangles is for dynamic objects/players versus environment polygons. Even then its usually a bounding volume versus a few triangles in the environment (and not triangle vs triangle).

The larger the object you have, the more surfaces it will have to be tested against. So larger objects cost a little more effort to test, but this isn't really a big deal.

[edited by - Z01 on November 6, 2002 5:26:16 AM]

Share this post


Link to post
Share on other sites