Sign in to follow this  
Hannesnisula

collision detection with world

Recommended Posts

Is there anyone who've done this that could help me? I'm creating my own collision detection and I need to know if there's any faster way, to check for collisions with the world, than checking for collision with the whole world mesh instead of some specific part of the world. If it's possible to select a specific part of the worldmesh, then how do you do that?

Share this post


Link to post
Share on other sites
Divide the world using some space partitioning which suits your type of world (like an octree, quad-tree or uniform grid), then use the structure to cull out all the polygons of the world that aren't anywhere near the candidate.

Share this post


Link to post
Share on other sites
Quadtrees or the like reduce the computer power actually needed. If you looped through every single object on a level for any function, it would take up a lot of processing. By dividing the objects into groups ( quadtrees ) you reduce the amount of objects to loop through.

If you have 1,000 bouncing objects the loop will be time consuming, if you divide the objects up ( 10 quadtrees = stored 100 objects? ) into a group and 4 groups are not even seen to begin with, that is 400 objects you don't even need to bother with checking for visibilty. Therefore it reduces "computer power".

Hope this made sense. :]

Share this post


Link to post
Share on other sites
It made a lot of sense, thanks! But even if I make a hierarchy of the subsets of the world mesh (that's what you meant right?:P) how can I then check the collisions faster? Since the player isn't allowed to go through ANY other object in the world (except players) then I still need to check somehow with all the meshes, no? I'd appreciate it a lot of you could give me a link or something to some tutorial that explains it in detail (or if you'd do it yourself)!

Share this post


Link to post
Share on other sites
Say you only have 4 quads, each consisting of two triangles(upper right, upper left, lower right and lower left) and your character is standing in the lower left corner. Since your "world" is subdivided into 4 "pieces", theres no reason to check him for collisions in the other three "pieces". You essentially just cut your processing time by 75%. Take this same example, but apply it to a "world" with 100's and 1000's of triangles, where each "peice" is subdivided further into 4 more pieces and so on and you will see how this starts to create a huge difference.

This example would be a quadtree. An octree would take the height of the world into account and divide each piece into 8 parts. Start reading up on those.

PS. This also applies to "meshes" or other items beside the "world" that you want to collide with. Only need to test collisions for those immediately around you.

Share this post


Link to post
Share on other sites
That's what I first thought, but then how do I know which quad my player's over? Do I have to go through the list of faces/vertices and then check against just that face? Do I have to do that or is there any faster way? Since I really can't come up with another method >.<

Share this post


Link to post
Share on other sites
Each node of the quadtree has a "bounding box". If your playing is inside of it then you can check to see if there are any child nodes. If there are, then check to see which one the player is in. keep going until you have no more children. Now you have a single node to test collisions against.(10 triangles against 100's for example).

If your player is not inside the node, then you dont bother checking any of the children because there is no way he will be inside of any of them(since the children are contained within the parent). This essentially cut down a whole bunch of geometry.

Share this post


Link to post
Share on other sites
Basically the root node has a width and height equal to the max side(which is just big enough to contain your entire environment) Then each child node is half width and half height of the parent, which turns into 4 nodes for quadtree and 8 for octree and so on

Share this post


Link to post
Share on other sites
Well you wouldn't even need to check if your player is colliding with all of the quad-trees bounding boxes. If your world is broken up into equal segments then the player position in itself will tell you what box it is in.

say if it was 10x10 grid (not taking height into account)
and your world would be say 500, 500.
First your check if the position is greater or lower then it could ever be.

If it's within acceptable bounds say player position 324, 243.

The X position in you 10x10 grid(each bounds 50x50) would be (int)(324/(width of a grid segment) so in this example it'd be (int)(324/50) = 6.48 but cast as an int so 6.
Y position would be the same just use the length instead of the width. (int)(243/50) = 4.86 = 4. Now your position in that grid would be 6,4 (and yes this works as zero indexed).

This could work on any level of the quad tree also. Just the width and length change. Also if it is a 3D area (with multiple making up a cube) then it'd be the same way to check the height.

Share this post


Link to post
Share on other sites
If you use a quadtree for a terrain with height, such as you are describing, it doesn't matter because you create 2d bounding boxes(x and z axis's) and just check ALL geometry in those boxes regardless of height. If you want to further it by height then you use an octree which uses x, y and z axis.

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