Sign in to follow this  
TheC00L1

Best and easiest way to handle collision

Recommended Posts

For the past few months i've been trying to find the best way to handle collisions, and heared a lot about AABBs, triangles, ellipsiods, OBBs, and the like, through various tutorials, sites, and posts, but nothing straight forward, hard code or tangible for me. So i come and present my case to you: I have a 3D model and a 3d scene, made of triangles(no need for speed improvements), i do not need fancy physics, i just want to prevent him from going through the walls, but i DON'T want:
     If collides, go back to last point
See what i mean? I seem to get the Collision Detection Part, but its the Reponse that i can't seem to comprehend Also, the model is animated and rotates without a chnage in the velocity. Thanx!

Share this post


Link to post
Share on other sites
Are you looking for the object to "bounce" off whatever it hits? If you can detect a collision, what behavior do you want when a collision IS detected?

Share this post


Link to post
Share on other sites
If you want your objects to bounce around realisticly you'll have to simulate them using 'rigidbody dynamics'. Just do a google search for these key words, there's plenty of free resources out there which explain the dynamics of rigidbodies and how to apply collision impulses to them to have them bounce of scenery and each other in a realistic fashion. In particular you might want to read up on Chris Heckers tutorials we pointed you to in your last thread or for an in depth view I recommend tracking down any papers by Baraff such as:

www.cs.cmu.edu/~baraff/sigcourse/notesd1.pdf

If you have any problems understanding this stuff you know where to come ^_^

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
no need for speed improvements

Are you Sure? triangle soup sounds potentially slow, as well as prone to problems with accurate collision detection (thin wall vs fast bullet problem)


The Easiest way to deal with collisions, so you don't have to mess with the difficult response, is to set the object's health to 0, animate a little explosion or death animation, then delete it.
This is done in many arcade games, as well as even more recently in Halo1; whenever a player touched a moving vehicle he died instantly, because it was simpler than calculating the soft vs solid body collision responce.


Other responce ideas include:
bouncing, or sliding

bouncing is pretty easy, you just reflect the velocity of the object against the plane it collided along.

for sliding, you project the velocity onto the collision plane; this gets complicated if you hit more than one plane at once or in succesion, since you'd have to figure out which came first and continue checking after each new slide

Yeah, Kill Player has got to be the easiest collision responce.

Share this post


Link to post
Share on other sites
Quote:
Original post by haphazardlynamed
Quote:
Original post by TheC00L1
no need for speed improvements

Are you Sure? triangle soup sounds potentially slow, as well as prone to problems with accurate collision detection (thin wall vs fast bullet problem)


What i meant was i can always do the octtree or bsp, later, i just want to be able to responed before things get to complex.

As for the fast collison detection i was going to turn the points into lines if it has a squared distance(x*x+y*y+z*z) greater than whatever.


Quote:

If you want your objects to bounce around realisticly you'll have to simulate them using 'rigidbody dynamics'. Just do a google search for these key words, there's plenty of free resources out there which explain the dynamics of rigidbodies and how to apply collision impulses to them to have them bounce of scenery and each other in a realistic fashion. In particular you might want to read up on Chris Heckers tutorials we pointed you to in your last thread or for an in depth view I recommend tracking down any papers by Baraff such as:

www.cs.cmu.edu/~baraff/sigcourse/notesd1.pdf

If you have any problems understanding this stuff you know where to come ^_^


Yeah, thanx Motorherp for your last reponse on my AABB thing,
The rigid body stuff is pretty tempting, but i don't want anything fancy yet, but i might just have to do it, that link actually wasn't that bad. And Chris Hecker's stuff has to do a lot with 2D and not clear enough about 3D response part, it has 3D rgid body, but not exacty what i'm look for.

Quote:

Are you looking for the object to "bounce" off whatever it hits? If you can detect a collision, what behavior do you want when a collision IS detected?


Well, i got a book, and i tested the functions and they did work on my testing enviroment. But i have a problem with fact that i don't want the character to go through walls, and sometimes bouncing has a problem.

Quote:

The Easiest way to deal with collisions, so you don't have to mess with the difficult response, is to set the object's health to 0, animate a little explosion or death animation, then delete it.
This is done in many arcade games, as well as even more recently in Halo1;
Yeah, Kill Player has got to be the easiest collision responce.

