[font=georgia, serif]I am almost ready to start adding physics to my 3D simulation/game engine, but have one last (but very annoying) job to perform in collision detection. That is, finding "first contact" time and positions. This is the time when the colliding objects first touched, and the locations (points, edges, faces) on the two colliding objects that were touching at first contact.[/font]

[font=georgia, serif]The existing, highly optimized collision detection process has up to 3 phases:[/font]
[font=georgia, serif]#1: broad-phase - rejects all object pairs whose AABBs do not overlap.[/font]
[font=georgia, serif]#2: narrow-phase convex - rejects all object pairs whose convex hulls do not intersect.[/font]
[font=georgia, serif]#3: narrow-phase concave/arbitrary - finds exact intersections of arbitrary shapes with concave features.[/font]

[font=georgia, serif]#2 performs the usual GJK algorithm, and has all the intermediate values GJK has computed when it finds intersection.[/font]

[font=georgia, serif]#3 is not performed unless one or both objects have concave features (or it isn't known whether they do). If #3 is performed, it finds every intersection between any triangle vertex or edge and any triangle vertex, edge or face on the other object. #3 is amazingly efficient given what a difficult problem exact intersection between arbitrarily irregular objects is, but is several times slower than GJK. Therefore I need to find first contact in stage #2 before possibly moving on to iterating #3. Note that the majority of the outside surface of most arbitrarily irregular objects is still locally convex, and thus the answer from #2 is usually correct even for arbitrarily irregular "concave" objects.[/font]

[font=georgia, serif]I rather doubt there is a general algorithm to compute first contact time and position for arbitrarily irregular "concave" objects as supported by #3. So let's forget that for the moment and assume we compute first contact when the GJK technique of #2 finds two convex objects overlap (whether one or both have concave features or not).[/font]

[font=georgia, serif]We've optimized the hell out of our GJK routine, and it is fast as blazes. So I'm not terribly concerned if a computed "first contact time" is not exact --- we'll just take the result, move the objects back to the computed "first contact" time, and perform the GJK routine again... iteratively... until the distances become "close enough". I assume this will be necessary anyway, since one or both of the objects may be moving and/or rotating, which I assume means no fast, efficient and precise algorithm exists.[/font]

[font=georgia, serif]Once this last bit gets done, it's on to collision response AKA physics. Believe it or not, I can't wait![/font]

I don't want to put a downer on proceedings, but there is an absolute ton of work ahead of you if you carry on down the line of wanting to compute TOI. You will end up with TOI islands and taking multiple sub-steps in order to find the true TOI.

Look at Box2d for a robust implementation of this, but make no mistake, its *extremely* hard to get right. If you can live with totally plastic collisions you might want to explore 'speculative contacts' which make the whole process a lot easier to manage. They have their own draw-backs but are an order of magnitude more easy to implement than a true, globally correct TOI implementation.

Cheers, Paul.

[font=georgia, serif]How many tons of work do you think are already behind me on this? Hahahaha. But sure, I'd like to avoid wasting too many more tons of effort, and that's why I hope you continue to help.

First, I consider the concept of "true TOI" to be inherently pointless in this context. The very objects themselves are created out of polygons, while the real objects they mimic have smooth curves. Thus, there's already an inherent inprecision in the whole system, and that sets a degree of precision that is completely and utterly pointless to improve upon. I freely acknowledge and accept this. On top of this, there is a question of the ultimate application that has implemented itself on top of my 3D simulation/game engine. If that application is a game, then it is more important to keep up a minimum frame rate of 30FPS than compute TOI with greater precision. If that application is a simulation, much less a simulation upon which life and death might someday depend, then as much frame rate as necessary can be sacrificed to find TOI within any reasonable precision.

That's my starting assumption, and the application will be able to tell the engine what tradeoffs between "frame-rate" and "precision" to make.

However, that still leaves the question of what is the best way to find TOI to the greatest precision in the least time possible. And that's the answer I hope to learn from the zillion hours of attempts others have made before me. I assume many of them performed their basic "narrow phase" collision detection with GJK, and therefore have access to the same variables I do when GJK encounters a collision. I suppose it would be easy enough to have access to these variables for both "this frame" (when the objects overlap == the origin is within the minkowski-sum) and for "previous frame" (when the algorithm terminated without finding the origin enclosed). Unfortunately, I'm not fluent enough in math-thinking to know what to do with these intermediate results, which is why I hope others are more fluent, and willing to point me in fruitful directions.

What are "TOI islands"?

As for "taking multiple steps", I'm not afraid of that. I benchmarked my GJK routine, and it is quite fast. I don't see a problem performing GJK interactively "a few times" (on average) to find reasonably precise TOI. However, I do want to avoid performing GJK interactively "many times" (on average) to find reasonably precise TOI, because there might be unusual cases where large numbers of objects collide during a given frame, and performing many iterations of GJK for each colliding pair could begin to become "too much".

There are certain aspects of reality that work in our favor. I'm sure you understand this. For example, if the relative velocity of two objects is huge, the objects will be blown to smithereens no matter how they collided. In these cases, the physics engine only needs to know roughly how far the center of the objects come to hitting each other, because that's enough to know what direction to send the smithereens of each object tumbling off in. Those kinds of catastrophic collisions cannot be precisely modeled, no matter how precisely we know the TOI and relative positions at impact, because the way real-world objects explode into pieces is largely a function of material weaknesses that are highly variable from piece to piece, and therefore never known in the first place. In contrast, when objects collide a modest relative velocities, they might not break apart at all, and thus their response to the collision is much simpler physics --- like "bounce off each other". So as a matter of fact, and as a matter of convenience, the precision we need in most cases is an inverse function of relative velocity. In other words, the slower the objects are moving and tumbling, the more precisely we need to find the TOI to compute a plausible, useful collision response. But the slower the relative velocity, the less iterations it takes to find a TOI within a given precision, just assuming the completely uninformed case of binary iteration AKA "successive approximation" (1/2, 1/4, 1/8, 1/16, 1/32, 1/64 frame, etc).

So all I'm looking for is something better than successive approximation. I'll be smart enough not to even bother with such silliness if objects collide at 10,000 meters per second! If that happens, I'll just create a huge explosion that generates a crater vastly larger than the smaller of the two objects. Sure, that's a slight cheat, but nobody will ever notice.

So maybe my question isn't as difficult as it seems. I'm just asking, does anyone have any way to find a "first guess" at TOI from information available from GJK that's better than just starting half-way back to last frame, and performing GJK in successive approximation?

I guess I should add a couple other observations. I'm not worried about the problem of "jitter" that others seem to fight with. I had a problem like that many years ago, and I solved it with rather simple fixes. For one, I simply refused to avoid performing collision-detection or physics on objects that are not moving! Sounds silly, but apparently many people don't bother to apply this simple test! And yes, it isn't quite that simple, because in many simulations/games forces like gravity push on every object, every frame. Yet "push" doesn't equal "move", and I found simply distinguishing on that basis stopped a whole slew of incredibly annoying and wasteful computation. Then, on top of "not moving", there is a need to implement dampening behavior, so objects don't bounce up-and-down and back-and-forth ad-infinitum. After all, no real objects have zero damping behavior, so why should idealized objects behave that way. If anything, unless it matters a lot for some reason in a simulation, damping should become much greater than reality might indicate once the distances involved become small (essentially invisible to the camera looking at the scene).

A while back I downloaded and read a few PDF papers on "speculative contacts" and other fancy ideas. To a large degree, I just "didn't get it"... meaning, I didn't understand "how this works" in detail, or "what's the point".

However, I must openly admit one possible reason for this. This reason might expose a weakness in my assumptions. In these papers I often see discussions and images that imply people are very concerned with situations like "20,000 boxes stacked on each other, and the whole pile is starting to collapse". Or "the bottom of a box full of 20,000 ball bearings is instantly removed and they all fall onto a table". Now, I must admit that my nominal ways of looking at things, and the approaches I consider as a result, probably don't measure up very well in these extreme kind of contrived circumstances. I mean, I sure don't want to perform 8 iterations on (20,000 * 20,000) object-object collisions each frame! Hell, even one iteration of GJK on (20,000 * 6-nearest-neighbors) sounds pretty terrifying to me! If that's the kind of premise you're holding in your mind, then I probably better just cry uncle and admit my approaches are screwed... because they are!

For that matter, I'm not sure I should START dealing with this field by starting with these (20,000 * 20,000) or (20,000 * 6) scenarios. I can certainly imagine that those kinds of scenarios are a royal, massive, pain in the brain. That indeed sounds like megatons of work.

So in your reply, tell me whether there is, or ever was, a less overwhelming premise of collision detection that simply wanted to be able to deal with a few (meaning less than 4~16) collisions per frame... at most. And distinguish roughly where is the dividing line is between the "simple-minded" scenarios and approaches I'm thinking about... versus... the monster complexity of 20,000 objects bouncing off each other when they collapse. Strange, but I've never read anything that even distinguishes simple from hyper-complex scenarios, and I'm not sure why.

-----

