=Paper=
{{Paper
|id=Vol-2212/paper47
|storemode=property
|title=Algorithms of automation of 3D modeling of urban environment objects using attributive information from a digital map
|pdfUrl=https://ceur-ws.org/Vol-2212/paper47.pdf
|volume=Vol-2212
|authors=Mikhail Osipov,Oleg Chekodaev
}}
==Algorithms of automation of 3D modeling of urban environment objects using attributive information from a digital map ==
https://ceur-ws.org/Vol-2212/paper47.pdf
Algorithms of automation of 3D modeling of urban
environment objects using attributive information from a
digital map
M P Osipov1 and O A Chekodaev1
1
Lobachevsky State University of Nizhni Novgorod, Prospekt Gagarina 23, Nizhni Novgorod,
Russia, 603950
Abstract. A method for generating three-dimensional models of urban environment objects
using attributive information from a digital map is described. Algorithms for automating the
process of modeling objects of the urban environment are presented. A flexible and expanding
structure is proposed that allows generating both types of objects already available in the
classifier, as well as new ones added by the user.
1. Introduction
3D models of urban environment are widely used in various fields, such as civil engineering and
architecture, culture and education, advertising and entertainment. Unlike a two-dimensional
schematic representation in maps, three-dimensional models of objects allows a person to perceive
information in a familiar spatial form. No special technical knowledge is required for the analysis of
such information, so decision-making based on the information thus provided is much quicker and
easier. Real-time visualization of a 3D model allows for a total immersion into the model space and
thus gives the user the most complete information about the object. With this approach, it is possible
to gain some experience in the operation of objects even at an early stage when their concept is being
developed. In particular, a 3D model of urban environment facilitates the interaction of designers and
investors. By incorporating the model of the future object (building) into the model of the surrounding
development, it is possible to perform a visual and landscape analysis, to assess the influence of the
future object on the appearance of the historical urban environment, to analyze the visibility, taking
into account the height of the buildings. In urban management, a 3D model helps to carry out
engineering calculations and to plan social infrastructure, to study possible consequences of
emergencies and to simulate the actions of emergency and other special services [1-4].
Urban environment models can be created manually, semi-automatically or automatically.
Automatic modeling is performed by software based on the results of airborne laser scanning and
aerial photography [5, 6]. This approach allows for rapid model generation, but the geometry of such a
model can be distorted due to overlap of objects and imperfection of existing equipment and
algorithms. With the manual and semiautomatic modeling of the urban environment, distortion of the
geometry can be avoided, but this process is quite time-consuming, because the modeling is either
completely or partially performed by an operator [7, 8]. The source of the data for creating the model
is a digital terrain map. The aim of automation of modeling methods is to minimize the proportion of
manual labor.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018)
Data Science
M P Osipov and O A Chekodaev
2. Problem statement
Automation of methods for modeling three-dimensional objects of the urban environment is achieved
through the development of "procedural modeling" algorithms using both ready-made 3D object
models and those that were completely generated with the use of attributive information from digital
maps. The term "procedural modeling" refers to the automatic creation of three-dimensional models of
objects using certain rules of spatial modeling based on various information contained in a digital map.
The main advantages of this approach include the high speed of creating an urban environment model,
the model's metric accuracy, and sufficient flexibility in editing. One drawback of the approach is the
insufficient photorealism of the model obtained. Methods using "procedural modeling" distribute all
objects according to the types of construction of their 3D model [9, 10]. The rules for generating 3D
models of each type of construction are formed, as a rule, separately and independently of each other,
which does not allow for the flexibility and extensibility of the generation process of the urban
environment model. For example, when creating a new type of object model construction, one has to
develop an algorithm for generating a 3D model of this type "from scratch".
The aim of this work is to develop algorithms for automating the process of modeling urban
environment objects using attributive information from a digital map. The objective is to identify the
general principles for constructing the geometry and model texturing (construction types), to develop
algorithms for constructing and creating a hierarchical structure of construction types for a 3D model
of the object, which facilitates the editing of the construction rules and automates the process of
creating new types of a 3D object model construction.
3. Methods for generating 3D models of the urban environment
The urban environment model includes a digital model of the terrain and models of the urban
environment objects.
The digital model of the terrain is built on the basis of elevation information (horizontals, elevation
marks, etc.) contained in the digital map (figure 1). Fast algorithms for the automatic generation of
such a model are developed by means of Delaunay triangulation [11] and its subsequent restructuring
in accordance with the shape of the terrain described by a set of structural lines from the digital map.
Figure 1. The digital model of the terrain.
As a basis for constructing Delaunay triangulation, a dynamic caching algorithm is adopted. It is
characterized by high speed (average complexity is O (N)) and ease of implementation [11]. It makes
it possible to complicate and rearrange the existing triangulation in accordance with the new altitude
information (points). In this way, it locally changes the parts of the terrain model according to the
updated high-altitude data without rearranging the entire model. Approaches to increase the speed of
the dynamic caching algorithm was proposed and implemented. These include the choice of data
storage structures, the use of integer arithmetic, the minimization of conditional transitions, the
unfolding of a part of the cycles, the simplification of the functions, etc. The optimal step to perform
the verification of compliance with the Delaunay condition was determined experimentally. This step
provides a gain in the running time of the algorithm on large amounts of data. A special structure for
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 360
Data Science
M P Osipov and O A Chekodaev
working with a list of verifiable triangles was proposed and implemented. It allows you to minimize
the use of procedures for allocating and freeing dynamic memory, by effectively managing the
allocated memory. The conducted experiments showed the effectiveness of the proposed approaches.
Objects of the urban environment are buildings and structures, roads, lawns, sidewalks, bodies of
water, infrastructure elements, etc. Most models of such objects can be generated manually beforehand
using a 3D modeling editor. The information about the ready 3D model and its position can be stored
in a digital map. In the absence of a ready model, it is generated automatically based on the attributive
description of the object from the digital map of the local area. For storing information about the
digital map, a distributed database management system is used, which is based on an object-oriented
approach to the representation and processing of complex structured spatially distributed information
[12]. The human brain can easily compare a real object with its unified 3D model, which allows the
urban environment objects to be typified [13]. Therefore, it is proposed to divide all objects of the
urban environment into types of their representation and to develop algorithms for generating a 3D
model of objects of each type. Objects can be divided by the type of presentation into two large
groups: those containing metric information and discrete objects.
Figure 2. The flowchart of model generation.
Discrete objects are typical objects of the urban environment that have no metric description: trees,
stops, traffic lights, etc. Each of such types of objects can have a different description represented by a
list of characteristics. This can be the type of material, age, dimensions, etc. Since the list of possible
characteristics of this type of object in a digital map is known and only a set of characteristics is
changed for a particular object, it is proposed to form beforehand a database of ready-made 3D models
of typical objects and textures representing different combinations of their characteristics. Attribute
information of discrete objects in the digital map also contains information about the object's location
on the ground. In this case, discrete objects are not generated, but are represented by ready 3D models
that are loaded into the program from the library of typical 3D models. If discrete objects have
characteristics that enable automatic generation of their geometry, they are allocated to separate
generation classes.
Objects that have metric characteristics will be generated automatically. Such objects include
buildings, fences, road network, water objects, etc. Each such object should have a description in the
form of a representation of its contour and a list of characteristics. For example, for a building, this is
the material, the purpose of the building, construction year, the number of floors, etc. It is proposed to
form beforehand a library of standard textures characterizing possible sets of characteristics of a
particular object. The geometric model of such objects is generated automatically by the contour
representation and the list of characteristics stored in the digital map. Also, based on these
characteristics, the desired texture for this model will be selected from the library of standard textures.
The general scheme of this principle is shown in figure 2.
All the automatically generated objects of the urban environment are divided into classes,
depending on the methods used to build their geometry. Such classes are a hierarchical structure,
where each next step of the hierarchy is a modification of a more general geometric construction of the
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 361
Data Science
M P Osipov and O A Chekodaev
model at the previous step. Thus, to draw an object added to the classifier, it is sufficient to indicate to
which class this object belongs. Figure 3 shows a block diagram of the distribution of objects from the
database by the initial classes.
Figure 3. Distribution of objects by initial classes.
Figure 4. Schematic of objects subdivision into types of geometric model construction.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 362
Data Science
M P Osipov and O A Chekodaev
In the case of an object of complex shape, the object should be divided into composite objects
whose shape can be generated by the existing construction classes. These composite objects must have
characteristic links, which allow storing information about the relations between composite objects.
For example, the object "fence with columns" is divided into several objects: a linear one ("fence")
and some discrete "columns". For the "fence", interrupts are stored at the metric points, where
"columns" adjoin the fence.
Let us consider in more detail the blocks defined in figure 3 as "Model generation by a metric
description". The breakdown by classes is based on various characteristics of objects, which make it
possible to identify common algorithms for constructing the geometry and texturing the model.
The general scheme of objects subdivision into types of geometric model construction is shown in
figure 4.
The subdivision into the types of the model construction is carried out according to the following
principle. Objects containing metric information are divided into area and linear objects. In turn, area
and linear objects may or may not be linked to terrain features. For example, a linear object that is not
linked to terrain includes power lines hanging in the air, elevated pipes, etc.
An area object that is not linked to terrain features can be flat or extruded. A flat object is
constructed by triangulation within a specified contour. Some examples of such objects are a lake or a
flat roof of a house. The geometry of an extruded object is represented by a set of vertical rectangles
obtained by extruding the segments of a metric description to a given height. Examples of such objects
are buildings.
The geometry of an area object linked to terrain features is a surface consisting of a set of triangles
(parts of triangles) of the terrain that falls inside a given contour of this object. Objects of such type
include elements of the underlying surface, such as a covered area, a green area, a square, etc.
Linear objects linked to terrain features are divided into two types: extruded or underlying objects
(being part of the earth's surface). The geometry of extruded linear objects is similar to the geometry
of an extruded area object. Various types of fences can be named as examples of such objects.
Due to the different configuration of the location of the underlying linear objects relative to one
another, it may be required to form intersections when such objects are modeled.
The geometry of underlying linear objects that do not require intersections to be formed is
constructed in the form of a set of bound quadrilaterals obtained by stretching the segments of a metric
description to a given width. In this case, the height of each point of the obtained quadrilateral should
correspond to the height of the terrain at this point. An example of this type of objects are road
sections without intersections.
Underlining linear objects that require to form intersections are divided into several parts of the
following type: underlying linear objects whose geometry was described above, and the intersection
area proper. To form a geometric model that describes the intersection of a set of linear objects is a
difficult task and will be described separately. This type of objects includes a road network, a river
network, and the like.
The texturing of the constructed models is performed based on the information from a set of
characteristics describing the object being modeled. The desired texture is automatically extracted
from the library of standard textures that characterize possible sets of object characteristics. The
principle of texturing will be considered below using a building model as an example.
4. Forming the areas of linear objects’ intersections
Linear objects such as the road network and the river network are extended and have crossings and
ramifications. If a usual algorithm for forming a linear object model is applied, overlapping of objects
will occur in such places, which will result in a poor quality of rendering of these areas. To avoid this,
it was decided to divide the algorithm for constructing a model of linear objects with intersections into
three stages: forming the sections far from the intersection, forming the sections near the intersection,
and forming the intersection areas themselves.
The sections of the road far from the intersections will be assigned to the class of underlying linear
objects without intersections, taking into account the terrain, while crossroads will be assigned to flat
area objects. The sections of the road near the crossroads will be moved to the next class in the
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 363
Data Science
M P Osipov and O A Chekodaev
hierarchy, in the branch of linear objects taking into account the terrain and the presence of
intersections. This division is due to the fact that the crossroads model in its origin is a set of linear
objects around the crossroads point, and to construct them, information on each of them is required for
the whole group. To build a section of the road near the intersection, information is required about the
adjacent linear sections of the road near the intersection. From the database point of view, these will
be another object. Therefore, in order to optimize the process of acquiring all the necessary
information, these road sections will be sorted clockwise.
Figure 5. Stages of forming an intersection of roads (from left to right).
After all necessary geometries of roads have been formed, all three classes are combined into one
and will represent a model of the road network. Figure 5 shows all 3 stages of the process of forming a
crossroads.
5. Producing a building model
A building is a combination of two objects: the sidewalls and the roof. The building’s flat roof is an
area object without height. The walls of the building remain in the class of extruded area objects. One
floor of the building is formed and the information about the roof contour is transferred to the class of
flat area objects without taking the terrain into account. Next, in the class "Building walls", the
building walls are formed in full from all floors (each floor being obtained by using a previous stage
algorithm). This class will be the final class for the walls, since this model has a specific algorithm for
calculating the geometry and texture coordinates. The reason for this is that, to make the building
more realistic, we decided to create a set of standard textures according to the following parameters of
the building: number of storeys, building type (residential or office buildings), the material from which
the buildings are made.
Figure 6. Standard texture for the building wall; division of the texture into sections: the entrance, the
window, the wall and the resulting 3D model.
The texture is a combination of the lower, middle and upper storeys of the building. This texture
will be superimposed on the walls according to the following principle: the walls of the building are
formed storey-by-storey and for each storey a respective part of the given texture will be assigned,
namely, the lower part of the texture for the first storey, the upper part for the upper storey, and the
medium part for all other storeys. To avoid distortion of the texture on narrow and wide walls, we
decided to divide the sidewall not only into storeys, but also into entrances, window apertures where
the wall is too small for the entrance and simply into pieces of the wall that are too small even for a
window. The geometry is calculated for each section of the wall described above.
Figure 6 gives an example of a standard texture, and shows how this texture is split into the
sections of the same storey described above.
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 364
Data Science
M P Osipov and O A Chekodaev
6. Conclusions
The proposed structure allows for the flexibility and extensibility of the urban environment model
generation process. When adding a new type of objects to the classifier, there is no need to create an
algorithm for forming a model of this type. It is sufficient to only specify in its description a set of
characteristics by which the program will determine which graphic class of objects it belongs to and,
based on the particular characteristics of the object indicated in the digital map, it will build the
desired graphic model. Figure 7 shows a fragment of the electronic map and a 3D model obtained on
its basis.
Figure 7. A fragment of the electronic map and a 3D model built on the basis of the attributive
information of the digital map.
7. References
[1] Vasin Yu G, Osipov M P and Tomchinskaya T N 2011 Development of Interactive Virtual
Models of the Urban Landscape of the Historical Center of Nizhni Novgorod Pattern
Recognition and Image Analysis 21(2) 351-353 DOI: 10.1134/s1054661811021100
[2] Kim D H and Bejleri I 2005 Using 3D GIS simulation for urban design ESRI Users Conf. 1-14
[3] Bourdakis V 2008 Low Tech Approach to 3D Urban Modeling Architecture in Computro 959-
964
[4] Guoqing Z, Zhenyu T, Penggen C, and Weirong C 2017 Modelling and visualizing 3D urban
environment via internet for urban planning and monitoring (Access mode:
http://www.isprs.org/proceedings/xxxv/congress/comm2/papers/151.pdf)
[5] Bondarets A 2010 Main strategies for creating 3D city models GisLab Geographic information
systems and remote sensing (Access mode: http://gis-lab.info/qa/3dcities.html)
[6] ArcReview: Three-dimensional modeling and photorealistic visualization of urban areas
Dataplus Geoinformation systems for business and society (Access mode:
https://www.dataplus.ru/news/arcreview/ detail.php)
[7] C3 - a precursor of the 3D revolution in computer mapping (Access mode:
http://www.ixbt.com/td/c3-technologies-3d-maps.shtml)
[8] Sholomitsky A A, Lunev A A and Tarasova O M 2011 A technology for three-dimensional
modeling of cities Scientific Bulletin of National Mining University 2 57-62
[9] Carrozzino M, Tecchia F and Bergamasco M 2017 Urban procedural modeling for real-time
rendering (Access mode: http://www.isprs.org/proceedings/XXXVIII/5-W1/pdf/carrozzino_
etal_ 2.pdf)
[10] Rautenbach V, Bevis Y, Coetzee S and Combrinck C 2015 Evaluating procedural modeling for
3D models of informal settlements in urban design activities South African Journal of Science
(SAJS) 111(11/12) 11-10 DOI: 10.17159/sajs.2015/20150100
[11] Skvortsov A V 2002 Delaunay Triangulation and its Application (Tomsk: Tomsk University
Publ.) p 128
[12] Vasin Yu G and Yasakov Yu V 2016 Distributed database management system for integrated
processing of spatial data in a GIS Computer Optics 40(6) 919-928 DOI: 10.18287/24126179-
2016-40-6-919-928
[13] Vasin Yu G, Osipov M P, Muntyan S V and Kustov E A 2015 Procedural Modeling and
Interactive 3D Visualization of Objects of the Internal Structure of Buildings and Facilities
Pattern Recognition and Image Analysis 25(2) 278-280 DOI: 10.1134/s105466181502025
Acknowledgements
The study was supported by a grant from the Russian Science Foundation (project No. 16-11-00068).
IV International Conference on "Information Technology and Nanotechnology" (ITNT-2018) 365