Sign in to follow this  
nini

Efficient Collision with a world mesh

Recommended Posts

nini    151
hi all, i render a world mesh created with 3d studio, the mesh is optimized and so the tesselation is not the same over the world... the rendering part is ok , now i'm thinking about collision , how should i do it efficiently ? typically on regular grid system there is no problem the quadtree culling is good enough and we only have to determine in wich face we are... but it is different here because of the varying tesselation...i've thinked to do this : Loop through the faces of the world mesh do a Ray/Face Plane intersection (Ray emanating from the player position but in a high altitude) if intersection is found then break the loop and we know in wich face we are... tell me what you think about it , am i wrong with the method , is there a better method to do this ? i want the world to be modelled in a 3D modeler (eg not a heightfield) thanx for any help.

Share this post


Link to post
Share on other sites
mrbig    100
Sounds good to me.
Number of potential faces should of course be limited by spatial subdivision, e.g. octrees, BSP.
You might find the following link useful:
http://www.flipcode.com/articles/article_basiccollisions.shtml

Share this post


Link to post
Share on other sites
mrbig    100
I don't know.
I think that's the standard way of doing it.
You should read this: http://www.gamedev.net/reference/articles/article1026.asp
It's a bit more advanced, but it's pretty much all you'll need for player-world collisions. (Or anything else you'd like to approximate by a sphere or an axis-aligned ellipsoid.)

Share this post


Link to post
Share on other sites
Motorherp    613
You dont want to be looping through your whole tri data for every collision. As soon as your worlds start to get a bit larger and/or you start putting more colliding objects in, this will really begin to slow down. Depending on whether your terrains are mostly in the 2d plane or if they have lots of vertical complexity you might want to try quad trees or octrees respectively. The trick is to run a pre-processing step during your level initialisation that builds up the tree where its needed most. I'll explain how to build the tree using quad trees as an example.

What you want to do is set a tri threshold beyond which you deam brute force testing to be too costly, and also a maximum tree depth. These values can be tweaked per level since these can have a large effect on performance. Each tree node should have at least an OBB(or AABB) which represents its size and location, pointers to its children nodes, and a list of tri's it contains (you might want to add other stuff later so keep it flexible). You then start off by building a cube which encompasses all your world tris, this becomes your tree's top node who's tri list will contain everything. You then run a recursive algorithm along the following lines to build the rest of the tree, starting with the top node you just created.

If the number of tris in the tri list is greater than your tri threshold then create 4 children nodes for this node which you add to its children pointer list. Each child nodes' OBB should represent one corner each of the parent node's OBB. Then for each child node intersect its OBB with the tris in the tri list of the parent node. Any that intersect, add them to its tri list. Keep repeating these steps for each node untill either every nodes' tri list is below the tri threshold or has reached the maximum allowed tree depth.

Each game object should then keep track of which tree node fully contains it at any one time, and when you want to collide it with the terrain you only need to test the tris in that node's tri list. You can speed up the object-node tracking for moving objects by taking advantage of the fact that they wont be moving far and will be moving in only one direction in that frame. To do this each node should probably store a list of all its neighbour nodes too so you can walk the tree sideways as well as up and down. This saves you from having to recursively collide against the whole tree from the top node down each time an object moves.

One last thing to be aware of when colliding against tri lists is that if you stop as soon as you detect your first collision you might end up with object being able to tunnel through narrow pieces of scenery. This is because your object could actualy be penetrating a tri on the far edge as well as the near edge and it just happens that you detect this one first. To help prevent this you can add in an extra rule for a valid tri which is to see if the objects velocity vector and the tri norm are pointing in opposite directions first (ie: their dot product is negative).

Hope this helps

PS: I should also mentio that this kind of tree structure can lead to problems at the intersections of nodes high up the tree. If objects overlap these intersection they will be forced into nodes much larger than they require meaning they have to do many more tri collisions than they need. There's a couple of ways around this but probably the most elegant is to stagger your tree levels thus making a 'loose tree'. After you've got the basic tree working correctly you might want to look into this and make the necessary modifications.

Share this post


Link to post
Share on other sites
Kestrel    158
You could also use a low-resolution mesh for your collision detection. I.e. Use separate meshes for collisions detection and for rendering.
That way your world can be as detailed as you want and not effect the speed of your collision detection system.

Share this post


Link to post
Share on other sites
nini    151
thanx for your feedback , but in order to build octree/quadtree data i must reorganise the faces of the mesh so that they fit in a node or maybe i'm wrong with the concept ?

my mesh is optimized and the faces are very variable in size , they can cover the full world if the land is flat for example...

here is a screen of the wireframe rendered mesh :

Share this post


Link to post
Share on other sites
Motorherp    613
Quote:
Original post by Kestrel
You could also use a low-resolution mesh for your collision detection. I.e. Use separate meshes for collisions detection and for rendering.
That way your world can be as detailed as you want and not effect the speed of your collision detection system.


Sound advice. Having seperate meshes also allows you to solve various game play related issues too, such as replacing stairways for ramps and removing door frames in the collision mesh to allow your character to move around less restricted.

Quote:
Original post by nini
thanx for your feedback , but in order to build octree/quadtree data i must reorganise the faces of the mesh so that they fit in a node or maybe i'm wrong with the concept ?


No you shouldn't have to alter the terrain data at all. The idea is that the tree builds itself to suit the terrain, not the other way around.

Share this post


Link to post
Share on other sites
nini    151
i want to make a car simulation but i want the player to be free in all the world , not constrained to the road , is collision mesh a viable solution , if the terrain is bumpy the collision mesh will be although detailled isn't it ?

Share this post


Link to post
Share on other sites
Motorherp    613
Quote:
Original post by nini
i want to make a car simulation but i want the player to be free in all the world , not constrained to the road , is collision mesh a viable solution , if the terrain is bumpy the collision mesh will be although detailled isn't it ?


Sure it is, this is how we do it on F1 2006 and we have profiled curbs etc so the bumpyness shouldn't cause you problems. Just build up the resolution where its needed most. Admitedly we have the advantage that cars tend to follow a racing line which allows us to make certain optimisations, for example we use a terrain walk instead of spatial subdivisions. In fact for the large type of terrain you're likely talking about you'll find that a seperate collision mesh is probably a must since you'll probably be lodding the render mesh and maybe even adding in procedural detail at the higher resolutions.

PS: A trick you might want to use with the lower detail collision mesh is to add in procedural bump values into your suspension ray casting to emulate a rough terrain without needing too much detail in the mesh itself.

Share this post


Link to post
Share on other sites
nini    151
thanx for your interest motorherp ,
at the moment i don't want to annoy with a lod system , frustum culling + optimized mesh is enough for me...perhaps if i want to save power i will make occlusion meshes to discard what is behind the mountains if the geometry has passed the frustum test...but that's another discussion.

okay so i will try the collision mesh method.


the post is still open , i wait for your feedback...

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