Interpolation between two 3D points?

I'm working with some splines which define a path a character follows (you can see a gameplay video here to get a better understanding of what's going on: http://www.youtube.com/watch?v=BndobjOiZ6g). Basically the characters 'forward' look direction is set to the 'forward' direction of the spline and when players tilt their phone left and right the character is strafed along its 'right' coordinate.

The issue with this is (rather obviously) in performance, interpolating over a spline to find the nearest position and tangent relative to the player is an incredibly costly operation. To get by this I cache a finite number of positions in what I call 'SplineDetails', the class is as follows:

public class SplineDetails
{
public SplineDetails()
{
Forward = Vector3.forward;
Position = Vector3.one * float.MaxValue;
Alpha = -1;
}
public float Alpha; // [0,1] measured along length of spline where 0 is the initial point and 1 is the end point of the spline
public Vector3 Position; // the point of the spline at this alpha
public Vector3 Forward; // the forward tangent of the spline at this alpha
}


I populate this with say 30 coordinates and I can give a rough estimate of a coordinate and 'forward' based on a position past in. It's not as accurate but it's much faster.

But now I'd like to make the system work better by estimating positions and 'forward' directions by interpolating between two of the cached points though I'm stuck trying to figure out some logic.

My first problem is, how can I determine between which two points the object is? Given each point can be placed at different intervals along the spline it could mean that two points in front or behind the object can be closer to the object.

The other problem is to figure out the proportion between the two paths it's between, i.e. if there is a point a at coordinate (0,0,0) and point b at coordinate (1,0,0) if the object is at position (0.5,0,0) then the result it should give is '0.5' (as it is equal distance away from point a and point b). That's a simple example, but what if the object is at coordinate (0.5,3,0) for example?

• A related question: if the object can only strafe w.r.t. the original (center) spline, why not keep the strafe amount as a control parameter and forget about projection altogether? That way you can still "advance" with the time parameter and with the other control the position of the player. Whenever a strafe command is issued, you could "slow down" the t time parameter and make it look like it's advancing less in the forward position. Could it work perhaps, to keep track via a spline offset (time) and a strafe offset (s)? – teodron Jun 17 '12 at 15:00
• I'm not sure I follow? The character moves forward based on its own move function, it doesn't move along the spline, just finds the splines nearest 'forward' and sets that as its forward move. – meds Jun 17 '12 at 15:02
• If you're not using the spline as a reference for 'right' and 'forward' then you can just store the initial forward and right direction (i.e: using unit vectors) and rotate said vectors when the camera is rotated. Any time the camera is rotated you apply the same rotation (or the opposite when the camera is pointing backwards, as in the video) to said memorized unit vectors, and apply them to the current character position. – Darkwings Jun 17 '12 at 21:01
• The cameras position is set using the spline too so no help there and I am using the spline for 'forward'. – meds Jun 18 '12 at 0:34
• Wait, then the character does actually follow the spline. If you define the spline using an approximating set of points, then setting a start and a goal would give you a way to determine the 'next' point to reach. If the points are close enough to each other, then using the next point as 'forward' should be close enough to the actual spline 'forward'. Assuming the spline (the track) is static getting the correct number of points and storing them in some list-like form shouldn't be a problem. – Darkwings Jun 18 '12 at 21:50

1. Find distance L the proportion p between the two points P1 and P2

L = dot_product ( P - P1, P2 - P1) / length ( P2 - P1 )

p = L / length ( P2 - P1 )

2. Find vector D by interpolating between vectors D1 and D2 using p

D = D2 * p + D1 * (1 - p)

3. Find the middle point M by interpolating P1 and P2

M = P2 * p + P1 * (1 - p)

4. Find the vector A = M - P

5. The desired direction in blue is A + D, optionally by multiplying A by a smoothing factor would cause the object to move faster or slower toward the spline