Introduction
During summer 2020, I wanted to try my hand at a classic procedural generation project: the procedural city. I based it loosely off of New York City, although it is intended to be flexible and art-directable. The project is done entirely in WebGL and TypeScript, with assets created in Maya and Photoshop.
Github Repo here. Demo can be found here. Requires WebGL2 and takes a bit to load.
Road Generation
Tensor-field Based Road Generation
To generate roadmaps, I relied on an extended L-System such as the one described here coupled with a tensor based method described in this paper. The road network is modeled as an undirected planar graph, stored in an adjacency list. We grow the graph from an initial list of segment/edge candidates, similar to an axiom in an L-System or Shape Grammar. Each segment candidate is extracted from the list and added to our graph (with some constraints listed below), and new candidates based on the extracted candidate are generated and added to the list.
Constraints
There are a few constraints for segment growth. If a segment goes out of our world bounds, we taper it at the bound and stop extending it. Next, if a segment intersects with or is sufficiently close to another segment already in the graph, we taper off the current segment and create a junction out of the segments. Similarly, if the segment intersects or is within the threshold of a vertex in the graph, we either attach that segment to that vertex or create a new edge from this segment to the vertex, depending on our threshold. In other words, we “snap” roads that are sufficiently near each other together.
Tensors
To generate new segment candidates, we design a 2D tensor field, which is basically just a function that maps the current vector to a set of new vectors that we can extend our roads into. For example, in the simplest tensor field, a grid, we take in the direction of a segment and output the same direction. Technically, a tensor is a 2D rotation matrix, whose eigenvectors are always perpendicular—very convenient for a road network where we often have perpendicular crossings. We can extract the directions of these eigenvectors by simply storing the angle θ of our current input vector with the x-axis (I calculated this with the inverse tangent), and calculating the vectors (cos(θ), sin(θ)) and (cos(θ + π /2), sin(θ + π / 2)). There are loads of other more technical/mathematical aspects to tensors, but for my purposes I found this conception was enough.
Designing the tensor field is where the art-directability comes in. There are many different ways to design a tensor, be it the aforementioned grid, a radial structure, a height-field based structure, or some combination of each.
In terms of implementation, for a grid, as stated above, I input the direction of the current segment and get the same direction as the output. For a radial structure, given an input segment vector, I get the direction between the segment’s endpoint and some user-specified center for the radial structure. Finally, for the height-field structure, I sample a perlin noise function and estimate the gradient of the current segment position. Again, along with these output vectors, the tensor also returns an orthogonal minor vector. To combine tensors, I linearly interpolate between these various output directions. With these simple functions, the road structure can simply be left to grow on its own, and results in a variety of networks.
Block Generation
Once the road network has been generation, I then extract spaces between the roads and turn them into city blocks.
Face Extraction
To extract faces from the generated planar graph, I used the method described here. For every vertex, we can determine all the faces adjacent to the vertex by iterating over its outgoing neighbors in counterclockwise order. We get this order by taking the cross product between each vertex and its outgoing edges, and determining the orientation (counterclockwise, clockwise, or parallel) depending on its sign. We then calculate the angles between the incoming edge and outgoing edges, and choose the smallest possible angle in counterclockwise orientation (this means that if all our edges are clockwise, we want the one with the largest angle). We traverse the edges in this order until reaching the original vertex, at which point we have determined a single, minimal face in the graph.
OBB Parceling
Blocks are generated based on the extracted faces, and inset by a constant perpendicular amount to allow room for roads. These blocks must then be further divided into “parcels” to place buildings and other elements.
For this step, I relied on the OBB parceling method in this paper. This method involves determining the Oriented Bounding Box (OBB) of a lot, then dividing the lot into pieces based on the edges of the OBB. To calculate the minimum OBB of a face, I iterate through all the edges in the face and rotate the polygon so that the current edge is aligned with the x-axis. I then calculate the bounding box in the x and z axes on this transformed shape, which simply requires us to calculate the minimum and maximum x and z coordinates out of all the points in the shape.
Once the OBB is determined, I then recursively divide each parcels in the direction of the shorter axis of the box (and thus orthogonally to the longer axis), until we reach a specified recursion depth or the parcels are below a specified area.
Along with block subdivision, parcels also provide a convenient method for many other types of asset distribution. For example, in the building generation stage, when decorating roofs, I use parcels to determine the placement of various assets in order to prevent self-intersections as much as possible.
Parcel Subdivision
Dividing parcels turned out to be a convenient extension of road generation, since I already had the architecture for planar segment intersection and face detection. To split a parcel, I create a long segment centered at the given point and pointing in the given direction, and determine all the points of intersections within the parcel graph. The splitting segment is long enough that it will easily cover the bounds of the graph. I then sort the resultant intersections in terms of distance from one endpoint of the graph, and for every pair of contiguous edge intersections, I split those edges at the intersections and create a new edge between them. We know that every time we cross an edge, we either enter or exit the face depending on if we were previously inside the face or not. Thus, assuming we begin outside the shape with our segment, we know that every two intersections in sorted order represents an entrance and an exit in our face, and thus we must split the graph along that edge. When dealing with concave polygons, we avoid adding an edge when we are not inside the shape.
Once we have generated a divided planar graph, we can again find the faces in that graph to determine our new parcels.
Building Generation
Shape Grammars
I used Shape Grammars to generate buildings. This method takes a set of starting shapes denoted with a specific label, and recursively iterates over this set, replacing each shape with a set of new shapes based on its label. For example, a box labelled “building” may be replaced with a set of smaller boxes that represent distinct floors of the building, then each of those floors might be replaced with geometry for windows, doors, and other details. We can also use shape grammars to generate unique architectural structures by performing various randomized transformations on existing shapes. This lets us create interesting and varied geometry out of only a few simple primitives, mainly cubes and planes.
In this implementation, bounding volumes for each building are generated based on our roads and scaled to match a specific height field. These volumes take the form of extruded planar facades. The volumes are then iteratively subdivided into smaller bounding structures to create varied and interesting building shapes. Once the outer hull of the building has been determined, the structure is then divided into levels for an entrance, middle floors, and roof. Depending on the level, the planar facades are then subdivided into sections for various features such as windows, doors, and foliage.
One useful application of this process is that we can guarantee buildings retain their original bounding positions in the x and z axes, preventing them from colliding and intersecting with other structures provided the original bounding boxes were well arranged.
The buildings are organized in a scene graph that follows this basic hierarchy:
Parent -> Subdivided bounding boxes -> Planar facade structures -> Divided Planes -> Facade Features
I found this to be somewhat easier for performing more detailed spatial transformations, since I got to work in local space when it came to specifying subdivisions and other operations. This also allowed me to store parameters for each building in the parent node (like textures, window and door types, etc.), which could be easily applied to all of its children to maintain architectural consistency.
Building Footprints
Facade shapes are generated by taking a face, given as a path of ordered planar vertices, and extruding a plane from each edge to a specified height. This approach lets us generate decently complex structures that are more interesting than simple boxes. It’s fairly easy since we only need to specify geometric points on a plane, whether through hard-coded or procedural means.
Levels of Detail
This process also gives us a convenient method for generating multiple levels of detail. Generating full detailed buildings becomes unsustainable after a certain point. However, we can resolve this by using the much simpler bounding volumes for larger cities, which is very efficient and lets us generate a lot of geometry over a large area. These look relatively acceptable from a far distance and make it much easier to load and visualize large road networks.
Other Assets
Models and Foliage
The city includes foliage generated by my L-System foliage tool, and distributed with some variance along city blocks based on observation. I also modeled simple street lamps to place along parcels. At some point I also plan on adding more detail with objects like traffic signs, mailboxes, trashcans, etc.
Textures
I created the textures by taking photos of various buildings around my neighborhood and assembling their parts in Photoshop. To save space on WebGL, textures are stored as cells on a 4096×4096 image. I’m currently still working on getting the textures and normal maps to my liking, although the works in progress can be found on Github.
