Coarse Collision Detection in highly dynamic environment

Millianz
  • Coarse Collision Detection in highly dynamic environment Millianz

    I'm currently working a 3D space game with A LOT of dynamic objects that are all moving (there is pretty much no static environment). I have the collision detection and resolution working just fine, but I am now trying to optimize the collision detection (which is currently O(N2) -- linear search). I thought about multiple options, a bounding volume hierarchy, a Binary Spatial Partitioning tree, an Octree or a Grid. I however need some help with deciding what's best for my situation. A grid seems unfeasible simply due to the space requirements and cache coherence problems.

    Since everything is so dynamic however, it seems to be that trees aren't ideal either, since they would have to be completely rebuilt every frame. I must admit I never implemented a physics engine that required spatial partitioning, do I indeed need to rebuild the tree every frame (assuming that everything is constantly moving) or can I update the trees after integrating?

    Advice is much appreciated - to give some more background: You're flying a space ship in an asteroid field, and there are lots and lots of asteroids and some enemy ships, all of which shoot bullets.

    EDIT: I came across the "Sweep an Prune" algorithm, which seems like the right thing for my purposes. It appears like the right mixture of fast building of the data structures involved and detailed enough partitioning. This is the best resource I can find.

    If anyone has any suggestions whether or not I'm going in the right direction, please let me know.

  • I unfortunatelly now don't have time to read about that SAP algorithm, but what I have read few months ago (but I don't know, if it's suitable for your problem, it's much more suitable for points - not objects):

    You can use some special case of kd-Tree - for example octree - which uses half partitioning in each axis (in article I have read, they were using quarter partitioning - each axis is split to 4 peaces). You use dynamic version of it.

    First you build your structure at the beginning. This means, you split space into kd-Tree. Leaf of tree should have some limited number of objects (for our example let's take 64). Each node knows of course how many objects is in it.

    When you update positions of objects, you transfer them also in structures nodes. After that, you update whole structure according to these rules:

    1) When inner node has less then limited number of points (sum of its leafs is less then 64), then you merge leafs and inner node becomes leaf.

    2) When some leaf has more then 64 objects, you split this node.

    If you want, I can try to find that article - when I will have some time.

  • I don't have enough experience with Sweep-and-Prune to know whether it's a good fit as the highest-level broad-phase algorithm, so I can't comment on that.

    You may want to take a look at loose octrees, which are a variation of octrees that are designed for frequent alteration. I'm not sure what the best reference would be, however; I have often heard that loose octrees with k = 2 work pretty well, but I don't have an online source handy.

  • I'd take a look at dynamic icoseptrees.

    1 ) Icoseptrees overall fares very well for large spaces due to its sparse nature. The memory requirements of the tree is directly proportional to the number of objects in the scene.

    2 ) You can use it for rendering as well ( in fact, that is the primary application of Icoseptrees ).

    3 ) Icoseptrees can deffer optimization of the tree while providing no false negatives.

    4 ) Terrific worst case performance.

    Icoseptrees loose vs pre processed octrees of static objects, but this is obviously no con for your use case.

Tags
c++ collision-detection physics optimization
Related questions and answers
  • don't want to find out in the end that I have to rewrite everything again, as a lot of other objects will be working with these data. Sorry if it's a too subjective matter, but I need some insight. I'm...well... I'm building the animation system of my game engine (the skeletal and skinned animation stuff), and I came to a point where I added so much functionality in the frame and node structures that it seems to be excessive for some applications, and it ends up adding too much complexity when working with simpler objects. Objects like boxes or simple meshes that are meant to be static objects

  • and traveling throug it. This is due to some odd reason for the "numb_collisions", which is used to count how many collisions have occured since initial collision (if it's 0 it means it IS the initial... every 3 or 4 X's down in the wall... I hope this is enough explination, Thanks for any Help, and LOOK AT PREVIOUS POST ABOUT COLLISION DETECTION FOR MORE SPECIFIC FUNCTION PROBLEMS otherwise, heres...Alright so i'm making a vertical side scroller where you are an '8' character traveling downward while avoiding my randomly generated walls (the "generation" function) on the left and right sides

  • loading, etcetera. I am also using OpenGL via the FreeGLUT library in conjunction with SDL to display graphics. My method of collision detection is AABB (Axis-Aligned Bounding Box), which is really all I need to start with. What I need is an easy way to both detect which side the collision occurred on and handle the collisions properly. So, basically, if the player collides with the top... want to learn on my own) or the something like the SAT (Separating Axis Theorem) if at all possible. Thank you in advance for your help! void world1Level1CollisionDetection() { for(int i; i < blocks

  • I been working in the animation of a 2D platformer game in C++/SDL/OpenGL, and my team and I reach the point where we need to establish that every animation of the player (Walking, Running, etc..) needs a different framerate for our concept, but I use as a guideline the Game Programming All In One as a example for the smooth animation, and in the book recommend have variables that limits...; maxFrames) { animationAlreadyEnd = true; currentFrame = returnFrame; } } return currentFrame; } I got working all that and everything executes apparently fine, but in some

  • to worry about this since it isn't an issue there. Moving to C++, this has become a fairly major problem and made me think I may have designed things incorrectly. I can't really imagine how to decouple... related to the graphics library I'm using, but is more of a conceptual thing. In C#, I coupled graphics in with alot of my classes which i know is a terrible idea. Wanting to do it decoupled... question about it is, is this a worthwhile approach at all? If it's a bad design I want to know now before I invest too much more time making all the screens I'm going to need. How do you build up

  • Collision Resolution ultifinitus

    Hey all, I'm making a simple side-scrolling game, and I would appreciate some input! My collision detection system is a simple bounding box detection, so it's really easy to implement. However my collision resolution is ridiculous! Currently I have a little formula like this: if (colliding(firstObject,secondObject)) firstObject.resolve_collision(yAxisOffset); if (colliding(firstObject... xAxisOffset as well. Now this is working great, in general. However there is a single problem. When I have a stack of objects and I push the first object against that stack, the first object get's "stuck

  • version of both. This is so the permanent ones can just be loaded in and are always drawn, and the temporary ones only get drawn for a frame. This way I can create moving lines for debugging, like... it has exposed a basic gap in my knowledge about what some of these lines of code do. should I just populate one big list from all the vectors and push that through? some need to be drawn with different passes, and some don't need to be changed each frame. for example, the permanent ones can just stay on the gpu. right?

  • second and 75 frame draws per second. Up until now, it is in the physics update routine that I do the collision detection and response. Your ship can collide with a rock. Your photons (bullets) can... the objects at a fraction of the distance between their previous and current value positions and rotations. That is yet to be done. Question: Will I also have to do move my collision detection code...Questions: When we draw with interpolation, where should the collision detection code be? Is it worth implementing interpolation in the following situation? This is for Scrolling Asteroids. I have

  • I'm working on a Component/Entity-System based game engine atm. And I have this little dilemma. I have simple geometrical structures which might be downloaded or created in game at some point. These structures are used to create models that are used in OpenGL and OpenGL ES and then for some collision processing. During dev and Beta I am quite ok with maintaining data copies for the physics and the display. But I started thinking about the future of this engine as I already invested some spare time over a year and a half in it. Now I would like to duplicate a few routines into OpenCL kernels

Data information