#### Archived

This topic is now archived and is closed to further replies.

# Collision Detection Algorithm

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

## Recommended Posts

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.

##### Share on other sites
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."

##### Share on other sites
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]

##### Share on other sites
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,E

you check

A with B
A with C
A with D
A with E

B with C
B with D
B with E

C with D
C with E

D with E

So 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.

##### Share on other sites
You missed the entire fact that you ONLY use the collision which happens first ... You have a list of moving objects

Double 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 * numEvents

which 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 ?

##### Share on other sites
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]

##### Share on other sites
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).

##### Share on other sites
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]

##### Share on other sites
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]

##### Share on other sites
having just been through all this.. heres what i learnt.

1 - priority queues are your friend

ok, 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 time

otherwise youll do what we did, and thats spend 3 months running around in circles with our heads hurting.

3 - close enough is good enough

your 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 gritty

heres roughly what needs to be done, implementation up to you we dont want to take out the fun bits.

things to do first

1- 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 dirty

we'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 wacky

4 - 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]

##### Share on other sites
About the swept volumes and interection...

I was just thinking I could come up with a set of parametric equations to describe the movement of the centers of the two objects with respect to time. Thus, I could solve the equations for a time when the distance between the centers became equal to the sum of the largest radii of the objects (basically when the two bounding spheres touch). I think this would allow me to easily incorporate accleration into the calculations (I don't know about jerk; I don't want to worry about that right now).

If I'm not mistaken, this seems like a good approach that would provide a smaller window of time for the possible collision.

[edited by - EvilProgrammer on December 17, 2003 7:04:55 PM]

##### Share on other sites
about the equations for two moving spheres....

struct CSphere
{
Vector Pos;
Vector Dir;
}
detecting a collision between two moving spheres S1 and S2 is equivalent to...

detecting collision with a moving sphere S1''(S1.Pos - S2.Pos, S1.Dir - S2.Dir, S1.Radius) and a static sphere S2''(Vector(0, 0, 0), Vector(0, 0, 0), S2.Radius)....

which is equivalent to detecting collision with a ray Ray(S1.Pos - S2.Pos, S1.Dir - S2.Dir) and a static sphere(Vector(0, 0, 0), Vector(0, 0, 0), S1.Radius + S2.Radius)

so you can simplify the test with a ray vs a sphere

equation of a ray

P = O + D.t eq(1)

equation of a sphere surface

(P - C)2 = r2 eq(2)

replace P in second equation and you have

((O - C) + D.t)2 = r2

develop and find the roots for t

if using a acceleration

P = O + D.t + 0.5 * A.t2 eq(3)

then you develop eq(3) into the eq(2), but that would give you a 4th order equation to solve. nasty. You can try anyway.

Algoithms using swept spheres consider the path of the sphere to be linear thoughout the timestep, thus all you have to solve is a second order equation (eq(1) substituted into eq(2)). The accuracy is good enough for games. in fact, it shoudl be more than enough.

Ok, thanks.

##### Share on other sites
oliii, could you please explain what O, D.t, C and r are?
I am a maths semi-literate.

Thanks,
Steele.

##### Share on other sites
"P = O + D.t"

P is on the ray (O, D) if it satisfy this equation,

and O is a point on the ray, D is the direction of the ray.

For example you can make a ''ray'' using two points in space (a segment S[S0, S1]). O = S0, D = (S1 - S0).

so P is on the segment [S0, S1] if

P = S0 + (S1 - S0)*t, and 0 <= t <= 1.

for a sphere, a point P is on the surface of the sphere if it satisfies the equation

(P - C)2 = r2

C is centre of the sphere, r is the radius of the sphere.

so to find the point of intersection between a segment [S0, S1] and a sphere (C, r), you solve the system of equations for t (the unknown).

P = S0 + (S1 - S0) . t
(P - C)2 = r2

=> ((S0 - C) + (S1-S0).t)2 - r2 = 0

second order equation in the form

a.t2 + b.t + c = 0

withoug going into details, (develop the equation yourself, it''s not hard)

a = (S1 - S0)2 = (S1 - S0) * (S1 - S0); // dot product
b = 2.0f * (S1 - S0) * (S0 - C)
c = (S0 - C)2 - r2

solving the usual way, ....

d = b2 - 4*a*c;

if (d < 0.0f) return false; // infinite line does not intersects the sphere

t0 = (-b - sqrt(d)) / (2.0f * a); // the solutions, where
t1 = (-b + sqrt(d)) / (2.0f * a); // the infinte line intersects the sphere

if (t0 > t1) swap(t0, t1); // order the roots

if (t1 < 0.0f || t0 > 1.0f) return false; // make sure the segment intersects the sphere, not just the infinite line.

if (t0 < 0.0f) t0 = 0.0f; // clip the intersections to the
if (t1 > 1.0f) t1 = 1.0f; // extremities of the segment

then to find the points that intersects the sphere, you simply plug t0 and t1 back into the first equation

P0 = S0 + (S1 - S0) * t0
P1 = S0 + (S1 - S0) * t1

so there, you found the points of intersection between a segment and a sphere. If the segment is inside the sphere, then P0 = S0, P1 = S1.

you do a similar thing for ray against cylinders, using the equation of the surface of an infinite cylinder.

((P - C) x L)2 = r2

C is a point on the cylinder core, L is the direction of the cylinder, r is the radius. ''x'' denotes a cross product.

.... and so one for implicit surfaces, or whatever you can parametrise.

##### Share on other sites
@oiii:
You can also include accelerations in swept spheres by increasing the radius with time. It would be a bit long to discuss here but this warrants conservative and continuous (in time) detection of potential collisions.

- solves "your cheats" and prevents algo bugs and side effects.
- it''s computationally optimal. (never compute unecessary stuff)
- not harder to implement

For that I use :

- multiple levels of refinement (as you said)
- full conservatism for paths and volumes (beware about swept spheres, include acceleration, and higher order derivatives)
- intervals of time instead of instants. It''s not a typical priority list.

A subtelty I did not mention. You have two potential events not totally sorted. One happens a priori before but it''s not certain.
Pass 1, BSpheres of swept spheres + Quadtree
Pass 2, after all the swept spheres have been tested.
------AB------
--------CD--------

AB and CD are two potential events with tmin and tmax boundaries.

Pass 3, each PE is processed in order.
if( AB.texact > CD.tmin )
compute(CD.texact); // detail : also mark as computed
if( AB.texact < CD.texact )
swap AB and CD in the list.

If you understood me well you should see that physics integration is done only when :
- a texact and a percussion is computed.
- a body reaches the end of the frame (tend)

##### Share on other sites
a first line of defense against collision detection ive implemented yesterday and which im very happy about is the following: sweep and prune.

basicly for each AABB you calculate the mininmum and maximum coordinates with regards to its speed, a trivial task. then you sort the boxes along one axis on their minimum coordinate with a simple bubble sort, which doesnt cost any time at all due to high frame coherance. then you can traverse this list, check for overlapping intervals along all 2 or 3 axis, and youll only test between the objects that are close to eachother, without atually doing the nasty O(n^2) comparison between all objects.

this appears to work like a charm for me. currently 1000 objects take less than 1 ms to do all this for. it should be noted though that its speed is dependant of the volume the object reside in. if they are very close together it will still be O(n^2), but expected is O(n), with low constants i might add.

what im planning on adding to this is first refining the collisions found this way with a swept sphere test. the objects will be constructed of multiple convex hulls bounded by boundingspheres, so when two outer boundingspheres overlap, im going to use a numerical rootfinder (they rotate so it cant be solved analiticly) to find in what timeinterval the boundingspheres of the convex hulls overlap.

