Computing geodesics (or shortest paths) I'm interested in computing geodesic curves (or locally shortest paths) on surfaces in 3D. We can assume that the surface is given in parametric form $(u,v) \mapsto \mathbf{S}(u,v)$. If it helps, we can even assume that the parameterization is given by polynomials of fairly low degree (say 3, 4, or 5). Further, we are given two points $\mathbf{P}_0 = \mathbf{S}(u_0,v_0)$ and $\mathbf{P}_1 = \mathbf{S}(u_1,v_1)$ lying on the surface. 
Two questions:
(1) I want to compute a curve of minimal length between $\mathbf{P}_0$ and $\mathbf{P}_1$, and lying in the surface.
(2) I want to compute a curve between $\mathbf{P}_0$ and $\mathbf{P}_1$, lying in the surface, on which the geodesic curvature is zero at every point.
I believe questions (1) and (2) have a close relationship, though I'm not exactly sure what it is. The relationship is not particularly important to me; I mentioned it only because it might allow us to solve both problems with one method.
The surfaces I'm dealing with are "real world" ones -- think about the roof of a car, for example, or the upper surface of the wing of an aircraft. The surfaces are very smooth, and are usually convex, if that helps. There are important applications in manufacturing, which I can explain if anyone is interested.
Edit: After some more searching, I found this paper, which seems to have what I need. The ideas are quite similar to those in the accepted answer below.

HINTS:
Both are parts of the same problem. Read topic of zero geodesic curvature in differential geometry. An ODE has to be solved. There is a unique geodesic of minimum length. Experimenting with cone geodesics is convenient for theory and visualization.
To practically trace such on an airplane wing for example use a wide 3M cello tape and start sticking along an approximate direction without frills on edges. Nudge/change its start orientation, come back until there is a hit at the other point by trial and error. Like shooting a point on an hill opposite  with a gun along a curved trajectory where elevation angle is adjustable. 
Numerical BVP shoot-through techniques are done in a similar way.
