A full explanation of the method is given in [883], and a brief intuition is given here. First drop down a dimension and pick to generate points on . Let represent the value for the third coordinate, . The slice of points on for which is fixed for yields a circle on that corresponds to some line of latitude on . The second parameter selects the longitude, . Fortunately, the points are uniformly distributed over . Why? Imagine 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 can be partitioned into a spherical arrangement of circles (known as the Hopf fibration); there is an copy for each point in . The method above is used to provide a random point on using and , and produces a random point on ; they are carefully combined in (5.15) to yield a random rotation. To respect the antipodal identification for rotations, any quaternion found in the lower hemisphere (i.e., ) can be negated to yield . This does not distort the uniform random distribution of the samples.

Steven M LaValle 2012-04-20