Roads in 3D scene

This tutorial provides some basic insight into problem of roads in 3D game engine and offers a solution using memory-friendly and in-game editable vector representation of road segments with ability to "rasterize" itself into proper 3D model as well as on demand fast data streaming.



Hello all, welcome to my first tutorial where I want to focus on roads in 3D scene and how I implemented them in my game engine. I don't claim it is the best possible solution (I really didn't perform some extensive research on internet), but my approach is very simple, reasonably fast and provides all features most people wants from their road network system. This tutorial is my response to all the people who wrote me an email (sorry I wasn't able answer you all!) and who wanted to know more information about technical details of my game engine. Now you have what you wanted plus bonus opportunity to admire my great writing skills in English :-).


Note that this tutorial is currently only in alpha version so if you find something unclear or even wrong, please send me an email.



Introduction

First we need to establish what we need from our road network implementation. Before I started coding it for my engine, I had these main points in my mind:

  • Vector representation – road network represented only by vectors has several advantages:
    • small file/memory size
    • easy manipulation in game editor (add/remove road nodes, road width and texture changes, ...)
    • fast AI pathplanning

  • Streamable – ability to load only part of the road network from data file (for example just for visible terrain tiles or tiles currently needed for pathplanning)

  • Generating nice road geometry model (textured, bump-mapped) with several LODs
    Problem of vector representation is that at some point 3D model has to be generated so we have something to draw in the scene. This new model should be textured, bump-mapped and should fit terrain geometry under it. It is significantly slow operation, luckily it can be easily parallelized using multiple threads.


Vector Representation

Representation of the roads in my engine consists from list of interconnected road segments (vectors), each with length of 5 metres described by following information:

  • ID of this segment (replaces memory pointers, see further for explanation)
  • Start/End positions in 3D scene
  • Start/End connections (IDs of previous/next segments)
  • Road type (determines road width and texture during geometry generation process)


Declaration of the road segment in C++: 
class RoadSegment
{
	RoadID _id;
    	RoadID _connections[2];
	Vec3D _positions[2];
	Type _type;
};

Streaming

The whole scene is then divided into grids (in my case 80x80m) where every tile contains list of road segments present on it. ID of the road segment contains coordinates of this tile and its index in list where it is assigned to:

struct RoadID 
{
  unsigned short X;
  unsigned short Y;
  int index;
};

Advantages of this implementation is that we can rid of memory pointers to segments we are connected to therefore we can easily save whole road network to a file and then load it back without any complications. Another significant advantage is that while traversing road network using connection lists we can determine location of the next segment and check if this tile is currently loaded in memory or not.

The disadvantage though is that after we delete some segment in editor, we need to decrement ID index values of all segments behind it in tile segment list (including IDs of their connections so we actually need to update also connections of segments from neighbor tiles which can have connections to the updated segments).

We can at least slightly speed-up searching of the segments using their IDs by union types which allows us to avoid slow comparation of all three members when we can instead compare them at once as long integer:

union RoadID 
{
 struct Coords
 { 
   unsigned short X;
   unsigned short Y;
   int index;
 } coords;
 long long int id;
 bool operator==(const ID& other) const {return id == other.id;}
};


Generating road geometry model

When road segment becomes visible, we need to create 3D model from its vector representation which can be then drawn by GPU. This process should be done for all segments in tile at once because we want rather one big model which can be drawn significantly faster than hundreds of small segments.

This new road 3D model has to have these features:

  • Has the same height profile as terrain geometry so it can be easily placed on it.
  • Has defined material properties (normals, tangent space, texture coodrinates, ...).
  • Has the same number of LODs as terrain tile.

To achieve the same height profile as terrain under it, we actually need to "cut" road model geometry by the geometry of the terrain grid under it. So after we clip individual road geometry triangle by triangle of the terrain under it, we receives several new road triangles where everyone has the size and shape that allows it to be directly placed on terrain triangle under it (see images below). I think the best way to achieve it is to use classic Sutherland–Hodgman clipping algorithm, just with modifications to obtain also material properties instead of just raw geometry.

This process consists from three main steps:
  1. Create quads from road segments
    • Create geometry quad based on segment direction, length and width.
    • If it is connected to another segment, modify edge angle for smooth transition.
    • Set texture UV coordinates to all vertices.
  2. Triangulate quads (one road segment quad → two triangles)
  3. Cut triangles by terrain grid geometry
    • Create list of terrain triangles (from selected LOD) and list of all segment triangles from selected tile and use Sutherland–Hodgman clipping algorithm to cut the geometry.
    • Calculate texture UV coordinates always when new intersection is found (it can be done by simple linear interpolation here since we intersected edge which both vertices have already set UVs). We also need to take care about new vertex normal and direction so we can later calculate tangent space for bump-mapping.
    • Expected result of this step is 3D model of all roads on this terrain grid and which can be placed on current LOD.
  4. Repeat for next LOD

This whole process may be slow but it can be easily parallelized using threads since road network no longer changes (except if editor is running, in that case we need to synchronize it with thread where geometry generator runs) so we can for example first create lower LODs (which will be needed first) and later add others.

This is C++ code my own implementation of road x terrain triangle clipping using Sutherland–Hodgman algoritm which also preserves road material atributes:

// structure to hold all necessary information about road vertex
struct RoadVertex
{
  Vec3D position;
  Vec3D normal;
  Vec3D direction; // direction of segment is needed to calculate tangent space for bump-mapping
  TextureCoordinates texCoords;
};

// Function that creates new road vertex at the intersection of road geometry edge 
// with terrain geometry edge.
RoadVertex CreateRoadVertexAtIntersection(const RoadVertex clippingEdge[2], 
  const RoadVertex polygonEdge[2])
{
  Vec3D intersection;
  float t1, t2;

  // function calculates intersection position and returns it distance on both edges
  Intersection2D(clippingEdge[0].position, clippingEdge[1].position, polygonEdge[0].position, 
    polygonEdge[1].position, false, &intersection, &t1, &t2);

  RoadVertex vertex;
  vertex.position = intersection;
  vertex.position[2] = Lerp(t1, clippingEdge[0].position.getZ(), clippingEdge[1].position.getZ());
  vertex.normal = Lerp(t1, clippingEdge[0].normal, clippingEdge[1].normal);
  vertex.normal.normalize();
  vertex.direction = polygonEdge[0].direction;
  vertex.texCoords.u = Lerp(t2, polygonEdge[0].texCoords.u, polygonEdge[1].texCoords.u);
  vertex.texCoords.v = Lerp(t2, polygonEdge[0].texCoords.v, polygonEdge[1].texCoords.v);

  return vertex;
}

// And finally function that executes Sutherland–Hodgman algorithm on two triangles:
void TriangleIntersection(const RoadVertex roadVertices[3], const RoadVertex terrainVertices[3], 
  std::vector& result)
{
  std::vector polygon;
  for (int i = 0; i < 3; i++)
  {
    polygon.push_back(roadVertices[i]);
  }

  for (int e = 0; e < 3; e++)
  {
    std::vector clippedPolygon;

    RoadVertex clippingEdge[2] = {terrainVertices[e], terrainVertices[(e + 1) % 3]};

    for (int p = 0; p < polygon.size(); p++)
    {
      RoadVertex polygonEdge[2] = {polygon[p], polygon[(p + 1) % polygon.size()]};

      if (DistanceFromLine2D(polygonEdge[0].position, clippingEdge[0].position, 
           clippingEdge[1].position) > 0.0f)  // edge start inside clipping area
      {
        if (DistanceFromLine2D(polygonEdge[1].position, clippingEdge[0].position, 
             clippingEdge[1].position) > 0.0f)  // edge end is too inside clipping area
        {
          clippedPolygon.push_back(polygonEdge[1]);
        }
        else  // edge end is outside of clipping area
        {
          // create new road vertex placed on the intersection with clipping edge
          RoadVertex vertex = CreateRoadVertexAtIntersection(clippingEdge, polygonEdge);
          clippedPolygon.push_back(vertex);
        }
      }
      else  // edge start outside clipping area
      {
        if (DistanceFromLine2D(polygonEdge[1].position, clippingEdge[0].position, 
             clippingEdge[1].position) > 0.0f)  // edge end is inside clipping area
        {
          // create new road vertex placed on the intersection with clipping edge
          RoadVertex vertex = CreateRoadVertexAtIntersection(clippingEdge, polygonEdge);
          clippedPolygon.push_back(vertex);

          clippedPolygon.push_back(polygonEdge[1]);
        }
      }
    }
    polygon = clippedPolygon;
  }

  // triangulate polygon (it should be convex)
  for (int i = 1; i < ((int)polygon.size()) - 1; i++)
  {
    result.push_back(polygon[0]);
    result.push_back(polygon[i]);
    result.push_back(polygon[i + 1]);
  }
}

After this function is called on all road triangles from the tile, result array will contain information about 3D model (every three vertices create one triangle) which can be then used to create vertex buffer and drawn on the GPU. This model has the same height profile as the terrain so it can be placed directly on sufrace without any other modifications (see image on the left).




Shaders

In vertex shader it is good to increase height of the road vertices to prevent Z-fighting, I used this simple code which increases vertex height based on its distance from camera: 

  vec4 vertexPos = gl_Vertex;
  vertexPos.z = gl_Vertex.z + dist_from_canera * 0.001;
  gl_Position = gl_ModelViewProjectionMatrix * vertexPos;

In fragment shader it is on your consideration what effects you want to have, I just implemented some basic bump-mapping using tangent space (created during geometry generation process from vertex normal and road segment direction for every road vertex). It is also good to implement alpha blending so road texture edges are smooth.


Conclusion

This tutorial provides basic solution how to represent vector roads with data streaming in 3D scene, although there is definitely much work to do, especially crossroads which are currently not supported. I hope I will have opportunity to write some other tutorial about it too in future.


Back to Tutorials