collision detection with world
Author
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?
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.
Author
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?
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. :]
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. :]
Author
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)!
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.
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.
Author
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 >.<
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.
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.
Author
Then I've got to create like hundreds/thousands of boundary boxes for the world?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