then in this timeinterval im going to do a binary timesearch between the convex hulls, which will be very low poly because its 2D. i guess its going to be pretty fast, i hope to be able to have a universe of about 1000 objects in 5ms at most on a decent computer. later on i hope to add stacking and friction, but ill see how far ill come.

##### Share on other sites
yeah, I''ve used 2-dimensional sweep and prune. It''s all list management. But objects have to be scattered well, and of decent size (there is no advantage adding a terrain or a large model to a sweep and prune algo, for example). It''s not very good for ray-tracing queries though, but for object/object collisions, it''s solid, and simple to implement. You can even benefit a lot from just one list, which is simpler than having two lists.

##### Share on other sites
quote:

You can even benefit a lot from just one list, which is simpler than having two lists.

yeah, i currently do that. not because its simpler, but because im affraid of introducing another O(n^2) factor in doing so. when i detect overlaps in both lists, ill have to crosscheck all the overlaps and cull out all that dont occur on both axes, whereas now i just add another ''if these aabbs also overlap on the other axis'', and im done. it seems faster to me than having two lists and crosscheck their results... but maybe i didnt correctly understand the algorithm as it was intended.

for side/vertical scolling games things get even better. sorting along the other axis would be a complete waste of time there.

##### Share on other sites
totally

I did my 2D sweep and prune, by compacting indices of pairs of overlapping objects into one unsigned int, and sorting and storing the pair of index in another list.

you do that on both lists, then you do an ''intersection'' between the two list of pairs of indices, and there you go. So another pair of sorted list to store.

##### Share on other sites
I''ve written triangle-triangle collision that does not work on intersections; it finds the exact distance between two triangles along the movement direction and handles the collision correctly (including "sliding" collision). I''m working on writing an article/tutorial on it but for now you can try to make sense of the source code posted here. The algorithm for calculating the bounced vector (the new movement direction after you hit something) isn''t totally perfect, but otherwise it should work without a problem.

~CGameProgrammer( );

##### Share on other sites
Im a little curious about some of the ideas presented here. Mainly the one where you (1) find all collisions, storing them in a list sorted by time of collision (2) do physics, apply forces on the first collision in the list (3) move all objects to the point in time where the first collision occurred (4) goto 2 until the list is exhausted.

Would this scheme work when a collision is a constant one? Like when a ball is resting on top a plane, and gravity is constantly pulling the ball directly down on the plane. It seems like in step 2 when you apply forces, nothing would happen with this collision and it would still collide instantly. Wouldn''t that mean it would still be the first in the list, and the loop would just stay there forever?

- Jeremiah

inlovewithGod.com

##### Share on other sites
Right sliding is not required, I can rely on impulse only in the particular game I have in mind and the test I already made (many balls on a planar surface (2D)). However, I would consider constrainted physics differently. Within certain conditions, I would add temporary constraints. For instance a planar constraint for sliding. I already explained the scheme in details in another thread at GD. But it''s true that I still have not tested it in real life. It may be full of subtelties to handle. Also something most probably required is cinetical energy must decrease, this avoids decor traversal instead of movement decrease then rest (you infinite loop remark).

##### Share on other sites
Im sorry, but I dont understand what you''re trying to say. Could you elaborate on your method and how it fixes the inifinite "resting object" loop? Thanks.

- Jeremiah

inlovewithGod.com

##### Share on other sites
Well, one thing you could do is only apply the force of gravity once, at the beginning of the frame. Then you only get one collision, handle it, and after that you''re fine.

Another approach is to have a flag for each object that tells if the object is at rest. If an object is at rest, it is sitting on something and the force of gravity is assumed to be instantaneously counteracted by that something. So when the object''s at rest, you don''t apply gravity to it and wait until someother object applies a force and gets it moving again.

• ### Forum Statistics

• Total Topics
628714
• Total Posts
2984350

• 23
• 11
• 10
• 13
• 14