Mesh generation for procedural city generator

Question

I have a programming problem relating to mesh generation for city grids. I've recently created a city grid generator and I've come as far as being able to reliably generate the road mesh for the grid my system spits out. However, now I am stuck with finding a method to generate the lots and spaces in between the roads. Eventually, I want the city grid to have elevation changes and for that, I need to be able to fill in the spaces between the roads.

Here's an example of what I have:

I've looked into triangulation methods like Delauney Triangulation, but the output is unreliable (maybe due to the way I am using it). Here's another example that shows the problem (the black lines are the road mesh, the magenta ones are the Delauney output):

For the most part, the Delauney output follows the mesh when I present it with only the vertices that make up the intersections. However, sometimes, the Delauney triangles overlap the ones from the road mesh (like with the wide road in the center of the image). I am using a port of as2Delauney for Unity and I simply create a list of all the vertices that make up the intersections and then pass it to the Delauney function and I wonder if there is something I need to consider before passing a bunch of points and letting the function sort it out.

Are there any special considerations I need to be aware of when using Delauney for this type of triangulation, or are there any other methods that I could use to create the fill ins for the road mesh?

I've thought about building a function that tries to follow the intersections in clockwise or counterclockwise order until it loops back to the start, but that would lead to infinite loops as some roads are dead ends.

Right now I am not really sure what to look for as I lack terminology and google has yielded no results as to the methods that I could use to generate the fill ins for the road mesh (there is some good stuff on city generation, however not on the mesh part).

Does anyone have any experience with this?

Edit: This is how my system works:

Basically, I use an open list of lines to grow my network and I check the lines against a bunch of constraints. Then I go through each line and I generate intersections for each start and endpoint. So if the end/start is already in my list, I add the other point as a destination for the current intersection.

I end up with a list of custom objects that hold their own position vector and all the position vectors of the intersections it connects to. With this I then create the mesh points for the intersection by checking the cutting points of the lines that make up the sides of the roads, so I have those points at my disposal and i use them to create the triangles for my mesh.

Now I just need to know how to organize them to create the fill ins that span multiple intersections.

Answer 1

There'a a variant of delaunay triangulation: Constrained delaunay triangulation lets you define which edges should never be flipped, e.g. in your use case, the edges belonging to roads.

Unfortunably, out of my head, for libraries which implement constrained delaunay, I can only mention CGAL, which is C++ and released under GPL: http://doc.cgal.org/Manual/3.3/doc_html/cgal_manual/Triangulation_2_ref/Class_Constrained_Delaunay_triangulation_2.html

That would allow you to properly triangulate the spaces between roads without damaging the road polygons. You could then use something like the methods described in "Procedural Generation of Parcels in Urban Modeling" by P. Cignoni and T. Ertl (https://www.cs.purdue.edu/cgvlab/papers/aliaga/eg2012.pdf) to divide the resulting city blocks into parcels.

TL;DR: One of the simpler algorithms presented in the paper goes like this:

For each space between roads: generate the oriented bounding box (OBB), divide the polygon along the longest axis, repeat for the resulting smaller OBBs until statisfied. Then place buildings to taste.

Answer 2

Problem

You need consistency in your systems / data structures. From your image, it appears that you:

1. Generate the basics on a regular grid / 2D array, where you have m vertices across, and n vertices down for a m x n grid. Then you have m-1 interstices across and n-1 interstices down. (This takes into account only intersections, not splits of each road into 2 segments. It also does not accommodate expansions / inclusions - see "high street", below.)
2. Split every road segment into 2 rects / 4 tris. I think to assist the curving roads (see next step).
3. Perturb these resultant points or otherwise apply a transformation across the entire space. This gives subtle curvatures to different city sections.
4. Try to overlay the lots (interstices) mesh, over the rest.

Resultant issues:

1. You're not tracking those splits on step 2, in your base array. By adding these splits, you've roughly doubled the number of points, but the base array does not reflect the new vertices created. So on step 4 above, you aren't matching vertices exactly.
2. You appear to have a special "high street" running through town, that is not reflected in the original data structure which you are using to generate the lots / interstices mesh.
3. Using a 2D array as your base data, you get crossings where you probably don't want them.

To clarify further, I've superimposed some split lines over the interstices ([0]s in solution, below):

Solution

You need an intermediate data structure that can hold your special case additions (splitting each road segment into 2 rects / 4 tris, and generation of a high street after the overall grid generation). You should use a graph, where every node represents not a road intersection, but rather any line down which we can split road segments, and where every edge represents a segment of road, e.g.

[I]--[0]--[I]--[0]--[0]--[0]--[I]->
 |Lot1     |Lot2               |
[0]       [0]                 [0]
 |         |                   |
[I]--[0]--[I]--[0]--[0]--[0]--[I]->
 |         |                   |
 V         V                   V

[0] = splits in the road, they are basically vertices where you split each road segment into 2 rectangles. [I] = intersections. Note that above and below Lot2, there are 4 segments of road, not just 2. This is to illustrate how you could add the high street running through, by node replacement:

[I]--[0]--[I]--[0]--[I]--[0]--[I]->
 |Lot1     |Lot2     + Lot3    |
[0]       [0]       [0]       [0]
 |         |         +         |
[I]--[0]--[I]--[0]--[I]--[0]--[I]->
 |         |         +         |
 V         V         V         V

Or you could add it into the existing nodeset rather than replacing:

[I]--[0]--[I]--[0]--[0]--[I]--[0]--[I]->
 |Lot1     |Lot2          + Lot3    |
[0]       [0]            [0]       [0]
 |         |              +         |
[I]--[0]--[I]--[0]--[0]--[I]--[0]--[I]->
 |         |              +         |
 V         V              V         V

Finally, you can have each of these nodes point to special-purpose "lot nodes" in the centre:

[I]--[0]--[I]
 | \     / |
[0]-[L1]--[0]
 | /     \ | 
[I]--[0]--[I]

From the aforementioned graph, generated in full (including high street), you can then generate your meshes. Remember: Update Data/Model first (the above), then Views (mesh information); how you triangulate your additions during the latter phase, is totally distinct from the problems you're facing.

Finally, you probably really do want one single mesh to represent everything, lots and roads. Only buildings would likely be kept separate.