Jump to content

  • Log In with Google      Sign In   
  • Create Account

Dirk Gregorius

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

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


#5001654 What side skills are essential / noteable plusses for becoming a game physics...

Posted by Dirk Gregorius on 16 November 2012 - 04:16 PM

Erin talks about a bunch of solver stuff in his presentation. His first presentation is called "Iterative Dynamics" essentially explains the ODE quickstep solver. A later presentation talks about sequential impulses. You can find his presentations here: http://code.google.c.../downloads/list

For solvers I recommend looking into "Computational Dynamics" by Shabana. Also the PhD thesis of Kenny Erleben is quite good It is also a great explanation of the ODE quickstep solver. http://image.diku.dk...n.05.thesis.pdf

Note that they are essentially three kind of solvers. Position based solvers (sometimes refereed to as Verlet solvers) which are usually used in cloth simulation. Look at the original Jakobsen GDC paper on this. Also Mueller has a nice paper called Position-Based Dynamics. Next you have the velocity based solvers which are currently used in all game rigid-body simulators out there - to my best knowledge. Finally there are the acceleration based solvers which are expalined quite nicely in the Baraff papers, but they are not very frequently used in games. They are *maybe* more important in engineering, but I am not sure what the current state of the art is there. Alygoryx uses the Spook solver as developed in Claude's PhD if I understand them correctly and this is also a velocity based approach.

Helmut describes some difference in his Master thesis pretty well. You can find it here: http://www.digitalru...dy Dynamics.pdf

Here are the papers about Spook: http://www8.cs.umu.s.../spooknotes.pdf
This is the course at Umea I recommended: http://www8.cs.umu.s...dv058sched.html

Enjoy! Posted Image

Jacobsen: http://www8.cs.umu.se/kurser/5DV058/VT09/lectures/JacobsenGDC2003.pdf
Mueller: http://www.matthiasmueller.info/

#5001594 What side skills are essential / noteable plusses for becoming a game physics...

Posted by Dirk Gregorius on 16 November 2012 - 12:22 PM

I worked as physics programmer my whole career. Initially I implemented a physics engine for Lair - on the PS3. After this I worked at Havok in the destruction and physics team. After some time as freelancer where I most mentionable implemented a bunch of subsystems (contact creation and solving) for Ubisofts inhouse Motion engine which is now used in e.g. Ghost Recon. Lately I integrated Blizzard inhouse engine used in Diablo 3 into Starcraft 2 - Heart of the Swarm. Now I am at Valve and do physics again :)

From my experience there are two things. Physics engine development and physics engine integration. Usually people are somewhat familiar with one the two though I argue it definitely helps to understand both ends. Obviously understanding the limitations of physics engines helps with integrating them. On the other end understanding the common requirements of a game engine helps with implementing the needed features in a physic engine.

For writing physics engines there is indeed not much bundled information out there. There is lot of information and there is a lot of useless information. I think in the first years I spend a lot of time reading through useless crap, picking up a gem every here and there. If you want to learn about physics engines I recommend taking Box2D Lite and port it to 3D. Then iterate from there with broadphases, block solvers, different friction, contact models or whatever interest you. One thing that is is really important is that the requirements for physics engines are changing. From my experience constraint solvers and ragdolls are nice, but what is much more important is is fast collision detection. This includes containment queries and any kind of casting rays, boxes, capsules, etc. So usually when you become a physics programmer you also become an expert on collision detection. Another thing that is always forgotten (even in some commercial packages until more recent times) is geometry processing. E,g convex hulls, convex hull simplification or convex decomposition. A solid understanding of computational geometry is very helpful.

For the integration part this is usually setting up the game engine to route collision queries through the physics system and attach it to the animation system. E.g. switching to ragdolls from animations and inherit the velocity. Or drive to some pose from where ta character can stand up. So on this end a good idea of a general game engine workings and of course the animation system in particular is very helpful.

Regarding your question about graphics programming I have a solid understanding of OpenGL and DirectX, but I would not be able to write a deferred renderer without some upfront reading into this topic. And to be honest this was never required. Usually you setup a simple rendering for your testbed for your physics engine which is quite trivial or you setup the current render system in the game to do your debug rendering. Personally I found that the better graphics programmers always a some artistic understanding which I am missing totally.

So if you want to learn physics programmer I recommend looking into Box2D and all of Erin Catto's presentations. Get something up and running and then experiment with this. A good start is a simple pendulum and a falling sphere. Then a box, a stack, etc. Don't try to reinvent everything, but make sure you understand the current state of the art first including its limitations.

Besides Erin's work you can also look for publication of Claude Lacoursiere. He was one of the initial engineers on the ODE while it was developed at MathEngine and he has put some good lectures out there at Umea (a swedisch university). You can google for "Spook" as well in the context.

For collision detection I recommend the books from Gino v.d. Bergen and Christer Ericson.

I hope this helps a bit. Good luck!

#4893567 Define a plane knowing a point and the normal

Posted by Dirk Gregorius on 13 December 2011 - 11:32 AM

A plane isdefined like P: n*x - d = 0

Given a point on the plane and a plane normal the plane can be defined as: n*x - n*p= 0
(Note that bold letter indicate vectors and * is the dot product)

#4878314 3D physics engine.

Posted by Dirk Gregorius on 29 October 2011 - 02:47 PM

I recommend looking into "Game Engine Architecture" and you can also google for Entity / Actor Systems or Game Objects.

I encourage you to write your own physic engine and a good start might the presentations by Erin Catto. You can also use Box2D Lite as an orientation. I assume that you have a reasonable mathmaetical background and are familiar vector calculus and dynamics (somewhere on a university level). If you don't have these prerequisites you can still try it, but it will have a very steep learning curve. Another thing to consider is to use Havok (3D) or Box2D (2D). You will learn a lot just from integrating and using these libraries.


#4845187 Relative angles with dot product (2D)

Posted by Dirk Gregorius on 05 August 2011 - 02:00 PM

You could simply do this:

angle = atan2( abs( cross( v2, v1 ), dot( v2, v1 ) );