[font="Book Antiqua"]I have finally arrived at that fateful point in my engine development when I need to make objects collide "correctly". Both broad phase and narrow phase collision detection are working fine now, for both "convex" and arbitrarily irregular "concave" objects. That was enough challenge and work by itself, but now even more "fun" appears.

Having detected that a collision has happened, I need to back up the objects to somewhere between the previous frame (where the objects were not in collision) and the current frame (where they are in collision). I have the transformation matrix for last frame and for this frame. The question is, can I somehow create a new transformation matrix that is effectively a part way "interpolation" between the previous frame transformation matrix and the current frame transformation matrix (for some arbitrary fraction of 1 frame time)?

The problem is this. The transformation matrix is usually modified by only one or two transformations (one rotation and/or one translation). However, there is no limitation on how many rotations and translations can be performed between frames. Therefore, to try the alternative to "interpolating the matrix" I would have to queue up some representation of all rotations and translations (at least) between frames and keep them available for all objects, just in case they encountered a collision next frame.

Clearly it would be more convenient to interpolate matrices if that works.

I guess the alternative is to interpolate the intermediate matrix, if that is more practical. In other words, during any frame, all rotations and translations are applied to a clean [identity] matrix to accumulate the series of rotations and translations. When it is time to translate the vertices, that intermediate matrix is multiplied by the main transformation matrix that transforms local-coordinates into world-coordinates. Since that intermediate matrix ONLY contains information about the transformations happening this frame, perhaps that intermediate matrix is an easier item to interpolate.

I managed to get all the matrix math working, but definitely can't say I'm an expert at matrix math! If I was, I'd intuitively know how to solve this problem, and I don't. Hence my question.

I assume everyone who ever faces collision detection and response encounters this same problem. How is this done?[/font]

[font="Book Antiqua"]
Having detected that a collision has happened, I need to back up the objects to somewhere between the previous frame (where the objects were not in collision) and the current frame (where they are in collision). I have the transformation matrix for last frame and for this frame. The question is, can I somehow create a new transformation matrix that is effectively a part way "interpolation" between the previous frame transformation matrix and the current frame transformation matrix (for some arbitrary fraction of 1 frame time)?
[/font][font="Book Antiqua"]

[/font]

[font="Book Antiqua"]The usual way to approach this problem is to not do this backing up at the matrix level, but to go back to the physics subsystem, and apply a physics update with half the delta-time of the whole frame. Of course you can interpret the data from matrices, but it will require some conversions.
[/font]

[font="Book Antiqua"]The problem is this. The transformation matrix is usually modified by only one or two transformations (one rotation and/or one translation). However, there is no limitation on how many rotations and translations can be performed between frames. Therefore, to try the alternative to "interpolating the matrix" I would have to queue up some representation of all rotations and translations (at least) between frames and keep them available for all objects, just in case they encountered a collision next frame.

[/font][font="Book Antiqua"]Clearly it would be more convenient to interpolate matrices if that works.[/font]

[font="Book Antiqua"]

[/font]

[font="Book Antiqua"]The usual way to interpolate between matrices which represent affine orthogonal bases is to decompose the matrix to a series of translation (float3), rotation (quaternion) and scale (float, or float3 depending on if you allow nonuniform scale). Then, you linearly interpolate the float3's, and [/font]slerp the quaternions[font="Book Antiqua"]. To decompose a matrix to scale, rotate and translate (assuming no shear), you read the 3x1 column vector from the top three elements of the fourth column (transpose that if working on v*M notation, like in D3D), then extract the magnitudes of the three first columns for scale, and finally convert the normalized 3x3 upper part to a quaternion (see Q55 at [/font]this page[font="Book Antiqua"]).
[/font]

[font="Book Antiqua"]After interpolating the components individually, you compose the interpolated data back to a matrix form.
[/font]

