Jump to content
  • Advertisement
Sign in to follow this  
Hannesnisula

collision detection with world

This topic is 3475 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Then I've got to check through the whole vertexbuffer for the worldmesh and save all those which are close in another buffer and then do collision detection, right? That must require a lot of computerpower, no? Is that the fastest way to do it?

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
Nope, you set a maximum depth of the quadtree/maximum number of triangles each node can contain. You have to play with these values to find out what works best for performance.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!