   Collision Detection Algorithm
  I''m making a game right now and I''m trying to implement some kind of collision detection system for the objects in my world. I''m a newbie so I have a lot of questions about things there are probably very simple solutions for.  Maybe this is more appropriate for the beginner forum, but I chose to put it here.  If you have a problem with that, I apologize.  I''ve read dozens of online tutorials about collision detection, all dealing with objects intersecting, planes, AABB''s, etc.  However, none of these has given a satisfactory explanation for how to go through all the objects in your world every frame and check for collisions.  What I mean is, suppose you have two moving objects and you want to see if they collide.  Well, you can see if their paths cross, and if they do you can calculate when this happens, but this introduces all kinds of complications (especially since for irregularly shaped objects, finding out when their paths crossed would be a simple matter compared to finding out when they actually collide).  Sure, you can say the movement of all objects each frame is so negligible (unless you have some super fast object) that you don''t really need to check their paths because they won''t move far enough to pass through another object.  But suppose the frame rate suddenly bombed.  You could have two separate results due to a frame rate discrepancy, something I''d like to avoid.Another problem is if you did manage to work out a system that worked, suppose object A collides with object B, bounces off, and crosses the path of object C, which you''ve already moved past the point of possible collision.  My personal solution to this problem would be to construct the algorithm so it finds the time it takes for the first collision to occur and animate the world that much time before moving on to the second soonest collision.  It all sounds good except it seems like it would all be really ugly and require a lot of math in the end.  I''m beginning to think an algorithm that slowly moved all the objects little by little from their initial to their final positions, checking for collisions along the way would be simpler and work faster.So, if someone could clear some of these things up for me tell me how to do this, or point out a really good tutorial, I would be very grateful.  If I said something that was incorrect please correct me.  Thank you. 
  Well, the first thing you want, which you''ve already probably thought about, is some form of partitioning that you can use to do some quick "collision culling." The example I''ll give will assume that you are working with convex sets (most-likely done via a BSP tree), as it makes collision very quick and easy. This will usually bring you down to under 10 planar collision checks (many times almost half of which can be further culled away dependant on the object''s direction of movement), a few lien and point collision checks, as well as possible collisions with other dynamic objects.Depending on what type of collision you are using for your objects, this can actually be very fast.Planar collision checks with spheres (or circles) can be easily culled simply by checking if the object is moving towards or away from the plane, and when they aren''t culled, collision checks can be brought down to simple linear equations.Aside from planar collision, you also have to do sphere/line collision and sphere/point collision for geometry (IE the outer walls of portals between sectors). Again, these are quick calculations and don''t have to be done in every physics loop as they are often culled away.Collision with dynamic objects, again, isn''t necessarily costly, especially if you are working with spheres. The problem can be reduced to a quadratic equation which can be culled away if the objects don''t collide (because the discriminant will be below 0).As you mentioned, multiple collisions within one loop can be costly, but are ultimately necessary, and with proper partitioning and culling, you''ll see that the cost of the checks is still not extreme.What you have to do is cycle through all your dynamic objects and check collision between them and static geometry, as well, check between dynamic objects and othe dynamic objects. Remeber that you only have to check collision between a dynamic object and all of the other dynamic objects AFTER it in the list (as you will have already calculated collision time between it and previous objects in the list in earlier iterations). Whenever you find a collision, store the time of that collision and other collision data (IE the object doing the colliding, and the normal of collision).After you cycle through the objects, pick the collision that happens first, calculate the new data for the object (IE resultant velocit) and then update your objects to the new time. Again, cycle through your objects, etc. until there are no more collisions which happen in the time frame.You might think that''s a lot of calculations, but in actuality, many of those times you will have no collisions, and of those times, it''s rare that you will have multiple collisions within one physics loop. With partitioning and early collision culling, this is still fast.What you do NOT want to do is use the logic "it will rarely happen, so I won''t account for the case." ;  Yep POOP, right there is much to Google about space partition and ColDet bewteen various primitives, and it's complex someties. But to me you don't answer but the most interesting question EP asks. It's about the potentially non bounded complexity of an exact multiple collision detection scheme. Exact means infinitely accurate in both space AND time.You say :"Remember that you only have to check collision between a dynamic object and all of the other dynamic objects AFTER it in the list (as you will have already calculated collision time between it and previous objects in the list in earlier iterations)."Hmm sorry I don't follow you here, what is this list for you ? Imagine the exact output list of events is :B&D, A&C, C&B, C&D&B (& means collision, C,D, and B collide exactly at the same time ... very rare pool like case). After A&C you have to check for A&B and C&B. Maybe B already collided with D during this frame but it can well collide twice or more right ?Your first pass is check every couple of objects, as if they were separate of the rest of the world. You use max velocities and space partition to accelerate. It takes roughly a time linear to the number of objects to compute these events. Well this gives you event A&B occurs first at time t1. But potentially, the states of A and B being changed after the collision, all the following events you have computed before may be invalidated and replaced by others. It may be a snow ball effect  . Remove event A&B and no collision occurs. Keep it and it's possible that all the other objects collide even during a small delta of time. Remember that if A is massive compared to B, B can suddenly get a huge speed and may collision with many objects you haven't even checked before with space partition and volumes bounding the path of B. Suddenly B becomes a candidate for many new possibilities.K now how would you animate N=100000 balls rolling on a small square area ? A huge density. I only consider collisions, and a simplified model with percussions only, no constraints. Is there a good algorithm for that ? I don't think the current physics engines based on time steps and dichotomies would behave well. They would miss most events and become very unstable quickly. What happens if each ball collides during your physics frame ? Will your engine be slowed down by a factor 100000 ? If you don't use space partition then the naive system would give the crazy computation time of k*N3. With the best space partition it would still remain k*N2. Is there a way to reach a computation time of the same order of magnitude as the output, that is the number of events, or at least the number of objects ? Can we reach k*N1 ?I have some ideas in mind but I'd like your opinions first. It's very complex to think of it in general. So let's examine a basic system first. It's clear that if your scene holds 4 objects, A and B in the same sector and another "group", C and D very far away, it should be possible to know quickly that the two groups will never interact during a certain duration. Why ? Intuitively, because there is not enough energy in each group, and the distance between the two groups is too big. So this should give some ideas about the general physical and mathematical model that could solve the issue with a decent algorithm ... [edited by - Charles B on December 16, 2003 4:20:04 AM];quote:Original post by Charles B  Yep POOP, right there is much to Google about space partition and ColDet bewteen various primitives, and it''s complex someties. But to me you don''t answer but the most interesting question EP asks. It''s about the potentially non bounded complexity of an exact multiple collision detection scheme. Exact means infinitely accurate in both space AND time.Actually, I did cover that. I said, "After you cycle through the objects, pick the collision that happens first, calculate the new data for the object (IE resultant velocit) and then update your objects to the new time. Again, cycle through your objects, etc. until there are no more collisions which happen in the time frame."In other words, you cycle through your objects and find the first collision, then you update everything to be at that time, then you have to check all your objects for collision again, and keep repeating the process until there are no more collisions.quote:Original post by Charles B  Hmm sorry I don''t follow you here, what is this list for you ?You have a list of moving objects int this order (here we''ll assume no static level geometry to make it easier to show exactly what I''m talking about):A,B,C,D,Eyou checkA with BA with CA with DA with EB with CB with DB with EC with DC with ED with ESo with each element you are checking one less possible collision because you don''t have to check collision with it and a previous one in the list (as that was already covered in a previous iteration).Every time you find a collision, you store the time and information about the collision (when it happened, the reflection normal, the two objects which collide). The, you only "use" the collision that happened first, you update your data (move all of the objects to the appropriate positions at that time), and then you do all those collision checks again to see if any collisions happen between that time and the remaining portion of time.quote:Original post by Charles B  Imagine the exact output list of events is :B&D, A&C, C&B, C&D&B (& means collision, C,D, and B collide exactly at the same time ... very rare pool like case). After A&C you have to check for A&B and C&B. Maybe B already collided with D during this frame but it can well collide twice or more right ?Your first pass is check every couple of objects, as if they were separate of the rest of the world. You use max velocities and space partition to accelerate. It takes roughly a time linear to the number of objects to compute these events. Well this gives you event A&B occurs first at time t1. But potentially, the states of A and B being changed after the collision, all the following events you have computed before may be invalidated and replaced by others. It may be a snow ball effect    . Remove event A&B and no collision occurs. Keep it and it''s possible that all the other objects collide even during a small delta of time. Remember that if A is massive compared to B, B can suddenly get a huge speed and may collision with many objects you haven''t even checked before with space partition and volumes bounding the path of B. Suddenly B becomes a candidate for many new possibilities.You missed the entire fact that you ONLY use the collision which happens first. You don''t store the collisions and then apply the effects of all of them. You store only the collision which happens FIRST. Then you update everything to be at that point in time (after you adjust the two objects velocities, etc) and then you have to do all of your collision checks again.In the end, you are left with perfect linearly interpolated space-time collision.;You missed the entire fact that you ONLY use the collision which happens first ... You have a list of moving objectsDouble qui-proquo : I thought you mentionned the list of events. And you missed the fact that I clearly mentionned the list of EVENTS not the list of OBJECTS.No I missed nothing at all concerning the classical algo I call worst case N2. Of course you don''t need to process at time t1 the percussions that are not certain to happen at time t2. I simply misunderstood your sentence concerning the term list left alone. Well if it''s the list of objects (input), the number of handshakes stuff, well it''s trivial. And anyway it''s just a *2 speed up. Of course don''t neglect it. If your objects are stored in a Quad Tree, your global list can be totally implicit. That''s why I missed the meaning of your sentence, because I think EP already knows that.Well you explain the common way to solve multiple collisions and the complexity for this solution I call A) is :ColDet * numEventswhich is at least numObjects * numEvents.I was focused on the global algorithm efficiency in the worst case. And I''d like a complexity of say numObjects+numEvents. Thus it''s about the list of events (output).EvilProgrammer said : I''m beginning to think an algorithm that slowly moved all the objects little by little from their initial to their final positions, checking for collisions along the way would be simpler and work faster.Trade accuracy and complications against speed (?) and brute force. Is that your deal EP ? I started to give a possible answer to his concern. But instead of little by little, which I call solution B), I would consider continuous time, solution C). Because little by little you may still have many collision events during the smallest time step thus potential unstable effects. Little by little only may simplify the coding and make the worst cases (many events at the same time) bareable but complexity will still be roughly equivalent to solution A).Comparing B) to A)You exchange numEvents steps (interruptions) against a constant number of subdivisions (say 1000FPS) during the same frame (100FPS). This is potentially more unstable in the worst case. You loose time in the best cases, typically the normal frames where nothing happens but dynamic state updates (Vel+=Acc*dt, etc..).That''s why I''d like to see a C) solution. But I am not sure many are concerned or have already thought this problem in depth :With C) I''d like to take the best of both worlds :A) For it''s timed based approach and stability. But without the update all stuff after each event.B) Only one pass, as if every couple of object could be treated separately. But without the bugs and at a lower FPS.With the minimal complexity : numObjects+ numEvents.Any ideas how to reach that ?;  I find what you two have to say about this rather interesting.  What I want to know now, though, is how you find the exact moment when two objects collide.  Suppose your two objects A and B have velocities (and since we want this to work in all cases, they have accelerations, too).  Now, I know very well how to tell if two objects are colliding at a given time.  My question now is how do you find out what that time is?  That is to say, what is the exact moment (or a moment within some small tolerance) the two objects come into contact?  Again, I've looked through many articles, none of which spend much time discussing this.  EDIT: I finally found a post that deals with this problem, where someone said this: "use a method of stepping that using a delta time. ever frame you check for penetrations. if you find one u divide your delta time by two and see if the objects collide at that time. you do this until u find the exact point in time they collide or until the amount they interpenetrate is within tolerable limits."Some other people posted and said basically the same thing, so I'm guessing this is the accepted solution.  Are there any other easy ways of doing this?   [edited by - EvilProgrammer on December 16, 2003 7:16:09 PM];  they have velocities? well then, use velcocities in the collision calcualtion tests however, this is another order of magnitude more complicated. for spheres, as said above, a quadratic equation solves most of the problems. Solving the system, you use a set of parametric equations (well 2 equations in most cases), and solve it, which should end up with a second order equation to solve. The problem can be broken down to a ray intersection test, so you use a parametric equation of a ray against, say a sphere equation, and solve it to find the time of collision of two spheres colliding. Problems arise when dealing with more complex volumes, like boxes, convex hulls, and such. Spheres are nice and easy.Using the rotational velocity in the test makes things even trickier. Look for Stephane Redon''s continous collision paper. You can also use a binary time search, going back and forth in the time step, and find the time where objects''s closest points distance is within a tolerance. You need an in-and-out detection, for when the objects overlap. The advantage is, you still use the same overlap test, which is easy, and you can use the rotational components, accelerations, ect... if you want. But, it''s costly (you can end up doing the test many times in a timestep). ;quote:Original post by EvilProgrammer   I finally found a post that deals with this problem, where someone said this: "use a method of stepping that using a delta time. ever frame you check for penetrations. if you find one u divide your delta time by two and see if the objects collide at that time. you do this until u find the exact point in time they collide or until the amount they interpenetrate is within tolerable limits."quote:Original post by EvilProgrammer   My question now is how do you find out what that time is?Algebra! You have the average velocity of the object for a period of time and the objects position and you know how to calculate if the edges of the objects touch. So just set up your equations and solve for time. With bounding spheres this results in a quick linear equation for sphere-to-plane collision, and a quadratic equation for sphere to sphere. Since they're so simple it's generally faster to just solve those than to do other approximations.One trade-off you should understand is that in most games (IE Quake, Doom, Unreal), acceleration, jerk, or anything further down the derivation line past velocity is not [diretly] taken into account when performign collision checks. Instead, you use the acceleration and jerk, etc. to calculate the average velocity over that period of time and then base your collisions on that. The reason why you want to do this is because if you try to take into account acceleration or anything further, your calculations have to get much more complex (and you don't exactly want to be solving quartic equations at runtime). At that point you might want to use other forms of approximations, but I still wouldn't recommend the method described earlier.   [edited by - Polymorphic OOP on December 17, 2003 1:29:23 AM];  There is a lot of math involved to solve collision events between two volumes in space and time, but it's well determined problem. Basically any ColDet system relies on a few primitives basically point/point (or sphere/sphere) point/plane, edge,/edge. With Voronoi Diagrams and nearest facets tricks convex/convex becomes point/plane or edge/egde. It's easy to solve these equations at the first degree of approximation or more. You can also use iterative searches based on decreasing time segments, taking relative speeds into account etc... Well but that's not the most interesting to me, you can find a lot of sources on the web.To sum up, it's a given fact that for any couple of solid volumes (any kind of) A and B it's possible to compute the exact contact point at the exact (or nearly exact) collision time in a generally constant time using space/time coherency. For deformable bodies I don't doubt efficient solutions can also be found. (I thought about metaballs approximations ...)But back to my subject, inspired by EvilP's remark :How would one code a ColDet sample involving many balls in a square ? Imagine the projected surface of the spheres covers 25% of the whole surface. If an optimal algorithm can be found for such a case I think physics engine could add new features to games. For instance you launch a rocket in a wall and the bricks explode, collide, etc... And it's not a precomputed animation.Here are the guidelines I would think of :- pass 1 compute all the potential events at a conservative precision level during a frame [tmin,tmax]. For instance check bounding spheres in translation (including max accelerations in the radius) or swept segments algorithms. Temp output is a list of time segments refering to couples of objects. I call it the  potential events (PE) list (PEL). It looks like this :------A/B------  ---------E/K--------    --------C/H------  That's done in linear time N (numObjects). OK ?Then check if event A/B actually occurs (infinite precision). If so recompute the dynamic states for A and B at time t0 (since it's the event number 0, the first after tmin). K that's what POOP mentionned. But then that's where I want to improve things.I don't want to loop again replacing tmin by t0 and launch my routine again. I don't want redundant computations (*). I can use space partition to determine which events can be influenced by the updated A and B objects. First since A and B do not follow the same paths as before t0 I can safely destroy any PE involving A or B. I check for any object in the path of A and B between t0 and tmax. It can be done quickly and locally with a quadtree for instance. Any object has a big sphere that bounds all the positions of the volume between tmin and tmax. Then you check dynamic spheres. That's a second degree equation. OK thus I create a sub list of new PEs involving the new A and B and their neighbourhood. I merge the sublist and the PEL. And I continue till I reach tmax and all the events have been processed. I have not missed a single one.I have what I wanted. It's nearly a constant time, linear to the number of objects with a coefficient k. k is the maximum number of objects that can collide with a single one during a frame. This ties numEvents and numObjects in fact. Intuitively I would say k is max 6 for a planar system of rolling balls. Because at worst each ball has 6 neighbours (hexagonal distribution).Maybe I reinvent the wheel if so tell me. Else it's really something I'd really like to develop in a near future.Next one must consider how this works with network synchronization. But I think dead reckoning, error decay, etc ... should conceptually be seen as a special Force object in a physics engine. So what works in single mode should also work in multiplayer games.(*) For each event solving additionnal 10000 sphere/sphere and a proportion of which as second degree equations takes time.   [edited by - Charles B on December 17, 2003 4:18:21 AM];  having just been through all this.. heres what i learnt.1 -  priority queues are your friendok, the first thing youll need, is somewhere to store your collisions, this is usually a nice prioirty queue indexed by time.2 -  allways, allways move forward in timeotherwise youll do what we did, and thats spend 3 months running around in circles with our heads hurting.3 -  close enough is good enoughyour not working for ferrari's f1 team, or nasa.. it just has to "look" ok.. not be mathmatically correct.. as the old adage goes, if you cant win, cheat like a mofo the nitty grittyheres roughly what needs to be done, implementation up to you  we dont want to take out the fun bits. things to do first1- firstly, pick a primitive that youll use for really-rough-guess collision testing, lets use a sphere, cos they are easy n stuff.2- find in a textbook, a nice quick n dirty swept sphere (capsule) intersection algorithm.(or swept your-favourite-primitive)swept volumes are handy to represent the movement of an object through space over a period of time, and using two of them (well actually just one(relative movement), and a static object) is perhaps the easiest way to test for an intial collision.3- make sure you include with your objects flags to indicate what is handled by your collider, and whats not.. and whats handled by your physics engine, and what isnt.right, armed with this.. heres how you do it the quick n dirtywe'll assume you dont have any space partitioning yet, and we'll assumue that however you do actually end up implementing this will scale to cope with crossing areas of space and what not. im trying to keep this simple ok 1 - collide everything thats collidable, with everything else thats collidable. remeber that testing A -> B is akin to testing B -> A. so you only need to do it once  at this point, we're not interested in resolving collisions, only working out if collisions have occured.we do this, by taking the starting positions of two objects, and a frame time, and feeding it into our swept primitive algorithm. this will indicate a collision. 2 - each collision you encounter, goes into our priority queue for resolution. we do this until we've tested all our objects.its usually a good idea to actually integrate those objects that dont register a collision, but make sure you store both starting and end positions in the case of compounding collisions hitting objects which dont collide in the first pass.3 - for each collision in the list, we go through and resolve it, starting with the earliest collision first.first thing to do, is actually test for a collision at this time (poly on poly usually, or some other advanced method). and during this calculation, generate enough data to apply an impulse (if your doing physics, remeber those object flags?). the trick here is, that in order for the physics to be  right   you need to apply the force at the right point in time. this requries the two objects to be integrated to the time the collision occured. once thats done, we can apply our contact forces to the objects so the next integration will move then off in the correct direction for the correct period of time.it also helps if youve got some way of marking back that this collision actually did result in a collision. itll make notifying  your in game objects after youve resolved your collisions easier remeber to check to see if the objects your colliding have hit soemthing before this collision, and integrate using the correct starting time, otherwise things will be  wacky4 - once we've resolved the collision, and stuck new contact forces on our objects, we need to retest these objects against everything else thats collidable in the scene.but heres the trick. If the start time is TS and the end time is TE, and our collision time is T1, then we need to check our objects in the space of time from T1 to TE. and as most of your objects will still be TS->TE you could run into issues.there are a few tricks to apply here- objects which havent collieded with anything this frame can be assumed to have a constant velocity and simply "fast forwarded" to the correct position using the known collision time.so now, the starting testing position is Pos @ T1 instead of at TS- objects that  have collided, can do the same thing, but youll have to "fast foward" them from the time of the last collision   as its probrable that their velocity has changed.of course this is widely known as  cheating   and may not fit all cases, especially those in which drag and friction are factors in your physical system. if your using drag, or friction, youll just have to bite the bullet and perform some re-integration in your collision testing.5 - continue doing this until youve run out of collisions. at this point, your objects should now be in their final state at  TE (end frame time) with all collisions resolved.the trick now is to go back and notify all your objects that theyve just hit something, and start doing all the game logic involved.you could theoretically stick this in the loop, and do it as part of the resolution, but we deicded that it would be unusual that the user would be able to discern which ones should, or shouldnt matter.anyway, thats how we're doing it (code in progress). hope it works for you  comments welcome too.. although abuse for not discussing space partitioning (which just confuses things at first pass) will be ignored. Matt D   [edited by - Matt_D on December 17, 2003 6:57:18 AM] [edited by - Matt_D on December 17, 2003 6:59:04 AM]