[font="Book Antiqua"]I guess the alternative is to interpolate the intermediate matrix, if that is more practical. In other words, during any frame, all rotations and translations are applied to a clean [identity] matrix to accumulate the series of rotations and translations. When it is time to translate the vertices, that intermediate matrix is multiplied by the main transformation matrix that transforms local-coordinates into world-coordinates. Since that intermediate matrix ONLY contains information about the transformations happening this frame, perhaps that intermediate matrix is an easier item to interpolate.
[/font]

I don't think working on an identity matrix for the duration of that frame makes it any more easier, since if we denote by A the local->world matrix at the start of the frame, and by B the local->world matrix at the end of the frame, then you can compute B * A^{-1} to get the difference between A and B, which is exactly the series of transformations you applied to A during this frame, to get B. So you don't need to explicitly store a separate clean identity matrix on top of which to apply the per-frame transformations, you can always compute it if you know A and B.

[quote name='maxgpgpu' timestamp='1313818163' post='4851487']
[font="Book Antiqua"]Having detected that a collision has happened, I need to back up the objects to somewhere between the previous frame (where the objects were not in collision) and the current frame (where they are in collision). I have the transformation matrix for last frame and for this frame. The question is, can I somehow create a new transformation matrix that is effectively a part way "interpolation" between the previous frame transformation matrix and the current frame transformation matrix (for some arbitrary fraction of 1 frame time)?[/font][font="Book Antiqua"]

