# How do I generate a 3D race track from a spline?

I want to generate a 3-dimensional race track around a spline that describes its shape. Here's an illustrative video.

The track should be an endless tunnel that sweeps along a 3D spline, with some obstacles thrown in. My best idea so far has been to loft a circle shape along the spline.

I would also like some pointers into how to manage the geometry i.e. how to create it from the loft operation, manage its 'lifecycle' in memory, collision and texturing.

• Looks very much like proun: proun-game.com. If there are no copyright issues, you might get a good answer out of the author of this game. You can get his info here: blog.oogst3d.net. – Vite Falcon Jan 30 '12 at 15:33
• yeah i was thinking about that - tnx! – Valentin Galea Jan 30 '12 at 15:45

I'm not sure what language you are working in but there is a procedural mesh extrusion example for Unity3D located here:

http://unity3d.com/support/resources/example-projects/procedural-examples

I'm sure you could look at the code and rework it for your situation.

EDIT: I'm working on a game that uses a procedural extruded rail system like the one you are starting but it's in C# in Unity3d. I'll give you an overview of how I create my rail extrusion based on a Cubic Bezier path so although the rail's mesh is procedurally generated, it's based on the Bezier path that I define ahead of time in an editor. It would be like a level editor in the case of your game, in my case, it's designing pinball tables. Listed below is an example of how I'm doing it:

1.) Build/Find and Implement a Bezier Path Class. This will give you the source data for your mesh extrusion. There is one in C# here that you can port to c++.

2.) Once you have a Bezier Path created, data points from this path are sampled. This can be done via the Interp method on the class provided above. This will give you a list/array of Vector3 points along the Bezier path.

3.) Create a helper class to convert the Vector3 Bezier path data from step 2. In this case, I have a simple class called ExtrudedTrailSection as defined below:

public class ExtrudedTrailSection
{
public Vector3 point;
public Matrix4x4 matrix;
public float time;

public ExtrudedTrailSection() { }
}


4.) Iterate through your Vector3 sample data and convert to an array of ExtrudedTrailSections supplying it with the sample data and a base matrix that would be the root location of your extruded mesh.

1. ) Use the array of ExtrudedTrailSections to create an array of final Matrix4x4[] using the following code:

Matrix4x4 worldToLocal = rootTransform.worldToLocalMatrix;

    for (int i = 0; i < trailSections.Count; i++)
{
if (i == 0)
{
direction = trailSections[0].point - trailSections[1].point;
rotation = Quaternion.LookRotation(direction, Vector3.up);
previousRotation = rotation;
finalSections[i] = worldToLocal * Matrix4x4.TRS(position, rotation, Vector3.one);
}
// all elements get the direction by looking up the next section
else if (i != trailSections.Count - 1)
{
direction = trailSections[i].point - trailSections[i + 1].point;
rotation = Quaternion.LookRotation(direction, Vector3.up);

// When the angle of the rotation compared to the last segment is too high
// smooth the rotation a little bit. Optimally we would smooth the entire sections array.
if (Quaternion.Angle(previousRotation, rotation) > 20)
rotation = Quaternion.Slerp(previousRotation, rotation, 0.5f);

previousRotation = rotation;
finalSections[i] = worldToLocal * Matrix4x4.TRS(trailSections[i].point, rotation, Vector3.one);
}
// except the last one, which just copies the previous one
else
{
finalSections[i] = finalSections[i - 1];
}
}


6.) Now you have an array of Matrix4x4[] and can extrude a mesh but first we need a reference mesh to extrude from. I have a utility class that will create a circular mesh face that we will supply to the mesh extrusion method.

public static List<Vector2> CreateCircle (double radius, int sides)
{
List<Vector2> vectors = new List<Vector2> ();

const float max = 2.0f * Mathf.PI;
float step = max / sides;

for (float theta = 0.0f; theta < max; theta += step) {
}

return vectors;
}


