Generating a random element of $ SO(3)$

One has to be very careful about sampling uniformly over the space of rotations. The probability density must correspond to the Haar measure, which means that a random rotation should be obtained by picking a point at random on $ {\mathbb{S}}^3$ and forming the unit quaternion. An extremely clever way to sample $ SO(3)$ uniformly at random is given in [883] and is reproduced here. Choose three points $ u_1,u_2,u_3 \in [0,1]$ uniformly at random. A uniform, random quaternion is given by the simple expression

$\displaystyle h = (\sqrt{1-u_1}\sin 2 \pi u_2,\; \sqrt{1-u_1}\cos 2 \pi u_2,\; \sqrt{u_1}\sin 2 \pi u_3,\; \sqrt{u_1}\cos 2 \pi u_3) .$ (5.15)

A full explanation of the method is given in [883], and a brief intuition is given here. First drop down a dimension and pick $ u_1,u_2 \in [0,1]$ to generate points on $ {\mathbb{S}}^2$. Let $ u_1$ represent the value for the third coordinate, $ (0,0,u_1) \in {\mathbb{R}}^3$. The slice of points on $ {\mathbb{S}}^2$ for which $ u_1$ is fixed for $ 0 < u_1 < 1$ yields a circle on $ {\mathbb{S}}^2$ that corresponds to some line of latitude on $ {\mathbb{S}}^2$. The second parameter selects the longitude, $ 2 \pi u_2$. Fortunately, the points are uniformly distributed over $ {\mathbb{S}}^2$. Why? Imagine $ {\mathbb{S}}^2$ as the crust on a spherical loaf of bread that is run through a bread slicer. The slices are cut in a direction parallel to the equator and are of equal thickness. The crusts of each slice have equal area; therefore, the points are uniformly distributed. The method proceeds by using that fact that $ {\mathbb{S}}^3$ can be partitioned into a spherical arrangement of circles (known as the Hopf fibration); there is an $ {\mathbb{S}}^1$ copy for each point in $ {\mathbb{S}}^2$. The method above is used to provide a random point on $ {\mathbb{S}}^2$ using $ u_2$ and $ u_3$, and $ u_1$ produces a random point on $ {\mathbb{S}}^1$; they are carefully combined in (5.15) to yield a random rotation. To respect the antipodal identification for rotations, any quaternion $ h$ found in the lower hemisphere (i.e., $ a < 0$) can be negated to yield $ -h$. This does not distort the uniform random distribution of the samples.

Steven M LaValle 2012-04-20