
Advertisement
RastaRunna
Member
Content Count
29 
Joined

Last visited
Community Reputation
159 NeutralAbout RastaRunna

Rank
Member

Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
The example above that uses appliedVelocity was part of my lessstable version which I am not using anymore. The idea comes from "Game Physics Engine Development" by Ian Millington (section 16.1.2 of 2nd ed) and is intended to remove the previous frame's applied velocity (primarily acceleration due to gravity) in order to reduce jitteriness. With position correction integrated, my engine was stable enough that the term wasn't needed anymore, so I've since removed it. :) If you still want to use it, my understanding is that you determine it's magnitude along the collision normal (appliedVel dot normal), and subtract it from the amount of desired change in velocity for that frame in order to prevent overcompensation. Regarding restitution, for my needs, I really don't need much to be "bouncy", so I'm setting the change in vel to be only enough to remove the relative velocity w.r.t the normal (i.e. changeInVel = magnitudeOfRelativeVelOnNormal). But anyways, the added energy may be coming because of the integration of the position correction. Remember position correction only needs to be applied for a single frame; and so when we apply it as an impulse, it will continue to affect the bodies in question over several frames. To account for this, you should experiment with only applying a fraction of this corrective impulse. This combined with warm starting should be enough. If you dig into the full Box2D (rather than Box2D lite) I believe it handles coefficients of restitution more dynamically. Something else to consider. If you are caching your contacts across multiple frames or have implemented any type of relaxation to solve your velocity constraints, you'll want to make sure that you update the "velAlongNormal" each time you apply an impulse to either body otherwise you may accumulate error which *could* be causing any extra bounciness. 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Thanks! For collision detection my engine implements a mix between GJK and the Xenocollide algorithm with Minkowski Portal Refinement (MPR) to get contact points. You can find the algorithm described in detail in Game Programming Gems 7 section 2.5. A simple 2D example is given on the authors website. Other specialcase detection I follow RealTime Collision Detection by Ericson modifying to my specific needs. For resolution I used a mixture of the following resources to understand the equations of motion and implement a sequential impulse solver: Game Physics Engine Development by Ian Millington  while a good resource for general physics engine development, I do not recommend following this approach if you want a stable system for stacking more than 3 or 4 boxes high. The latest edition has an addendum for 2D physics if that is your interest. Game Physics by David H. Eberly  This book is very thorough and gives lots of details on the math for resolution. At an implementation level this book tends to be more focused on block solvers and simultaneous resolution. Finally, I followed Box2D lite for ordering the integration / detection / resolution pipeline as well as for how to resolve via impulses only (with no direct position corrections), and how to best do warmstarting. All this said, the two features that added the most to the stability were: 1) Warm starting on normal and tangential impulses 2) Impulses for penetration correction 3) Adjusting the coefficient of restitution (bouncy objects don't lend well to stacking). Box2D lite effectively sets this to 0 along the normal if you look in the code. Hope this helps! 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Okay, just to update with some results... So I went back and revamped my resolution system; gutted out the penetration resolution via direct position corrections and switched to impulse only adjustments. This along with warmstarting my impulses (both normal and tangential) made a rather dramatic difference to both the stability and performance of my system. Here are some videos demonstrating the improved results (sorry for the poor compression quality... but I think you'll get the point. Also I made the blocks smaller so I could fit more on screen): Here's one with 50 rows (slow w/out any broadphase implementation, but stable!!): Another with 30 rows and projectile box w/higher mass: Also, I went back to the book I had been following for so long and realized that it indeed does focus on doing what I was doing wrong: direct position corrections. So I'm not as slow / crazy as I was beginning to think; just misled. Direct position corrections is so much slower due to the constant need to rerun the detection system (as Dirk already mentioned). I was actually very surprised how easy it was to apply penetration corrections via impulses. Simply convert the contact's overlap by the change in time to obtain a velocity and add it to your desired change in velocity when computing your resolution impulse. You'll want to only take a fraction of it otherwise you end up adding energy to the system resulting in jitters. Also you'll want to clamp overlap to be positive (which I'm not showing here): contact.penetrationAsVel = amntOverlapResolve * contact.overlap * dtInv; impulseMag = (changeInVel + contact.penetrationAsVel) * contact.effectiveNormalMassInv; Thanks Dirk for the help. 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Wow, this is great info, and will definitely keep me be busy for a while . Thank you for taking the time to list all of these. I've had an interest in 2D physics simulations for the past 12 years; started in high school building really small orbit and spring simulations. About 5 years ago I decided I want to build an engine so started collecting / reading books in my spare time (so very slowly). My first go at it I built a basic engine w/spatial grids for broadphase, and SAT for narrow but then got stuck on resolution so essentially copied the parts of Box2D I didn't understand. Feeling unsatisfied that I didn't really understand the resolution math and wanting to do something in C++ I started over back in November and built an engine that does GJK / MPR for narrow (saving broadphase for after I get resolution working). But all of this time I've always had this notion of having to solve penetration through position corrections. I think my previous mindset came from "Game Physics Engine Development" by Ian Millington. For instance Pg. 122 he says "We could combine interpenetration resolution with collision resolution. A better solution, in practice, is to separate the two into distinct phases. First we resolve collisions... Second we resolve the interpenetrations." And I think I just always assumed that "interpenetration resolution" meant fixing pos... Which doesn't make any sense looking back because the book only ever talks about impulses.... Ahhh!! All this time....... (bangs head on desk). Anyways, an epiphany for a slow guy. Thanks again for your help. 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
So came across slide #54+ of Erin's "Understanding Constraints" presentation titled "Why not work with positions directly?" which kindof answers my question (though it seems to be addressing "positiononly" solvers rather than position and vel solvers): http://box2d.org/files/GDC2014/GDC2014_ErinCatto.zip I think it's sounding like both solvers could be accurate, but overkill since a velocity solver should do just fine in most cases according to the presentation. 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Okay, I'll give that a try and post my results. Thanks for your help, I do appreciate it. Sorry if I keep beating a dead horse  Im trying to really understand what's going on more than just copy code. Any intuition on why this gives better results (besides being correct)? 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Ah, okay that makes sense. I was thinking in this manner: fix overlap (via position corrections) then resolve velocity (via vel corrections or impulse). But from what you're saying it sounds like I should not fix overlap directly via position corrections, but only through impulses. Is that correct? 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Isn't it possible though that by resolving one contact pair, new contacts or collisions are created? 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
Clamping the friction as you mentioned seems to have helped a bit, though at first there is definitely this odd jarring to right of the pyramid before it falls. Once it falls though, the objects do settle down pretty quickly without pushing apart as much as before, though that could just be due to the configuration of how the blocks lie once they fall: impulseMag is supposed to be the total impulse required to cause the appropriate change in velocity. I assume it is the accumulated value because I solve for this impulse in one go rather than in several small iterations (per time step). Or does accumulated mean something else? Here is how I compute impulseMag: flttype relativeVelOnNormal = (relVel>x * normal>x + relVel>y * normal>y); if (relativeVelOnNormal > 0.0) continue; // get applied velocity from previous step along normal (i.e. gravity) flttype velFromAcc = (entityB>appliedVel.x  entityA>appliedVel.x) * normal>x + (entityB>appliedVel.y  entityA>appliedVel.y) * normal>y; // determine desired change in velocity (w/out applied vel from prev step) flttype changeInVel = velFromAcc + (1.0  curContact>coefficientOfRestitution) * (relativeVelOnNormal  velFromAcc); // determine impulse required to cause desired change in vel flttype relAPN = (posRelA>x * normal>y  posRelA>y * normal>x); flttype relBPN = (posRelB>x * normal>y  posRelB>y * normal>x); flttype relACrossNormal = entityAInertiaTensorInv * relAPN; flttype relBCrossNormal = entityBInertiaTensorInv * relBPN; flttype angularMassA = relACrossNormal * relAPN; flttype angularMassB = relBCrossNormal * relBPN; flttype totalLinearMass = entityAInvMass + entityBInvMass; flttype impulseMag = changeInVel / (totalLinearMass + angularMassA + angularMassB); // keep impulse positive impulseMag = impulseMag < 0.0 ? 0.0 : impulseMag; 
Sequential Impulse Solver and Sliding Contacts
RastaRunna replied to RastaRunna's topic in Math and Physics
I'm not. Any recommended ways for doing this? Or would simply feeding in the previous frame's friction impulse work? Here's my current friction implementation: Geometry::Vector2D tangent; tangent.x = relVel>x  normal>x * relativeVelOnNormal; tangent.y = relVel>y  normal>y * relativeVelOnNormal; Geometry::Normalize(tangent, tangent); //tangent.x = normal>y; //tangent.y = normal>x; flttype planarVel = (relVel>x * tangent.x + relVel>y * tangent.y); flttype changeInPlanarVel = planarVel; flttype relAPT = (posRelA>x * tangent.y  posRelA>y * tangent.x); flttype relBPT = (posRelB>x * tangent.y  posRelB>y * tangent.x); flttype relACrossTangent = entityAInertiaTensorInv * relAPT; flttype relBCrossTangent = entityBInertiaTensorInv * relBPT; flttype angularMassAT = relACrossTangent * relAPT; flttype angularMassBT = relBCrossTangent * relBPT; flttype frictionImpulse = changeInPlanarVel / (curContact>totalLinearMass + angularMassAT + angularMassBT); // clip friction mag to min (impulseMag * frictionCoefficient, frictionMag) flttype frictionMag; if (frictionImpulse < curContact>friction * impulseMag) { // static friction frictionMag = frictionImpulse; } else { // dynamic friction frictionMag = curContact>friction * frictionImpulse; } ///////////////////////////// // // Update velocities // // // linear vel entityA>velocity.x = (impulseX + frictionMag * tangent.x) * entityAInvMass; entityA>velocity.y = (impulseY + frictionMag * tangent.y) * entityAInvMass; entityB>velocity.x += (impulseX + frictionMag * tangent.x) * entityBInvMass; entityB>velocity.y += (impulseY + frictionMag * tangent.y) * entityBInvMass; // angular vel entityA>angularVelocity = (relACrossNormal * impulseMag + relACrossTangent * frictionMag); entityB>angularVelocity += (relBCrossNormal * impulseMag + relBCrossTangent * frictionMag); 
Hi All, Been implementing a 2d sequential impulse engine (mostly for the academics of it). The main pipeline of my current engine is: 1) Detect Collisions 2) Resolve % of each penetration 3) Repeat 1 & 2 'n' times 3) Resolve velocities 4) Integrate 5) Repeat This seems to give fairly descent results. However, no matter what I try when objects stack in vertexedge configurations, or edgeedge in pyramidlike structure, then the angled objects will push others out of the way regardless of how many objects are in the pile being pushed. Here are some videos showing the results: Initially I thought there was something wrong with my friction implementation but I've tried increasing friction to no avail. Next, for edgeedge cases I only resolve a single contact, so I've experimented with different contact points also to no avail. I can only think of two things which may be causing this, either: 1) This is unavoidable for a sequential impulse solver  which doesn't feel entirely correct. sliding from sequential solvers should be gradual drifts; not this dramatic but perhaps I am wrong. 2) Steps 1 & 2 in my loop place a large emphasis on resolving penetrations (via position corrections) rather than giving more weight to #3. As I've been reading around online, it seems many don't even do #2 but rather only resolve the velocity by applying the appropriate impulse plus some small portion of the penetration (baumgaurte stabilization?). As far as my penetration resolution implementation: it resolves the penetrating objects in the direction of the contact normal according to the objects' mass. Each pair is resolved in the order of greatest separating velocity. Simple answer seems to be put everything to sleep.... though I feel like that's just masking a stability problem. I'd appreciate any feedback on the ordering of my main loop, and any suggestions on what may be causing my stacks to push apart / how I might be able to mitigate that? Would a TOI solver fix this, or is simultaneous resolution the only answer? Anyways, I feel like I have lots of ideas, but no clear direction; so some guidance would be very helpful. Let me know if you need more info from me. Thanks

Very cool, thanks!

I'm not sure I understand what this means. For sphere, is this just a pointpolygon distance test verifying that distance is greater than radius? Or do you mean that you use GJK to get closest point between point and polyhedral and then do a radius check?

Is that because of numerical robustness? I have been starting to think I'll only use GJK for polygonpolygon tests and then special case the rest as it seems it will likely be more efficient in some cases (e.g circle vs circle in gjk seems overkill). But if there's a robustness issue as well that's good to know.

True. It seems though that it does play nicely into abstraction. Let each shape type determine it's own support / vertex query mechanism. The algorithm itself is none the wiser. The support "key" could even be wrapped in something more nicely so it doesn't feel like I'm trying to stuff indices and angles into the same result. That's a justifiable reason to change.

Advertisement