PlanetoidGen

A highly parallel distributed system for pipeline-oriented geographic data processing.

This page is divided into two parts. The first part covers PlanetoidGen, briefly described above. The second part covers LandscapeGen, a predecessor of the PlanetoidGen system, developed several years prior. A list of relevant publications can be found at the end of each part.

This project is part of a larger body of research I conducted together with Roman Moravskyi¹, Pavlo Pustelnyk¹, Yevheniia Levus¹, Rüdiger Westermann², and Asanobu Kitamoto³.
¹ Lviv Polytechnic National University, Lviv, Ukraine.
² Technical University of Munich, Munich, Germany.
³ National Institute of Informatics, Tokyo, Japan.

Overview

The system was developed to use cloud computing to provide near real time generation of large-scale 3D models of eastern Ukraine during the full-scale russian invasion for news coverage and education purposes with a storytelling aspect. The result is similar to a dynamic timeline-based version of Cesium Ion or Google Earth with a small web client using limited pre-generated data and full desktop client displaying landscapes with streamed models. The system follows a Microservice architecture using REST and gRPC for communication through the API, PostgreSQL for temporary map data and metadata storage, MongoDB for 3D model, satellite image, texture, and description storage, Kafka for processing request querying and distribution among multiple worker Software Agents through a load balancer, and Overpass as the cartographic data source. Parallel computing and asynchronous execution is utilized where possible, database information serialization routines are generated through runtime bytecode JIT-compilation, and dynamic SQL stored procedure generation is used for query optimization. The system supports extensions through runtime plugin loading using Dynamic Link Libraries. Kubernetes are used for component container management. Monitoring, reliability, scalability and other aspects are considered. The system can be hosted independently or through AWS/Azure/Google.

Architecture

This system builds on the advancements in multiple academic domains, including databases, distributed systems, cloud computing, and parallel execution, to allow data processing and content generation algorithms to use state-of-the-art hardware and software to a better extent, focusing on performance, flexibility, and extensibility of the proposed system.

The system is built as a distributed loosely-coupled set of microservices, supporting both horizontal and vertical scaling. The components contain the minimum required set of microservices, dismissing service registries, gateways, etc. for performance and simplicity.

The abstract components of the system include multiple data sources, a data processing pipeline, and multiple storage options. For the practical use case of the system, the generation of 3D models for news coverage, a predefined set of sources and sinks is used, outlined in the figure above.

While all components of the system are required to complete the data transformation flow, each component can start up independently. A container orchestration system, Kubernetes is chosen to manage the lifetime of the components and handle reliability concerns. It also provides automatic scaling, load balancing, and failover. The environment is optimized for hosting both on-premises and using cloud providers like Microsoft Azure Cloud Computing Services or Amazon Web Services.

Components

The concrete components of the system include a simplified web client with pre-generated and pre-loaded data, an external API component, a generation job queue, a set of worker instances for software agents, and a set of data storage components for data processing results. An additional results queue is used for caching intermediate agent results. The software agents are ordered and non-cyclical dependencies between them can be introduced.

The main API component, which handles generation and data loading requests from the clients and sends generation messages to the broker, is developed using an N-layer architecture, following SOLID principles. The presentation layer of the API uses gRPC for high-throughput content streaming. To be more specific, bidirectional streaming of data processing requests and content streaming responses is used, maintaining a connection with the client to route the processed data correctly. The API is stateless and can be horizontally scaled to handle more simultaneous clients. A set of REST endpoints is added for potential legacy clients.

For central storage of client connection and reporting about successfully processed requests in a distributed environment, a results queue is introduced. Its goal is to receive and pass onto clients the event messages from software agents about the successful completion of the data transformation pipeline for a specific request. The clients then can query generated data immediately upon notice, making this push-pull approach perform faster than the typical open-drain one. Alternatively, an additional agent can be implemented to send data to the client, but this option is not explored deeper.

To speed up and parallelize the execution flow, a Morsel-driven parallelism approach is used. The data processing tasks are divided into small, independent pieces called "morsels" and distributed across a pool of worker threads, processes or instances. Each worker is responsible for executing a single morsel and communicating the results back to the main thread or process. A job notion is introduced, where a job is a processing request from a single client for a specific software agent in the pipeline. The only limiting factor to parallelism in the system is the necessity to process jobs of dependent agents first.

To solve this issue, a message broker, Apache Kafka, is used to store scheduled and in-flight jobs. A topic-based system was chosen with a topic per each agent. This allows workers to subscribe to topics in the order of agent dependency. While other components, mainly storage, are mounted to physical disk file systems for external access, the message broker and the API only use private virtual session storage, as the job requests aren't sensitive and their loss on errors is neglectable, as new requests from the client can be issued after a timeout.

The storage in the system is split between multiple providers on different orchestrated nodes with support for further sharding. For metadata storage, due to its relational nature, PostgreSQL was chosen. It is used for maintaining the generation process and the pipeline configurations. This includes planetoid descriptions with common parameters, zoom mappings, agent lists with settings. The file storage, on the other hand, contains partially structured data in the form of files and dependencies, which is a good case for NoSQL databases. MongoDB was selected for this task. Because of the 16 MiB limit on record sizes, large files have to be broken down into chunks and placed on the GridFS database component.

Since agents can introduce data in different shapes, a flexible dynamic relational table schema description has been introduced. A service then uses this description to create stored procedures for CRUD operations, as well as table management SQL statements. Agents have functions to describe their input and output data using the schema description, allowing for easier inter-agent dependency control and validation.

The next tackled slow point of the system is the entity serialization process. Runtime-compiled methods relying on Run-time type information (RTTI) are used through bytecode jeneration for the Just-In-Time compilation module of .NET Roslyn API.

To support geographic queries retrieving real-world data on buildings and roads, an additional geo-storage is needed. Overpass is the provider of choice, providing per-minute updates of data returned in a vector format.

There are two clients for the system: a web client relying on pre-fetched pre-generated data and a desktop client using real-time data streaming to acquire 3D models and display them. The location of interest is picked based on the virtual camera position and normalized to conform to a rectangular point grid on a side of a cube wrapping the planetoid. A local cache is introduced to avoid sending duplicate requests for existing data. For the use case described in the overview section, a UI was implemented to allow before/after comparisons of large-scale landscapes of eastern Ukraine during the full-scale russian invation for news coverage and education purposes with a storytelling aspect.

The worker servers are built on the same structural foundation as the main API, following an N-layer architecture. The hosting part of the application runs a set of background worker threads, each polling the respective job message topics inside the message broker. Multi-level retry policies and transactions are used to fulfill ACID properties and achieve better performance. To allow easy access to service abstractions, a combination of Dependency Injection and Service Location frameworks is used.

One of the most important services exposed to the software agents is the tile metadata repository, since it gives agents the ability to update timestamps for processing timeouts. If the agents take too long to process a tile without updating the timestamp, the request is considered as failed and a different agent instance will try to process it.

Technologies

With a distributed pipeline to generate large-scale data, the issue of produced data size needs to be tackled. If the server produces too much data for a single request, the performance of the system may drop significantly, especially for a client with limited resources. To prevent this, the client should be able to select the quality level of produced content, where better quality represents more detailed data, and worse - simplified approximations. A discrete solution using Level Of Detail is used to create multiple versions of the same models with different quality levels, and use the appropriate version based on the viewing distance or the hardware capabilities.

Another side effect of using LOD is that it can be mapped to different zoom levels for landscape areas. This allows for more optimized processing queries, represented by an index or area midpoint and a zoom.

The system uses three different GIS coordinate models for the generation process.

The API receives requests using a modified spherical coordinate system, containing the longitude and latitude of the area to process; the LOD is also included to select a subset of software agents used. The LOD value is subsequently converted to a zoom value in the API component, making it a traditional GIS spherical coordinate system without elevation.

