Recap
I’m thinking about how to model a road network. I’ve ruled out a tile-based approach.
How to model curves?
Representing a straight segment of road is easy: store start and end points in 3d space. The length of the road segment is just the distance between those points, and the direction of the road at either end is just the normal vector pointing at the end of the road from the start of the road.
Curves are harder though: how will we represent them mathematically? I’ve got a few implementation criteria on which to judge possible approaches:
- Simplicity – this approach needs to be easy to implement and maintain
- Performance – this approach needs to run on commodity hardware
- Interestingness – will I learn something while designing and implementing?
- Flexibility – can the network designer represent any curve that could be built in the real world using this model?
- Renderability – I need to be able to render these curves as roads on-screen
- Seam handing – can we precisely butt segments against each other so that no visible seam is present?
- Simulatability – to simulate cars running on a curve, I need to calculate
- Length of the segment
- Rate of change of direction at a point on the segment (would be nice for tighter curves to cause cars to travel slower)
- Robustness – can a curved segment be split into two segments while still meeting precisely at either end as well as at the split point?
- Can stipulate start and end point - the user should be able to choose the points at which a new road segment intersects existing road;
- Can stipulate start and end tangent - the system should constrain the curve at both ends so that the new segment aligns nicely with the existing segments it’s being welded to.
- Can influence curviness without manipulating control points - the system should not force the user to manually drag control points around. This is a road simulator and editor, not Photoshop.
- Rate of curve varies as real roads do – I believe (but haven’t tracked down any evidence yet) that in the real world, 90 degree highway curves (say) are not just circle segments (i.e. with constant radius), but instead ease in, steadily tightening the corner radius to a minimum level, and then ease out, releasing the corner radius back to infinity to blend with a straight.
- This may be important to make the curves in the simulation look “real”.
- This may be important in simulating driver behaviour.
Take the example image below. Imagine the two road segments in black have already been built, and the user wants to provide a slip lane (in red) joining the bottom leg to the left leg.
You can see that the slip lane has to align precisely with cross roads at the join points – in this mock-up, I’m a couple of pixels out, and it’s already pretty annoying :-).
Approach 1 – model curves as circular arcs
What if we model curves as segments of a circle?
Well, this approach actually works really well for the simple example shown above: the red road segment looks a lot like the top right quarter of a circle.
Life is good! We have a circle which connects A and B, and the tangent at those points is aligned with the pre-existing road at those points.
But maybe we were just lucky. Imagine that the user wants to connect B to point C rather than A. What happens then? There’s no circle which passes through C with a left-to-right tangent and also passes through B with an up-down tangent.
I’m abandoning circular arcs without proving anything, but my intuition says that just as three non-colinear points uniquely identify a circle, one point + tangent and another point also uniquely identify a circle. That is, two points that both specify tangents over-specifies the system, so you won’t always be able to find a circular arc that satisfies your givens.
Let’s move on.
Approach 2 – circles didn’t cut it, so let’s model curves as elliptical arcs
Notice in the diagram above that if we stretched the circle horizontally so that its top-most point was at C, then we’d satisfy all our requirements.
Maybe elliptical arcs can do the trick?
Well, maybe. But on the other hand, this whole approach has the smack of the epicycle to it. Time to do a bit of reading, I think.
Approach 3 – Hermites
After a bit of reading about Beziers and various generalizations, I ran into cubic Hermite splines - this article provides a nice introduction.
You might think of a curve as a way of moving a point (let’s call it “blending”) between two points A and B on a plane. The curve is then just a “history” of the point’s location at all moments in time as it moves from A to B.
The simplest blend of all has the point begin at A and move at a constant rate towards B. If we plot an X every second as the point moves from A to B, we’ll get an evenly spaced series of Xs that together plot a straight line:
We could get a bit more clever: we could start out with the point stationary at A. Then, the point could accelerate in a straight line towards B, and then slow to a stop. If we plot one X per second on this blend, we’ll see that the Xes are packed closer together at the start and end of the line, although they’re still arranged in a dead straight line:
A Hermite can provide exactly this sort of basic cross-fade, where the starting and finishing “velocity” of the point are both zero.
But the Hermite also caters for arbitrary starting and finishing velocities. So, in the example diagram above, when the point starts at A, we might give it a starting velocity of (20, 0) – that is, a steady clip to the right – and an ending velocity of (0, 20) – movement downwards, at the same speed. And in fact, a Hermite curve with those parameters actually gives a pretty close approximation to the circle segment approach. More than that, we’re able to soften or sharpen the curve by tweaking the length of the starting and ending velocity vectors.
The three curves below have the same start and end point. The first has zero start and end velocities. The second and third curves both start with a rightwards velocity and end with a downwards velocity; the only difference is the magnitude of those velocities.
Of course, we can increase or decrease the number of points we render, so as to get a smoother result:
Where does that leave us?
I've got some outstanding questions:
- How will I find the tangent (by which I'm trying to say instantaneous direction) of the curve at a point? Can I embrace my maths noob-ness and just add or subtract some small epsilon to s and find the difference, and treat that as the tangent? What happens at s == 0 and s == 1, exactly? In those two cases, I know the tangent damn well - after all, they've been specified as curve parameters.
- How will I animate a point moving at a steady speed along the curve? I can't just lerp s from 0 to 1, as (see diagrams above), three points evenly spaced in "s space" are not guaranteed to be evenly spaced in "actual physical distance covered along the curve" space. I could embrace my maths noob-ness here again and approximate the physical length of the curve for some interval of s just by adding the lengths of some division of s into small, straight line segments.
Apart from these outstanding questions, for which I'm happy I can use dirty hack approximations if I can't turn up an elegant approach, I'm very happy that Hermites will do the trick.
The results
The image below was rendered in my quick and dirty Hermite-drawing test harness in WPF.
/// <summary>
/// Generates an array of points on the Hermite curve whose parameters are passed in. Based on the approach at http://www.cubic.org/docs/hermite.htm
/// </summary>
/// <param name="p1">The start point</param>
/// <param name="t1">The direction and "strength" (magnitude does influence the shape of the curve) of the curve at the start point</param>
/// <param name="p2">The end point</param>
/// <param name="t2">The direction and "strength" (magnitude does influence the shape of the curve) of the curve at the end point</param>
/// <param name="nPoints">The number of points to return. More points gives a closer approximation to the curve.</param>
/// <returns></returns>
private Point[] GenerateHermite(Vector p1, Vector t1, Vector p2, Vector t2, int nPoints)
{
Point[] points = new Point[nPoints];
double delta = 1.0 / (nPoints - 1);
int[,] h = new int[4, 4]
{
{ 2, -2, 1, 1 },
{ -3, 3, -2, -1 },
{ 0, 0, 1, 0 },
{ 1, 0, 0, 0 }
};
double[] basis = new double[4];
double[] sMatrix = new double[4];
double[,] curveParameters = new double[4, 2]
{
{ p1.X, p1.Y },
{ p2.X, p2.Y },
{ t1.X, t1.Y },
{ t2.X, t2.Y }
};
// For each point on the curve
for (int i = 0; i < nPoints; i++)
{
double s = i * delta;
// Pre-calc our table of powers of s
for (int z = 0; z < 4; z++)
{
sMatrix[z] = Math.Pow(s, 3 - z);
}
for (int j = 0; j < 4; j++)
{
basis[j] =
sMatrix[0] * h[0, j] +
sMatrix[1] * h[1, j] +
sMatrix[2] * h[2, j] +
sMatrix[3] * h[3, j];
}
double[] result = new double[2] { 0, 0 };
for (int z = 0; z < 2; z++)
{
for (int j = 0; j < 4; j++)
{
result[z] += basis[j] * curveParameters[j, z];
}
}
points[i] = new Point() { X = result[0], Y = result[1] };
}
return points;
}
private void Window_Loaded(object sender, RoutedEventArgs e)
{
// In this method, we draw each of the curve roads in blue and then the crossroads in black.
// First, we define a bunch of hermite curves. It takes four vectors to define a hermite. We add the definitions to the List hermites.
List<Vector[]> hermites = new List<Vector[]>();
const int strenthOfSlipLaneTangents = 200;
// Sliplanes
hermites.Add(
new Vector[4] { new Vector(100, 300), new Vector(strenthOfSlipLaneTangents, 0), new Vector(300, 100), new Vector(0, -strenthOfSlipLaneTangents) }
);
hermites.Add(
new Vector[4] { new Vector(100, 300), new Vector(strenthOfSlipLaneTangents, 0), new Vector(300, 500), new Vector(0, strenthOfSlipLaneTangents) }
);
hermites.Add(
new Vector[4] { new Vector(500, 300), new Vector(-strenthOfSlipLaneTangents, 0), new Vector(300, 100), new Vector(0, -strenthOfSlipLaneTangents) }
);
hermites.Add(
new Vector[4] { new Vector(500, 300), new Vector(-strenthOfSlipLaneTangents, 0), new Vector(300, 500), new Vector(0, strenthOfSlipLaneTangents) }
);
const int strenthOfCloverLeafTangents = 450;
// Cloverleaves
hermites.Add(
new Vector[4] { new Vector(280, 300), new Vector(-strenthOfCloverLeafTangents, 0), new Vector(300, 280), new Vector(0, strenthOfCloverLeafTangents) }
);
hermites.Add(
new Vector[4] { new Vector(320, 300), new Vector(strenthOfCloverLeafTangents, 0), new Vector(300, 280), new Vector(0, strenthOfCloverLeafTangents) }
);
hermites.Add(
new Vector[4] { new Vector(280, 300), new Vector(-strenthOfCloverLeafTangents, 0), new Vector(300, 320), new Vector(0, -strenthOfCloverLeafTangents) }
);
hermites.Add(
new Vector[4] { new Vector(320, 300), new Vector(strenthOfCloverLeafTangents, 0), new Vector(300, 320), new Vector(0, -strenthOfCloverLeafTangents) }
);
// Now we've defined all our curves in the List hermites, we loop through, calling GenerateHermite to get an array of points, and then
// loop through those points, adding them to a Polyline (one for each curve)
foreach (Vector[] hermite in hermites)
{
Polyline curve = new Polyline()
{
Stroke = Brushes.Blue,
StrokeThickness = 4
};
canvas1.Children.Add(curve);
foreach (Point point in GenerateHermite(hermite[0], hermite[1], hermite[2], hermite[3], 40))
{
curve.Points.Add(point);
const bool drawPointMarkers = false;
if (drawPointMarkers)
{
canvas1.Children.Add(
new Line()
{
X1 = point.X - 10,
Y1 = point.Y - 10,
X2 = point.X + 10,
Y2 = point.Y + 10,
Stroke = Brushes.Red,
StrokeThickness = 2,
Opacity = 0.6
}
);
canvas1.Children.Add(
new Line()
{
X1 = point.X + 10,
Y1 = point.Y - 10,
X2 = point.X - 10,
Y2 = point.Y + 10,
Stroke = Brushes.Red,
StrokeThickness = 2,
Opacity = 0.6
}
);
}
}
}
canvas1.Children.Add(
new Line
{
X1 = 300,
Y1 = 000,
X2 = 300,
Y2 = 600,
Stroke = Brushes.Red,
StrokeThickness = 8
}
);
canvas1.Children.Add(
new Line
{
X1 = 000,
Y1 = 300,
X2 = 600,
Y2 = 300,
Stroke = Brushes.Red,
StrokeThickness = 8
}
);
}
Subscribe