Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

Member Since 24 Apr 2002
Offline Last Active Yesterday, 05:53 PM

#5308403 Resolving and Remembering Collisions

Posted by on 28 August 2016 - 07:22 PM

After you compute a TOI you need to make sure to move the shapes 'close enough' such that the contact generation doesn't fail. E.g. the classical error is to advance the shapes to the determined TOI and when running the contact creation routine you end up an empty manifold. This will lead to the object tunneling out of the world even though you determined the correct TOI. In order to to handle this my contact creation routing considers shapes withing some margin touching and builds the manifold. I use an adjusted SAT which can handle small separations. 


For me the major source of failure in the TOI computation using any form of conservative advancement was the GJK. If you run a GJK with some epsilon tolerance to support e.g. quadric shapes you run into a numerical nightmare with 32bit floating precision. So in Rubikon I only support spheres, capsules, hulls and meshes and the GJK implementation continues until it doesn't make any absolute progress getting me as close as possible. With this I haven't seen any numerical problems in practice. Note that spheres can be handled as points and capsules as segments and the radius is handled afterwards.


Erin's GJK and TOI actually address these problems, though they might not be explicitly mentioned here:




I gave a presentation a GDC on contact creating in general which might also be helpful:



Finally I recommend studying the Box2D continuous physics solution. It addresses a lot of problems with continuous physics. You will find a great example of sub-stepping there as well which I didn't discuss in my answer here.




#5305644 need a algorithm to update skin mesh global AABB

Posted by on 13 August 2016 - 11:52 AM

Usually the artists also define a worst-case AABB which gets exported with the model. This AABB would fully contain the model in every possible pose. You really don't want to update the AABB at runtime.

#5303892 How To Correctly Caluclate Compression Speed For Damping?

Posted by on 03 August 2016 - 08:07 PM

I would think the relative velocity along the spring axis.

#5302835 Stackoverflow And Money

Posted by on 27 July 2016 - 07:34 PM

This is a solid pay, but you can make 2-3 times of this in the US as programmer (base salary, bonus and stocks). 

#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.