The history of the endless city. On Three.js

  • Tutorial
WebGL is one of the most interesting new technologies, which is capable of surprisingly transforming the Internet. Based on this technology, several engines have already been created that allow you to create amazing things without extra effort, and the most famous of them is Three.js. It was my long-standing desire to get to know him, and the best way to do this is to create something interesting. The first idea was to outline an “inspiring” scene on Three.js containing both a large number of polygons, light sources and particles, and having, at the same time, some meaningful context. Soon, this idea turned into a desire to create an endless city in which one could plunge through a browser.

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

image


Road construction


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

1. One or more guide roads are built from one or more points that are gradually growing.
2. With growth, with a certain probability, the road can turn a certain degree, or generate another road growing to it perpendicularly 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 something like this:


The result of the operation of such an algorithm looks very natural, but it has several serious drawbacks:

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

These shortcomings do not allow you to build a city on the fly. Therefore, it was necessary to come up with another algorithm that would be devoid of these shortcomings and at the same time give a fairly similar result. The idea was not to “grow” the roadbed, but to build an array of points — the intersections of the roads, and then connect them with lines. In detail, the algorithm is as follows:

1. A web of equidistant (with some random error) points is constructed, which will be the centers of our city. For each point, the dimensions and shape within which further construction will take place are determined.
2. For each point, within the framework of a certain form, its own canvas is constructed of equidistant (to a much shorter distance and also having some error) points that will be the intersection of roads.
3. Points that are too close together are deleted.
4. The nearest points are connected.
5. For each point, a certain number of “buildings” is constructed equal to the number of connections at the point. (The building is in quotation marks, so in theory this is not the building itself, but the form within which this building can be built, with the confidence that it will not intersect with other buildings)

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

1. Intersections still occur occasionally, although their probability is quite low.
2. Sometimes there are separate sections of the city that are not connected by the highway with the rest of the city.

The algorithm looks as follows:
image
Red - viewing radius
Yellow - limiting radius of construction


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, for everything to work quickly, all buildings must be stored in one single mesh, and therefore with a single material, which needed to transfer several textures of buildings in order to at least slightly diversify them. Although it is not a problem to transfer an array of textures to a shader, there is a special type of uniform for three.js, the problem was that in GLSL ES 1.0 (which is used to compile shaders in WebGL) it is not possible to use an array index as an index, but Means and use the transmitted texture number for each specific building.
The solution was that a loop iterator could be used as an index. It looks something 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, such a 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 a greater visual appeal, I decided to add lighting simulating the light of street lamps. Of course, the standard lighting used in Three.js is not suitable for this task, the amount of which is significantly limited, while on average there are ~ 8000 light sources on the stage. However, all this lighting is equidistant from the base, which means that it is not necessary to process each point individually as a lighting source; instead, you can create a lighting texture at the stage of city generation. This texture looks like this:

image

All that remains to be done directly in the shader is to find the intensity of light reflection 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 save the height at which the light source is located, and thanks to this, place the scene on a relief surface.

Smooth construction


This task turned out to be the simplest, since the main idea was simple: it is necessary to build a city at a slightly greater distance than the user sees and while he is moving from one key point to another, regenerate the city based on the next key point. The main thing is to limit the user's movement speed so that during the time of moving to the next point + construction time, it was impossible to reach the border of a pre-built part of the city.

As for the generation itself, it was divided into many stages, with statistics for each stage (which can be viewed by going to the browser console) of how much processor time this or that stage takes to the frame, and if this time was more than some values, the stage was divided into several sub-stages until this allowed to achieve a stable high FPS.

Result


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

Also popular now: