Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to sample uniform random rotations. I'd like the rotations to be restricted in a range [-θ,θ]. I found a method by K. Shoemake which can be summarized as:

s = rand(1.0);
σ1 = sqrt(1 − s);
σ2 = sqrt(s);
θ1 = 2π ∗ rand(1.0);
θ2 = 2π ∗ rand(1.0);
w = cos(θ2) ∗ σ2 ;
x = sin(θ1) ∗ σ1 ;
y = cos(θ1) ∗ σ1 ;
z = sin(θ2) ∗ σ2 ;
return (w, x, y, z);

But I want to only sample the given angle range. Does anyone know of any method to do that?

Btw, I also read in a paper that sampling a random unit vector together with an angle using a uniform distribution also gives you a bias.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

It's not clear to me what you mean by restricting the rotations to a range $[-\theta,\theta]$. The sign of the rotation angle of a rotation isn't meaningful, since you can instead view the rotation as a rotation about the opposite axis through the negative angle. Thus I'll assume that you intended the rotation angles to be restricted to $[0,\theta]$.

Also, I'll assume that you want the distribution to be uniform with respect to the Haar measure of $SO(3)$, which is what the method you quote produces. You're right that this isn't achieved by a uniform distribution over the angles. The probability of an angle should be proportional to the corresponding slice of the surface of $S^3$, the three-dimensional hyper-sphere in four dimensions parameterizing the unit quaternions, and this is proportional to $\sin^2\alpha\,\mathrm d\alpha$.

You can use the method you describe and then reject rotations with angles you don't want. I suspect that this would be one of the more efficient methods if your angle range is large. As your cutoff $\theta$ decreases, however, this becomes increasingly wasteful, since small angles are unlikely, but in this case it becomes increasingly efficient to use rejection sampling with the $\sin^2\alpha$ distribution approximated by $\alpha^2$.

Thus, you could generate a sample from the density $\alpha^2$ using $u=\alpha^3$ and $\mathrm du=3\alpha^2\mathrm d\alpha$ by generating a uniform sample $u\in[0,\theta^3]$, computing $\alpha=\sqrt[3]u$ and accepting the sample with probability $\sin^2\alpha/\alpha^2$, which will be close to $1$ for small $\theta$.

[Edit in response to the comment:]

Rejection sampling for a density $f(\alpha)$ works by sampling from a different density $g(\alpha)$ and then accepting the samples with probability $f(\alpha)/Mg(\alpha)$, with $M=\sup_\alpha f(\alpha)/g(\alpha)$. In the present case, $f(x)\propto\sin^2\alpha$, $g(x)\propto\alpha^2$ and $\sup_\alpha\sin^2\alpha/\alpha^2=1$, so you can accept with probability $\sin^2\alpha/\alpha^2$, which is greater than $99.7\%$ for angles below $5^\circ$, that is, you almost never have to reject a sample and the sampling is very efficient.

To generate samples with density $g(\alpha)\propto\alpha^2$, you can transform to $u=\alpha^3$, since then we have $\mathrm du=3\alpha^2\mathrm d\alpha$, so $\alpha$ has density $\propto\alpha^2$ if $u$ has constant density, i.e. is uniformly distributed. Thus, you can generate uniform samples on $[0,\theta^3]$ (which would be $u=\theta\cdot\theta\cdot\theta\cdot\operatorname{rand}(1.0)$ in your code), then calculate $\alpha=\sqrt[3]u$, then generate another variable $t$ uniformly distributed on $[0,1]$ and accept $\alpha$ if $t\lt\sin^2\alpha/\alpha^2$. If $\alpha$ is rejected, you try again.

This gives you a rotation angle $\alpha$ with the right distribution; then you just have to generate a random axis and form the corresponding rotation.

share|improve this answer
    
Hey, thanks alot for your reply. Your assumptions are correct. I'm mainly interested in very small angles. Unfortunately, I'm not as familiar with probabilities as I'd like to be. As such, could you elaborate a bit more on the last paragraph? The method you explain doesn't seem very efficient, can't I make further simplifications since I'm only interested in angles $<5^o$ ? –  user1294203 Apr 13 '12 at 16:39
    
@user1294203: I've made the computation more explicit. Why do you say the method doesn't seem very efficient? The acceptance rate is almost $100\%$, so you only have to generate two uniform random numbers, draw a third root and compute a sine to get an angle -- that doesn't sound too bad to me :-) Depending on what you need this for and how accurate it has to be, you might even get away with omitting the rejection part and just sampling from $\alpha^2$ instead of $\sin^2\alpha$. –  joriki Apr 13 '12 at 17:19
    
Thanks again for taking the time to answer. Your answer gave me some good hints on what to read and I now understand everything fully! About the efficiency, I was thinking about the $\sqrt[3]{}$ but now I understand that it's unavoidable. I'm doing MC simulations and need to randomly rotate objects. –  user1294203 Apr 13 '12 at 19:41
    
@user1294203: You're welcome. MC simulations, nice; I used to do lattice gauge theory and spin glass simulations a long time ago for my diploma thesis :-) –  joriki Apr 13 '12 at 20:29
    
Wow, nice, I didn't even know there were MC simulations in gauge theories! –  user1294203 Apr 13 '12 at 21:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.