I am trying to move a first-person camera around the surface of a sphere. Imagine Super Mario Galaxy but you look through Mario's eyes.

I set up the camera with a look vector that is tangent to the sphere. The algorithm I have at present is;

- Move along look vector
- Move camera down into contact with the sphere
- Calculate new up and strafe vectors
- Use old position, new position, radius and cosine rule to calculate the angle moved around the sphere
- Rotate the look vector by the above angle about the strafe vector.

Obviously at the moment this just moves in a straight line. The problem I have is that the look vector does not rotate down enough. Eventually the look vector is perpendicular to the sphere and the camera does not move.

I narrowed this down to float rounding error. acos() returns 0 degrees if the angle is too small, even with a long double. I figure I could use MPFRCPP and GMP to use rediculously large floating points, however having to do so seems to me like this is a retarded way of doing it.

I've never used Quaternions and from what I've looked at I've no idea how I would implement this. Using Quaternions for a single position seems fine but the camera needs to move along the look vector, and the look vector has to rotate down every frame to keep it as a tangent to the sphere.

Any ideas?

A standard solution to this problem is:

1. Move the object along the forward direction vector.

2. Raycast downwards to find the surface point and normal beneath the object (if the object is a sphere, you can instead compute the normal as the normalized vector from the sphere center to the object position, and compute the point on the surface from the normal and the sphere radius).

3. Move the object to the surface point.

4. Apply a corrective rotation that rotates the object's up axis onto the surface normal.

For step 4, a standard method is to compute the axis of rotation as the normalized cross product of the first (object 'up') and second (surface normal) vectors, and the angle as the unsigned angle between the two vectors. This approach does require some special-case handling though (there's a couple of nice quaternion-based alternatives that have fewer special cases).

Assume: Unit sphere centered at origin (You can generalize!).

Variables:
k = index of timestep
p[k] = position at timestep k
v[k] = forward (unit) vector at timestep k
r[k] = right (unit) vector at timestep k
u[k] = turning rate. Positive for left, negative for right.
s[k] = walking speed.

The following predictor-corrector scheme will walk around the sphere (or, "parallel transport the frame"):

p[k+1] = normalize(p[k] + s[k]*v[k]*dt)
v[k+1] = normalize(v[k] - s[k]*p[k]*dt - u[k]*r[k]*dt)
r[k+1] = normalize(r[k] + u[k]*v[k]*dt)

[EDIT: I'd left out a term; fixed.]

In principle, all your vectors will remain orthogonal and unit length under this iteration. In practice, rounding errors may make this not so. To correct this, you can occasionally do the following:

v[k] := normalize(Project_perp(v[k], p[k]))
r[k] := normalize(Project_perp(Project_perp(r[k], p[k]), v[k]))

where

Project_perp(a,b) = a - <a,b> b

with <a,b> representing the dot (or "inner") product of a and b (note: this is for unit vectors, which is what I have in this example; you can generalize). This projection step is really Gram-Schmidt orthonormalization. I.e., you're snapping all your vectors to be perpendicular to one another.

You can also do this more exactly with some exact rotations (just remember that walking forward on a sphere means rotating about an axis parallel to your right vector and passing through the center of the sphere), but with a small timestep this is nearly the same thing.

Finally, I should point out that there really aren't any special cases in any of this; you're just working with global representations for rotations, really...

[EDIT: I should add that the basic idea here comes from the notion of a Darboux frame.]

[Edited by - Emergent on November 10, 2010 10:55:27 PM]

Quote:

Finally, I should point out that there really aren't any special cases in any of this; you're just working with global representations for rotations, really...

Was that in reference to my post? If so, I was just referring to the possible special-case handling involved in computing the corrective rotation, that's all. (The specific case being when the input vectors are nearly parallel and the cross product has small magnitude. The quaternion versions of the algorithm don't suffer from this problem though.)

Quote:

Original post by jyk Was that in reference to my post? If so, I was just referring to the possible special-case handling involved in computing the corrective rotation, that's all. (The specific case being when the input vectors are nearly parallel and the cross product has small magnitude. The quaternion versions of the algorithm don't suffer from this problem though.)

