Skip to main content
GameDev.net gamedev.net
🔒 Locked

Angular constraints

Started by LGAB Aug 5, 2005 at 12:36 PM 14 replies 10k views
Original Post
LGAB
LGAB
Hello all, I'm seeking a way to have a solid angular constraint for my 2D verlet-based physics sim, it's for making arms and legs not bending in the wrong direction. The search for this has reached near mystical proportions, as I'm now stumped after trying all ideas I can come up with. Finding if the angle is outside it's boundary is simple, but responding to it always make the entire body being jerked, as the other constraints try to compensate for it. I've searched a lot for answers on this topic, but I haven't been able to find any answers, or even a pointer in the right direction, perhaps angles isn't the way to go at all, but I just can't seem to wrap my head around this one - possibly something very simple that I'm just overlooking.. but I need some fresh idea at this point. I bet some of you've seen this floating around the internet: http://pekkasandborg.com/portfolio/?id=2 There's some solid looking angular constraints, and it uses the same base as I do, except that the famous Jacobssen article he mentions doesn't actually stretch as far as explaining angular constraints, so I guess he solved it himself. Any ideas, pointers? Much appreciated.
LGAB
LGAB
Unless I'm missing something, I believe I've tried that, and it sends "shivers" through the rest of the character as it's settling down. Forcefully moving a particle is the same thing as introducing a force, right, so instead of just stopping the particle when it goes to far, it's jerking it back violently, creating wild bounces of the limb in question. I tried moving the "old position" an equal ammount as to preserve velocity, but that didn't seem to help either.. I can't really tell why this is a problem.

edit:
There are 3 particles involved, t1, t2, t3 in this func, for example t1=shoulder joint, t2=elbow, t3=wrist, with vector properties pos, oldpos etc. for verlet
	Vector top = t1.pos - t2.pos; // vector of upper arm	Vector bot = t2.pos - t3.pos; // vector of wrist	float da = top.AngleBetween(bot); // returns angle from -PI to PI	if (da>0) // ie. more than 180 degrees	{		float len = bot.Length(); // store length of wrist		bot = top.UnitVector();   // set to same angle as upper arm		bot.Mult(-len);           // restore length of wrist		t3.pos = t2.pos+bot;      // move wristpoint to elbow+wrist	}


Well, that's what I have at the moment, very jerky indeed :) When the lower limb moves beyond the constraint, there's a violent kick backwards, which brings the entire character with it.

[Edited by - LGAB on August 5, 2005 1:12:21 PM]
LGAB
LGAB
I was using 4, for no particular reason, but even up to 20 there's no change in this particular behaviour..
The code is based on the Jacobsen article, so you can find pseudo code of it there, I've just adapted it to my needs, the integration part is the same, and the part where constraints are satisfied goes something like this..

if (any particles, or any constraints)  for number_of_iterations    for all constraints      case constraint.type        NONE: (do nothing)        NAIL: CnsNail(params)        SPRING: CnsSpring(params)        etc, etc.      /case    /for  /for/if

Nothing spectacular here :)
LGAB
LGAB

Sure no problem, let me know if I was being to unspecific, and I'll elaborate for you! Just trying to spare you from somewhat longish pieces of source code :)

I commented out the Verlet() part of the update, and you're right! It's like dragging the character through mud, but the constrain really works, it stays straight when it should, and bends when it should, so that was very useful!

Now to figure out how to correct this problem with the velocity.. is there a flaw in the integration described by Jacobsen?
LGAB
LGAB

I've tried a bunch of things, but mocking about with the velocity/oldpos invariably results in either violent spinning, or unnatural slow-downs of the feet/hands, so they drag behind instead. I think I've seen all kinds of weird behaviour!
Looking at the code in my second post, how would you change it to take velocity in to account?

Thanks for your efforts!
LGAB
LGAB

I'm afraid I've tried every conceivable combination of what've talked about, none works any better than the original code.
So I'm sort of back to square one with this. I can't help but think there's a different approach to angular constraints, one that's stable and solid regardless of velocities :) I need to do some serious algo-sketching and think this over one more time.