Next, the system needs to find a GIS tile that envelops the requested point. The planetoid is then divided into a rectangular grid of areas and indexing them for referencing. The most common Web Mercator Projection severely distorts points around north and south pole, projecting the poles at infinity. For this reason, an equal-area projection with support for accurate mapping of poles is needed. The Quadrilateralized Spherical Cube Earth Projection is chosen for the task, being commonly used in databases for indexing geographical areas. Moreover, the distortion factor is lower than for competitors. The projection involves projecting the ellipsoid of the planetoid onto six sides of a cube with subsequent distortion correction. The coordinate range of the pair $(x,y)$ on each cube face is mapped to $[0;1]$.

For storage indexing purposes, an index pair $(i,j)$ is used instead. Together with a zoom value, it represents the planar coordinate model. While conversion between spherical and cubic models is covered by the standard WGS1984 to QSC projection routines, the conversion to the planar model is hand-crafted as: $$\begin{matrix*}[l] i &= x * 2^{zoom} \\ j &= y * 2^{zoom} * 6 + i_{face} \end{matrix*}$$ which with 64-bit integers supports up to zoom 61, giving sub-meter accuracy for Earth-sized planetoids. On the other hand, it should be noted that even the conversion between cubic and spherical coordinates is lossy in nature, so in general these operations should be performed as infrequently as possible.

The coordinate models are agnostic to the underlying ellipsoid properties, but for correct data processing and relative 3D object placement on the client, the system needs to support converting between these coordinates and common ones understood by external systems, like meters. To achieve this, a projection mapping service is used, generating projection strings in WKT and Proj formats. Since different planetoids require separate projection strings due to their ellipsoid properties, the strings are placed in the spatial reference system table in the metadata storage. This table can later be fed to external relational GIS data consumers for coordinate conversion procedures.

The foundation for the extensible software agent component is the common software agent interface. The construction, initialization, and execution is split into different methods of this interface, providing flexibility in managing its lifetime. As a result, the agents can be loaded based on a system configuration value using dynamic .NET assembly loading and invocation.

Each agent has a set of strongly-typed settings values to control the algorithm behavior. Moreover, the agent specifies input and output data as well as a list of adjacent tiles that need to provide the input data. The information about inputs and outputs can be specified per zoom or in general. These records from consequent agents can then be combined into agent dependency chains. Since direct connections are not required, a dependency graph is formed. Moreover, agents can depend on data from adjacent areas, leading to a growing number of total jobs per request.

Publications

1. Y. Levus, P. Pustelnyk, R. Moravskyi and M. Morozov, "Cloud-Based Distributed Approach for Procedural Terrain Generation with Enhanced Performance," IEEE 18th International Conference on Computer Science and Information Technologies, Nov 2023, ISSN: 2766-3639, [mirror].
2. M. Morozov, A. Kitamoto, "Interactive Storytelling with 3D Visualization for Illuminating the Impact of War in Ukraine," Proceedings of the 12th Conference of the Japanese Association for Digital Humanities, Sep 2023, vol. 2023, ISSN: 2432-3187, [mirror].
3. Y. Levus, P. Pustelnyk, R. Moravskyi and M. Morozov, "Architecture of a Distributed Software System for Procedural Planetoid Terrain Generation," Ukrainian Journal of Information Technology, May 2023, vol. 5, no. 1, pp. 1-8, ISSN: 2707-1898, [mirror].
4. Master's Thesis:
   1. Mykola Morozov, "An Extensible System for Large Scale Cultural Heritage Data Visualization," Technical University of Munich, Apr 2023, [mirror].
   2. Roman Moravskyi, "Use of software agents in a distributed system for planetoid landscapes generation," Lviv Polytechnic National University, Jun 2023.
   3. Pavlo Pustelnyk, "Model of server architecture and spatial relational database for planetoid landscapes generation," Lviv Polytechnic National University, Jun 2023.
5. Y. Levus, R. Westermann, M. Morozov, R. Moravskyi and P. Pustelnyk, "Using Software Agents in a Distributed Computing System for Procedural Planetoid Terrain Generation," 2022 IEEE 17th International Conference on Computer Sciences and Information Technologies (CSIT), Jan 2023, pp. 446-449, ISSN: 2766-3655, [mirror].

LandscapeGen

A full-stack visualization system of natural and anthropogenic landscapes, including terrain, infrastructure and architecture.

Overview