PS: I went back and re-read "Continuous Collision Detection and Physics" by Erwin Coumans (August 2005, draft 5), and the notion of "conservative advancement" became clearer... I think. But my takeaway is, successive approximation is better, or at least CAN be better if an object is rotating quickly. Tell me if I'm wrong about the following. If a hyper-rapidly rotating ball is slowly approaching another object, the "conservative advancement" computes the velocity of the vertex furthest from the center of mass of the ball, sums that into the relative linear velocities of the objects, and computes how long it will take for the closest points on those objects to converge to contact at that computed "maximum possible relative velocity"... and then advances the objects that far, or as far as one frame time would take them, whichever is less.

I see a huge problem with this approach! The ball is moving very slowly towards the other object, and will take dozens if not hundreds or more frames before the ball strikes the other object. However, the vertices on the periphery of the ball are moving at enormous velocities due to the hyper-fast rotation of the ball. So "conservative advancement" will advance the objects one-hundredth, one-thousands, maybe even one-millionth of a frame... one-hundred, one-thousand or one-million times before it finally realize the objects do not impact. And this will happen frame after frame after frame.

This makes successive approximately look GREAT, because no perverse cases like this exist. Boiled down to one simple question, I ask whether anyone has figured out whether the information available in GJK at termination (one pre-collision and one in-collision) might let us perform a quicker conversion than successive approximation. That's my primary question, though I'm quite happy to hear and consider any number of additional insights and suggestions that might be relevant.

-----

PS: The admission in my previous PS immediately above got me thinking. I'm trying to create an 3D simulation/game engine that is as general purpose as possible. So my admission is now gnawing on my conscience, as it should. So now I'm starting to think ahead a bit, and perhaps face some of the issues you collision/physics pros have been fighting for a long time. I'm still skeptical about "conservative advancement" versus "successive approximation" or possible quicker-converging alternatives [that work in the face of rapid rotation]. No, I'm thinking about scenarios like those 20,000 similar-size boxes... and maybe even more so scenarios like 2,000 random shape-and-size objects. I dislike "pile of boxes" and "boxes of spheres" examples because anything that uniform clearly opens itself up to special-purpose acceleration hacks to make article-writers and algorithm implementers look good --- on paper. I want my application to work well in practice --- on all sorts of objects of different shapes and sizes.

The bottom line is, I feel rather buggered about the complexity involved in a scenario like dropping a bunch of ball-bearings on a table or into a box. It is obvious that even a "fairly correct" solution would compute TOIs for every collision, then process them starting with the first TOI, thereby directing those two objects in different directions, then finding whether they collide with other objects, and if they do, add them in the time-sorted list of collisions and process them when their time comes.

It is clear to me --- I think --- that speculative advancement is far from that rigorous. From what I can tell so far, it more-or-less puts every object where it would be when it collided (sometime/anytime between last frame and next frame), then let the next frame happen. I think this can place some object-pairs in overtly overlapping states, because objects are not where they would have been "next frame". Maybe this doesn't happen "that often", and as long as they get kicked apart next frame, maybe it doesn't look too bad in practice. Hmmmm. This scenario is gonna be a real mess to work through.[/font]

[font=georgia, serif]-----[/font]

[font=georgia, serif]PS: One final comment (for this posting, anyway). I don't consider or care-about things like "swept-volumes" or "continuous collision detection" in order to solve the "bullet through paper" issue. That's a non-issue for me, because I detect the possibility in a super-fast, super-trivial test before other processing happens. Essentially, in the "sweep and prune" broad phase it is almost free to notice that one object moved from "to the left" of another object to "to the right" of that object. The following trivial, trivial tests performed on the AABBs of the two objects then finds potential cases of "bullet through paper" (BTP).[/font]

[font=georgia, serif]if ((objectA.maxx < objectB.minx) || (objectB.maxx < objectA.minx)) for both this & last frame, then no collision.
if ((objectA.maxy < objectB.miny) || (objectB.maxy < objectA.miny)) for both this & last frame, then no collision.
if ((objectA.maxz < objectB.minz) || (objectB.maxz < objectA.minz)) for both this & last frame, then no collision.[/font]

[font=georgia, serif]In the above, the "no collision" conclusion includes "no bullet through paper".[/font]

[font=georgia, serif]If none of these 3 tests rejects the collision, then the object-pair might BE in collision, or might HAVE BEEN in collision sometime between last frame and this frame. Once the GJK test verifies the object pair is not in collision, the following tests reject (or find) bullet-through-paper collisions:[/font]

[font=georgia, serif]#1: perform the following tests:[/font]
[font=georgia, serif]if ((objectA.origin.x0 < objectB.origin.x0) && (objectA.origin.x1 < objectB.origin.x1)) then no collision[/font]
[font=georgia, serif][font=georgia, serif]if ((objectA.origin.y0 < objectB.origin.y0) && (objectA.origin.y1 < objectB.origin.y1)) then no collision[/font][/font]
[font=georgia, serif][font=georgia, serif][font=georgia, serif]if ((objectA.origin.z0 < objectB.origin.z0) && (objectA.origin.z1 < objectB.origin.z1)) then no collision[/font][/font][/font]

