Hi. The best way I know of to prevent tunneling is to use predictive collision routines. For example if your objects were spheres then over the time step the path they sweep out would be capsule shapes. The trick is to do the collision detection using the swept volumes which will let you know if two objects should have collided that frame. Spheres are a simple case since they are rotationaly invarient and things get more complicated for arbitrary meshes. To keep things simple you could wrap your objects with spheres and use the swept sphere test to 'zoom in' on the exact collision time and then use regular collision on time subdivisions around that time to determine when/if they actually collide. This wouldn't be the fastest though. Alternatively you can integrate your object to the end of the time step then create a convex hull around the its start and end positions to get its swept volume. Collision detection is then perfomed on these swept hulls using any of the methods available for convex meshes (eg: seperating planes). Unfortunately this still doesn't account for rotation along that time step and so will break down for long, thin, and faslty spinning objects. However if your time steps are small enough and your objects rotations are capped to within sensible values this method should work fine. I don't know of any predictive methods that take into account the rotation of the objects but I imagine they would be very complex and as far as I'm aware every collision method I've ever come accross just assumes the rotation within each frame to be negligable. Hope this helps

PS: just incase that convex hull thing wasn't too clear this is what i mean:

For abitrarily shaped meshes I'm not aware of an anylitacal method for determining exact collision times/points in this way. What I suggest is to wrap your objects with spheres and do the swept tests with these since it is possible to determine collision times between swept spheres analytically. Once a collision time estimate is found you can then move your objects to this time and perform mesh-mesh collisions in forward time steps to find the exact point in time they touch (or at least to within a given tolerance). To speed this up I'd use seperating axis theorem and cache the seperating plane from time slices were they don't collide. Then in the next time slice check this plane first since it will probably still be the seperating case. To make it even quicker, although less accurate, linearly interpolate the objects positions between time slices rather than firing up your integrator each time.
Are you sure you need to worry about exact collision times and tunneling though. In my experience this only becomes a problem for very small fast objects (eg: bullets), for which case you'll be better of firing rays to determine collisions. Either that or collisions with flat tri meshes (eg: the terrain mesh) but these tend to be static and so aren't as difficult (just one swept volume). Do you mind me asking what it is thats causing your tunneling problems since I might be able to heklp further with more info??

Ok, if you analytically find the collsion time between both objects bounding spheres this is garaunteed to be before the actual collision occurs (actually I think the solution will return two answers, one at first contact and one at last contact, simply take the smaller one). This at leasts gives you a starting point on the right half and close to the actual collision time. If you just step forward from here in small increments then you wont overshoot (adjust the time slices for the best speed / accuracy trade off).
Now for seperating axis theorem. Don't worry too much about its speed, its certainly faster than just intersecting all the tris each time. Heres how its done:

STEP 1
For each tri in turn in mesh A calculate which half of that tris plane each vert in mesh B lies on. If the all lie on the same half then you've found a seperating plane. Cache this plane for later and quite the seperating plane routine. else go to step 2.

STEP 2
Do step 1 but with mesh B's tris against mesh A's verts. If no seperating plane found go to step 3.

