Procedural Road Generator
Language: C++, Middleware: OpenGL
Overview of the project
Motivation
- How to generate road network which suit given terrain.
Problem which I had
- The structure of road network should not be regular not like Manhattan (grid) style. Since the terrain is not flat, the elevation of terrain should vary to place roads on terrain surface.
Which features are included in this project
- Roads are intersected with others without visible flaws.
- Roads should adapt the elevation of terrain.
How to solve the problem
- Used Voronoi cell to diversify the shape of road network and each road should choose its route having minimum elevation different to go around mountains.
Limitation
- Since the system uses Voronoi, it is difficult to control the shape of road network. Namely, the user cannot control specific part of roads.
Detail of the project
1. Process of road generation
In order to generate natural road network, the system follows the process below.
(1) Terrain is generated from a plane
1. Process of road generation
In order to generate natural road network, the system follows the process below.
(1) Terrain is generated from a plane
(2) Generate base road network on the plane. Since Voronoi cell is 2D function, it should adapt the elevation of terrain
(3) Each road is subdivided into 4 segments and the segment of road adapts the elevation of terrain
(4) Each road chooses the route having minimum elevation difference
2. Specification
The process of road generation can be divided into 2 parts.
First, Voronoi Diagram is generated on a plane. Voronoi Diagram consists of Voronoi edges, Voronoi cells and Voronoi Vertex.
Voronoi edges. An edge of a Voronoi diagram is where the closest neighbor of a point changes. By continuity of the distance function, this means that every point on a Voronoi edge is equidistance from at least two sites. In other words, the points satisfy the equation
Voronoi cells. A Voronoi cell consists of all points closer to a fixed site than any other site. It can be expressed as the intersection of all halfspaces generated by the Voronoi edges for the site w.r.t all other sites. Since the bounding line is convex, the halfspaces are convex.
Voronoi vertex. Finally, a vertex of a Voronoi diagram is the intersection of at least three edges, and so a Voronoi vertex is equidistant from at least three sites.
Voronoi vertex. Finally, a vertex of a Voronoi diagram is the intersection of at least three edges, and so a Voronoi vertex is equidistant from at least three sites.
Voronoi Diagram in the plane
Second, each road is subdivided into 5 segment and each of them adapts the elevation of terrain. There are three strategy of choosing route.
Different strategy of choosing route.Blue - Minimum Elevation,
Red - Least Elevation Difference, Green - Even Elevation Difference.
(based on citygen paper)
Red - Least Elevation Difference, Green - Even Elevation Difference.
(based on citygen paper)
Minimum Elevation Strategy: This is the most basic strategy in which the sample with the lowest elevation is selected resulting in a road path similar to the route a river or a stream would take.
Minimum Elevation Difference: A more competent strategythan the first, this strategy avoids elevation drops or rises, and seeks to maintain an even elevation for the complete road segment.
Even Elevation Difference: The combination of first and seconde approach.
In this project, I used 'minimum elevation difference' approach. This approach makes roads go around the mountains rather than choosing the shortest part, which passes a peak of the mountain.
In addition, following image shows how roads adapt the elevation of terrain.
Minimum Elevation Difference: A more competent strategythan the first, this strategy avoids elevation drops or rises, and seeks to maintain an even elevation for the complete road segment.
Even Elevation Difference: The combination of first and seconde approach.
In this project, I used 'minimum elevation difference' approach. This approach makes roads go around the mountains rather than choosing the shortest part, which passes a peak of the mountain.
In addition, following image shows how roads adapt the elevation of terrain.