Week 4 — Road Geometry, Lanes, and Map Representation

Overview

A driving simulator is only as good as its road model. This week builds the data structures and procedural geometry for roads, lanes, and intersections, and a lane graph that downstream systems (traffic agents, routing, planning) will traverse. The road is represented twice: as a semantic structure (lanes, connectivity, rules) for reasoning, and as rendered geometry (procedurally generated mesh) for display and sensors. Keeping these two representations consistent but separate is the core design idea.

Course 5 supplied the differential geometry of curves (curvature, arc length) and graph algorithms (shortest paths) that this week applies — lane centerlines are curves, and the lane graph is a graph. By the end you have a procedurally rendered road network with a queryable lane graph.

Readings

FCG: procedural geometry generation. Extract: turning a centerline curve into a triangulated road surface.
3DMP: splines/curves and coordinate frames. Extract: spline representation of lane centerlines.
(Curvature/arc length of curves and graph/shortest-path algorithms: assumed from Course 5.)

Key Concepts

Lane centerlines as curves

A lane is a centerline curve (polyline or spline) plus a width and attributes (direction, speed limit, type). Sampling the curve by arc length gives evenly spaced points for meshing and for agents to follow. Curvature (Course 5) along the centerline bounds vehicle speed and is reused by the planner — the same geometry serves rendering and reasoning.

The lane graph

Model connectivity as a directed graph: each lane is a node (or a sequence of lane segments), and edges encode legal successors (through an intersection: left/straight/right turn connections). A four-way intersection with three legal moves per incoming road contributes twelve connection lanes, each a short curve. This graph is what routing (Week 9) searches and what traffic agents (Week 5) follow.

Procedural road mesh

Generate the road surface mesh by sweeping the lane cross-section along the centerline: at each sampled point, place left/right edge vertices offset by half-width along the curve normal, and triangulate between consecutive cross-sections. Add lane markings as textured quads or separate geometry. The intersection polygon is the union/blend of incoming road ends.

Semantic vs rendered separation

The semantic model (graph + attributes) drives behavior; the mesh drives display and sensors. They are generated from the same source curves but stored separately so that, e.g., the planner never parses triangles and the renderer never needs rule data.

Theory Exercises

Given a spline centerline, derive the left/right road-edge vertices at arc-length sample \(s\) using the curve normal and lane width.
Model a four-way intersection as a lane graph: enumerate nodes and connection edges for three legal moves per incoming road.
Compute the max safe speed on a lane segment from its curvature and a lateral-acceleration limit (Course 5 geometry + a friction bound).
Describe a data structure for the lane graph supporting efficient successor and shortest-path queries.
Estimate triangle count for a road network of total length \(L\) at cross-section sample spacing \(\Delta s\).

Implementation

Build the lane/road data model (engine/simulation or a map/ module), a procedural road-mesh generator, and a lane graph with successor/shortest-path queries. Render a simple network (a few roads + one four-way intersection) using the Week 3 renderer. Visualize the lane graph overlay for debugging.

Benchmark

Road-mesh generation time vs network size; lane-graph query latency (successor, shortest path); triangle count and render cost of the generated network. Verify generated curvature matches the analytic centerline curvature.

Expected baselines: mesh generation is a one-time cost proportional to road length; graph queries are fast (small graphs); the rendered network’s cost is dominated by triangle count, foreshadowing Week 10 scaling. Curvature sampling matches analytic values within discretization error.

Connections

The lane graph is traversed by traffic agents (Week 5) and the route planner (Week 9); centerline curvature feeds feasibility/speed limits. The procedural mesh is what the camera sensor (Week 7) sees. Course 5’s curve geometry and graph algorithms are applied directly here.