Need help to get all possible 3d rotations?

Need help to get all possible 3d rotations?

Post by Macro Z » Sat, 05 Jul 2003 00:20:24



Hello, there,

Here I am trying to rotate a rigid body in 3D space.
I will only rotate the object without translation, and I want to
rotate the object to all possible configurations in 3D space.
So I tried to use 3 loops with the same "step" for the three euler
angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
rotations.

for(psi = 0; psi < 180; psi += step)
  for(theta = 0; theta < 360; theta += step)
    for(phi = 0; phi < 360; phi += step)
{
   ......

Quote:}

I checked this on the web and I think it's called "gimbal lock".
So I think I may solve it by using quaternion but failed to find
way out. Does anybody know how to recaculate the given "step" s.t.
we can elimilate these dupicated positions? Or can anybody give me
some hint for references?

Thank you very much!

Macro Zhu

 
 
 

Need help to get all possible 3d rotations?

Post by Hans-Bernhard Broeke » Sat, 05 Jul 2003 00:28:17



> I will only rotate the object without translation, and I want to
> rotate the object to all possible configurations in 3D space.

No, actually you almost certainly don't want to do that --- it'd take
literally forever to do that, because the number of possible
configurations is infinite.

So the first thing you'll have to do is re-evaluate what it is you're
really trying to achieve.

Quote:> So I tried to use 3 loops with the same "step" for the three euler
> angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
> rotations.

That's mainly due to gimbal lock, indeed.  And possibly due to the
ranges you're rotating over, i.e. choosing the wrong one of the three
Eulers to rotate only up to 180 degrees by.

Quote:> for(psi = 0; psi < 180; psi += step)
>   for(theta = 0; theta < 360; theta += step)
>     for(phi = 0; phi < 360; phi += step)
> {
>    ......
> }

Assuming your angles are chosen somewhat correctly, for psi = 0 this
will generate 360/step duplicates, because phi and theta rotate around
the same axis.  The same would happen at psi=180 degrees, but your
loop avoids that case.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Need help to get all possible 3d rotations?

Post by Just d' FAQ » Sat, 05 Jul 2003 08:25:54



Quote:>Here I am trying to rotate a rigid body in 3D space.
>I will only rotate the object without translation, and I want to
>rotate the object to all possible configurations in 3D space.
>So I tried to use 3 loops with the same "step" for the three euler
>angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
>rotations.

Perhaps you should tell us what you want to do with these rotations
once you have them. There are deeper issues than duplication that may
be involved, such as uniformity.
 
 
 

Need help to get all possible 3d rotations?

Post by Macro Z » Sat, 05 Jul 2003 20:38:06


Firstly, thank you, Hans-Bernhard, for your reply!

Quote:> > I will only rotate the object without translation, and I want to
> > rotate the object to all possible configurations in 3D space.

> No, actually you almost certainly don't want to do that --- it'd take
> literally forever to do that, because the number of possible
> configurations is infinite.

Yes, I agree with you.
Let's say it in this way: I want to get all the discrete rotations
with the given step for three euler angles (phi, theta, psi, around
x,y,z axis respectively).

Quote:

> So the first thing you'll have to do is re-evaluate what it is you're
> really trying to achieve.

> > So I tried to use 3 loops with the same "step" for the three euler
> > angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
> > rotations.

> That's mainly due to gimbal lock, indeed.  And possibly due to the
> ranges you're rotating over, i.e. choosing the wrong one of the three
> Eulers to rotate only up to 180 degrees by.

Shouldn't I iterate all angles for the three euler angles?

Quote:

> > for(psi = 0; psi < 180; psi += step)
> >   for(theta = 0; theta < 360; theta += step)
> >     for(phi = 0; phi < 360; phi += step)
> > {
> >    ......
> > }

> Assuming your angles are chosen somewhat correctly, for psi = 0 this
> will generate 360/step duplicates, because phi and theta rotate around
> the same axis.  The same would happen at psi=180 degrees, but your
> loop avoids that case.

Here I assume phi is the euler angle around z axis, theta is around y,
and phi is around x axis.  So i can't get you here. Why phi and theta
rotate around the same axis?
 
 
 

