Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

Member Since 24 Apr 2002
Offline Last Active Aug 28 2014 05:14 PM

#5161516 Explosive tangent impulses causes extreme rotation

Posted by Dirk Gregorius on 19 June 2014 - 10:30 AM

I recommend starting from Box2D *Lite*. Then you can start playing around from a working solution. Regarding the changes you made to Box2D I wonder what problem you try to solve and where you think your solution is better. I personally would only make such changes if it solves a particular problem while not breaking anything else.

#5160144 Spline Ik and Fullbody Ik

Posted by Dirk Gregorius on 12 June 2014 - 03:52 PM

I am looking for some references on Spline Ik and Fullbody Ik. I found tons of good material on basic Ik solvers like Jacobian methods, CCD, analytical and particle methods, but I failed to find anything about these two topics. I must assume I lost my Google Fu :)


For Spline Ik my understanding is that your are given a bunch of joint pivots and find a curve through all these points. Then while moving the spline control points you reconstruct the bone chain. There are some tricky details for the twist.


Fullbody Ik seems to combine different kinds of Ik solvers (e.g. spline solver for the spine, and maybe analytical methods for arms, etc) and then solve those in some hierarchical way with constraints between the Ik handles.


Any information is welcome! Thanks!

#5155675 Sequential Impulse Solver and Sliding Contacts

Posted by Dirk Gregorius on 24 May 2014 - 10:50 AM

There are two things with position solvers. 


1) Friction and motors are usually modeled as velocity constraints. It is tricky to do this on the position level

2) If you solve on the position level you need to solve a non-linear system. Solving on the velocity level is a linear problem. Also constraint equations and Jacobians are functions of the positions and orientations. So you need to re-evaluate them while you iterate over them. This is *pretty* costly. On the velocity level they remain constant and can be pre-computed. For particle systems it is a great choice though. Check all the Position-Based-Dynamics (PBD) work by Mueller and the original presentation by Jacobsen using Verlet integration.


If you really want to understand what is going on, here are a couple of links:






Everything from Erin Catto here:



These are good as well:




Finally you can read also everything from David Baraff and Brian Mirtich. Just google for those names


If you want to write your own physics engine I recommend starting from Box2D Lite and then port it slowly over to 3D. Once you have the basic understanding you can improve broadphase, collision detection, contact persistence, etc. based on you personal preferences. You can use the real Box2D as guidance then


Edit: Here are links to the Mueller and Jacobsen papers




For a formal background look into technical mechanics books or online lectures.


Happy studying! :)

#5155466 Sequential Impulse Solver and Sliding Contacts

Posted by Dirk Gregorius on 23 May 2014 - 09:41 AM

Yes! You first solve the velocities. The projection steo give you the 'best' velocities to advance to the positions. Then you correct positions. I would not re-run the collision detection though, but keep contact points local and measure the penetration along the normal. 


Again, I recommend having look at Box2D and Box2D Lite.

#5155141 Sequential Impulse Solver and Sliding Contacts

Posted by Dirk Gregorius on 21 May 2014 - 05:19 PM

First I would make sure that your tangent doesn't go to zero when the relative velocity vanishes. What is the impulseMag? Is this the incremental or the accumulated impulse? You need to clamp against the accumulated impulse.


I would clamp the friction impulse like this (assuming impulseMag > 0) :

frictionImpulse = clamp( frictionImpulse, -curContact->friction * impulseMag, curContact->friction * impulseMag );

#5143727 Support Vector

Posted by Dirk Gregorius on 01 April 2014 - 10:26 AM

The support point is the furthest (extreme) point in a given direction:

int Support( const std::vector< vector2 >& vertices, const vector2& vDirection )
  float flBestDistance = -FLT_MAX;
  int nBestVertex = -1;

  for ( int nVertex = 0; nVertex < nVertexCount; ++nVertex )
    float flDistance = DotProduct( vertices[ nVertex ], vDirection );
    if ( flDistance > flBestDistance )
      flBestDistance = flDistance;
      nBestVertex = nVertex;

  return nBestVertex;

#5128780 Unity-like transform component

Posted by Dirk Gregorius on 04 February 2014 - 12:37 PM

I like how joints in Maya handle scale. Essentially the scale doesn't propagate down to the children. I recently needed to work with Maya and while their SDK is definitely ugly, you will find a lot of interesting things.


Here are some references:




#5128638 Unity-like transform component

Posted by Dirk Gregorius on 03 February 2014 - 11:37 PM

I wonder how Unity does this. If they support non-uniform scaling they cannot decompose necessarily only into TRS. They might be also a shear component like in Maya.

#5126846 Naming conventions for math statements

Posted by Dirk Gregorius on 27 January 2014 - 07:04 PM

I like to distinguish between game code and low level code. In game code I also use longer names like e.g. a descriptive player_position over just 'p'. For my low level collision or physics routines I prefer short names as I derived them on paper. I usually check in theses paper with the code and add a reference in the code. Then those can be used for debugging. E.g. a function to compute the intersection between a ray and a triangle would look like this:


float IntersectRayTriangle( Vector A, Vector B, Vector C, Vector P, Vector Q ). 


If you need functions that take a triangle or ray structure you just overload the function and delegate to the leaf code function. Personally I found this very convenient to work, but YMMV.


As the point came up here I personally recommend against using a special point class. I have to use this lately a lot inside the Maya SDK and find this more confusing than helpful. E.g. you get the translation from a transformation matrix as vector and pass this as position (a point) for e.g. a manipulator you have to convert between types for this. Also the overloading of a multiplication operator between vectors and points which ignores the translation in the first place is very error prone. In this case I prefer explicit functions of the form TransformVector( Matrix m, Vector v ) and TransformPoint( Matrix m, Vector p ). This is my personal preference and it worked well for me, but again YMMV.


In general I find most most libraries that are available as open source these days way over-engineered for such a simple problem like a math library. E.g. using templates and extra point classes and what not else. 

#5094383 Advanced collision detection technique resources

Posted by Dirk Gregorius on 15 September 2013 - 10:46 PM

Sorry Serumas, but this is not correct. E.g Box2D has what is called a TOI solver to handle collisions in the order in which they occur. Ipion (the physics engine used in Half-Life 2 and which later was merged into Havok) had one as well. Havok also solves TOI events. I am also aware of other in-house physics engines which solve TOI events.


If you want to have a look at an example TOI solver I recommend looking at Box2D source code. Check b2World::SolveTOI()

Erin also gave a great presentation this year at the GDC how to calculate the TOI between two objects. It is an improvement of the Conservative Advancement method suggested by Mirtich.


You can find the downloads here: https://code.google.com/p/box2d/downloads/list

#5089291 GJK Simplex Caching and Circles

Posted by Dirk Gregorius on 26 August 2013 - 03:40 PM

Correct, you get the closest point between the sphere center (or capsule segment) and the polygon/polyhedra and then move the closest point onto the sphere (or capsule) surface.  


I think some sample code makes this clearer:

ClosestPointsResult result = FindClosestPoints( pSphere, pPolyhedra );

if ( result.m_flDistance > pSphere->Radius() )
   // Shallow penetration - correct for sphere radius and move closest point onto sphere surface
   float flSeparation = result.m_flDistance - pSphere->Radius();
   Vec3 vClosestPointOnSphere = result.m_vPoint1 + pShere->Radius() * Normalize( result.m_vPoint2 - result.m_vPoint1 );
   Vec3 vClosestPointOnPolyhedra = result.m_vPoint2;
    // Deep penetration -> do something else...

#5089082 GJK Simplex Caching and Circles

Posted by Dirk Gregorius on 25 August 2013 - 11:00 PM

Yes, GJK has severe numerical issues in 32 bit floating point math. I would not use it for anything else but polyhedra. Both Christers and Ginos books explain the details. For sphere and capsule I use the center point and segment while adding the radius afterwards.

#5088115 "Each vs. any" collision shape implementation

Posted by Dirk Gregorius on 22 August 2013 - 09:49 AM

Note that you can also have a simple matrix of function pointers. 

typedef void (*rnCollideFunc)( rnManifold&, const rnTransform&, const rnShape*, const rnTransform&, const rnShape* );
static const rnCollideFunc CollisionMatrix[ RN_SHAPE_COUNT ][ RN_SHAPE_COUNT ] =
	{ rnCollideSpheres, rnCollideSphereCapsule,  rnCollideSphereHull,  },
	{ NULL,             rnCollideCapsules,       rnCollideCapsuleHull, },
	{ NULL,             NULL,                    rnCollideHulls,  NULL },
	{ NULL,		    NULL,		     NULL,		   }

And then you simply call the function like this:

RN_ASSERT( Shape1->GetType() <= Shape2->GetType() );
rnCollideFunc Collide = CollisionMatrix[ Shape1->GetType() ][ Shape2->GetType() ];
Collide( Out, Transform1, Shape1, Transform2, Shape2, Cache );

You usually have a contact class which holds the pointers to the shapes. If you sort them on construction such that Shape1->GetType() <= Shape2->GetType() you don't need to deal with the lower collision matrix. I am using this for years and always liked its simplicity. IIRC I took this idea from the ODE.


As a side note: Someone above suggested to swap the pointers. You usually have the convention that the contact normal points from A -> B (or vice versa). So don't forget to invert the orientation of the normal as well when you flipped pointers.

#5087734 Enforce Angle Limits On a Quaternion

Posted by Dirk Gregorius on 20 August 2013 - 10:11 PM

I also recommend normalizing at the end when using the quaternion derivative:

(quat) qrotation.Normalize();

(quat) qspin = quat(0.0, angVelocity) * 0.5 * qrotation;

qrotation += spin * dt;   // current orientation


Should be:


(quat) qspin = quat(0.0, angVelocity) * 0.5 * qrotation;

qrotation += spin * dt;   // current orientation

(quat) qrotation.Normalize();

#5087733 Enforce Angle Limits On a Quaternion

Posted by Dirk Gregorius on 20 August 2013 - 10:07 PM

First note that you integration is not correct:


You are multiplying the angular momentum from the *end* of the timestep with the inertia tensor from the *beginning* of the timestep. The inertia is a function of the orientation. In formulas:

omega( t + dt ) = InvInertia( t + dt ) * L( t + dt ) 


You have:

omega( t + dt ) = InvInertia( t ) * L( t + dt ) 


The is the essentially the same as dropping the gyroscopic term when integrating angular velocities.


To enforce your limits you need to decompose your quaternion into orthonormal factors (google for swing-twist decomposition) and then enforce the limit on your axis.

Given your quaternion q = ( x, y, z, w ). You decompose into q = q_xy * q_z where q_z = ( 0, 0, z, w ) / sqrt( z^2 + w^2 ) and q_xy = q * conjugate( q_z ). Then you apply the limit and multiply by q_xy.