This section contains various ideas I've had for possible future research. Most ideas will probably be quite terse in their presentation here as I hope to migrate them over to projects as I have time to develop them more fully.
I've already talked a bit about this elsewhere (articles - terrain) but I'll summarize my thoughts here. Potential gains for using a smooth terrain representation (e.g. implicit surface) and dynamically triangulating to render:
(1) Large terrain memory efficiency; the equation for an implicit surface paired with a triangulating scheme can encode large amounts of terrain for virtually no memory.
(2) Building the level of detail into the triangulation scheme prevents the necessity for lower res terrain meshes.
(3) Smooth pathfinding algorithms paired with mesh-projection methods makes pathfinding indepedent of level of detail, and removes the necessity for nav meshes, or any kind of navigation data structure.
(4) Procedural terrain algorithms tend to work better with underlying implicit surfaces than mesh-based approaches (see first example of level set surfaces project or procedural terrain project).
Downsides to the proposed scheme:
(1) Real-time triangulation of smooth surfaces is barely possible (for implicit surfaces, but possible for parametrized surfaces).
(2) Pathfinding on smooth manifolds is also extremely difficult to do in real-time.
(3) There are currently no methods that can handle pathfinding problems on smooth manifolds when there are obstacles on the manifold (regions where the paths can't enter - arguably there are methods but they turn the smooth problem into a graph-search problem).
Pathfinding on smooth manifolds with obstacles. Suppose we have a parametrization of a surface, say a Bezier patch p(u,v) embedding in Euclidean 3D space (the ambient space). Then suppose there is a region in the ambient space that paths are not allowed to enter. Further suppose we can find the outline of this obstacle on the surface p(u,v) and finding the corresponding region of the domain, (u,v) that represent invalid values. We can define a new surface p'(u,v) that is equal to p(u,v) everywhere except when (u,v) maps to a point inside the obstacle.
What we want to do is replace the "black zone" corresponding to the obstacle with an extension of the original surface p(u,v) in such a way that (1) the extension is smooth so pathfinding algorithms still work, and (2) the shortest path between any two points outside the obstacle will never pass through the obstacle.
We can do this by defining p'(u,v) to be p(u,v) when (u,v) is not inside the obstacle, and the point on a "balloon" positioned so that it's intersection with p(u,v) is exactly the outline of the obstacle. Furthermore the transition between balloon and p(u,v) must be smooth but nearly anti-parallel so that no path will ever get shorter by including some part of it. See diagram for visuals.
One of the problems with doing pathfinding on smooth surfaces is that it takes a long time. However we don't have just any surfaces; if we restrict ourselves to Bezier Patches, then we might be able to reuse our previous solutions in later pathfinding calls. Put another way, the Bezier Patch has a closed form parametrization dependent on it's 16 control points. There are two ways this can help, (1) writing down the geodesic equations for an arbitrary BP might show some symmetry that can be utilized in the numerical solution, and (2) solutions for a BP with some specified control points might be useful in finding the solution for a BP with different control points.
The Feynman Path Formulation of Quantum Physics elucidates how we can consider an electron to be a particle that travels all paths between one place and another, and the extent to which it's action is minimized along those paths corresponds directly to the probability of measurement should we decide to measure a particle path. The Feynman Propagator is the exponential of the integral of the action, integrating over all possible paths between two points. In one dimension a finite difference approximation to the paths can yield a matrix form for the propagator, which we can use to move the particle along by multiplying it's wavefunction by the propagator matrix each time step. The fact that we get a 2D (matrix) propagator from a 1D problem represents the finite difference of the velocity term in the action integral (e.g. deltaT dx/dt = x[j] - x[i]), where x[i] represents the value of the path at the ith spatial grid point.
To go to 2D (and use for pathfinding) this approach needs a tensor with four indices as opposed to two, since each path has to be broken up in two directions, and then each point along the path can vary in two directions. It's not immediately obvious what sort of transformation rules we would need to propagator the wavefunction (now a matrix). However, we could arrange all the 4D entries inside a matrix (block matrix), but this seems a bit complicated.
Opposite sign charges attract one another. In pathfinding algorithms, often the question is "find the shortest path" between two points. However, we might as a different question, "what would charges do?" If two charges are constrained to a surface, and their interaction (electric field) can only take place on the surface-- what path will they take to approach one another? To solve this problem analytically, we should consider the Poisson Equation on the surface, which involves the christoffel symbols, and is generally quite ugly. However, it does not reduce to the Geodesic Equations, and what's more, we want to solve a special case of the Poisson Eq., namely find the Green's function for the Laplacian on the surface. This approach possibly amenable to analytic techniques since there is quite extensive literature on Green's functions, however they typically refer to only curvilinear or orthogonal coordinate systems, which Bezier Patches are not.
Suppose we're pre-computing paths between points on a surface. We could store these paths as sequences of points on the surface. Now we know each path represents a Geodesic on the surface, however we don't have an analytic expression for exactly what curve the path represents. However, we know that the space of geodesics is two-dimensional, in the sense that when we specify two points, there will be a geodesic between them (we are not too concerned with the possibility of having multiple equidistant geodesics between points, since both are likely good paths for pathfinding). The question then becomes if we want to do fast pathfinding, (i.e. something better than solving the geodesic equations each time during run tim) what can we do? If we consider each path as a sequence of points, then we are essentially trying to interpolate this family of curves over a two dimensional parameter space. This is somewhat reminiscent of surface interpolation of point clouds from 3D scanners.