7.) Find the center of this data:

    public static Vector2 CalculateCentroid(List<Vector2> vectorList)
{
//////////////////////////////////////////////////////////////////////////
// Local variables.
float fArea = 0.0f, fDistance = 0.0f;
Vector2 vCenter = Vector2.zero;
int nIndex = 0, nLastPointIndex = vectorList.Count - 1;
//
//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
// Run through the list of positions.
for (int i = 0; i <= nLastPointIndex; ++i)
{
//////////////////////////////////////////////////////////////////////////
// Cacluate index.
nIndex = (i + 1) % (nLastPointIndex + 1);

// Calculate distance.
fDistance = vectorList[i].x * vectorList[nIndex].y - vectorList[nIndex].x * vectorList[i].y;

// Acculmate area.
fArea += fDistance;

// Move center positions based on positions and distance.
vCenter.x += (vectorList[i].x + vectorList[nIndex].x) * fDistance;
vCenter.y += (vectorList[i].y + vectorList[nIndex].y) * fDistance;
}
//
//////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////
// Calculate the final center position.
fArea *= 0.5f;
vCenter.x *= 1.0f / (6.0f * fArea);
vCenter.y *= 1.0f / (6.0f * fArea);
//
//////////////////////////////////////////////////////////////////////////

return vCenter;
}


8.) Now that we have the edge and center data for a radial face mesh, you can construct a mesh object using your data. The final vertex in the mesh is the center point we calculated. The final mesh is just a face that is supplied to the mesh extrusion method that I provided an example of in the Procedural mesh extrusion class of the Unity package. Again, this is my method and obviously you would have to feed this data into OpenGL. If you have a 3d utility library that you are using or can write your own mesh class, it would probably work better to generate your final extruded mesh as this data isn't really needed by opengl for rendering. This face mesh is just used as the reference for the mesh extrusion.

    List<Vector3> levelVerts = new List<Vector3>();
List<Vector2> levelUVBary = new List<Vector2>();
List<Vector2> levelUVs = new List<Vector2>();
List<int> levelTris = new List<int>();

int verticesPerNode = 4;
int edgeCount = sourceMeshData.Count;

List<Vector3> sourceVerts = new List<Vector3>();
//Debug.Log("smd.c:" + sourceMeshData.Count);
for (int i = 0; i < edgeCount; i++)
{
//sourceVerts.Add(new Vector3(levelShapeData[i].x, levelShapeData[i].y, modelLength / 2f));
}

for (int i = 0; i < edgeCount - 1; i++)
{                                       //0, 1, 2, 3
levelTris.Add(sourceVerts.Count - 1); //4, 4, 4, 4
levelTris.Add(i + 1);               //1, 2, 3,
}



9.) Find the outside edges of the circular mesh as needed by the mesh extrusion method. Again, this code is provided in the unity package.

public class Edge
{
// The indiex to each vertex
public int[]  vertexIndex = new int[2];
// The index into the face.
// (faceindex[0] == faceindex[1] means the edge connects to only one triangle)
public int[]  faceIndex = new int[2];
}

public static Edge[] BuildManifoldEdges (Mesh mesh)
{
// Build a edge list for all unique edges in the mesh
Edge[] edges = BuildEdges(mesh.vertexCount, mesh.triangles);

// We only want edges that connect to a single triangle
ArrayList culledEdges = new ArrayList();
foreach (Edge edge in edges)
{
if (edge.faceIndex[0] == edge.faceIndex[1])
{
}
}

return culledEdges.ToArray(typeof(Edge)) as Edge[];
}


10.) Feed all of this data into the Mesh Extrusion method..