STEP 3
Now the difficult and expensive bit but chances are you wont get this far very often. For each edge combination between the two meshes in turn form a vector (which I'll call the cross axis from now on) which is the cross product between the two edges. Then project all the verts from one mesh onto the cross axis forming a range of how far they span it. Then for each vert of the other mesh project it onto the cross axis and check if it lies within the range calculated earlier. If so then this isn't a seperating axis so drop out and go to the next edge combination. If non of the projected verts lie in the range then this is a seperating plane. If no seperating planes are found after all this then the objects are intersecting.

Sorry if the explanation isn't too clear but google it and you'll no doubt find plenty of hits. The beauty of this method is that with a seperating plane cached this can be checked first in the next time slice which is very fast. if its still valid then move to the next time slice. This way you should be able to rapidly converge on an intersection time. Just one thing though, this method wont give you intersecting points. When you've found your intersection time you'll have to use another method to get those.

This will all give you very accurate collision but this may not always be needed. Have you considered representing your objects with hierarchies of bounding volumes like spheres and boxes. Collision checks between these types of objects are MUCH faster than arbitrary meshes. Also for missiles I'd either use ray collision or represent the path of the missile each frame as a capsule (swept sphere) and use that alone to determine collisions. I don't think theres much point colliding with the missile mesh and it'll much faster and I don't think the decrease in accuracy will be that noticable for these small objects. Just think of the huge swarms of missles you'll be able to handle :)

PS: Just occured to me I didn't explain why I say you should step forward linearly rather than use binary subdivision with this method and its quite important so I'll explain now. Firstly by stepping forward linearly you get the most benefit from your cached seperating planes. But more importantly by stepping forward linearly you will only reach the situation where the seperating axis algorithm returns intersecting once, whereas jumping back and forth will return many. This is important because for the algo to return intersecting it must try all possible cases which can take a long time, especially for complex meshes.

[Edited by - Motorherp on September 13, 2004 10:24:04 AM]

Quote:Original post by Motorherp
For abitrarily shaped meshes I'm not aware of an anylitacal method for determining exact collision times/points in this way.

In theory it's not possible efficiently in the referential of one convex, the other can describe complex movements, resulting on equations really hard to inverse. If you consider numerical precision limits (ex: 24 bits) I am nearly certain it can be done quickly, in quasi constant time, if rotational speeds (refered to as Omega later) are not too great. I wish to be back to physics programming and test the many ideas I have compended on paper the last months.


As Motorherp said use the swept spheres to find a reduced time interval of potential collision.

The spheres do not have to be in linear translation (constant velocity vector). To be totally conservative you can take the accelerations into account. Majorate them and you can grow the spheres linearilly. Thus no collision will be missed here. Let the sphere centers match the gravity centers even if the radius is bigger, it's easier.

Next finding the first time of contact is the big deal. If you have the contact time, just integrate, run a static coldet and you get the contact point, the relative velocities, etc ...

Binary recursion algorithms suppose abusively (if not erronously) the precondition that the MIN DISTANCE between the two objects is monotonously decreasing. In many cases it works but with fast rotations, the mindist(t) curve might well be of sinusoidal shape. Even around the time of contact the curve might be parabolic shaped :

A 'parabolic' shaped min-distance curve.    \     /  0--X---*---> time      \_/ <- inflexion point here  X is the contact time

My assumption is that the frequency of inflexion points is closely related to the two Omegas. This way slicing the function enough on the time line we can certainly assert to be left with the monotonous and parabolic cases.

Then we need to check each slice in chronological order. It's easy to see that for quick rotations, no other way will be quicker. In each slice we need :

d(t0) d'(t0) (d' is the derivative)
d(t1) d'(t1)

d(t) can easilly be found with the algos based on the well documented separating axis theorem. A connexity graph or a 3D Voronoi diagrams can be used to speed it greatly with space time coherency. The power of this method is in most cases only 5-6 dot products (plane-point distances) are required.
d'(t) can also be evaluated once the two nearest d-facets in each convex (point/plane, plane-point, edge/edge), that define the separating plane are identified.

Thus a probably very good approximation of the parabolic curve. Find the time of minimum. Then you are left with the monotonous case. You can easilly use a binary recursion quite confidently and find the first zero, normally on the left side.

If you understand this well, it's quite obvious that the algorihtm is really close to optimality. I could comment it in details but that would make the post very lengthy.

[Edited by - Charles B on September 13, 2004 3:07:19 PM]

Quote:Original post by Motorherp
... Collision detection is then perfomed on these swept hulls using any of the methods available for convex meshes (eg: seperating planes). ... doesn't account for rotation ... time steps are small enough ...

It's also something I have in mind for many years.

Merging hulls.
--------------
Getting this hull caps cand be fast using merge methods, that is taking advantage of the prexisting connexity graphs.

Also note that you can merge as many hulls as you want in
log(n) time : Hull(A0,A1,A2,A3) = (Hull(A0,A1), Hull(A2,A3))

This can reduce the problem of rotations.

However merging hulls, requires walking in connexity graphs which is usually inefficient in runtime. (AGIs, prediction and cache problems)

Growing hulls
-------------

You can also grow the convex polyhedra by pushing the planes in their normal direction by Delta. Recompute the vertices as intersections, or something quicker.

With this error volume added, it might become a conservative rejection test.

Also, the big problem is you can't exploit the accelerated version (space-time coherent) of the separating plane algos because the convex shapes are recreated each frame. However I think it's possible to greatly improve the static algorithms in real life.

So in the end I am not sure this idea might be really efficient.