Need help to get all possible 3d rotations?

Post by Macro Z » Sat, 05 Jul 2003 20:46:52




> >Here I am trying to rotate a rigid body in 3D space.
> >I will only rotate the object without translation, and I want to
> >rotate the object to all possible configurations in 3D space.
> >So I tried to use 3 loops with the same "step" for the three euler
> >angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
> >rotations.

> Perhaps you should tell us what you want to do with these rotations
> once you have them. There are deeper issues than duplication that may
> be involved, such as uniformity.

Oh, actually I have two rigid bodies and I want to find out how they two
fit to each other geometrically. So I am doing it like this:

1) keep rigid object a (let's say, OA) still;
2) rotate rigid object b (OB) around its mass center, to all the possible
   relative directions to OA.
   Here in this step I used the three loops to find all possible discrete
   rotations (in the form of 3 euler angles), and then transfer them to    
   rotation matrix, s.t. I can rotate the OB with this rotation matrix.

 
 
 

Need help to get all possible 3d rotations?

Post by Hans-Bernhard Broeke » Sat, 05 Jul 2003 21:20:34



> Let's say it in this way: I want to get all the discrete rotations
> with the given step for three euler angles (phi, theta, psi, around
> x,y,z axis respectively).

That still makes only marginal sense.

Quote:>> That's mainly due to gimbal lock, indeed.  And possibly due to the
>> ranges you're rotating over, i.e. choosing the wrong one of the three
>> Eulers to rotate only up to 180 degrees by.
> Shouldn't I iterate all angles for the three euler angles?

Yes, but from your description, it was quite unclear what the actual
definition of your Euler angles is, in terms of which angle refers to
a rotation about which axis, and in what order the three are meant to
be carried out.

Quote:> Here I assume phi is the euler angle around z axis, theta is around y,
> and phi is around x axis.  

There's a fatal typo in there: two phi, and no psi.

Quote:> So i can't get you here. Why phi and theta rotate around the same
> axis?

Let's get rid of those names, and say we're talking about "aircraft
Eulers": heading, pitch, and roll.  Now, if the pitch is vertically up
or down (+/- 90 degrees out of the horizontal, or 0/180 degrees,
depending on your conventions), the aircraft has no real "heading" any
more.  It's forward axis is the parallal to the world-fixed upward
axis, so "heading" and "roll" rotate about the same axis, effectively.
That's the essence of gimbal lock.
--

Even if all the snow were burnt, ashes would remain.
 
 
 

Need help to get all possible 3d rotations?

Post by Gernot Hoffma » Sat, 05 Jul 2003 21:23:49



> Hello, there,

> Here I am trying to rotate a rigid body in 3D space.
> I will only rotate the object without translation, and I want to
> rotate the object to all possible configurations in 3D space.
> So I tried to use 3 loops with the same "step" for the three euler
> angles,i.e., pitch, yaw and roll, but I got a lot of duplicated
> rotations.

> for(psi = 0; psi < 180; psi += step)
>   for(theta = 0; theta < 360; theta += step)
>     for(phi = 0; phi < 360; phi += step)
> I checked this on the web and I think it's called "gimbal lock".
> So I think I may solve it by using quaternion but failed to find
> way out. Does anybody know how to recaculate the given "step" s.t.
> we can elimilate these dupicated positions? Or can anybody give me
> some hint for references?
> Thank you very much!
> Macro Zhu


Macro,

the task is quite clear - finding all orientations in 1 steps.
If you want to cover all single axis rotations  as well, then you will
need 0..360 for each angle.
If you want all rigid body orientations, then this would be sufficient:
Psi=-180..+180
The= -90.. +90
Phi=-180..+180
Then you will have duplicate positions.  

Storing millions of rotation matrices doesnt look promissing.
If your body rotation is not physically restrained, then its IMO not
avoidable to allow full rotations for each angle.
You could do this by 3D tables in 10 steps and 3D linear interpolation
(45656 matrices with 9 single entries each). Unfortunately, the 3D inter-
polation is time consuming, and it has to be done for each of the nine
components.  

There is nowhere gimbal lock. The pure geometrical rotation is well
defined for all arbitrary angles.