I could do that with the builits, but killing him does not make it fun, when he falls on the ground or hits a wall. Plus I want gravity to have a share in all the polygons not just the ones facng almost or directly up.

I guess i could try the bounce part, since i haven't yet, though since my objects are iregulary shaped, like there's hands that stick out, i might have to do the rigid body stuff.

Quote:

for sliding, you project the velocity onto the collision plane; this gets complicated if you hit more than one plane at once or in succesion, since you'd have to figure out which came first and continue checking after each new slide


Yeah, sliding sounds better, is it better for irregularly shaped object, there could be a problem where, like a protruding rock hits the inside of his hand, as he rotates.

But i'm not sure what i should include, maybe it is the rigid body. Should i take a physics engine and plug it into my geometry?
Have any of you designed the collision reponse part in a 3D game before?

Thanx for your time and patience.

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
But i'm not sure what i should include, maybe it is the rigid body. Should i take a physics engine and plug it into my geometry?
Have any of you designed the collision reponse part in a 3D game before?


Yup I certainly have, I'm a proffesional games programmer and I specialise in systems such as collision detecton and response, vehicle dynamics, ragdoll, etc. Anyways now that I know that you're talking about colliding a player controlled character this makes the situation a lot different. Rigidbody collision response is definately the way to go for objects such as furniture and vehicles but you'll find using this for a player character will just create a very fustrating user experience. For these situations you'll want to go more with a sliding type collision response.

This can actualy be very simple to implement in your typical 1st/3rd person game environments since the scenery polygons tend to be fairly large. Basicaly you need to calculate the amount by which the character penetrates the scenery in the direction of the normal of the triangle the character intersects with. Then simply translate the character that distance in the direction of the tri normal so penetration no longer occurs. This will allow the player to slide along walls without penetration and without hinderance to his movement along the wall.

For higher resolution environments or scenery with very sharp concave corners you might need a more sophisticated approach however since it might be possible for the character to cross many triangles in one frame or get stuck in an infinite collision loop between facing triangles. In this case I'd recommend using predictive collision routines and only move the character up to the time of the first collision. At this point it will be a matter of trying different approaches to see what works best for your game. You could just leave it here but that would lead to your character seeming to get stuck. You could try pushing the character out along the collision normal slightly, or maybe even canceling out his movement velocity in the collision normal direction and continue to update his motion over the rest of the frame with his new velocity.

Share this post


Link to post
Share on other sites
Quote:

Basicaly you need to calculate the amount by which the character penetrates the scenery in the direction of the normal of the triangle the character intersects with. Then simply translate the character that distance in the direction of the tri normal so penetration no longer occurs.


Now, how you do this, like calculate the distance of pentration(using the plane?)? Would i just use the point which overlaps the trangle, and what about when both trangles intersect each other as opposed to one piercing the other?

Quote:

Yup I certainly have, I'm a proffesional games programmer and I specialise in systems such as collision detecton and response, vehicle dynamics, ragdoll, etc. Anyways now that I know that you're talking about colliding a player controlled character this makes the situation a lot different. Rigidbody collision response is definately the way to go for objects such as furniture and vehicles but you'll find using this for a player character will just create a very fustrating user experience. For these situations you'll want to go more with a sliding type collision response.


This probaly a very trivial task for you, isn't it.

I Bob Janova gave me some information, but i couldn't get it to work: http://www.gamedev.net/community/forums/topic.asp?topic_id=396096

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
Now, how you do this, like calculate the distance of pentration(using the plane?)? Would i just use the point which overlaps the trangle, and what about when both trangles intersect each other as opposed to one piercing the other?


Again it really depends the specifics of your environment and the type of game experience you're trying to create. However for typical situations where you're dealing with terrain whos features and curvature are generaly much larger than the triangles that make them up then its usualy sufficient just to treat the intersecting terrain tri as a plane. Simply calculate the depth of each penetrating point of the body below this plane and use the largest distance to push the body out along the plane normal. If you start faffing around with detecting tri edge collisions and the like you'll end up with situations where objects cant slide smoothly across flat expanses made up of many triagles without difficulties. Maybe if you posted a screen shot of your character and terrain it would give me a better idea on what to suggest.