Yeah, your mention of special cases had confused me a little, because what I was doing has none (now that I look at it, there's isn't a single if statement in the whole thing), and initially I'd assumed that what you had described in words couldn't be that different from what I was describing in equations -- unless maybe I'd misunderstood whalebiologist's question (I'd never player Super Mario Galaxy).

But now I just reread your post more carefully, and I see that we really are talking about the same thing -- and I see where our approaches differ.

The difference is that I explicitly keep a "right" vector around as part of the program's state, whereas you compute it as the cross product of the agent's "up" vector and the surface normal between different timesteps -- which will fail if your surface is flat or your timestep is small enough (so I get what you mean by "special cases!"). For a sphere, you don't actually need to keep r[k] around the way I did, but the cross product I'd get it from would be r[k]=(p[k] x v[k]); this will always work regardless of timestep.

I assume that the quaternion version you referred to is basically equivalent to what I described. The vectors p[k], v[k], and r[k] are just the columns of a rotation matrix, after all.

Quote:

Original post by Emergent The difference is that I explicitly keep a "right" vector around as part of the program's state, whereas you compute it as the cross product of the agent's "up" vector and the surface normal between different timesteps -- which will fail if your surface is flat or your timestep is small enough

Yup, a 'naive' cross-product-based implementation will fail in those cases. That's why I usually recommend using one of the quaternion-based versions of the 'shortest arc rotation' algorithm, as those methods are insensitive to the alignment of the input vectors and will behave robustly even in the cases you mention. (The only special case that needs handling with the quaternion-based method is when the input vectors are oppositely aligned or nearly oppositely aligned, but any such method will need to handle that as a special case.)

For the case of a sphere I imagine a lot of this can be avoided, but for what it's worth, the 'corrective rotation' method can be used with arbitrary environments (not only with spheres). That may not be relevant for the OP though.

Hey Emergent,

Thanks for your solution here really well laid out. You lead me here from stackoverflow a few months ago, and im just getting round to implement this. I really like how simple and mathematical it is... One question before I go ahead with this is....

So say im moving my object along the sphere with its forward vector... thats all good. Now what happens if i want to set a destination point somewhere on the sphere. I need to somehow rotate this forward vector so that it point along the surface of the sphere towards the target. any clues on how this might work??

So say im moving my object along the sphere with its forward vector... thats all good. Now what happens if i want to set a destination point somewhere on the sphere. I need to somehow rotate this forward vector so that it point along the surface of the sphere towards the target. any clues on how this might work??
This is only off the top of my head, but you could try something like this (untested pseudocode):

Vector3 diff = targetPoint - currentPosition;
targetPoint -= currentUp * dot(diff, currentUp);
float length = targetPoint.length();
if (length > epsilon) {
currentForward = targetPoint / length;
}
// Else current forward direction is as good as any.

So say im moving my object along the sphere with its forward vector... thats all good. Now what happens if i want to set a destination point somewhere on the sphere. I need to somehow rotate this forward vector so that it point along the surface of the sphere towards the target. any clues on how this might work??

There are a few different ways you could do this

The simplest: Turn 'n go

Step 1: Rotate to face correct heading
Step 2: Go straight.

You know how to do step 2, so let's just address step 1.

Say you're at a point p in R³ on the sphere, and you want to get to a point p'. The vector

v' = Project_perp(p' - p, p)

is tangent to the sphere at p and points towards p' along a geodesic.* So you just need to rotate your current velocity, v, towards v'. You can do this by choosing

u[k] = -<v', r[k]>

until that quantity is roughly zero.

* Note that this fails if p and p' are antipodes (i.e. 180 degrees apart). In this case, all directions will get you there in the same time, so just pick one at random (also, this happens with probability zero, so it's not exactly a huge deal).

A pretty one:

There's another simple method, with a complicated name, that could work. I've done it on the plane, but not on the sphere, so I'll need to get back to you on exactly how to do it. For now, I'll note that it has the following characteristics:

1 - Pro: It simultaneously turns and moves forward in a smooth, coordinated way.

2 - Con: It won't actually end up at the goal point p', but rather at some point a distance epsilon from p'.

I'll also hint at the idea: You tie a stick of length epsilon to the front of your dude, and attach a spring between the end of the stick and the goal. At equilibrium, the end of the stick will be at the goal, which means the dude will be epsilon from the goal. You need the stick so that the spring has a moment arm to exert torque on the dude to turn him. This intuitive set of ideas gets called "approximate diffeomorphism feedback linearization control of unicycles" in my field. Yay, syllables! ;-)

(I'll get back to you on a sphere implementation, if you're interested.)

Say you're at a point p in R³ on the sphere, and you want to get to a point p'. The vector

v' = Project_perp(p' - p, p)

is tangent to the sphere at p and points towards p' along a geodesic.* So you just need to rotate your current velocity, v, towards v'.

@The OP: Note that this is more or less the same as what I suggested earlier. (My solution was simply for computing a new forward direction vector, but you can of course rotate towards the new orientation if preferred.)