skittleo, your input on this is much, much appreciated! This battle aint over :)
sbroumley
sbroumley
I've solved the angular constraint problem in 3d:
1) a "keep 2 particles at least a min distance apart" constraint for min angle
2) a "keep particle on one side of a plane" constraint for max angle.

You could easily apply a similar solution for the 2d case:

1) a "keep 2 particles at least a min distance apart" constraint for min angle
2) a "keep particle on one side of a line" constraint for max angle.

For example, to keep the lower leg from bending the knee backwards, stop the foot particle from going on the outer side of the upper leg line (hip -> knee particle). To do this, just compute the normal pointing out from the hip->knee line and check to see which side (via the dot product) the foot particle is. Also instead of just moving the foot particle to correct the error, move the foot particle 50% one direction and the knee particle 50% the other direction, otherwise you'll introduce rotational velocity (taking particle mass into account is a simple extension - the ratios will no longer be 50% each)

The big advantage of a "keep on side of plane/line" constraint for a max angle is that it is always stable (ie. the normal of the plane/line never flips). The only tricky part is computing the line/plane normals from the particle configuration, but it all boils down to simple math (cross products in 3d).

Does this make sense?

See this thread for my 3d implementation source:
http://www.gamedev.net/community/forums/topic.asp?topic_id=324795


hope that helps-Steve.
Steve Broumley
LGAB
LGAB
That made a lot of sense! Moving back the knee was the solution! Thanks a lot, I'll see if using your plane/line method is faster or better, but detecting the angle in radians works fine too :)

The revised code is this, in case someone might find it useful in the future:

Vector top = t1.pos - t2.pos;     // thigh/upper armVector bot = t2.pos - t3.pos;     // lower leg/wristfloat da = top.AngleBetween(bot); // angle in -PI to PIif (da>0){	float l = bot.Length();   // store length of wrist	bot = top.UnitVector();   // copy orientation	bot.Mult(-l);             // scale to original length        // difference of where it is, and where it should be:	Vector diff = t3.pos - (t2.pos+bot);        // scale it to half length:	diff.Mult(0.5);        // give knee and foot one push each in opposite dirs:	t3.pos = t3.pos - diff;	t2.pos = t2.pos + diff;}



It's rock solid, thanks a bunch!!!
sbroumley
sbroumley
Cool - glad that worked out.

Isn't it funny how the paper skips the hardest part! I burnt many hours of my life getting verlet ragdolls working - you can keep on tweaking for ever...
Steve Broumley
LGAB
LGAB
Very true.. my ragdoll feels pretty competent now, and I can have hundreds flying around, getting their limbs blasted off :)

  Doll.SplitDoll();  BloodSquirt(Doll.GetJoint(4));


:)
Sphet
Sphet
Quote:
Original post by sbroumley
I've solved the angular constraint problem in 3d:
1) a "keep 2 particles at least a min distance apart" constraint for min angle
2) a "keep particle on one side of a plane" constraint for max angle.

You could easily apply a similar solution for the 2d case:

1) a "keep 2 particles at least a min distance apart" constraint for min angle
2) a "keep particle on one side of a line" constraint for max angle.

...

The big advantage of a "keep on side of plane/line" constraint for a max angle is that it is always stable (ie. the normal of the plane/line never flips). The only tricky part is computing the line/plane normals from the particle configuration, but it all boils down to simple math (cross products in 3d).

Does this make sense?

See this thread for my 3d implementation source:
http://www.gamedev.net/community/forums/topic.asp?topic_id=324795


hope that helps-Steve.


How did you deal with avoiding twisting when determining rotation of objects in 3D from simple particles_
sbroumley
sbroumley
Ah yes - the rendering side of things - which also turns out to be quite tricky. Similar to the max angle constraints, it boils down to basic cross/dot product math.

To extract bone transform matrices from the set of particles for rendering a character mesh, I came up with what I called a set of stick bones. The stick bones represent a skeleton applied on top of the particles. For each stick bone I derived a local to world matrix from the current particle positions.

For orientation of each stick bone, I used the cross product of various particle positions (be prepared to scribble lots of little diagrams) and the start/end can be derived directly from the positions of the particles.

Once the local to world transforms have been computed for all the stick bones, you can then map a geometry skeleton heirarchy directly onto them to use for rendering (the character skeleton may have more geometry bones than stick bones - to solve this, just attach each geometry bone to the nearest stick bone using a simple bind offset matrix).