[/font]
[font="Book Antiqua"][font="Arial"]The usual way to approach this problem is to not do this backing up at the matrix level, but to go back to the physics subsystem, and apply a physics update with half the delta-time of the whole frame. Of course you can interpret the data from matrices, but it will require some conversions.[/font][/quote]
What do you mean by "apply a physics update with half the delta-time of the whole frame"? The physics subsystem takes linear forces, rotational forces and interval, converts that into altered linear and rotational velocity and acceleration, and updates the object by performing rotation and translation operations. Therefore, if I understand you, what you suggest requires I queue up the set of physical influences that acted upon the objects the previous frame, rather than queue up the rotations and translations those influences cause. Is that correct? That might have some advantages (I'll have to think more carefully and deeply on this question), but it doesn't seem to make the process any easier. I'd still need to have the transformation matrix from the previous frame (no problem), plus the queue of physical influences applied the previous frame. I guess that does avoid having to perform an interpolation (which is good), but otherwise doesn't save any work. Also, the number of potential physical influences is much greater than one rotation/translation matrix, so it could definitely be more work to perform. While your way definitely has the advantage of purity (being grounded in the physical phenomenon directly rather than indirectly through the matrix), performing those physics processes will often require much more compute power than fiddling a matrix. Normally I wouldn't worry about this, but if we must perform these physical process computations many times as we interpolate to find the time and positions of first-contact, we would be executing those [sometimes rather involved and compute-intensive] physics processes many times. I worry this might become a "frame buster" (slow the frame time so much that we miss the next vertical retrace), hence my preference to find a way to interpolate matrices or something simpler than repeating all the physics processes many times per frame for the two colliding objects.
[/font]

[font="Book Antiqua"]The problem is this. The transformation matrix is usually modified by only one or two transformations (one rotation and/or one translation). However, there is no limitation on how many rotations and translations can be performed between frames. Therefore, to try the alternative to "interpolating the matrix" I would have to queue up some representation of all rotations and translations (at least) between frames and keep them available for all objects, just in case they encountered a collision next frame.

[/font][font="Book Antiqua"]Clearly it would be more convenient to interpolate matrices if that works.[/font][font="Book Antiqua"]

[/font]The usual way to interpolate between matrices which represent affine orthogonal bases is to decompose the matrix to a series of translation (float3), rotation (quaternion) and scale (float, or float3 depending on if you allow nonuniform scale). Then, you linearly interpolate the float3's, and slerp the quaternions. To decompose a matrix to scale, rotate and translate (assuming no shear), you read the 3x1 column vector from the top three elements of the fourth column (transpose that if working on v*M notation, like in D3D), then extract the magnitudes of the three first columns for scale, and finally convert the normalized 3x3 upper part to a quaternion (see Q55 at this page).

[font="Book Antiqua"]After interpolating the components individually, you compose the interpolated data back to a matrix form.[/quote]
Thanks, I'll study those references. Hopefully I can avoid quaternions (I managed to so far). My engine runs on OpenGL and has column matrices.
[/font]

[font="Book Antiqua"]I guess the alternative is to interpolate the intermediate matrix, if that is more practical. In other words, during any frame, all rotations and translations are applied to a clean [identity] matrix to accumulate the series of rotations and translations. When it is time to translate the vertices, that intermediate matrix is multiplied by the main transformation matrix that transforms local-coordinates into world-coordinates. Since that intermediate matrix ONLY contains information about the transformations happening this frame, perhaps that intermediate matrix is an easier item to interpolate.[/font]

I don't think working on an identity matrix for the duration of that frame makes it any more easier, since if we denote by A the local->world matrix at the start of the frame, and by B the local->world matrix at the end of the frame, then you can compute B * A^{-1} to get the difference between A and B, which is exactly the series of transformations you applied to A during this frame, to get B. So you don't need to explicitly store a separate clean identity matrix on top of which to apply the per-frame transformations, you can always compute it if you know A and B.[/quote]
[font="Book Antiqua"]I think we can assume no shear or scale operations on the frame before a collision. While I do support shear, skew and [non-linear] scale operations, I purposely handle those operations differently than most engines. In my engine, shear, skew and scale operations do not alter the transformation matrix. This eliminates hassles transforming surface vectors (normal, tangent, bi-tangent), and eliminates any need to carry along (or compute on demand) any inverse transformation matrices. Thus, my transformation matrices are as clean as can be, since nothing but rotations and translations alter them.

Thanks for the ideas and links.[/font]

[font="Book Antiqua"]After some further thought, I realized how dumb my first response paragraph was. Doh!

In the previous frame, some [potentially large] number of physical influences each generated a linear and rotational force on the object. Those forces essentially got vector summed to generate a single linear force vector and a single rotational force vector. From those two vectors the linear and rotational velocity and acceleration got updated, and from that, one translation and on rotation operation was generated and then applied to the object.

Which means, I can back up to an arbitrary in-between frame time by taking those two force vectors, multiplying them by a fraction, then recomputing a new translation and rotation vector to apply to the previous-frame local-to-world transformation matrix. Bingo.

While that's not quite as fast as what I was hoping for, it is fast enough and doesn't require the engine queue up an unknown and arbitrary length set of rotation and translation operations (or physical force computations). The great thing about those two force vectors is... they can be fractionalized in the easy way to produce a correct intermediate-frame result.

In other words, you were right, and I just didn't see why at first... probably because I thought you intended me to back up further into the physics engine than I thought (go back all the way and recompute all the forces). But why bother? We can take an arbitrary fraction of the result force vectors and work from there. Great news. Thanks.[/font]

Are you sure you really want to be backing up the entire simulation to find the collision time? There are much nicer (i.e quicker) ways to achieve the same result these days

For example, you can use conservative advancement to get the TOI without backing everything up.

http://www.continuou...onDetection.pdf

http://www.wildbunny...on-for-dummies/

And/or you can use speculative contacts if you want an even faster approximation (which was good enough for Little Big Planet and other AAA titles)

http://www.wildbunny...pproach-part-1/

Both of these techniques work in 2d or 3d...

Cheers, Paul.

Wow, lots of great material. Thanks. And on top of umpteen PDF files I already have on this topic.

Tell me though. Compared to the techniques described above, what's the drawback of tracing back through the minkowski sum along the relative motion vector until we find the outer surface (can't go any further), and taking the length of that vector as the distance to backtrack to find approximate "first contact"? Well, that doesn't much help with rotation unless somehow we're recomputing the minkowski sum as we go (which I guess is possible, but obviously slower).

I have read your material, and lots of other internet-downloaded PDFs on the same topic, but it will take a fair quantity of my brain grappling with all these approaches to figure out the relative merits, drawbacks and tradeoffs. Thanks for the information - I just wish you could transfer your comprehension and clarity as easily! :-)

[quote name='maxgpgpu' timestamp='1314325767' post='4853906']
[font="Book Antiqua"]Tell me though. Compared to the techniques described above, what's the drawback of tracing back through the minkowski sum along the relative motion vector until we find the outer surface (can't go any further), and taking the length of that vector as the distance to backtrack to find approximate "first contact"?[/font]

The drawback is that you're doing things the wrong way around if you do it like this - letting objects get into penetration and then back-tracking is the same amount of work as firing a ray from the origin to the MD of the two shapes along the delta velocity (as described by Gino Van Den Bergen), and getting the point and time of first contact. If you do it like that, you don't need to worry about back-tracking at all and you'd save yourself the first collision check which tells you that you need to back-track

[font="Book Antiqua"]Well, that doesn't much help with rotation unless somehow we're recomputing the minkowski sum as we go (which I guess is possible, but obviously slower).
[/font][/quote]

That's what conservative advancement does. Yes, its slower but it works very well, and if you only need an approximate result, just run it for a couple of iterations - likelihood is, objects are moving/rotating so fast that you can't see the slight error anyway.

Cheers, Paul.[/quote]
[font="Book Antiqua"]I much appreciate your feedback, and I do intend to read and re-read and re-re-read all the descriptions I can find before I make any final decisions. But with great respect for your experience with this, I worry about any scheme that depends on pre-emptively finding collisions before they happen. I mean, that can probably work for a great many games, and maybe on 99.9% of instances in every game, but what happens when a game character kicks a socker ball or shoots an arrow or gun, or something blows up. What I mean is, sometimes objects will go from zero to FAST (and a significant distance) in less than one frame. And other cases exist too, including multiple ricochets of multiple objects that then collide on the next frame. How on earth could any engine ever anticipate all these cases? And if they can't, I guess you must be saying the engine needs two schemes, one predicting collisions and another for when that doesn't work. But if the later algorithm works effectively, why implement the former?

OTOH, I have a feeling I'm misunderstanding some very significant detail about the scheme you mention above (Gino). It sounds like you're saying "once you find a collision you go back to the object states in the previous frame and compute forward to find first contact rather than compute backwards from penetration. If so, I agree that seems like an identical amount of work (and pretty much the exact same code). However, I don't see how that gives any better or worse estimate of first contact time or position than back-tracking. But you seem to be saying a collision is never checked-for or detected at all? If so, how does the program know which objects to trace forward to [possibly] find first contact time? Sorry if I'm asking questions that should be clear after reading his paper. Probably I'm reading too many papers on the general topic and can't keep any single approach clear enough in my mind. But I can't see how the initial collision check can be avoided without needing to perform n-squared of these processes (one for every object-pair combination). I'll go back and re-read Gino again.[/font]

[quote name='maxgpgpu' timestamp='1314386589' post='4854173']
[font="Book Antiqua"]gun, or something blows up. What I mean is, sometimes objects will go from zero to FAST (and a significant distance) in less than one frame. And other cases exist too, including multiple ricochets of multiple objects that then collide on the next frame. How on earth could any engine ever anticipate all these cases? [/font]
[font="Book Antiqua"]

[/font]

[font="Book Antiqua"]'How' is that they first of all bound the motion of the object in question with an AABB. So you know where the object is now, and you know where it will be next frame (i.e. very far away), you just stick an AABB around the entire motion for the object, do the same for all other objects in the game and then you have the set of all possible interactions.[/font]

[font="Book Antiqua"]Regarding ricochets, all you need is to bound what 'could happen' with the AABB overlaps, this gives you your interaction islands. Then you let the solver run and find a feasible solution. If you use speculative contacts in the solver, you can move the TOI impact problem out of the collision code and into the physics solver. Check my blog article for details [/font]

[font="Book Antiqua"]I just wanted to leave you with a thought: your current technique of back-tracking from penetration - how do you deal with the bullet through paper problem? Seems like you would miss these collisions... That's one of the main reasons to go forward in time, not back-tracking [/font]

