How to do that is not entirely obvious.
Most modern processors do multiplies and inverse square roots fairly quickly.
Not doing them is even quicker.
Basically, my algorithm is:
compute f®,
compute f(R’) for all R’ “close” to R.
If f® is the minimum, return
Else for the minimum f(R’), recursively apply the formula.
Now, this would be trivial in translation because the points “near” (x, y, z) would just be (x +or- delta, y +or- delta, z +or- delta)
I’m trying to find the equivilant for rotations.
You may find it useful to precompute a set of near-identity rotations (you can do this with quaternions by creating a list L of elements close to 1; with rotation matrices, you can choose elements in the Lie algebra so(3) and find corresponding SO(3) elements, or just choose three Euler angles close to zero). This avoids having to do the time-consuming normalizations at each stage; for any rotation R, just evaluate f(Rx) for each x in L. You still have one matrix multiplication per evaluation; I’m not sure if that’s acceptable for you. This also uses a constant set of rotations (probably scaled with time, as for an annealing search: that is, you start with rotations of magnitude d; after a while, you further optimize with rotations of magnitude (say) d/2, using a new list L’; etc.), which may affect the convergence speed if f is sufficiently annoying. If this is a problem, you can occasionally rotate all of the elements of L by some random matrix to randomize the directions of your small-rotation matrices.
Depending on what language you’re using, multiplication by a compile-time constant matrix can be made very fast, so that may not be a horrible issue.
I don’t remember if it’s already been stated, but quaternions representing orientations can be thought of as an axis (x, y, z) and a rotation about that axis, r, in the form:
cos(r/2) + i * sin(r/2) * x + j * sin(r/2) * y + k * sin(r/2)
where the starting orientation to be pointing along the x axis with the y axis to its left and the z axis to its top.
If you can multiply two unit quaternions together and will get another unit quaternion representing the rotation from the starting point to the orientation you would get to if you did those two rotations consecutively. So, if you gave some small number, s, you can use a rotation about the y and z axis by that amount. So say that some number s is small enough. you would come up with another number t = sqrt(1 - s[sup]2[/sup]).
Suppose at the current iteration you have the quaternion
a + bi + cj + dk
you would multiply it by each of the four quaternions:
t + sj
t - sj
t + sk
t - sk
you would then get the four quaternions:
at + bti + ctj + dtk + asj + bsij + csj[sup]2[/sup] + dskj
at + bti + ctj + dtk - asj - bsij - csj[sup]2[/sup] - dskj
at + bti + ctj + dtk + asj + bsik + csjk + dsk[sup]2[/sup]
at + bti + ctj + dtk - asj - bsik - csjk - dsk[sup]2[/sup]
Remember, the ordering of the multiplications matters, and ij = -ji = k, jk = -kj = i, ki = -ik = j, and i[sup]2[/sup] + j[sup]2[/sup] + k[sup]2[/sup] = -1. Multiplying it all out:
at - cs + (bt - ds)i + ctj + (dt + bs)k
at + cs + (bt + ds)i + ctj + (dt - bs)k
at - ds + (bt + cs)i + (ct - bs)j + dtk
at + ds + (bt - cs)i + (ct + bs)j + dtk
would be four small steps to the up, down, left, and right directions.
Well, not without a better notion of what this function is. Still, if I were writing the program I’d at least try to see if there’s a natural formula before coding up the ugly algorithm which renormalizes each time.
This gives a slight displacement either way in two dimensions. As we’ve said before, the Lie group SO(3) is three-dimensional. I’m not saying your answer is wrong, but rather that it’s incomplete since there should be two more displacements to find.
There’s also the alteration of twist, around the x axis, but Shalmanese implies that it’s only the direction that is important. If the complete orientation was important, you’d then need:
at - bs + bti + (ct + ds)j + (dt - cs)k
at + bs + bti + (ct - ds)j + (dt + cs)k
too.
I don’t get that implication at all. what Shalmanese asked for was a way to find nearby rotations, not nearby directions. If the function depends on a rotation (as stated) rather than on only the direction into which the x-axis is rotated then it can depend on that third coordinate and leaving it out of the calculations will lead to a bad algorithm.
OK, no sweat.
Nah, my only point was that quaternions didn’t get ignored for a hundred years, and that the guy who didn’t ignore them was Maxwell, whose own work led inexorably to…
Well, jeez, nobody was saying that. It just seems to me that the discovery of abstractions like quaternions can easily predate the idea that they might have any connection whatsoever to the physical world; and I brought up the interesting anecdote of Heisenberg’s invention of matrix mechanics to show that while these abstractions don’t sit around collecting dust in some circles, in others, they remain completely unknown, and can be, in fact, reinvented for the specific purpose of describing physical phenomena. It’s that (seemingly) deep and unanticipated connection between these abstractions and unforseen observations that gives me a bit of a tingle. I readily admit, and am aware, that there’s a certain amount of mytholologizing going on when describing these Great Men, in no small part because the reality of the history is so messy and convoluted it makes a very difficult historical narrative. If I’m completely off base about the myths, even, then fine, call me a dunderhead. The received wisdom from the Greats to the dunderheads is sometimes there are these uncanny connections, an I find the idea fascinating.
An earlier thread on the subject:
http://boards.straightdope.com/sdmb/showthread.php?t=260773&highlight=quarternions
OK, I gotcha.