Interpolating between points in 3D I want to interpolate a spline of some sort between several points in three dimensions, but I have some very specific requirements.


*

*I must know the length of each spline segment between two points

*I must be able to find the point on any spline segment some distance along that spline segment

*I must be able to find the direction of the spline segment at any such point

*Interpolation between points must be smooth: i.e. first and second derivative define at all points


Additionally, the algorithm should be fast and efficient. What method would best suit my purposes?
 A: Your requirements are somewhat conflicting. #1 and #2 would lead you to use some sort of arc-spline. This is a "spline" that's composed of a sequence of circular arcs joined end-to-end. See here or here or here for more info. It is common to use a "bi-arc" construction to build arc splines. An early paper on bi-arcs is this one. You can refer to it and later papers that cite it. Using circular arcs is the simplest way of getting easy arclength computations.
But arc splines will only be tangent continuous, at best; they will have discontinuities of curvature. So, they violate your condition #4. If you use a large number of circular arcs then these discontinuities will be small, so they may be tolerable for your application. Only you can decide. A word of warning: there is only a flimsy relationship between continuity of derivatives and visual/aesthetic smoothness. So, if visual smoothness is what you really want, it might be fine to give up on C2 continuity. 
If you really need continuity of second derivatives (requirement #4), you are forced to use more complex curve segments to build the spline. The most common choice would be cubic segments (i.e. parametric cubic splines). These will give you C2 continuity, but calculating arclengths will require numerical methods. Cubic splines are somewhat easier to construct than arc splines, and lots of software is available to help.
If you're willing to do some work, you could try constructing so-called "Pythagorean Hodograph" curves. These are special polynomial splines whose arclength functions are polynomials. I guess they give you everything you want, but constructing them is fairly complicated. A good starting point is this book and other papers by Rida Farouki.
So, you can have easy construction, continuity of derivatives, speed of arclength calculations. Pick two.
A: Use a cubic spline, easy to program and fulfills requirement 4. Check Numerical Recipes.
Requirement 3 is achieved by computing the tangent vector (http://en.wikipedia.org/wiki/Differential_geometry_of_curves#Tangent_vector).
For 1. and 2., there are two options:
1) you don't care about true length, all you need is being able to move points along the curve: this is straight forward, you know the variation intervals for every pieces of the curve.
2) you do care about true length: you will need to perform some numerical integration to establish the s(t) function (curvilinear abscissa as a function of the parameter) and be able to invert it. As a first approach, sample points at increasing values of t and accumulate the chord lengths. Inversion will imply dichotomic search and inverse linear interpolation.
Additional suggestion: for good accuracy, you can implement a good numerical integration scheme, giving you a number of (t, s) values along the curve. You then accurately interpolate t as a function of s using... spline interpolation.