Share this post


Link to post
Share on other sites
Quote:
Maybe if you posted a screen shot of your character and terrain it would give me a better idea on what to suggest.


Will do... it might just clear a lot up.



ignore the white boxes, yeah, i'm planning on textureing it, but not till i got collision down.

Share this post


Link to post
Share on other sites
Looks good. Rightio for this kind of thing I think you're going about this the wrong way. You'll no doubt find it sufficient to simply treat the characters collision geometry as an OBB which encompases him and collide this with the scenery rather than trying to collide his tri's. Simply treating the intersecting tri's as planes will give you the desired sliding along and around walls behaviour for the most part without catching on tri edges. The only problem you'll get is when walking directly at a sharp convex corner which will cause the character to suddenly pop slightly to the left or right when you connect with it. You could probably detect these circumstances though because non of the OBB verts will be on the penetrating half of either of the planes belonging to the tris which intersect the box and project into the triangle face at the same time. In this case treat the collision resolution differently by seperating using the tri's penetration depth into the box along the box axes.

Its getting on a bit over in the uk now though and I'm getting tired so you might want to think that through for yourself to make sure it'll work ^^

[edit:] .... urggh definately getting tired. If your characters box always has its y axis pointing directly up then you'll be able to detect these special corner cases because one of the tri verts will project inside the rectacle that the OBB projects onto the x-z plane. That would be easier to calculate

Share this post


Link to post
Share on other sites
oh, cool, thanx, i think i will use the OBBs, i gave up the AABB cause it was annoying.

Yeah, the corner case be some what hairy, but if i treat the box as always point up y(no regression then) as you said, then it should just be a matter of linear algebra for most of it. Also there'll be a lot done on the x-z plane, so it'd be easy to tell if a point was inside a square or tri.

The only thing, is what should i do when he walks up a slope? (should of done 1st person)


I probably should delve more into the OBBs.

EDIT: What about walking up stairs, any suggestions?

[Edited by - TheC00L1 on June 8, 2006 6:16:19 PM]

Share this post


Link to post
Share on other sites
Sorry for the late reply, needed some sleep ;D. Slopes shouldn't cause you any problems since in reality a person will always try to remain vertical rather than leaning back when they walk up hill. Just keep his y vector pointing up. The only trouble you might get is that if you use the same collision for the floor as you do the rest of the terrain the character might appear to float slightly on a slope since it'll be the leading edge of his box which makes contact with the floor where as his feet are likely to be placed more on the center line. Its quite normal to treat the floor collisions seperately for character collision systems by flagging floor tri's and other tri's seperately. The collision box would only collide with the other tri's and to get the characters hight you can shoot a ray directly down from his central point until you hit a floor tri and use this ray length to determine the correct hight so his feet just touch the floor.

As far as stairs go you'll be wanting two seperate terrain meshes. The render mesh which will include all the details such as modelled stairs and all the extra polygons needed to create material swaps and decals etc. Then you'll want a seperate collision mesh which is just a very simplified version of the render mesh. In the collision mesh it becomes very easy to solve the stairs problem by simply making them slopes instead ^_^

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
the character might appear to float slightly on a slope since it'll be the leading edge of his box which makes contact with the floor where as his feet are likely to be placed more on the center line.


Your character is using a bounding box?
Why not use a bounding ellipsoid or sphere? thats pretty much 'standard' with most 3d fps games.
It's also easier to collision check a bounding ellipsoid than it is a box, you do a radius check rather than 6 polygon checks.

Share this post


Link to post
Share on other sites
I dont think a sphere would work very well since its a very bad representation of the human shape. This will become especially apparent when two characters collide with each other. Ellipsoids could work very well though from the sounds of it. In fact I just quick scan through some articles on the subject and this looks very promising:

http://www.gamedev.net/reference/articles/article1026.asp

Seems they've come up with nice elegant way of dealing with the whole corner problem verses edge collision on a plane problem. I'm not entirely convinced all the extra work and calculations are fully justified though since with all the extra resolution being added to environments due to advancements in graphics capabilities, collision systems have a hard time using these same meshes and keeping up. Therefore its quite common to have simplified collision meshes and its possible to sort out most of your problems here, things like taking out door frames and replacing stairs for slopes etc.

