Sign in to follow this  
johnstanp

3D steering for an unconstrained rigid body

Recommended Posts

The 2D case is generally explained but not the 3D one. I need a 3D steering algorithm to implement flocking for a group of objects flying freely. I also basically have no idea about the way one would implement an average orientation( in 3D ), nor make a rigid body iteratively be oriented that way. [Edited by - johnstanp on March 8, 2010 1:33:30 PM]

Share this post


Link to post
Share on other sites
It's pretty easy to average what ever property you're interested in. If you want them all to face the same way they average their facing direction. If you also want their "up" vectors to follow the group then you'll need to steer that property also.

Given the groups average facing direction and the current object's facing direction you can compute a quaternion which will rotate the latter onto the former. Scale this by your steering factor and combine it with your current orientation.

Share this post


Link to post
Share on other sites
I think this is a good question. Here's how I'd go about doing it... first conceptually, then practically:

I am agent i. My orientation, R_i, is an element of the manifold SO(3) (the rotation matrices). I have N neighbors, with orientations Q_1,...,Q_N also in SO(3). What I will do is,
1 - figure out what the tangent vectors to the shortest geodesics in SO(3) are from R_i to each of Q_1,...,Q_N.
2 - average these tangent vectors
3 - adjust my orientation in this direction

In the above, the tangent vectors to SO(3) are just skew-symmetric matrices (or equivalently just triplets of numbers, since a skew-symmetric matrix only has three unique elements; the hat operator (screw theory) and its inverse convert back and forth between these representations).

Step #1 is done in the following way: Just compute the transformation that will take R_i to Q_j (for each j); this is M_ij = Q_j R_i^T, which is also an element of SO(3). Then take a particular matrix logarithm of M_ij (given here) to get the tangent vector. ("matrix logarithm" in this case is really just fancy-speak for "axis-angle representation of M_ij")

As for step #3: You can either just do a predictor-corrector step; e.g.,
1 - Update with euler integration step
2 - Snap back to SO(3) (e.g., by polar decomposition, or approximately by Gram-Schmidt)
--- OR ---
you can compute the matrix exponential of the tangent vector you got in step #2; the special case of the matrix exponential for 3x3 skew-symmetric matrices is given by Rodrigues' formula.

To summarize, you're basically just simulating the following ODE,

(d/dt)R_i = (1/N)[log(Q_1 R_i^T) + log(Q_2 R_i^T) + ... + log(Q_N R_i^T)]

