The story of the endless city. On Three.js

WebGL is one of the most interesting new technologies that can miraculously transform the Internet. On the basis of this technology, several engines have already been created that allow you to create amazing things without any extra efforts, and the most famous of them is Three.js. Getting to know him was my longtime desire, and the best way to do this is to create something interesting. The first idea was to jot down an “inspiring” scene on Three.js containing both a large number of polygons, light sources and particles, and having, in this case, some meaningful context. Soon, this idea turned into a desire to create an endless city in which you could dive through the browser.

It is worth saying that the article is not devoted to the whole construction, but only to solving the most interesting problems that had to be faced as the scene was created.



')

Building roads

Having plunged into the works found on the Internet devoted to the procedural creation of virtual cities, I found that, as a rule, the following algorithm is used to build roads:

1. Construct one or more guide roads from one or more points, which gradually grow.
2. With growth, with a certain probability, the road can turn a certain degree, or generate another road that grows perpendicular to it with an error of several degrees.
3. As soon as the road reaches the maximum length, or intersects with another road, its growth stops.

It looks like this:


The result of the operation of this algorithm looks quite natural, however, it has several serious flaws:

1. High time complexity: for each point in time of construction, you need to go through all the roads by increasing them by a certain amount. And for each individual road, you need to go through all the unfinished roads to find possible intersections.
2. It is impossible to reproduce a section of a road if key points (from which construction starts) were out of sight, which means that it is necessary to create a large amount of data that is not needed at a particular moment.

These shortcomings do not allow building a city on the fly. Therefore, it was necessary to come up with a different algorithm, which would be deprived of these shortcomings and at the same time would give a fairly similar result. The idea was not to “grow” a canvas of roads, but to build an array of points - intersections of roads and afterwards connect them with lines. The algorithm is as follows:

1. A canvas of equidistant points (with some random error) is being built, which will be the centers of our city. For each point is determined by the size and shape within which further construction will take place.
2. For each point, within a certain form, one builds his own equidistant canvas (for a much smaller distance and also having some error) points that will be the intersection of roads.
3. Points that are too close to each other are deleted.
4. Nearest points are connected.
5. For each point, a certain number of “buildings” is built equal to the number of connections at the point. (The building is in quotes, so in theory this is not the building itself, but the form within which this building can be built, with the certainty that it will not intersect with other buildings)

Thus, the whole city is built without a heavy search for intersections, and can be recreated from any starting point. However, the algorithm still has disadvantages:

1. Intersections still sometimes occur, although their probability is quite low.
2. Sometimes there are isolated parts of the city not connected by a highway with the rest of the city.

The algorithm works as follows:

Red - viewing radius
Yellow - the maximum radius of building

Building construction

To speed up the output of complex geometry in Three.js there is a module for working with buffer geometry, which will allow you to create scenes with an incredible number of elements ( example ). However, in order for everything to work quickly, all buildings need to be stored in one single mesh, and therefore with a single material that needed to transfer several textures of buildings in order to diversify them a little. And although transferring an array of textures to a shader is not a problem, there is a special type of uniform for this in three.js, the problem was that GLSL ES 1.0 (which is used to compile shaders in WebGL) cannot be used as an index of the array, not means and use the transferred texture number for each specific building.
The solution was found in the fact that you can use a loop iterator as an index. It looks like this:

const int max_tex_ind = 3; //   uniform sampler2D a_texture [max_tex_ind]; //  varying int indx; //   (    ,     ) ... void main() { vec3 tex_color; for (int i = 0; i < max_tex_ind; i++) { if (i == indx) { tex_color = texture2D(a_texture[i],uv).xyz; } } ... } 

Of course, this solution will work well only if the maximum number of textures is not large. An alternative solution may be to use one large texture, glued from the necessary textures, but in this case you will have to sacrifice the quality of each individual texture.

Lighting

To give the city more visual appeal, I decided to add lighting simulating the light of street lamps. Of course, the standard lighting used in Three.js is not well suited for this task, while on average there are ~ 8000 sources of light on the stage. However, all this illumination is equidistant from the base, and therefore it is not necessary to process each point separately as a source of illumination, instead you can create an illumination texture, even at the stage of generation of the city. This is the texture:



All that remains to be done directly in the shader is to find the intensity of reflection of light from the plane and multiply it by the illumination specified in the texture.

Here you can go a little further. If the light sources do not intersect, you can create another texture where you can maintain the height at which the light source is located, and due to this, place the scene on the relief surface.

Smooth construction

This task turned out to be the simplest, since the basic idea was simple: it is necessary to build a city a little more than the user sees, and while he moves from one key point to another, re-generate the city based on the next key point. The main thing is to limit the speed of movement of the user so that during the move to the next point + construction time, it was impossible to reach the border of the pre-built part of the city.

As for the generation itself, all of it was divided into many stages, with statistics for each stage (which can be viewed by going to the browser console) of how long the processor takes one stage or another per frame, and if this time was more than some values, the stage was divided into several substages until it allowed to achieve consistently high FPS.

Result

The scene itself and the source code: here
Video version: