Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

Member Since 24 Apr 2002
Online Last Active Today, 06:13 PM

#5302390 What Brings About Linear Complementarity Problem In Rigid Body Dynamics?

Posted by on 24 July 2016 - 05:52 PM



I just can't seem to understand the underlying LCP problem, the math things I mentioned above.


Assume you have a 1d LCP of the form: w = a * z - b >= 0 and z >= 0 and w * z = 0


From the complimentary condition w * z = follows that either w or z must be zero  (a product is zero if any of its factors is zero). Let' start with w = 0


w = a * z - b = 0 <=> z = b / a >= 0


We know that a (the effective mass) is larger zero so z is larger zero if b is larger zero. b = -J*v which is positive if the relative velocity is negative (which is the case if the two bodies are approaching each other). If we cannot find a w = 0 and z >= 0 we test the other complimentary condition z = 0:


w = a * 0 - b <=> w = -b >= 0


Again we know that b = -J*v . If the the relative velocity is larger zero than the impulse/force z must be zero. Otherwise we would create a sticky contact. 


For the LCP it really doesn't matter whether you solve for impulses/velocities or forces/accelerations. What is important is how contacts work. You need to look at the problem momentarily. At some instance in time two objects are overlapping and creating a geometric contact (contact points and normals). If the objects are approaching each other the contact impulse/force kicks in and prevents this by removing all relative velocity towards each other. If the objects are overlapping but separating then no contact impulse/force is activated as the objects are already separating. This is the correct physical behavior obviously since there is no resistance if you pick some object up from the ground for example.


In order to understand these things you don't need to read more (this can be often more confusing than helpful), but you need to write down a simple 1d example and put in some feasible numbers and examine what the results mean. Best by hand, second best in the debugger. 

#5302171 What Brings About Linear Complementarity Problem In Rigid Body Dynamics?

Posted by on 23 July 2016 - 09:21 AM


LCP only exist in case of multiple contacts

Nope, this is wrong. The LCP exist even for a single contact point. We need an LCP to model contacts properly, not to handle many contacts.

#5301985 What Brings About Linear Complementarity Problem In Rigid Body Dynamics?

Posted by on 22 July 2016 - 10:59 AM

Think of a ball resting on the ground. The contact point is only active if the ball is accelerating downwards. In the moment you pick it up there is no contact force.

I think the confusion here is about the term linear system. Richard means a system of linear equality equations. You cannot model contact with equality constraints. You model contacts using the Signorini conditions (should also be in the citied paper) which makes the problem an LCP. The LCP is still linear, but with inequalities and the complimetary condition. If you would use a linear condition you would get sticky contacts.

The complimentary condition is what is essential for modeling contacts. If the relative acceleration is larger zero the contact force is zero. Or the contact force is active and removes all relative acceleration.

A good excersise is to solve a 1d LCP and then translate the meaning to the contact problem.

So yes, global LCP solvers can indeed solve this as well. There is a whole lot of problems with overconstrained systems. The four leg table is a good example. The solver can give you mg/2 in two diagonal legs and you would get the correct dynamic response. All variations that create equilibrium are feasible, but we know that we have in each leg a force of mg/4. I think Mirtichs PhD talks a bit about these problems.

#5299649 SAT - Same Plane Triangle

Posted by on 07 July 2016 - 11:46 AM

Thanks, I am glad you like it. If you are interested in these kind of presentations (what your name suggests) you kind find a lot similar presentations on the GDC Physics Tutorial website hosted on Box2D: http://box2d.org/downloads/


Similarly, the GDC Math tutorial has lots of presentations collected over the years as well:


#5299402 SAT - Same Plane Triangle

Posted by on 06 July 2016 - 05:03 PM

Your observation is totally correct! None of the triangle/triangle tests (SAT, Moeller, ...) handle the co-planar case by default iirc, but all rely on handling it as a special case. Sorry, I should have pointed that out. I only read over the SAT part and the possible separating axes.

#5299379 SAT - Same Plane Triangle

Posted by on 06 July 2016 - 03:13 PM



His question demonstrates why there are additional planes/axes to test for beyond the 3*3 edge cross products (and 2 plane normals). For each triangle, besides the main plane, there are also 3 additional planes/axes, totaling 17 (3 * 3 + 3 + 3 + 2). The 3 extra per triangle are the axes constructed with the cross between each edge and the plane normal (for right handed/clockwise triangles). The same reason is there are 15 for OBBs and not merely 9. 


Sorry, what you are writing is simply wrong! You only need to test axes that build a face on the Minkowski sum of the two triangles and there are *exactly* 11 possible separating axes you need test for two triangles. I recommend reading Christer's and Gino's books which are great resources on this topic.


I also gave a presentation on the topic which explains how to identify the possible separating axes (in particular for the edge/edge cases) and how this is related to the Minkowski space. You can download it e.g. here: http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip

#5299348 SAT - Same Plane Triangle

Posted by on 06 July 2016 - 11:27 AM

My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that?


Why are you crossing the normals? As you mention yourself the possible separating axes are the two triangle normals and the 9 pairwise cross products of the edges. 


I also noticed that you are using an absolute tolerance. Christer wrote a good summary of relative and absolute tolerances here:



Another thing to watch out for are sliver triangles which can result in ill-defined face normals. A simple trick to build a robust face normal is to use the two shortest edges in the cross product.

#5295149 Identifying polygons of one mesh inside another mesh?

Posted by on 05 June 2016 - 04:43 PM

Maybe you can use a BSP tree for this. I remember we used this for some project quite some time ago.

#5294898 FBX Transformation problem

Posted by on 03 June 2016 - 11:18 PM

You cannot just use the local translation, rotation, and scaling. You need to use EvaluateLocalTransform() and then decompose.

#5294719 Quaternion as angular velocity

Posted by on 02 June 2016 - 04:38 PM

You can do this all without trig functions. The quaternion derivative is defined as:


dq/dt = 0.5 * w * q 


You can approximate this using the differential quotient:


(q2 - q1) / h = 0.5 * w * q1


Solving for w which gets you from q1 to q2 in h time yields:


w = 2 * (q2 - q1) * conj( q1 ) / h


Here w is pure quaternion containing the angular velocity omega. E.g. w = ( omega.x, omega.y, omega.z, 0 )


This method works great in practice e.g. to initialize ragdoll velocity given two keyframes when switching from animation to physics.

#5291951 Plane equation, + or - D

Posted by on 16 May 2016 - 03:38 PM

I think about planes as being defined by a normal n and a point on the plane p. Then we can define the plane as (read * as dot-product):


P: n * x - n * p = n * ( x - p ) = 0


We can now define d = n * p and get:


P: n * x - d = 0


I thinks this is the more formal definition that you would find it in a textbook. If you use 4D vectors for planes and want to define the distance of a point to a plane using the dot product you would define d = -n * p which yields:


P : n * x + d = 0


I think the 4D vector definition also works well with transformations where you simply multiply the 4D 'plane' vector with a 4x4 transformation matrix (not sure though). Personally I prefer with the more formal definition and use explicit plane functions to evaluate the distance to planes or transform them. If you want to wrap everything into a generic 4D vector the later might be the better choice.




#5290700 Custom editor undo/redo system

Posted by on 08 May 2016 - 02:26 PM

Assume you have decoupled your editor into a scene description (model) and a UI presentation (view), There are now two ways you can implement Undo/Redo:


In the first scenario your scene description (model) doesn't know anything about undo/redo and all changes to the scene inside the UI layer go through commands that are stored on a command stack which can be re-winded. E.g. The scene class has a addNode() function and in the UI you create a command that adds a new node to the scene and removes it again in redo.The Qt Undo framework is indeed a nice example for this approach. This is also a nice blog post on this approach:



In the second scenario the undo/redo is implemented in the model directly. E.g. whenever you change a node the old state is somehow serialized and can be reset if needed. Note that you don't need to store the whole scene, but only the sub-tree that is about to change. The advantage of this approach is that is easier to implement and you cannot mess up undo/redo in the UI by forgetting changing the scene through commands instead of the scene model API. On the downside it is intrusive in the scene description. Mikko has a short blog post about this approach here:





#5289265 Lagrange multiplier in constrained dynamics

Posted by on 29 April 2016 - 10:54 AM

I think you might be a bit to concentrated on the term 'Lagrange Multiplier'. The important part here is that you know the direction of the constraint force is the gradient of the constraint function and you only need to find a scalar multiplier to determine the constraint force. The reason for this is that constraint forces doesn't do work. IIRC you can show this using virtual displacements. Maybe concentrate a bit more on the physical meaning rather than trying to be overly mathematical  abstract.


Thanks! I am glad you found it useful!

#5289162 Lagrange multiplier in constrained dynamics

Posted by on 28 April 2016 - 05:21 PM

I think this is all related to Lagrange's equations (1. kind). You are not minimizing the constraint function but the Lagrange function which (IIRC!) the sum of potential and kinetic energy: 




I always found it difficult to find good material in English on this. In German there are tons of good resources...

#5285455 box-triangle test: how to ignore redundant edges?

Posted by on 06 April 2016 - 11:31 AM

Well, you can mark up your triangle mesh. Check the adjacent faces of a shared edge and mark edges as concave, convex or flat. You can also mark concave vertex. A vertex is concave if at least one adjacent edge is concave. When you check the edges, you simply skip over those that are concave.


I don't think that concave edges should be skipped though. In your example image just move the the lover right vertex of the box such that it is exactly coincident with the concave edge and pressing into it. If you ignore the concave edge you can be pushed out of the world. I assume that have wrong contact geometry and I would debug this first.