Euler Spirals, Curves, Spiro

The euler spiral or fresnel integral

My attention was grabbed by OpenTTD before I got to finish the cffi binding generator. It led me to study euler spirals and helixes.

Screenshot from someone's multiplayer session in OpenTTD

OpenTTD is a rail networks simulator game based on square grid. It's fun but not very accurate. The game features sources and sinks for various resources. You get more money farther your trains carry their load, even if there were a fine destination nearby the source. The rails are built by laying a square at a time. You can't copy the rail configurations you've made and put them into another context. Every piece appears to the map as you lay it so you can't produce plans for the rails ahead of time. Many small problems like these motivate me to consider to build my own rail network simulator.

Grid for a rail networks simulator is a classic choice, but it brings you a macro scale idea of such networks. If you introduce micro-scale elements such as trains there, they become gigantic such as in OpenTTD. The quality or maximum speed of the rail becomes the inverse of amount of turns in the rail. The optimal track in OpenTTD is a long straight or diagonal line with terrain rolled flat under it. That can be avoided if you get rid of the grid.

Getting rid of the grids, you'll end up with rail network paths and stations. The quality of the rail can be determined from the curvature of the track and the maximum speed it allows trains to travel on it. Train trajectories can be physically modelled as they traverse the rails. There's still the problem of how to let the user lay rails on the map though. If you don't want an entirely abstract representation of rail networks, you need to define the paths as rail segments spanning over the map. Either layed out by the user or the game. Those segments must be interpolated to the map and rendered. It brings us to evaluation of splines.

The first and obvious choice would be the bernstein polynomial based curves: hermite and bezier curves. These curves would be problematic for a rails simulator because they do not produce natural-appearing trajectories between the points they connect. In fact this property makes them overall pretty ugly splines.

It takes lot of time for an artist to produce anything with bezier vectors. The usual workflow with beziers is that you draw the curves by hand in an image editing software and then fit the beziers to the handdrawn curves. In 3D modelling it gets out of hands. We see this phenomena in multitude of ugly electronic enclosures, ugly car interiors and ugly furniture made possible by beziers. Beziers give you curved surfaces, yet they suck for modelling beautiful surfaces.

Rail decomposition

Real rail networks consists of straight lines and arcs. You could piece a path out of straights and arcs in a game, it would produce weird looking tracks. There's a problem in plain lines and arcs. When a train travels a straight line with constant speed, it doesn't experience accelerations of any kind. When it travels along an arc, it experiences a constant acceleration of magnitude inverse to the radius of the arc |acc| = 1 / R. If you connect a line to an arc, you'll introduce an instantaneous change in acceleration. In a high-speed train this means that passengers will find the one side of the train more attractive for a small while when the train enters an arc. For this reason the arcs and lines are connected together with euler spirals, clothoids. During a clothoid the acceleration increases or decreases linearly in respect to the travel along it. Clothoids form beautiful curves.

When looking for resources to read, the first resource I found was the curved paths article from red blob games. It tells most of computer games settle to bezier curves and paths. It works somewhat well along the knowledge of analytic geometry. Computer modeling of things prefer discrete approaches that are usually well understood by programmers. Unfortunately we have to throw a curve into the spokes of otherwise good train of thought.

To approach construction of paths for railroad networks, you'd first think about just connecting curves with euler spiral segments. At this point it gets complex. Different people have created different ways to fit euler spirals to connect two points with varying angles and curvatures together.

Fresnel Integral gets mentioned as it is used by some of the algorithms. Apparently it could be treated similar to sine or cosine functions. There are procedures for computing the fresnel integral with accuracy in the CEPHES module, pointed out by Guide to Available Mathematical Software. Since the spiral itself is quite fun, I tried to evaluate it with euler integration at first. It shot off on x-axis and eventually stops converging entirely.

Piecewise clothoid curves are difficult to construct because the curve cannot be just strewn across points. Consider you connect orbits using a clothoid, the larger orbit must be inside smaller orbit. Opposite and other orbits require at least two clothoids between them. Scaling of the clothoid spiral will change it's curvature.

My studied led me eventually to look into the Spiro -library written by Raph Levien. It is a library written for drawing planar curves with precise curvature. Using an option in inkscape, you can use the spiro curves. Inkscape handles them in half-assed way but gives you an idea of how great they are.

When spiros fail

Occassionally the spiro solver fails to converge and you get something above. It draws your screen full of spirals. The failure itself looks exciting.

When spiros do not fail

I drew the 9-figure above using the inkscape. It took minutes and doesn't look like shit. Looking at the spiros they seem brilliant tools for drawing all kinds of shapes.

Even if you're a programmer, like me, it's perfectly pointless to read the code of the libspiro. You gain nothing from it. The effective code of libspiro is concentrated in one file, it's about 1000 lines of equations and few solvers. A little bit more useful is to look at what the functions produce, but even that doesn't open it to you. To understand how the library works you need to understand the mathematics it's rooted on.

The spiro integral, defined in levien's thesis

Fortunately the math is described in Raph Levien's thesis on interactive curve design. I'm still studying it. It seems to come in two parts you need to understand with excellence. The spiro integral and the constraint solver which fits the terms of the curvatures around line segments.

I could use the spiro library to draw my rails, but the results are correct only on the plane. It may be fine, but I'm excited about helixes too, such as the one below. It means I would have to extend ralph's code for torsion component.

A helix

While reading Raph's thesis, I became excited about possibility to apply it all on surface modeling. I have to find out if that's out of my reach or not, by trying it. The surfaces made that way would look vastly better than bezier shapes.

Having to understand mathematics related to curves has been a big crash into lots of calculus that's been previously unknown to me. It is trickling towards other complex mathematics. For example I understand navier stokes equations better now. This might get interesting.