Quaternions are probably the best choice, without storing predefined
orientations.

Best regards  --Gernot Hoffmann

 
 
 

Need help to get all possible 3d rotations?

Post by Just d' FAQ » Sun, 06 Jul 2003 13:05:49



Quote:>Oh, actually I have two rigid bodies and I want to find out how they two
>fit to each other geometrically. So I am doing it like this:

>1) keep rigid object a (let's say, OA) still;
>2) rotate rigid object b (OB) around its mass center, to all the possible
>   relative directions to OA.
>   Here in this step I used the three loops to find all possible discrete
>   rotations (in the form of 3 euler angles), and then transfer them to    
>   rotation matrix, s.t. I can rotate the OB with this rotation matrix.

Ouch! That sounds horribly brute force. Will you compute a number to
measure the fit? Do you really need such tiny increments in angle? Are
you looking for a "best" fit?

Euler angles are a poor approach to mapping 3D rotation space, because
they give very uneven coverage and brutally disrupt natural proximity.

A better method would be angle-axis: Choose angles evenly spaced from
0 to 2pi, rotating around z; then tilt the z axis to a direction that
is evenly distributed on the sphere. You *must not* try to simplify by
uniformly rotating around a uniform axis; the results would be quite
different!

 
 
 

Need help to get all possible 3d rotations?

Post by Macro Z » Wed, 09 Jul 2003 01:14:13


Quote:> Let's get rid of those names, and say we're talking about "aircraft
> Eulers": heading, pitch, and roll.  Now, if the pitch is vertically up
> or down (+/- 90 degrees out of the horizontal, or 0/180 degrees,
> depending on your conventions), the aircraft has no real "heading" any
> more.  It's forward axis is the parallal to the world-fixed upward
> axis, so "heading" and "roll" rotate about the same axis, effectively.
> That's the essence of gimbal lock.

well, let's use the following terms: yaw, pitch and roll.
And your explaination makes sence. But all these just explained the
problem (Gimbal lock) again. Is there any practical hints about how
to overcome it (in the background of my problem definition?)

I thought of calculating all the possible angles in prior.
I can keep a reference vector, and whenever I got a new set of
rotation angles, I rotate this reference vector accordingly and use the
result vector to check whether the rotation/angles duplicated with
some existing one. But this seems too complex and time-consuming.
Is there any faster method?

 
 
 

Need help to get all possible 3d rotations?

Post by Macro Z » Wed, 09 Jul 2003 01:24:21


Quote:> Macro,

> the task is quite clear - finding all orientations in 1 steps.
> If you want to cover all single axis rotations  as well, then you will
> need 0..360 for each angle.
> If you want all rigid body orientations, then this would be sufficient:
> Psi=-180..+180
> The= -90.. +90
> Phi=-180..+180
> Then you will have duplicate positions.  

Yes, that's what I meant.

Quote:

> Storing millions of rotation matrices doesnt look promissing.
> If your body rotation is not physically restrained, then its IMO not
> avoidable to allow full rotations for each angle.
> You could do this by 3D tables in 10 steps and 3D linear interpolation
> (45656 matrices with 9 single entries each). Unfortunately, the 3D inter-
> polation is time consuming, and it has to be done for each of the nine
> components.  

It may be too complicated :( . And if I change the interval, for instance,
to 0.5 or 0.9 degrees, I have to re-do calculations  :(

Quote:

> There is nowhere gimbal lock. The pure geometrical rotation is well
> defined for all arbitrary angles.

> Quaternions are probably the best choice, without storing predefined
> orientations.

Any further hint? I searched this topic on the web, but most articles are
about interpolation.
Quote:

> Best regards  --Gernot Hoffmann

 
 
 

Need help to get all possible 3d rotations?

Post by Hans-Bernhard Broeke » Wed, 09 Jul 2003 01:52:35



> well, let's use the following terms: yaw, pitch and roll.

Fine.

Quote:> And your explaination makes sence. But all these just explained the
> problem (Gimbal lock) again. Is there any practical hints about how
> to overcome it (in the background of my problem definition?)

Your best bet still is to abandon the whole idea of using Euler angles
in the first place.  Their distribution in "orientation space" is
highly non-uniform, with Gimbal lock being interpretable as the
extreme case of exploding local "density" at the borders of its
parameter space.  Use an axis/angle or quaternion description of
orientations instead.  

Quote:> I thought of calculating all the possible angles in prior.

Your main problem is this concept of "all the possible" angles itself.
There are infinitely many, really, so you can't possibly fulfill that
description anyway.  

So you have to define a finite subset as your search space.  But
whatever sampling density in what ever coordinate system you choose,
it'll be quite wasteful to go through *all* of the finite subset to
find the optimum.

Use a proper minimization technique, like a nonlinear least squares
fit or a simplex-based search technique, instead.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Need help to get all possible 3d rotations?

Post by Gernot Hoffma » Thu, 10 Jul 2003 01:36:57



> Any further hint? I searched this topic on the web, but most articles are
> about interpolation.

Macro,

Euler angles are not bad. For geometrical rotations, all angles given,
THERE IS NO GIMBAL LOCK.

You may make two tables with 3600 entries each for the sines and cosines
in 0.1 steps and build the rotation matrix newly in each step.
Any attempt to make the tables shorter and swap&mirror is quite useless.
Each angle is mapped into [0,360], multiplied by 10 and rounded.
Then one needs 6 table accesses and typically 14 mults for the matrix.
(Yes, I know that the tables are not kept completely in the cache).

By the way a question: does C have a statement for the simultaneous
calculation of the sine and the cosine ? Intel FPUs calculate both in
one pass using about 20% more cycles than for a single function.

Best regards  --Gernot Hoffmann

 
 
 

Need help to get all possible 3d rotations?

Post by Hans-Bernhard Broeke » Thu, 10 Jul 2003 01:50:05



> By the way a question: does C have a statement for the simultaneous
> calculation of the sine and the cosine ?

Of course not.  C has no "statement" for any kind of trig function,
and certainly not for unportable platform specifics like the fsincos
opcode.  C has a standardized library of portable math functions instead.

Most decent C compilers for Intels have inline assemblere
capabilities, though, so you can write such a function yourself, if
the system you use doesn't provide one already.

--

Even if all the snow were burnt, ashes would remain.

 
 
 

Need help to get all possible 3d rotations?

Post by Horst Kraeme » Thu, 10 Jul 2003 04:38:17



Quote:> > Macro,

> > the task is quite clear - finding all orientations in 1 steps.
> > If you want to cover all single axis rotations  as well, then you will
> > need 0..360 for each angle.
> > If you want all rigid body orientations, then this would be sufficient:
> > Psi=-180..+180
> > The= -90.. +90
> > Phi=-180..+180
> > Then you will have duplicate positions.  
> Yes, that's what I meant.

> > Storing millions of rotation matrices doesnt look promissing.
> > If your body rotation is not physically restrained, then its IMO not
> > avoidable to allow full rotations for each angle.
> > You could do this by 3D tables in 10 steps and 3D linear interpolation
> > (45656 matrices with 9 single entries each). Unfortunately, the 3D inter-
> > polation is time consuming, and it has to be done for each of the nine
> > components.  
> It may be too complicated :( . And if I change the interval, for instance,
> to 0.5 or 0.9 degrees, I have to re-do calculations  :(

> > There is nowhere gimbal lock. The pure geometrical rotation is well
> > defined for all arbitrary angles.

> > Quaternions are probably the best choice, without storing predefined
> > orientations.
> Any further hint? I searched this topic on the web, but most articles are
> about interpolation.

The problem with "finding all possible rotations in for instance 1
steps" without duplication is an ill-defined problem. The topological
structure of 3d-rotations corresponds to the structure of a
4-dimensional sphere where any pair of opposite points represent the
same rotation. Another equivalent structure: The set of all straight
lines through the origin in 4d.

The structures of the set of rotations and the set of point pairs on a
4d-sphere are equivalent in the sense that there is a one-to-one
mapping between point pairs and rotations such that point pairs that
are "close" in the geometrical sense correspond to rotations which are
"close" in terms of axis and angle.

As you may guess the mathematical objects linking point pairs on a 4d
sphere and 3d rotations, i.e. objects which can represent both kinds
of entities are - quaternions. Pairs of unit quaternions alias 4d unit
vectors, to be precise, because q and -q represent the same rotation
if interpreted as rotations and two opposite points on a 4d unit
sphere if interpreted as point pairs.

Now the problem boils down to representing pairs of 4d unit vectors
with a suitable parametrization.

A "natural" parametrization of one half of the 4d unit sphere without
duplication yielding a set of quaternions representing all possible 3d
rotations is a parametrization using 3 angles (which have no relation
to Euler angles and such) a1,a2,a3.

       x = sin(a1)sin(a2)sin(a3)                
       y = sin(a1)sin(a2)cos(a3)
       z = sin(a1)cos(a2)
       w = cos(a1)

       0  <= a3 < pi
       0  <= a2 < pi
       0  <= a1 < pi

using a1 as inner, a2 as middle and a3 as outer loop.

Regards
Horst

 
 
 

Need help to get all possible 3d rotations?

Post by mar » Thu, 10 Jul 2003 18:41:19




> > > Macro,

> > > the task is quite clear - finding all orientations in 1 steps.
> > > If you want to cover all single axis rotations  as well, then you will
> > > need 0..360 for each angle.
> > > If you want all rigid body orientations, then this would be sufficient:
> > > Psi=-180..+180
> > > The= -90.. +90
> > > Phi=-180..+180
> > > Then you will have duplicate positions.  
> > Yes, that's what I meant.

> > > Storing millions of rotation matrices doesnt look promissing.
> > > If your body rotation is not physically restrained, then its IMO not
> > > avoidable to allow full rotations for each angle.
> > > You could do this by 3D tables in 10 steps and 3D linear interpolation
> > > (45656 matrices with 9 single entries each). Unfortunately, the 3D inter-
> > > polation is time consuming, and it has to be done for each of the nine
> > > components.  
> > It may be too complicated :( . And if I change the interval, for instance,
> > to 0.5 or 0.9 degrees, I have to re-do calculations  :(

> > > There is nowhere gimbal lock. The pure geometrical rotation is well
> > > defined for all arbitrary angles.

> > > Quaternions are probably the best choice, without storing predefined
> > > orientations.
> > Any further hint? I searched this topic on the web, but most articles are
> > about interpolation.

> The problem with "finding all possible rotations in for instance 1
> steps" without duplication is an ill-defined problem. The topological
> structure of 3d-rotations corresponds to the structure of a
> 4-dimensional sphere where any pair of opposite points represent the
> same rotation. Another equivalent structure: The set of all straight
> lines through the origin in 4d.

> The structures of the set of rotations and the set of point pairs on a
> 4d-sphere are equivalent in the sense that there is a one-to-one
> mapping between point pairs and rotations such that point pairs that
> are "close" in the geometrical sense correspond to rotations which are
> "close" in terms of axis and angle.

> As you may guess the mathematical objects linking point pairs on a 4d
> sphere and 3d rotations, i.e. objects which can represent both kinds
> of entities are - quaternions. Pairs of unit quaternions alias 4d unit
> vectors, to be precise, because q and -q represent the same rotation
> if interpreted as rotations and two opposite points on a 4d unit
> sphere if interpreted as point pairs.

> Now the problem boils down to representing pairs of 4d unit vectors
> with a suitable parametrization.

> A "natural" parametrization of one half of the 4d unit sphere without
> duplication yielding a set of quaternions representing all possible 3d
> rotations is a parametrization using 3 angles (which have no relation
> to Euler angles and such) a1,a2,a3.

>        x = sin(a1)sin(a2)sin(a3)          
>        y = sin(a1)sin(a2)cos(a3)
>        z = sin(a1)cos(a2)
>        w = cos(a1)

>        0  <= a3 < pi
>        0  <= a2 < pi
>        0  <= a1 < pi

> using a1 as inner, a2 as middle and a3 as outer loop.

> Regards
> Horst

Just curious, but would it be possible to instead iterate (by 1 degree
using the original example) through latitude and longitudes (to get
all axes for that increment), and also iterate angles on those axes to
get all orientations?