# PrestoChung

Member

396

334 Neutral

• Rank
Member

• Interests
Programming
1. ## When contact resolution fails

Not sure what the "gradient" is supposed to be here? Here is how I currently solve for normal velocity constraints: The difference between the current velocity and the target velocity (zero for resting contacts) in the direction of the contact normal is computed and then multiplied by a scalar (basically the "kn" value on slide 21 here [Catto GDC06](http://ppt-online.org/187866): it involves the skew symmetric of the contact point vectors, the inverse intertia tensors, inverse masses, and the contact normal itself), giving the magnitude of the impulse to be applied After this successive impulses converge on a solution, position is integrated with the new velocities to give the resulting poses at t==1.0. Now if there is a penetration here, I will have a penetration vector indicating the depth and direction of the penetration. So do we then go *back* to the time of contact, and based on the penetration depth and direction, apply pseudo-velocity impulses to reach some target pseudo-velocity along the *penetration vector direction*? So the kn scalar above would be the same except that it should be computed with the (normalized) penetration vector p as the input "direction", giving some other scalar, say kp. Then the solver iterations are essentially the same, except each contact point has its current velocity computed along the *penetration vector direction* instead of the contact normal direction, until the target velocity along the penetration vector direction is reached. Once the pseudo-velocity targets converge, integrate to t==1.0 using velocity + pseudo-velocity and check the poses again for penetration, running another penetration solve, with a new penetration vector, if needed. It sounds like this would eventually solve all penetrations, the only thing that seems a little odd is that each contact point would have the same target pseudo-velocity, since the depths of individual contact points weren't computed. Maybe the right way is to look at the resulting distance vector between the contact points on the surfaces of each object, and project that against the penetration vector? So each contact point would have its own target pseudo-velocity, which would be zero for points that have a positive dot product with the penetration vector.
2. ## When contact resolution fails

I think I understand why they are called "pseudo-velocities" now: they don't modify the velocities of the object, but get used for the post-integration after the contact has been resolved. I'm still not sure exactly how it's supposed to work. Is it as simple as projecting the penetration vector against the contact normals, and then re-running the PGS solver with new target normal velocities that are adjusted by this extra amount? It doesn't sound that much different from steering velocity or Baumgarte, except that this extra velocity doesn't accumulate in the object momentum since it is "thrown away" at the end of the frame.
3. ## When contact resolution fails

I think what I have is considered CCD, the collision detection pipeline uses swept volumes in the broad phase with conservative advancement in the mid phase and bilateral advancement in the narrow phase, so it's good at detecting any collisions where rotational velocities are less than about PI radians per frame. Not sure what continuous physics is, but we handle the collisions in the order they occur (at exact fractional frame TOI) to prevent tunnelling. So ignoring high rotational velocities, penetration really only occurs in this case where contact resolution fails for some reason, and that's usually this gradual drifting where the negative velocity is a small value within the target tolerance. I'm still not exactly clear on what orthogonal projection, pseudo velocities, NGS actually do, maybe because I don't have a general "constraint" framework to work with: right now the only constraint is the velocity constraint imposed by contact resolution, which I think is the "Projected-Gauss-Siedel" (PGS ) method where final impulses are arrived at iteratively that satisfy the "Signori Conditions". It kind of sounds like the algorithm for solving a set of non-penetration (position) constraints would be a similar process, applying penetration resolves in sequence over all contacts until the system converges to one where there are no more penetrations? One thing I do have at my disposal is the exact penetration depth and vector as calculated by GJK. With this information a simple linear offset can be applied that will solve a single penetration more or less exactly (accounting for relative masses of the objects), if one doesn't rotate the objects at all-- although a more "correct" solution would rotate the objects as well, so maybe this is where things get more complicated.
4. ## When contact resolution fails

What is this method called, is it related to one of the pseudo-velocity methods or NGS? I don't have any joint constraints, so stability there is not a concern. So far we have gone to great lengths to prevent penetration , so I would probably not consider Baumgarte (solving the penetration over several frames).
5. ## When contact resolution fails

What do people usually do when a contact resolution algorithm doesn't succeed in preventing overlap of collision manifolds? I have n-object contact resolution working in 3D using velocity constraints, but since it's a linear approximation after enough time objects can slowly drift closer until they overlap, and the algorithm will do nothing for small negative velocities that are within the target tolerance. Objects can also overlap after a contact resolve even when the local contact velocity constraint *is* satisfied (objects are separating at the given contact points): for example a box balanced on an edge or a corner tips over while remaining in contact, until it eventually falls flat. In that case I would want to break contact and perform a collision so that a 'bounce' will result when it lands. What I've decided to do is a penetration resolve (solve for a position constraint: push the objects apart) *only* if the local contact velocity was negative after attempting to resolve the contact group. After applying a penetration resolve, I have been updating velocities to match the apparent motion resulting from the position update, which means that the contact group needs to be resolved again to make sure the velocity constraints are now satisfied, at least within tolerance, and no more overlaps remain. Whether or not this velocity update is a good idea or required I'm not sure if it's just causing extra work to be done. Things get a little more complicated when it's a new collision involving two contact groups: the trajectories of all the objects in the contact groups will be modified, so they will have to be re-entered into the collision pipeline to catch new collisions, but this is more of an implementation specific problem, I think. Anyway, just wanted to see if these are valid approaches or if I'm solving an intractable problem.
6. ## Is a contact graph needed/desired for sequential/impulsive velocity constraints?

So I have implemented a sequential impulses collision/contact solver including the contact manifold generation (up to 4 points for a pair of objects) in the 3-dimensional case. Now, do I *need* a contact graph to solve for "stacking" groups of objects? Or can I just add more points to the solver without regard to where they are relative to some "root" object, i.e. just use a "flat" list of contacts. For example if there were 3 objects and two contacts between them, that would be up to 8 contact points to solve for in the iterative solver. To help converge faster, I am aware of "warm-starting" which is basically caching the impulses over frames for persistent contacts (of course there are issues with "identifying" contact points when the manifolds are changing). Is this all I need to worry about? No contact graph necessary?
7. ## Question about target velocities in sequential impulses contact resolution [3D]

That is the presentation I have mainly been working from. Part of the confusion might come from trying to apply the conditions to colliding contacts. The 3rd condition:   vrel_i = 0   or  \lambda = 0   seems different for collisions:   if you have a colliding contact point with a negative relative velocity of magnitude -1.0 in the normal direction, you want to drive the velocity to a positive value scaled by some restitution factor, say, 0.5: -1.0 -> 0.5   so you want to apply an impulse that changes the velocity in the normal direction +1.5. so the impulse \lambda is positive (non-zero), and the target velocity is positive (non-zero).   for the second point, say it is initially separating with velocity +0.7, by the signiori conditions because the velocity is positive, \lambda has to be zero (no impulse at separating contacts), at least for the 1st iteration.   but applying the impulse to the first point results in the second point having a negative velocity, say -0.3. if this was a resting contact, i would assume that we need to apply a positive impulse \lambda now that changes that -0.3 velocity to 0.0 velocity, fine. but this is a colliding contact, should the target velocity for the second point be a positive velocity determined by the restitution factor? 0.3  * 0.5 = +0.15, should it be 0.0 since the point was already "in contact" there's no distance to accelerate to -0.3 so this velocity is more or less virtual? or should the target be the original separating velocity +0.7? either way a positive \lambda is chosen, i *think* the answer is the target should be 0.0 for this second point since it was already in contact when the first point caused a collision in the first place.
8. ## Question about target velocities in sequential impulses contact resolution [3D]

Right, but my question is what should the target velocity be for the second point after the accumulated impulse is applied? It was separating before the impulse for the first point was applied, now it is negative (closing). I want to find an impulse for the second point that either: makes the relative velocity 0.0? or returns it to the positive separating velocity it had at the time of impact?   After the impulse for the second point is found the the solver will loop back around to the first point and repeat the process.
9. ## Question about target velocities in sequential impulses contact resolution [3D]

I'm using sequential impulses to drive the velocities of contact points to their targets:   - for collisions that means the target is the restitution velocity (separating) - for resting contacts it's 0.0 (the objects were already in contact so there was no distance to accelerate over so the target should remain zero)   How are targets chosen for other points that are *initially separating* but whose velocities become *closing* velocities as a result of handling the other contact points in the contact manifold?   If the same reasoning for resting contacts are applied, then there is no distance over which to accelerate so the restitution should not be some positive rebound velocity, so that leaves only two real choices of targets that I can see: either 0.0 or the *original* separating velocity. I'm guessing 0.0 but I don't have a real reason for it other than that's the way contacts work, but is the answer the same for both collisions and contacts?
10. ## How good are SDL event timestamps?

i use "asynchronous" in two senses:   1. the input thread is waiting on events (SDL_WaitEvent) instead of pumping at a fixed frequency 2. the input thread sends commands to the renderer via an asynchronous channel (since I"m using OpenGL i guess this is kind of like simulating multi-threaded rendering via command buffers)   #2. ensure that when the renderer is waiting on VSync, input processing still happens. #1. maybe isn't necessary if events received from SDL are already properly timestamped
11. ## How good are SDL event timestamps?

I'm currently using SDL contrary to specification and collecting events "asynchronously" on the main thread and rendering with OpenGL (vsync) in another thread. It seems to work fine. It may be internally that SDL is still blocking input collection on vsync, but it allows me to decouple input from rendering at least code-wise. Assuming input really is asynchronous, are SDL timestamps good enough to be used in a case such as this?:   http://www.gamedev.net/page/resources/_/technical/general-programming/asynchronous-keyboard-input-for-fixed-time-step-games-r3959   or should I be doing my own time-stamping?
12. ## Collision detection

if you have line triangle you can get line prism by testing the line against each of the 8 triangles making up the prism (1 for each end, 2 for each side)
13. ## Contact tangents

Thanks for the pointers, I was going to modify my post to mention that I do use GJK already for distance and penetration calculation, but it does things pretty minimally so it usually returns a point/face as nearest features in a resting scenario.
14. ## Contact tangents

So it turned out I was looking at the Catto "Iterative Dynamics" paper, which is a bit more advanced than this scenario, and actually what I had been using before was Catto's GDC2006 powerpoint, which I had previously compared to Bender and Schmitt and found to be essentially the same, although Catto goes into picking points on boxes and some other tricks such as a 'bias' velocity.   Then I would say it's time to add more contact points, but I have general meshes, not only boxes. Does anyone have any pointers for finding contact points on a general surface? I'm guessing the brute force approach is just searching along the surface normal and comparing dot products.
15. ## Contact tangents

That is the tangent used for collision response, the tangent for contacts is described on page 6.