Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

334 Neutral

About PrestoChung

  • Rank

Personal Information

  • Interests

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. Well I think the answer might be the general case can be formulated as some kind of Linear Programming problem solvable by simplex method (I think this is what's called "Dantzig's algorithm"). Coutinho 2013 discusses using Dantzig's algorithm for computing frictionless contact forces, which is to say its solving a 2nd or 3rd-order problem when here I'm just considering a 1st-order constraint, so maybe it doesn't even need to be that complex. Under the assumptions of the problem (positive definite matrix, existence of a solution), it's claimed that this algorithm will terminate in a "finite number of steps", so I take that to mean it's not an "iterative method" that approximates, but an exact solution. It doesn't seem too bad but there is some bookkeeping going on with tracking what contacts are "active" or not and updating their state accordingly and the algorithm proceeds to add more constraints one by one. Then there's the problem of adding friction (Baraff's algorithm) which makes things even more ugly so I guess that's why iterative impulse-based methods are preferred to the force-acceleration model. Edit: One final thing I have been searching for an answer on relating to iterative methods, what is "Nonlinear" referring to in "Nonlinear Gauss-Seidel" (NGS)? Is it just "normal" Gauss-Seidel applied to a nonlinear system of equations? If so when does the system of equations become non-linear, is it due to introducing rotation specifically, or does it arise when the constraints are linearly independent? (Linearly independent constraints arises in the 2D or 3D case, but in the 1D case the constraints are collinear if I am thinking about this correctly.)
  2. As an exercise I wrote a solver for a non-peneration constraint of three 1D spheres (intervals). Basically the solution is found by projecting to the nearest surfaces or edges on the configuration manifold. Adding mass to the picture was tricky, but it's possible by intersecting the desired solution lines with the 'mass plane' passing through the initial configuration point. This is a plane with a normal in the direction given by creating a vector with the mass of each sphere for each component. When all the spheres are equal mass, the normal direction is (1.0, 1.0, 1.0) as in the original mass-less case. I think the approach may extend to more than three bodies in 1D but I haven't tried it. Anyway there are $n^2-n$ possible solutions of an n-body system where all bodies are affected (i.e. the solution results in all 'n' bodies in contact, and there are $n^2-n$ possible orders), that might be a not-so-great asymptotic compared to sequential offsets. This was possible to visualize since configuration space for three 1D positions is a 3D space (attached example). Visualizing the configuration space of two or more spheres in 2D or 3D is more difficult since it's either 4D or 6D minimum. One difference with position constraints in 1D is the configuration space is disconnected since spheres must cross through each other to exchange ordering (there's no other dimension to go "around" an obstruction in 1D, you can see this as the six wedge-shaped regions outside the manifold in the attached image). Does anyone know if a closed form solution (using just a finite number of projections, intersections, etc.) is even possible in the 2D (or 3D), for three or more spheres?
  3. PrestoChung

    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.
  4. PrestoChung

    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.
  5. PrestoChung

    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.
  6. PrestoChung

    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).
  7. PrestoChung

    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.
  8. 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?
  9. 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.
  10. 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.
  11. 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?
  12. PrestoChung

    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
  13. 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?
  14. PrestoChung

    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)
  15. PrestoChung

    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.
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!