It took me a couple reads but I think I see what you're getting at. basically what you're saying is to progress up time slices chronologically until you can be sure that in the remaining time slices up to the exact collision time the min distance between the two objects is only decreasing. At this point you then use binary subdivision to converge on the exact collision time faster. Is this correct?? It sounds good but there are a couple of issues I have that maybe you could clear up for me. Firstly in order to make the determination that in the remaining time its safe to use binary subdivision wouldn't you already have to know the exact collision time??? Also it sounds like a lot of extra checking and calculating which would only pay off when the objects got very close to the collision time. I'm not convinced you would get a speed boost over just skipping the extra checking and progressing up time slices in chronological order regardless. Finally as I finished with my last post, by jumping beyond the collision time you are entering the region where the objects are colliding and the seperating axis algo drags. By progressing chronologically you only enter this region once (when the collision time is determined) whereas with subdivision you'd be entering it n/2 times where n is the number of jumps taken to determine the collision time. But then again maybe I've just understood you wrong??

"Firstly in order to make the determination that in the remaining time its safe to use binary subdivision wouldn't you already have to know the exact collision time ???"

Monotony is the only condition I see. For "Binary subdivision", I think more and more in my case I'll replace it by a highly disymetric trinary search :

a0             a1  b1          b0[               [t0]           ]t is evaluated (root of polynomial)[a1=t0-Delta, b1=t0+Delta] is recursed first.If invalid (0,0001%), then [a0,a1] or [b1, b0] are recursed.

Somehow it's Newton Raphson modified because only an approximation (say p(t)) of d(t) is known instead of d(t). But p(t) gets closer to d(t) when [ai,bi] shrinks. Thus instead of a serie of points, it's a serie of intervals.



"wouldn't you already have to know the exact collision time ???"

??? Not sure I see your question here :/.

No the error done by approximating d(t) to a second degree polynomial is not around the contact time (d(t)=0) it's around the minimum of d(t) which is after the collision if it's negative. If this minimum is positive, there is no collision in the slice. Quick rejection BTW (*). Maybe in the next slice if there is one, that is only with very high angular velocities. In rare cases the contact time may be very close to the minimum (negative) distance time, but then it means that the objects hardly touch, and if a collision is missed there, it's of nearly no consequence since this also means the normal relative speed is very small, and would have a very small impact. (I put apart angent speed and friction).

Example :       ^ \        __ |  \      /   \       /|   \____/    |\     /-------|------|-X-m-/----> t       |      |  \_/<-----><-----><----->   0-1   1-2    2-3

Slice 0-1
- all monotonous, d'(0)<0, d'(1)<0,
- Since d(1)>0, no collision. Two calls to d(t) (boosted separation plane algo)

Slice 1-2
- all monotonous since d'(0)>0, d'(1)>0,
- Since d(1)>0, no collision. One call to d(t) (boosted separation plane algo)

Slice 2-3
- one inflexion point, 2nd degree approximation
- quick search closing X (b1=max(b1,m))
- X found in 1 or 2 steps (a few calls to d(t), 2,3,4 ? )

Calls to d(t) (collision primitive) : 6,7, or 8 ?

As you can see the boosted trinary recursion is only done in one slice at max, here 2-3 (*)

Slice frequency must be chosen appropriately. Omegas and other factors to study very precisely on paper. But it's sure one such freq exists. There will always be a possibility to majorate it so that the slices are always chosen small enough.


"Finally as I finished with my last post, by jumping beyond the collision time you are entering the region where the objects are colliding"

Depends how far beyond. Not necessarilly. In some cases the objects hardly touch. And then you miss ;). It's not always a 'frontal' collision. That's the whole issue I think my algo treats with both solidity and speed.


"By progressing chronologically you only enter this region once (when the collision time is determined) whereas with subdivision you'd be entering it n/2 times where n is the number of jumps taken to determine the collision time."

"the seperating axis algo drags."

I think I know how to handle negative distances in the collision detection primitive, with Voronoi stuff. Positive or negative d(t) should be returned as fast. Even if I was wrong :

First you probably admit that this n is very small with my trinary search. Probably 2 or 3. Samples are (cf my example scheme) 3, and t0+Delta.

To be accurate enough you need very small time steps if ou don't recurse.

Conclusion :

For very high rotations, traditional methods would fail. If you read carefully I can't see any important objection against the speed of my algo. Except maybe the negative d(t) 'stall' issue. I need to check my ideas about Voronoi. But then I object against your algo (precision). But you might say since it's rotating or translating very fast, or if the error is not too big, the gamer will not notice ... hmm right maybe.