See below for the stick bone code. Once you've figured out how to compute the rotation and translation for one stick bone, you'll soon get the hang of the rest. To help you on your way, make sure you draw plenty of debug information (an XYZ axis, and start/end/mid position for each stick bone) to make sure you have your math correct. The arms are the trickiest part to get correct.

Hope that shines some more light on the problem for you...
-Steve.



//==============================================================================// Here's the stick bone class - it basically contains a local to world matrix// which is used to render the attached geometry//==============================================================================class stick_bone{// Datapublic:    matrix4     m_L2W;             // Local->World matrix    vector3     m_Start;            // Start of bone    vector3     m_End;              // End of bone    const char* m_pName;           // Name of stick bone    xcolor      m_Color;           // Debug color of stick bone// Functionspublic:    // Constructor         stick_bone();    // Initialization    void Init( const char* pName, xcolor Color );    // Updates stick bones axis and position. (normalizes axis)    void Update( const vector3& BoneAxisX,                  const vector3& BoneAxisY,                  const vector3& BoneAxisZ,                  const vector3& BoneStart,                  const vector3& BoneEnd );    // Returns local->world matrix    matrix4& GetL2W( void );        // Renders the stick bone    void Render( void );    };//==============================================================================// Here's the function to update a stick bones world space info// It gets called from "ragdoll::UpdateStickBones()"//==============================================================================void stick_bone::Update( const vector3& BoneAxisX,                          const vector3& BoneAxisY,                          const vector3& BoneAxisZ,                          const vector3& BoneStart,                          const vector3& BoneEnd ){    // Setup rotation    vector3 AxisX = BoneAxisX;    vector3 AxisY = BoneAxisY;    vector3 AxisZ = BoneAxisZ;    AxisX.Normalize();    AxisY.Normalize();    AxisZ.Normalize();    m_L2W.SetColumns( AxisX, AxisY, AxisZ );    // Setup position    m_L2W.SetTranslation( BoneStart );    // Keep end points for debug rendering    m_Start = BoneStart;    m_End   = BoneEnd;}//==============================================================================// These structures are defined inside the ragdoll class to keep track of things//==============================================================================struct particle{    vector3         m_Pos;             // Current position of particle    f32             m_InvMass;         // Reciprocal mass of particle (1.0f / Mass)    f32             m_Mass;            // Mass of particle    vector3         m_LastPos;         // Last frame position of particle    const char*     m_pName;           // Name of particle    xcolor          m_Color;           // Debug color of particle};struct joint_side{    particle*   m_pFoot;    particle*   m_pKnee;    particle*   m_pHip;    particle*   m_pTorso;    particle*   m_pShoulder;    particle*   m_pElbow;    particle*   m_pWrist;};struct joints{    joint_side  m_Side[2];    particle*   m_pNeck;    particle*   m_pHead;};struct stick_bone_side{    stick_bone  m_Foot;    stick_bone  m_Calf;    stick_bone  m_Thigh;    stick_bone  m_UpperArm;    stick_bone  m_Forearm;    stick_bone  m_Hand;};struct stick_bones{    stick_bone_side m_Side[2];    stick_bone      m_Hips;    stick_bone      m_Torso;    stick_bone      m_Chest;    stick_bone      m_Head;    s32 GetCount( void )    {        return (sizeof(stick_bones) / sizeof(stick_bone));    }    stick_bone& operator [] ( s32 Index )    {        ASSERT(Index >= 0);        ASSERT(Index < GetCount());        return ((stick_bone*)this)[Index];    }};//==============================================================================// This is the relevant data inside the ragdoll class//==============================================================================    // Physics components    particle                m_Particles[MAX_PARTICLES];    s32                     m_NParticles;    stick_bones             m_StickBones;    joints                  m_Joints;//==============================================================================// Here's the function to update all stick bones from the // current particle positions//==============================================================================void ragdoll::UpdateStickBones( void ){    vector3 AxisX, AxisY, AxisZ, Start, End;    // Setup both sides    for (s32 i = 0; i < 2; i++)    {        f32                 Side   = (i == 0) ? 1.0f : -1.0f;        joint_side&         Joints = m_Joints.m_Side;        stick_bone_side&    Bones  = m_StickBones.m_Side;                // Thigh        Start = Joints.m_pHip->m_Pos;        End   = Joints.m_pKnee->m_Pos;        AxisZ = End - Start;        AxisX = AxisZ.Cross(m_Joints.m_Side[1].m_pHip->m_Pos - m_Joints.m_Side[0].m_pHip->m_Pos) * Side;        AxisY = AxisX.Cross(AxisZ);        Bones.m_Thigh.Update(AxisX, AxisY, AxisZ, Start, End);        // Setup leg plane "out"        AxisX = AxisX.Cross(AxisZ);        // Calf        Start = Joints.m_pKnee->m_Pos;        End   = Joints.m_pFoot->m_Pos;        AxisZ = End - Start;        AxisY = AxisX.Cross(AxisZ);        Bones.m_Calf.Update(AxisX, AxisY, AxisZ, Start, End);        // UpperArm        Start = Joints.m_pShoulder->m_Pos;        End   = Joints.m_pElbow->m_Pos;        AxisZ = End - Start;        AxisX = Joints.m_pTorso->m_Pos - Joints.m_pShoulder->m_Pos;        AxisY = AxisZ.Cross(AxisX);        AxisX = AxisZ.Cross(AxisY);        Bones.m_UpperArm.Update(AxisX, AxisY, AxisZ, Start, End);                // Forearm        Start = Joints.m_pElbow->m_Pos;        End   = Joints.m_pWrist->m_Pos;        AxisZ = End - Start;        AxisY = AxisZ.Cross(AxisY);        AxisX = AxisY.Cross(AxisZ);        Bones.m_Forearm.Update (AxisX,  AxisY,  AxisZ,  Start, End);    }    // Hips    Start = (m_Joints.m_Side[0].m_pTorso->m_Pos + m_Joints.m_Side[1].m_pTorso->m_Pos) * 0.5f;    End   = (m_Joints.m_Side[0].m_pHip->m_Pos   + m_Joints.m_Side[1].m_pHip->m_Pos)   * 0.5f;    AxisZ = End - Start;    AxisX = m_Joints.m_Side[1].m_pTorso->m_Pos - m_Joints.m_Side[0].m_pTorso->m_Pos;    AxisY = AxisZ.Cross(AxisX);    m_StickBones.m_Hips.Update(AxisX, AxisY, AxisZ, Start, End);        // Torso    Start = (m_Joints.m_Side[0].m_pShoulder->m_Pos + m_Joints.m_Side[1].m_pShoulder->m_Pos) * 0.5f;    End   = (m_Joints.m_Side[0].m_pTorso->m_Pos    + m_Joints.m_Side[1].m_pTorso->m_Pos)    * 0.5f;    AxisZ = End - Start;    AxisX = m_Joints.m_Side[1].m_pShoulder->m_Pos - m_Joints.m_Side[0].m_pShoulder->m_Pos;    AxisY = AxisZ.Cross(AxisX);    m_StickBones.m_Torso.Update(AxisX, AxisY, AxisZ, Start, End);        // Chest    Start = m_Joints.m_Side[0].m_pShoulder->m_Pos;    End   = m_Joints.m_Side[1].m_pShoulder->m_Pos;    AxisZ = End - Start;    AxisX = m_Joints.m_pNeck->m_Pos - ((m_Joints.m_Side[0].m_pTorso->m_Pos + m_Joints.m_Side[0].m_pTorso->m_Pos)*0.5f);    AxisY = AxisZ.Cross(AxisX);    AxisX = AxisZ.Cross(AxisY);    m_StickBones.m_Chest.Update(AxisX, AxisY, AxisZ, Start, End);    // Head    Start = m_Joints.m_pNeck->m_Pos;    End   = m_Joints.m_pHead->m_Pos;    AxisZ = End - Start;    AxisX = AxisZ.Cross(m_Joints.m_Side[0].m_pShoulder->m_Pos - m_Joints.m_pNeck->m_Pos);    AxisY = AxisZ.Cross(AxisX);    m_StickBones.m_Head.Update(AxisX, AxisY, AxisZ, Start, End);}
Steve Broumley
Sphet
Sphet
Thank you for your reply.