[font="Book Antiqua"]Cheers, Paul.[/font]
[/quote]
[font="Book Antiqua"]Okay, I'm trying to get my head around this. It sounds like your fundamental "frame loop" (or "game loop") is constructed differently. Maybe that will help make your approach work better. With the addition of collision-detection and collision-response, my current approach is indeed stuck with a very unpleasantly long serial set of steps before the engine can draw. Otherwise a collision might move an object after it has been rendered, and the only way to fix that is to clear that back-buffer and redraw everything again. That would be very unpleasant and too slow. So I'm trying to see whether you have a way around this by re-organizing your frame loop. Hmmmm.

#00: frame++;
#01: process network input (generates messages in message queue)
#02: process OS event queue (generates messages in message queue)
#03: process client application (generates messages in message queue)
#04: process message queue (generates and sums forces on objects)
#05: convert linear/rotational forces into new linear/rotational velocities
#06: from #05 compute object rotation/translation this frame
#07: transform object vertices => VBOs.
#08: perform collision-detection (identifies intersecting objects)
#09: perform collision-response (modify forces on objects)
#10: if any collision-response modified any object forces, for those objects only
--- A: convert linear/rotational forces into new linear/rotational velocities
--- B: compute object rotation/translation for partial frame (starting at collision TOI)
--- C: transform object vertices => VBOs
--- D: hopefully no need to recursively perform collision-detection/response and #10
#11: draw VBOs.
#12: swap buffers
#13: clear back buffer
#14: go to #00

Though I've left out a few low-overhead subsystems (sound, for instance), that's about it. So... now that I look at it, I don't see how you're modifying the frame-loop, except you're performing collision-detection on a swept volume. So I guess that means you are performing classic collision-detection on those swept volumes, which means you have completely transformed the objects to their next frame to create the swept-sum minkowski sum/difference (whichever you prefer to call it) in order to create the minkowski sums of the swept volumes. Then when you find they are in collision, you perform the forward looking pseudo-iteration (maybe done analytically when possible) from the last frame state to determine time of first impact before this frame. That is, if I understand your comments correctly.

If so, you indeed are not backtracking, and don't need to, though it is difficult to believe information about the object intersections doesn't or wouldn't help your computations in some way, if only "corroboration" of the [hopefully] analytic solution.

I do not compute swept volumes, though I certainly could. Instead, I note simple facts about "bullet through paper" type problems. Namely, for object A to have passed through object B, object A must move to opposite sides of object B on all three world-coordinate axes (X, Y, Z) - where "overlapping" the other object counts as "on the opposite side" for purposes of this computation. That does not prove the objects collided, but provides a trivial analytical way to find the time of closest approach [and impact] where the objects can be moved and checked for impact or separation, or the swept volumes could be checked from the first place the bounding spheres/AABBs touched to the last place the bounding spheres/AABBs touched, ala what you suggest. My main "justification" for this approach is that the number of false collisions generated by performing collision detection on swept volumes can be very high, especially when performed on every moving object every frame.

I'm slowly getting my head around the other techniques, but I'm not yet sure there is much difference. Unfortunately, the biggest hassle is we can't draw the damn VBOs until we're sure all collisions are resolved, unless we decide to tolerate up to one frame of "total BS" in cases of collision, and hope "nobody much notices". That might almost work at 60FPS, but probably not so well at 30FPS (or 20FPS or 15FPS).

So I'm almost there, but not quite. Maybe a couple more runs through all the material will crystalize the various approaches better, though the more I look, the more similar they seem (and similar to what I'm doing already, though not exactly).

My other problem, of course, is that I'm not naturally fluent in math. I guess I've done a lot of what some people might consider "fancy math" from time to time, but that experience is always like a brutal war for me, not a trivial and natural exercise like it is to a natural math whiz. So the math of an analytical solution of rotating minkowski volumes scares the crap outta me, and I'll need to be really convinced that is the best approach before I decide to fight another brutal war - and possibly end up in a grave this time!

Thanks for your continuing help.[/font]