Conservative advancement and permanent constraints

[Numsgil]

See the attached diagram. It's basically a box hinged to another box. How do you handle finding the time of impact for something like this? That is, I want to find the time when the top box is flush with the bottom box. I was going to use conservative advancement (where you take the lower bound for distance between objects and the upper bound for point velocity on either object to find a minimum safe time to advance without worry of a collision) but I don't see how you'd get CA working in this case since the minimum distance is supposed to always be 0 since two of the vertices are constrained together with a 2D hinge.

I can kind of imagine a solution that involves destructing the boxes into lists of features (edges and vertices), and disabling collision between features that are constrained. I'm not sure if there are unforeseen issues with that, though, and I'm not sure how clever you'd have to be based on constraint layout.

Are there any other TOI algorithms worth considering? It doesn't have to be all that fast (this isn't necessarily a real time engine I'm working on), but it should be robust and accurate, and catch the bullet-through-paper case, and handle this particular case, too.

[raigan2]

I've always assumed that this sort of collision is best implemented using joint limits... at least, that's how I would approach it.

[Numsgil]

Assuming you could express it in terms of joint limts, it seems to me that that would suffer from the same issue of CCD. You have to find the time when the joint limit is first violated, which is probably not on a frame boundary.

[raigan2]

In the case of hinge constraints you can definitely define joint limits which exactly mimic collisions -- you could even automatically detect and generate them in a preprocess by e.g incrementally rotating about the joint and stopping when you find a collision.

I see what you mean though -- very fast rotation might cause flythrough, or even just a large constraint violation which ends up being solved the wrong way (e.g the box on top swings down from above, but is pushed out of the left side rather than the top side). If objects are rotating more than 90deg per frame this is a pretty hard problem.

Two recent discussions might be helpful:

One idea from this thread http://www.gamedev.net/topic/596865-swe ... nd-physics that should work in your case is to use "core" shapes (e.g spheres) that are contained inside your objects. Combined with this method of resolving swept collisions http://www.wildbunny.co.uk/blog/2011/03 ... ach-part-1 you should be able to insure that the circles will be stopped when they first come into contact, and the joint solver can take it from there since there will be only shallow violation of the constraint limits.

(sorry, I'm not sure why the URL tags aren't working...)

[Numsgil]

It's funny you link to that second one: a RL friend linked it to me yesterday.

I don't really understand what the speculative contacts are doing, so I'll have to sit and stare at it for a while.

In the mean time, I'm pursuing the swept feature-to-feature idea, since I can easily incorporate changing the shape over time, which is another goal I'm working on.

Basically my overarching idea is:

1. Integrate the motion of the island forward in time for the whole step, and resolve all the persistent constraints. Ignore entirely any considerations of collision detection.
2. Construct a quadratic vector spline for the linear and angular motion of bodies. That is, you have a vector quadratic approximating the motion of a body with a ballistic path, and you have a scalar quadratic for the angular motion about the center of mass of the body.
3. To test for collision between two bodies, iterate over all vertex-edge pairs between the two bodies.
4. You now have a vector quadratic for linear ballistic motion and a scalar quadratic for spin for 3 points of interest: two for the line segment and one for the target vertex.
5. A bit of mathmagic later (which I haven't verified yet, so I could be way off), you have an equation of the form: p1 - [cos(t1)cost(t2) + sin(t1)sin(t2)] * p2 = 0, where p1 and p2 are (quartic) polynomials varying over time, and t1,t2 are quadratic polynomials varying over time. [cos(t1)cost(t2) + sin(t1)sin(t2)] is always in the range [-1,1], which is interesting, but not something I see a way to exploit.

The goal is to find the first odd root greater than the time of interest and less than the end of the frame. Obviously there could be infinitely many roots, and all the roots could have even multiplicity (two gears rotating next to each other whose teeth only even *just* glancingly touch). But it's at least into a form that I can feed into more standard root finding methods (Newton's method, though the possibility of even roots makes it tricky), so I'm at least treading in familiar territory.

Obviously instead of quadratics above you could replace it all with linear approximations over the frame, which would reduce the resultant quartics to quadratics.

The disadvantage here obviously is that this is pretty slow, since you are dealing with feature pairs, which means O(n^2) for the 'n' number of vertices in your convex hull, but I think it'd be fast enough for my purposes. And it requires a fairly robust root finding method that can tip toe through even multiplicity roots and always converge to a valid answer if an answer exists, which is actually asking a lot out of numerical root finding methods. On the plus side it would give an exact TOI, depending really only on the quality of the numerical root finding method (for which various packages and literature exist). It's also easy enough to shoehorn a changing shape into the equation of motion of a feature (instead of linear motion + constant distance from center of mass * angular motion, you have linear motion + time varying distance from center of mass * angular motion).

Eh, reading over all that again it sounds pretty technical But I think it looks promising so far.

[Numsgil]

Ah, nevermind the bit of math: my math was bad. I still think the general idea has promise, though.