I am doing the exact same thing. I have a skinned mesh. I create a particle for each bone I want to simulate. I am never simulating the whole thing, only ponytails and such. After I simulate my particle, which involves angular constraints, I create a matrix to represent the location and orientation of each bone. Z twisting is the biggest issue here and I can only solve it using "magic untwist matrices". Also, deriving the angular constraints is frustrating because they have to be accumulated along the hierarchy since the angular constraint is relative to the parent, not world space.

Process without rotational constraints:

- Simulate the particles, with length constraints.
- For each particle, subtract it´s position from it´s parent to define a forward vector, guess at a right vector and cross for an up vector. This gives me a rotation. Poke in the translation and use this for drawing.

This works, of course, but I get rotation around the forward axis that does not match my skin mesh. Somehow I need to constrain rotation around the forward vector as i recreate the rotation matrix. Any thoughts on this?

It gets worse when I need to think about constraints of rotation. Since rotation is relative to the parent, I have to create the rotation matrix just to get the constraint space. Again, while visually it does not matter since I am not drawing with the constraint space matrix, I need to have a valid forward, right and up vector since I need to constrain differently in each axis.


Have you done this kind of thing before, or thought about it at all. Anyone else? Sadly I am miles from home without my code so I can only think about this theoretically, but it is a task that remains once I return from vacation.

Any thoughts on this would be great.

- S
sbroumley
sbroumley
I'm thinking the problem you mention could be solved in a similar way I solved computing the matrices for the upper and lower arm of the ragdoll bones.

Instead of constructing a guess at a side or forward vector for each set of particles, only do it for the first particle set, then pass on one of the vectors when computing the axis for the next particle set in the chain.

Psuedo code would be something like (this is not tested, just theory!):


// Assume you have "m_nParticles" in array "m_Particles" // This equates to "m_nParticles-1" bone matrices in array "m_BoneMatrices"// Compute local to world matrices for bone chainvetor3 AxisX, AxisY, AxisZ;for( i = 0; i < m_nParticles-1; i++ ){    // Lookup next set of particles    particle& P0 = m_Particles;    particle& P1 = m_Particles[i+1];    // Compute 3 axis for particle(0)?    if( i == 0 )    {        AxisY = P1.GetPosition() - P0.GetPosition();    // Compute "up" dir        AxisX = Guess initial side direction... ( 1, 0, 0  or something )        AxisZ = Cross( AxisX, AxisY );  // Compute "forward" dir        AxisX = Cross( AxisY, AxisZ );  // Re-compute final "side" dir    }    else    {        // Compute 3 axis for particle(i)        AxisY = P1.GetPosition() - P0.GetPosition();    // Compute "up" dir        AxisX = Cross( AxisY, AxisZ );  // Compute "side" dir using "forward" dir from previous link        AxisZ = Cross( AxisX, AxisY );  // Re-compute final "forward dir    }    // Setup bone local to world matrix    matrix4& BoneL2W = m_BoneMatrices;    AxisX.Normalize();    AxisY.Normalize();    AxisZ.Normalize();    BoneL2W.SetRotation( AxisX, AxisY, AxisZ );    BoneL2W.SetTranslation( P0.GetPosition() );}


[Edited by - sbroumley on August 8, 2005 1:08:18 PM]
Steve Broumley
Sphet
Sphet
Thanks, that is what I have been doing and it seems to work - thank you for your input. What do you do if the forward vector is rotated so much that it lies along the right or up vector?
sbroumley
sbroumley
You would have have to test for that case explicitly. Maybe if it happens, you could use the result from the previous frames "AxisY" for bone(0) when choosing an initial "side" vector (in the case of the code below) to avoid sudden geometry flips. In the code below it would just be a matter of testing the sign of the Y component of AxisY and then setting AxisX to either (0,1,0) or (0,-1,0) - depending upon your cross product it could also be (0,0,1) or (0,0,-1).

That reminds me, you might also have to check to see if 2 particles are almost on top of each other in each "P1.GetPosition() - P0.GetPosition()" or you'll run into problems. If that happens you may have to offset them by a random amount or something.

I hope that helps. Do you have any demos or screen shots we could see?

-Steve.


Steve Broumley

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.