Give it a go and see it if it works for you, if not try something else. Thats the best advice I can give ^_^



PS: Even ellipses will still give you the 'standing on tip-toes' look on a slope I imagine haphazard. I still recommend shooting rays for determining character height.

[Edited by - Motorherp on June 9, 2006 12:04:00 PM]

Share this post


Link to post
Share on other sites
The only problem is he'll be hovering above the ground, noticably, which with an OBB he'll be more fixed to the ground, and most likely won't be hovering.

But it seems that the ellipsiod is better for collisions, would it be better to have the ellipsiod, cut off at the feet?

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
The only problem is he'll be hovering above the ground, noticably, which with an OBB he'll be more fixed to the ground, and most likely won't be hovering.

But it seems that the ellipsiod is better for collisions, would it be better to have the ellipsiod, cut off at the feet?
In my experience at least an ellipsoid is a good choice for this kind of motion. To keep his feet on the ground, just size the ellipsoid so that its bottom corresponds with floor level. This might result though in some small part of the model being outside the ellipsoid (which may or may not be a problem for you).

There's a good article by Kasper Fauerby on swept ellipsoid collision detection and response, with code, that covers this. The only problem is (and apologies to Kasper if I'm misrepresenting here), the algorithm that the article proposes requires some tweaking and additions to give acceptable real-world results. I can elaborate on that if needed.

Another possibly useful bit of info is that most FPSs of the Quake era and on use AABBs for object representation. This does result in objects having different 'profiles' depending on what direction they're moving, but anyone who's played these games can attest that this is hardly noticable. The big advantage here (and this holds for ellipsoids in this context as well) is that unlike OBBs, AABBs are invariant under rotation of the object. This means that if you're standing next to an obstacle, you can rotate the object freely without worrying about collision response.

My advice would be to go with an AABB and/or an ellipsoid.

Share this post


Link to post
Share on other sites
Hmmm... AABB seems tempting, i think i'll try the ellipsiod, since it seems better for stairs, if i don't like it, i'll go to the OBB, AABB seems to be bad if the player walks the character into a wall, and sees the the open space difference.

And that sphere tutorial thing, is pretty sw33t!!! :)

Thanx for all your help and info!

Any suggestions and/or advice would be greatly appreciated.

[Edited by - TheC00L1 on June 10, 2006 1:36:28 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by TheC00L1
Hmmm... AABB seems tempting, i think i'll try the ellipsiod, since it seems better for stairs, if i don't like it, i'll go to the OBB, AABB seems to be bad if the player walks the character into a wall, and sees the the open space difference.
Here are just a couple more thoughts to consider. Imagine your player is represented by an OBB, and is standing flush against a wall (so that one side of the OBB is more or less flat against the wall). If the player turns (yaw), the OBB will penetrate the wall, and you now have a discrete intersection to resolve. If you, say, push the player out from the wall, then you've got a situation where simply rotating the player may also move him or her, which is generally not what's expected. I've never actually tried using OBBs for this so I can't speak from experience, but I think the preceeding example may be a good reason to use a rotationally invariant bounding volume such as an ellipsoid or AABB instead. (Note that although an ellipsoid is not by definition rotationally invariant, it can be considered so in the given context.)

As for the 'open space difference' that you mention, I'm pretty sure AABBs were used in all the Quake games for player collisions, and I think you'll agree that this was not a noticable problem in those games. I highly doubt the player will notice (but if you're concerned about it, you can use an ellipsoid instead).

Note also that you don't have to use the same volume for all tests. For example, you could use an ellipsoid for player-world interaction, a cylinder for player-projectile interaction (for a tighter fit), and an AABB for inter-object interaction (to avoid having to deal with ellipsoid-ellipsoid tests).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Note also that you don't have to use the same volume for all tests. For example, you could use an ellipsoid for player-world interaction, a cylinder for player-projectile interaction (for a tighter fit), and an AABB for inter-object interaction (to avoid having to deal with ellipsoid-ellipsoid tests).


Yeah, that's a good idea.


And yeah, i was thinking of the OBB rotatng and pushing the player out, but i seen this in many games, but mostly unprofessional ones though.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this