[font=georgia, serif][font=georgia, serif]#2: compute closest-approach time based upon origins and/or bounding AABBs for both objects.[/font][/font]

[font=georgia, serif][font=georgia, serif]#3: if object bounding spheres [or AABBs] do not overlap, then no collision.[/font][/font]

[font=georgia, serif][font=georgia, serif]#4: move objects to their positions/rotations at computed time of "closest approach".[/font][/font]

[font=georgia, serif][font=georgia, serif][font=georgia, serif]#5: perform the normal GJK routine and if GJK says "no collision", then "no collision".[/font][/font][/font]

[font=georgia, serif]#6: if either object is concave [or not known to be convex], perform ANY routine.[/font]

[font=georgia, serif]#7: if ANY says "no collision", then no collision.[/font]

[font=georgia, serif]This entire set of steps (and especially their order) above is chosen to find "no collision" as quickly as possible. If none of these steps return "no collision", then I'm again back at the nasty question I started this thread with, namely "how to find the time of first impact". The ANY routine is what I call my algorithm to detect collision between ANY two objects, no matter how arbitrarily irregular and "concave" they might be (2x to 20x slower than GJK).[/font]

[font=georgia, serif]Lots of words? About the same as your very excellent webpage about "speculative contacts". :-)[/font]

[font=georgia, serif]I guess my response to your suggestion is this. I'm trying to figure things out before I implement. The reason I wrote lots of words, and often write lots of words, is because I prefer to spend a LOT of time thinking and brainstorming before I try to implement anything complex or important. I'm not inclined to just dive in willy nilly and implement whatever I hear about, whatever happens to be popular, etc. I want to understand the issues involved well enough to identify and evaluate tradeoffs, and spot new approaches.[/font]

[font=georgia, serif]Why? Because, as you correctly stated, these subsystems are tons of work, and I prefer not to perform "tons of work" on several approaches that don't pan out. At least those I could have avoided in the first place if I had thought enough about it.[/font]

[font=georgia, serif]After reading your "speculative contacts" webpage, I must say, I was very impressed by what I see. Your examples are extremely compelling. Your technique "sounds almost absurd", but the visual examples you provide certainly make one consider whether the seeming "gross hack" of moving objects into contact and completely ignoring TOI and "lost time" is in fact a great idea. Your examples sure make it seem that way. However, I am a bit concerned by the fact that your visualizations are pretty much all "pile of balls/boxes" type examples. How "speculative contacts" work (visually) on other kinds of collision scenarios is not obvious, and that makes me worry.[/font]

[font=georgia, serif]The other problem, that is unique to me and a small minority, is that I'm not just making a "game engine". My engine is just as much a "simulation engine" as a "game engine", and simulations are mostly about "being accurate", not "being visually plausible". So I'm still scratching my head. Yes, I could implement a "speculative contacts" scheme AND some more accurate kind of scheme, and let the application choose which scheme to execute. Maybe I'll end up there, but I always prefer to find a technique that works for everything... if I can. Of course, I'm not entirely sure I can.[/font]

[font=georgia, serif]This topic might be one of those topics where I just need to turn my gaze away from "what others do", and tackle it more-or-less from scratch myself. Good chance I'll get into difficult situations that others already found ways to deal with, and that's what I was hoping to find out now, before hand.[/font]

[font=georgia, serif]I also have the feeling this whole area of study is too greatly influenced by the specific way game physics is generally implemented. There is something quite wacko about objects jiggling all over the place when they should be just sitting still. I ran into something like this a long time ago on a project that was somewhat similar (but just physics, not graphical)... but I found quite simple, accurate ways to eliminate all this silly jiggling. Just because gravity keeps pulling an object downward (against another object) is no reason to move the upper object inside the body of the object below, and start/continue some kind of undamped oscillations. So I have a feeling that whole problem will not exist for me, and leave me free to ignore all sorts of funky games others seem to play to deal with those situations. Maybe my scheme will be lots simpler because I don't need to worry about those problems, because I fixed them where the fix belongs (physics), not in a different subsystem (collision-detection). We shall see.[/font]

[font=georgia, serif]I'll just keep struggling with the problem. I almost have enough context built up in my mind to have a chance to find or develop a good approach. Hopefully a better approach. Hopefully something fairly accurate, fairly fast, and inherently stable.[/font]

[font=georgia, serif]I expect "tons of work" to implement TOI and physics. So be it. I just don't want to flail around wildly because I was too lazy to take the time to wrap my head around every consideration I could identify before I started designing and coding.[/font]