public static void ExtrudeMesh (Mesh srcMesh, Mesh extrudedMesh, Matrix4x4[] extrusion, Edge[] edges, bool invertFaces)
{
int extrudedVertexCount = edges.Length * 2 * extrusion.Length;
int triIndicesPerStep = edges.Length * 6;
int extrudedTriIndexCount = triIndicesPerStep * (extrusion.Length -1);

Vector3[] inputVertices = srcMesh.vertices;
Vector2[] inputUV = srcMesh.uv;
int[] inputTriangles = srcMesh.triangles;

//Debug.Log("inputUV:" + inputUV.Length);

Vector3[] vertices = new Vector3[extrudedVertexCount + srcMesh.vertexCount * 2];
Vector2[] uvs = new Vector2[vertices.Length];
int[] triangles = new int[extrudedTriIndexCount + inputTriangles.Length * 2];

// Build extruded vertices
int v = 0;
for (int i=0;i<extrusion.Length;i++)
{
Matrix4x4 matrix = extrusion[i];
float vcoord = (float)i / (extrusion.Length -1);
foreach (Edge e in edges)
{
//Debug.Log(e.vertexIndex.Length);
vertices[v+0] = matrix.MultiplyPoint(inputVertices[e.vertexIndex[0]]);
vertices[v+1] = matrix.MultiplyPoint(inputVertices[e.vertexIndex[1]]);

uvs[v+0] = new Vector2 (inputUV[e.vertexIndex[0]].x, vcoord);
uvs[v+1] = new Vector2 (inputUV[e.vertexIndex[1]].x, vcoord);

v += 2;
}
}

// Build cap vertices
// * The bottom mesh we scale along it's negative extrusion direction. This way extruding a half sphere results in a capsule.
for (int c=0;c<2;c++)
{
Matrix4x4 matrix = extrusion[c == 0 ? 0 : extrusion.Length-1];
int firstCapVertex = c == 0 ? extrudedVertexCount : extrudedVertexCount + inputVertices.Length;
for (int i=0;i<inputVertices.Length;i++)
{
vertices[firstCapVertex + i] = matrix.MultiplyPoint(inputVertices[i]);
uvs[firstCapVertex + i] = inputUV[i];
}
}

// Build extruded triangles
for (int i=0;i<extrusion.Length-1;i++)
{
int baseVertexIndex = (edges.Length * 2) * i;
int nextVertexIndex = (edges.Length * 2) * (i+1);
for (int e=0;e<edges.Length;e++)
{
int triIndex = i * triIndicesPerStep + e * 6;

triangles[triIndex + 0] = baseVertexIndex + e * 2;
triangles[triIndex + 1] = nextVertexIndex  + e * 2;
triangles[triIndex + 2] = baseVertexIndex + e * 2 + 1;
triangles[triIndex + 3] = nextVertexIndex + e * 2;
triangles[triIndex + 4] = nextVertexIndex + e * 2 + 1;
triangles[triIndex + 5] = baseVertexIndex  + e * 2 + 1;
}
}

// build cap triangles
int triCount = inputTriangles.Length / 3;
// Top
{
int firstCapVertex = extrudedVertexCount;
int firstCapTriIndex = extrudedTriIndexCount;
for (int i=0;i<triCount;i++)
{
triangles[i*3 + firstCapTriIndex + 0] = inputTriangles[i * 3 + 1] + firstCapVertex;
triangles[i*3 + firstCapTriIndex + 1] = inputTriangles[i * 3 + 2] + firstCapVertex;
triangles[i*3 + firstCapTriIndex + 2] = inputTriangles[i * 3 + 0] + firstCapVertex;
}
}

// Bottom
{
int firstCapVertex = extrudedVertexCount + inputVertices.Length;
int firstCapTriIndex = extrudedTriIndexCount + inputTriangles.Length;
for (int i=0;i<triCount;i++)
{
triangles[i*3 + firstCapTriIndex + 0] = inputTriangles[i * 3 + 0] + firstCapVertex;
triangles[i*3 + firstCapTriIndex + 1] = inputTriangles[i * 3 + 2] + firstCapVertex;
triangles[i*3 + firstCapTriIndex + 2] = inputTriangles[i * 3 + 1] + firstCapVertex;
}
}

if (invertFaces)
{
for (int i=0;i<triangles.Length/3;i++)
{
int temp = triangles[i*3 + 0];
triangles[i*3 + 0] = triangles[i*3 + 1];
triangles[i*3 + 1] = temp;
}
}

extrudedMesh.vertices = vertices;
extrudedMesh.uv = uvs;
extrudedMesh.triangles = triangles;
}


The final output in my case looks like this..

Good luck, your game looks really cool! Let me know if you figure it out?

Chuck

• I am primarily interested in OpenGL and C++, but 'pseudocode' should help too :) – Valentin Galea Feb 1 '12 at 10:30
• I've updated my original post to include a solution that i've just completed. – Chuck D Feb 1 '12 at 20:40