[EDIT: I'd left out the 1/N factor before... not that it really matters, since the timescale is arbitrary.]

in a way that makes sure that cumulative errors don't eventually take you off SO(3) (in which case, in other words, R_i would no longer be a rotation matrix).

=====

Also... although everything I said was in terms of rotation matrices, you can do the equivalent thing with quaternions. It will make the "snapping back to the manifold" part very simple at least...

If you want to do it with quaternions, then the tangent vector is just the tangent vector to the unit 3-sphere embedded in 4-space; the tangent space at p is just all the vectors orthogonal to p...

[Edited by - Emergent on March 9, 2010 7:28:27 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by bzroom
It's pretty easy to average what ever property you're interested in. If you want them all to face the same way they average their facing direction. If you also want their "up" vectors to follow the group then you'll need to steer that property also.

Given the groups average facing direction and the current object's facing direction you can compute a quaternion which will rotate the latter onto the former. Scale this by your steering factor and combine it with your current orientation.


Well, after thinking about it, I see quite well, what is the average orientation, in 3D. It became obvious when I understood that:

the sum over i of ai(i=1,.., N) is orthogonal to the sum over i of bi(i=1,...,N), bi being orthogonal to ai(i=1,..,N)

That basically means that I could simply do:


average_orientation=zero

for each boid
average_orientation.x_axis += boid.orientation.x_axis
average_orientation.y_axis += boid.orientation.y_axis
average_orientation.z_axis += boid.orientation.z_axis
end

normalize average_orientation.x_axis
normalize average_orientation.y_axis
normalize average_orientation.z_axis





average_orientation is orthonormal because boid[i].orientation, is orthonormal(i=1,..,N)
This is less obvious when the average orientation is computed with quaternions( what would mean the average of cos(alpha/2), alpha being the angle of rotation, in an axis-angle representation? Maybe should I just try to think about it? )
This shouldn't be a problem after all, if all boids converge to the same orientation, whaterver it means.

So, the case is closed for me.

The other question required a deeper answer. We're in a simulated environment. Meaning that I need to compute the actual forces that will bring my boid in a specified orientation.
The idea I came up with, was to compute the rotation matrix which applied to a boid, would make it aligned with the average orientation...in order to extract its axis, and apply a torque along that axis, in such a way that the boid would be, step by step, rotated to be aligned with the average orientation. The problem is, I shouldn't decouple rotation and translation( I don't think doing that would result in a "natural" motion ).

[Edited by - johnstanp on March 9, 2010 5:16:33 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
I think this is a good question. Here's how I'd go about doing it... first conceptually, then practically:

I am agent i. My orientation, R_i, is an element of the manifold SO(3) (the rotation matrices). I have N neighbors, with orientations Q_1,...,Q_N also in SO(3). What I will do is,
1 - figure out what the tangent vectors to the shortest geodesics in SO(3) are from R_i to each of Q_1,...,Q_N.
2 - average these tangent vectors
3 - adjust my orientation in this direction

In the above, the tangent vectors to SO(3) are just skew-symmetric matrices (or equivalently just triplets of numbers, since a skew-symmetric matrix only has three unique elements; the hat operator (screw theory) and its inverse convert back and forth between these representations).

Step #1 is done in the following way: Just compute the transformation that will take R_i to Q_j (for each j); this is M_ij = Q_j R_i^T, which is also an element of SO(3). Then take a particular matrix logarithm of M_ij (given here) to get the tangent vector. ("matrix logarithm" in this case is really just fancy-speak for "axis-angle representation of M_ij")

As for step #3: You can either just do a predictor-corrector step; e.g.,
1 - Update with euler integration step
2 - Snap back to SO(3) (e.g., by polar decomposition, or approximately by Gram-Schmidt)
--- OR ---
you can compute the matrix exponential of the tangent vector you got in step #2; the special case of the matrix exponential for 3x3 skew-symmetric matrices is given by Rodrigues' formula.

To summarize, you're basically just simulating the following ODE,

(d/dt)R_i = log(Q_1 R_i^T) + log(Q_2 R_i^T) + ... + log(Q_N R_i^T)

in a way that makes sure that cumulative errors don't eventually take you off SO(3) (in which case, in other words, R_i would no longer be a rotation matrix).

=====

Also... although everything I said was in terms of rotation matrices, you can do the equivalent thing with quaternions. It will make the "snapping back to the manifold" part very simple at least...

If you want to do it with quaternions, then the tangent vector is just the tangent vector to the unit 3-sphere embedded in 4-space; the tangent space at p is just all the vectors orthogonal to p...


Thank you very much for your time...This is what I was actually looking for: a way to compute dR(t)/dt to bring my boid to the desired orientation!
More importantly, I need computing the actual forces( and torques ) that would make me achieve such a variation of orientation. But I have to agree, if I can directly compute dR(t)/dt, I don't need computing the forces and the torques that generate that variation of orientation. Thank you.

P.S: my initial question had more to do with how steering is implemented with forces and torques, than how it is achieved with rotation matrices...In a way, the question still remains open. Not really, since I could compute the forces and torques that bring a specific dR(t)/dt, but that would be a circonvoluted way of doing things.

[Edited by - johnstanp on March 9, 2010 4:20:07 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by johnstanp
the sum over i of ai(i=1,.., N) is orthogonal to the sum over i of bi(i=1,...,N), bi being orthogonal to ai(i=1,..,N)

That basically means that I could simply do:

*** Source Snippet Removed ***


Am I understanding correctly that basically you're talking about adding up your neighbors' rotation matrices and then normalizing the columns of the result? If you try this procedure out you'll see that it won't actually produce a rotation matrix, since although all the {ai} are orthogonal to one another, and all the {bi} are orthogonal to one another, the {ai}s are not orthogonal to the {bi}s.

Share this post


Link to post
Share on other sites
Quote:
Original post by Emergent
Quote:
Original post by johnstanp
the sum over i of ai(i=1,.., N) is orthogonal to the sum over i of bi(i=1,...,N), bi being orthogonal to ai(i=1,..,N)

That basically means that I could simply do:

*** Source Snippet Removed ***


Am I understanding correctly that basically you're talking about adding up your neighbors' rotation matrices and then normalizing the columns of the result? If you try this procedure out you'll see that it won't actually produce a rotation matrix, since although all the {ai} are orthogonal to one another, and all the {bi} are orthogonal to one another, the {ai}s are not orthogonal to the {bi}s.


You've well understood. I made a mistake in generalizing what is true in 2D.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this