The tool has been implemented as a session-based Node.js server component of a client-server application for easy integration with existing software systems. A simple JavaScript web client was also created for testing purposes. Software Agents are used instead of traditional parallel algorithms and plugins to unify the API and improve performance. The server consists of 3 layers: a REST-based service layer, the business logic layer with the agent registry, and the data processing layer with permanent Data storage and a System cache for results. The natural landscape agents utilize Bezier curves and surfaces for terrain and water bodies. Produced anthropogenic data has LOD support, being stored and transferred as Containerized entities. The containerization is achieved using Hierarchical axis-aligned bounding volumes.

Architecture

As mentioned in the overview, the overall systems consists of a simple client and a three-layer server. On the other hand, the server can be divided into a few distinct components, communicating with each other upon receiving each request.

Mainly, the server consists of an agent registry, a cache, and a worker service. When a new request appears, the following procedure is executed:

1. The request to generate a landscape area (chunk) is passed to the worker.
2. The worker collects a list of agents necessary to fulfill this request, then queries the agent registry for the concrete agent implementations.
3. The worker applies the agents to the chunk object in the correct order based on their dependencies.
4. The chunk object is containerized and stored in cache, then returned to the client.

The division of the overall landscape into chunks works as a simple axis-aligned grid division, e.g. into 128-meter segments. Each chunk object contains a list of entities produced by the agents, including terrain, cities, roads, districts, buildings, and trees.

The resulting structure is containerized using hierarchical axis-aligned bounding volumes, which is also used for occlusion checking during rendering. Bounding volumes are produced during generation, but no further agent-specific optimizations are performed within the scope of the developed prototype. The incuded agents are:

1. Terrain generation agent using Bezier surfaces. The heightmap is produced using Perlin noise.
2. City generation, selecting several potential points within a region of 9x9 chunks using Alea random and MurmurHash3.
3. Road generation within cities using ARC4 random. Manhattan-style roads in the image.
4. Road generation between cities. Bezier curve roads in the image.
5. Intersection generation between road segment pairs.
6. District bounds generation using Delaunay triangulation.
7. Architecture generation using Boolean operations.
8. Decoration generation, including roofs, on architecture, using Mesh extrusion.
9. Vegetation generation around buildings in certain districts using Random scatter.

The generation metadata is stored during the generation process and afterwards in the cache, so repeated or additional subsequent generation is faster.

The resulting solution can be used as training data for Machine Learning, for visualizations, simulations, and for interactive experiences.

Publications

1. M. Y. Morozov, R. O. Moravskyi, P. Y. Pustelnyk, and Y. V. Levus, "Algorithms and Architecture of the Software System of Automated Natural and Anthropogenic Landscape Generation," Radio Electronics, Computer Science, Control, Jul 2022, vol. 61, no. 2, pp. 154–164, ISSN: 1607-3274, [mirror].
2. M. Y. Morozov, R. O. Moravskyi, P. Y. Pustelnyk, and Y. V. Levus, "Containerization method for visualization of natural and anthropogenic landscapes," Scientific Bulletin of UNFU, Nov 2021, vol. 31, no. 5, pp. 90–95, ISSN: 1994-7836, [mirror].
3. Bachelor's Thesis, Software system for visualization of natural and anthropogenic landscapes:
   1. Mykola Morozov, "Generation of three-dimensional objects of architecture and infrastructure taking into account the characteristics of the landscape," Lviv Polytechnic National University, Jun 2021, [mirror].
   2. Roman Moravskyi, "Landscape generation using Bezier curves and surfaces," Lviv Polytechnic National University, Jun 2021, [mirror].
   3. Pavlo Pustelnyk, "Containerization of three-dimensional scenes with different levels of detail," Lviv Polytechnic National University, Jun 2021, [mirror].
4. M. Y. Morozov, R. O. Moravskyi, P. Y. Pustelnyk, and Y. V. Levus, "Landscape Generation for Spherical Surfaces: Problem Analysis and Solution," Scientific Bulletin of UNFU, Feb 2020, vol. 30, no. 1, pp. 136–141, ISSN: 1994-7836, [mirror].