Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

Member Since 24 Apr 2002
Offline Last Active Apr 03 2014 03:55 PM

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




#5085072 2d rigid body colision response physics with friction

Posted by Dirk Gregorius on 11 August 2013 - 07:58 PM

You question is too general. You should try a more specific question what point of the theory you don't understand. Did you look into some of these links here at GameDev.net:



The Bullet forum has a similar section:



You will have to study some of these references and then you can ask about specifics you are not understanding. This is in my opinion the best way to use forums.

#5085066 Separating Axis Theorem In 3D

Posted by Dirk Gregorius on 11 August 2013 - 06:52 PM

I gave a presentation on the topic (3D) this year at the GDC. You can download it (plus sample code) here: https://code.google.com/p/box2d/downloads/list

You might also find Christer Ericson's presentation (and book) helpful: http://realtimecollisiondetection.net/pubs/

#5084595 2d rigid body colision response physics with friction

Posted by Dirk Gregorius on 09 August 2013 - 09:20 PM

Just out of curiosity - what is wrong with the "muddy" Box2D source? It has plenty plenty of derivations in the comments as well? Actually I collaborated implementing the 2x2 block solver. So I wonder what you think is bad about it.

#5082817 Volume of the clipped shapes

Posted by Dirk Gregorius on 03 August 2013 - 01:56 PM

DId you see Erin Catto's article in GPG 6? It comes with source code as well which can be downloaded from the Box2d site. From the shapes you mention capsules are pretty hard. You might consider to approximate this with a simple box.

#5057027 Fluid Dynamics Books

Posted by Dirk Gregorius on 26 April 2013 - 11:40 AM

This book is pretty good:



Bridson gave a course at Siggraph which contains a lot of this material. You can have a peek there before you buy the book:



This page sites a lof of publications from Siggraph and other conferences. You can search there as well: