Contributions to Big Geospatial Data Rendering and Visualisations - Ph.D Thesis: Literature Review chapter 3
This section covers the related work of other scholars and researches. Due to the large domain coverage of our work, this is the reasoning to split the segments into separate chapters of Background and Literature Review. These chapters will reference each other and be partially mixed.
Figure 17 shows our research and experience with the current commercial and open GISs. From the specifications of functionalities, we state is needed, we notice that none of the GISs allow direct access to the GPU, nor do they allow custom GPU programmes to be applied to the data within the GISs. Providing access to the GPU will allow improvements to visualisations by tapping into the hardware acceleration of modern GPUs.
Figure 17 GIS Functionalities implemented from the specification we state is needed for a modern advanced GIS
1.1 Why use a Game Engine?
Within the work of [32], Baare and Grigg compare the productivity between game engines. We take from this work the speed at which the productivity took place from the experiments they undertook. They stated that the game engine of Unity3D was 1.9 times faster than that of using UnrealEngine4s’
Blueprint mechanisms for development purposes. The Blueprints mechanism we speak of can be thought of as a ‘drag and drop’ component architecture used for rapid prototyping of commonly used assets/components/games types. Although the work was comparing the two game engines against each other, it emphasised the abilities of modern games engines which contain many user
interfaces to commands, and the additional functionalities the game engines provide the user. They issue the statement that C++ knowledge should be known. This is not a knowledge trait expressively needed within modern computer game development; especially with the use of the drag and drop components of Unreal Engine 4 Blueprints and the use of other scripting languages such as Boo or JavaScript in Unity 3D.
For our project, knowledge of programming is needed to develop novel data structures, algorithms, and mechanisms.
Herwig and Paar [33] state the suitability of using a games based API for terrain and landscape visualisation. They discuss what problems game engines can overcome in relation to the visualisation of landscape virtual scenes. They state that 3D game engines require fundamental knowledge and expertise in 3D designs and level construction. They state working with geo-terrain data is commonly a trial-and-error approach for visualisation when loading into a game engine. We agree with this in regards to the large amounts of geo data available in many different formats that a considerable large amount of development is needed, but a trial-and-error approach is a derogative approach.
We do however agree with their statement that game engines are a low-cost alternative than GIS and CAD software. For this reason, we will utilise game engine API which is either free to use, or has an open source licence.
Within many commercial game engines, scenegraph structures are implemented but restrict the data attributes attach to each node. Moa [11] creates a scenegraph to organise the buildings within his virtual city. He uses an open source scene graph implementation; OpenSceneGraph26. Combined with X3D27 he generates and organises large amounts of data to be viewed within real-time standards. This proves that custom scenegraph data structures, specifically designed and built for virtual urban environment organisation and visualisation are viable. Although scenegraph structures have shown to be a viable solution to organising a city’s worth of data, a novel data structure is needed to apply attributes from the more complex OSM data.
An example of a rendering API which can be utilised for academic research as well as game engine development is the Microsoft XNA API.
The XNA API has been used in many other projects for visualisation, training and many other domains. Ouch and Rouse use the API to generate a mobile driving training game to teach uses safer driving skills [34]. Denninger and Schimmel [35] utilise XNA for the teaching of complicated paradigms. They state the reasons to use XNA is for language simplicity being C# and not C++ which is difficult for beginners to understand. XNA is also a wrapper for the underlying DirectX making it a managed DirectX API. XNA has also been used on a similar project to this in [36]. Herrlich et.al. use CityGLM data to produce virtual scenes. Assets are loaded in via COLLALDA, a mesh representation. We are unsure as to why they utilise COLLALDA as XNA has built in model processing capabilities.
26 https://www.openscenegraph.org/
27 https://www.web3d.org/x3d/what-x3d
Alternatives to the XNA API is JMonkey. At the time XNA was maintained by Microsoft, it was the more powerful of the two APIs according to the results of [37]. From the results, JMonkey has faster frame rates with low numbers of objects within a scene. Increasing the number of objects in a scene, XNA becomes the faster of the two. At 50 objects, JMonkey ran at 598.41 FPS, where XNA ran at 235.29 FPS. With 4000 objects, JMonkey ran at 4.95 FPS, whereas XNA ran at 29.13 FPS. XNA can still handle 16,000 objects at 4.69 FPS where JMonkey cannot. For this reason, XNA is still the better choice due to the expectation of large scene visualisation.
To summarise the contributions of our intended work, the utilisation of game technologies can fill the gap of knowledge and current issues within the domain of GIS, issues such as procedural content generation, and visualisation. These contributions can enhance virtual scene visualisations of current GIS standards.
3.2 Visualisations
In this section we introduce the current research within the domain of visualisation and concurrent domains which visualisation techniques and technologies have been applied to.
Robinson and Shapcott [38] attempt to improve data-mining understanding from non-domain experts of analysts by introducing visualisation techniques. They state to improve data-mining understanding that visualisation needs to;
1. Support the whole of the data mining process.
2. Are usable by domain resident data miners who are not expert analysts.
3. Support data miners who are from a diverse range of backgrounds.
4. Allow interaction with the data mining tool.
Remove the domain of data mining from the list stated and the statements are current for the domains of this project.
They state that visualisation needs not only bar charts or graphs but visualise relatable objects, and be directly integrated into an interface for the user to interact with as well as manipulate the scene or data. We agree with this. Having relatable objects, and manipulating them in many manners within a simplified user interface is needed for a modern GIS. The relatable objects need to be objects which many individuals encounter on a daily basis; buildings, highways, paths, amenities, transport routes and many other interconnections within modern cities.
Visualisation techniques can be used for example, to portray potential failures within critical infrastructures. Wilde and Warren [39] discuss how visualisation techniques can be applied to critical infrastructure protection and to visualise potential un-foreseen domino failures. They specifically focus on the interdependencies of internal infrastructures and of interconnected infrastructures. The paper is a research description of a wider research project but states the use of visualisation techniques to explain the characteristics and complexity involved in critical infrastructure protection and interdependency connectivity. This reinforces the need for a modern GIS which can visualise multiple data-sets within a real-world visualisation simulation. It also reinforces that visualisation techniques can be applied to portray complex interconnections and data to users. We will create a framework which can visualise 3D Big-Data city models, and allow the interaction from users to manipulate individual objects within a virtual scene spatially and visually.
Generating 3D urban environments lends itself for project managers and urban planners, both private and governmental, to advance the understanding of familiar and unfamiliar territories. The work by Falconer et.al. [1] does exactly this. They produce a virtual environment of a city within the UK and allow users to view the scene by procedurally generated visualisations with each component of the visualisation corresponding to a specific criterion the user is most interested in. The project is discusses in section 2.4.2. The components of the visualisations are parameters which the user can set values for e.g. a user can state the importance of price for components of building should be rendered from white to red, lowest value to highest value respectively. We will utilise this technique of applying attributes to rendered objects within a scene which are set by a user. The user can assign their own schema to the visualisations; creating the same effect to the visualisations as the SAVE project. Visualisations do not and should not only be colour based, and animations both spatially and colour based can provide an additional layer of information. For example, increasing the scaling of a building dependent to depict the value of a building, bringing the attention of a high valued building to the user.
Urban planning is a complex activity with many unforeseen issues. Modern hardware and software can alleviate the traditional methods of urban planning and be used for the visualisation of potential developments within urban areas. These visualisations can be used to encourage residents within an area to be on-board with the idea to change. This notion is discussed in [33], [40]. Our project can be utilised for micro and macro urban visualisations. Details of areas will need to be encoded as attributes or from lookup tables for each of the assets within the visualisations we propose; buildings, highways, amenities, etc. for this we will create data structures which will extract attribute data and create 3D model mesh objects which can contain this data. These attributes can then be utilised by a user to query the objects within a scene. The generation of a queryable algorithm for use with various types of objects is needed. We plan on using the .Net Language-Integrated Query (LINQ)28 API for this task.
In the work of [41], the visualisation of cascading failures within critical cyber infrastructures is discussed. The framework provides the understanding of possible cascading failures within the networks, combined with the organisation of large amounts of GIS data. Combined to generate further understanding of the topological considerations of real-world network structures to provide awareness with past and future decisions.
An early prototype application built from our work has been utilised for visualisation of real-world urban environments for use by tinnitus sufferers, projecting procedurally generated 3D primitive model mesh objects created by data-driven techniques with real-world noise levels, section 1.4.1, item 4. The use of the prototype has shown the scalability and adaptiveness a game-engine can bring to visualisations.
Visualisations of urban environments, and the accompanying techniques used can be found in [42]– [44].
Visualisation techniques can be implemented with game engines for visualisation of scientific data as stated in [23]. Visualisations of other data types can be found in [38], [41], [44]. The wide domain of where visualisation techniques have been employed to portray complex and confusing datasets is encouraging.
The framework proposed will need the ability to adopt all the visualisation topics of the stated research. This is justifiable due to the similarities between the domains. With small changes and adaptations of the framework, plus additional data, the needed visualisations can be achieved, if not improved on by utilising the rendering techniques we propose.
Visualisation techniques for disaster management are also a domain which can benefit from a modern advanced GIS. Within the work of Kwan and Lee [45] they examine the potential of using real-time 3D GIS for GIS-based intelligent emergency response systems. Their framework allows the potential for the reduction of delays within multi-level structures. The framework also supports pathfinding algorithms between emergency service buildings such as fire-stations, and the disaster sight, taking into account traffic speeds, blocks, and stops. The framework is a fine example of what can be done with real-world data for 3D visualisation of cities for data overlay and data management. It proves that the framework which we have proposed is achievable in relation to visualisation technology for displaying data to improve the understanding of real world data maps.
To summarise, the issues of rendering and visualisations within the domain of GIS’s can be alleviated by employing the algorithms and techniques currently used within CGT. We contribute our work by the implementation of advanced rendering techniques applied within the domain of GIS.
28 https://msdn.microsoft.com/en-us/library/bb308959.aspx
3.3 Spatial Analysis with Visualisations and 3D Models
Lv et.al. [46] present a big city visual analysis platform based on Web Virtual Reality Geographical Information System (WEBVRGIS). Within the platform there are extensive analysis functions which a user can select; spatial, terrain, sunlight, traffic, population, and community. The purpose of WEBVRGIS is to create a dynamic visualisation of geographic information, transforming GIS data into a more intuitive, and user realistic 3D experience. The analysis functions are intended for use by external domain experts. We wish to include spatial analysis techniques into the framework but for use within a data-inference algorithm which will calculate specific attributes about assets within a scene; e.g. calculating a buildings height from OSM if only the number of floors are present within the attribute description. Using a pre-defined value for the average height of a floor, the height can be estimated, improving data visualisations.
Utilising spatial analysis techniques can be combined with 3D generated cities for the creation of interesting and novel pathfinding techniques used by a multitude of vehicular structures and sizes. For instance, pathfinding for a person on foot will be different for a car, which will be different for an oversized vehicle which will need roads larger than a given width.
Pathfinding techniques commonly used by AI systems within computer games are spatial analysis functions. Many pathfinding techniques are available as stated by [47], [48]. We wish to highlight path finding techniques used for finding paths for multi-sized agents (vehicles, none player characters, water flow, etc.) through 3D virtual scenes. Harabor [49] present clearance-based pathfinding, a technique which generates paths for multi-sized vehicles within real-time strategy game Command and Conquer. The algorithm takes into account the destructible buildings, which when changed will update the 2D grid map representation used to generate the clearance-based A* path. This technique can be used with virtual scenes generated from real-world data to generate input maps for the clearance-based pathfinding technique. Using LiDAR and spatial analysis functions, a similar result could be generated for real-world users and real-world vehicles of varying size. A form of this is presented in [50] by using explicit corridors to generate obstacle avoidance paths. We are currently not utilising the framework for this purpose. A framework which can use geospatial data for the input for AI algorithms has not been implemented within the domain of GIS.
Hagelback and Johansson [51], [52] use potential-fields for creating input maps for pathfinding algorithms. We highlight this work because of its similarities with using textured LiDAR maps; converting height points to pixel colour values of the 2D texture can give similar results to that of potential fields. Utilising ‘depth rendering’, a technique to render objects according to the distance they are from the 3D camera, potential fields, or height maps can be created. We plan on utilising this shading algorithm within the framework. This allows for further visualisation combinations and potential avenues for future work and research.
Utilising texture formats, we discuss in section 6.8 a technique to store all height data within the UK within a novel storage technique within a formatted texture file by employing parsing procedures within the algorithm.
Within the body of knowledge, the use of spatial analysis techniques applied to real-world data sets to infer information. The contribution of procedural techniques to analyse and query the data for the generation of additional data for the improvement of visual accuracy of real-world virtual scenes.
The next section discusses the literature and techniques of Procedural Content Generation (PCG).
3.4 Procedural Content Generation
To introduce PCG we refer to the work of Khaled, Nelson, and Barr [53] who present metaphors commonly used with PCG. PCG has input into many domains and thusly various names are used for the same techniques.
Many of the projects, which create 3D city representations use a form of PCG for the creation of data or visual assets [36], [54]–[58]; buildings, highways, terrain, etc. Muller et.al. [55] present their procedural modelling techniques used to generate realistic, theme inspired, buildings. We state theme inspired because their technique can be tuned to create buildings which represent various characteristics of well-known and distinct cities, new and old. Figure 18 shows a procedural representation of the ancient city of Pompeii. We show this image from the paper [55] because we wish to highlight the realism it portrays. The human eye is adapted to spotting patterns within scenes, especially scenes which represent real-world instances. Errors, or repeating patterns are easily spotted. Within [55] each building is different in some way, be it textures, rooftop styles, shape of the building, and the height of each building. This is achieved through the use of rule-based comprising of 190 manually written shape rules. What is great about this work is the fact that each buildings blueprint is accurate from archeologically documents. Using shape rules to create, and augment a building is an interesting technique to generate realistic, but procedurally devised buildings.
Figure 18 Screen grab of a procedural representation of Pompeii from the work of Muller et.al [55].
Games set within real-world parameters: Friberger et.al [18][19] use open GIS data to create interesting variations of well-known games; Monopoly with real-world place names, Top Trumps with real-world countries with accurate states, and using real-world maps to create 2D tile maps for a Civilisation style game. The interest with this work is not the end-results but the intuitive nature for which the games suggest; taking real-world map data and integrating that map data within popular implemented commercial games.
PG of buildings for city models are discussed within the SIGGRAPH course proposal [59]. Within the work of Parish and Muller [55], [60], they discuss their techniques for generating 3D buildings by extruding primitive polygons by multiple heights, as well as attaching primitive model meshes (cubes, rectangles, and most commonly tubes) to create complex and realistic buildings. They also discuss the techniques for attached facades to the buildings. Within the research, the facades have effect on the building structure and vice-versa. Their work also includes generation of highway structures commonly found within real-world instances, but are procedurally generated not taking into account of real-world data. The generation, like the building generators utilise rules for particular instances of error/issue to resolve constraints. The highway generation utilises a self- sensitive L-System to great success.
Our work will not need the use of L-Systems for the highway generation due to highway data already described in the OSM data. Our work proposes to implement procedural techniques to generate highway structures, parsing from OSM data to 3D model mesh data.
A survey paper discussing the procedural techniques for city generation is found in [61]. They present the work of [62] who use primitive polygons for the combination and generation of floorplans which are then extruded to create buildings. Some polygons are extruded at different levels. Using a similar technique combined with OSM building boundary data, we can generate extruded buildings. Reducing the scale or the boundary, we can create roof tops for the buildings, just as [62] have.
Their work takes into account the population density, creating highly dense building structures and road systems to where the population is higher. This creates high-rise buildings and a limited number of large road ways between the populations which act as separate cities. This technique works to great success and produces city landscape similar to real-world cities. We are not interested in procedurally generating large cities, but procedural techniques are needed to generate objects and assets within a scene. Procedural estimations are also needed to calculate estimate parameter values for said objects; the number of floors within a building. Knowing the number of floors within a building can improve visualisations by texture mapping accordingly.
Evaluating the realism of this work with the results of the proposed framework can take place. With a procedurally generated city made of real-world data and comparing the results of a procedurally generated city which is generated by pre-defined terrain layout and rules is a starting comparison point for our work.
Martinovic and Gool [63] utilise Bayesian Model Merging but within a 2D textural domain to resample and generate stochastic fa?ade textures to replicate buildings with the same style. Resampling images of real-world facades and locations is an interesting approach to create none- repeating city structures. As stated the human eye is very adapt to spotting repeating instances. An issue arises within this instance of increased memory footprint, or if the data is procedurally generated when needed then extra processing is needed. For our work, this would be a future parameter of the work needed. Currently we will focus on the use of advanced IASF and the user ability to integrate additional data within the visualisations.
A survey paper discussing search-based PCG is found in [64]. Togelius et.al. discuss many features of PCG and we wish to highlight some of them. They discuss the need for either pre-processed or runtime content generation; what needs to be done before the application is used by a user or can be done in the background as the user interacts with the system. They state it is done pre runtime, then manual editing of the final artefact can take place which cannot be done at runtime generation. We agree with this and stipulate that PCG of assets such as buildings/highway/terrains should be done pre-runtime. Other content which can be done procedurally at runtime may be debugging features such as creating the bounding box mesh objects to view the spatial scenegraph bounds we described earlier.
The use of seed values for PCG is one of the benefits of creating large assets but only storing a single seed value. Togelius et. al. discuss the differences random seeds versus parameter vectors [64]. An issue arises with the generation of this seed value. Creating complex 3D structures which are unique in nature and still classifiable to be ‘correct’ is difficult. Trial and error techniques are normally employed with these algorithms. The preferred method for commercial companies is to combine procedural techniques with manual editing done by artists. The artist will generate multiple versions of the asset, and pick the one they think is best and work manual from thereon. The alternative to this is to create a parameter based algorithm which takes into account the parameters listings. With procedural city generation techniques, this could be to limit the number of buildings, or limit the height of the build or the textures used. Although the writers of the survey paper split sections of
‘Random seeds versus parameter vectors’ and ‘stochastic versus deterministic generation’, we state that although they are vastly different, they also overlap vastly. Utilising a seed value to create assets is a form of deterministic PCG, and is a form of data compression. Stochastic techniques can be thought of as the process to create the assets in the first place. Within a city generation framework, the deterministic approach will be the best approach, combined with parameter based inputs for the PCG algorithm. This will prove efficient in terms of development as well as flexibility.
Combining this with the addition of manual editing is also needed, but not for prototypes of the framework but for the final product.
The framework of Galin et.al [65] creates procedural highway structures such as roads, tunnels, and bridges by analysing terrain data and descriptions of their geometric characteristics. Their research is still in the early stages in this field. The cost function to determine the trajectory of a path is calculated taking into account the slope of the landscape. Their results are positive and realistic.
Combining this with real-world data, future planning of highway structures can be calculated accurately.
3.5 Photogrammetry
Photogrammetry techniques can be utilised for the generation of many GIS data-sources. In the work of [66], Enem et.al utilise photogrammetry to determine the height of buildings from a multitude of angled aerial images; top-down, 2.5D, and 3D perspective images. They state that in spite of the horizontal and vertical accuracies of photogrammetric maps, it is not possible to use them directly in 3D city modelling. Current techniques introduce errors which have to be edited manually by a data analyst specialist, or a 3D modelling artist. Thusly photogrammetric map images need to be processed further to create accurate 3D building blue-prints. Their system still uses manual editing of errors, but is one of the most advanced 3D modelling GIS we have seen during this research. Although the data produced, and in which produces procedural buildings, the realism is lost due to the non-textured and simplified extruded building structures. Another weakness within this work is the lack of additional assets within a 3D city modelling GIS. They only utilise 2 tree models, and 1 street lamp. We wish to improve on this by not only adding additional model assets, which is not a novel technique, but utilising other mapping data sources such as OSM to gather further information into the style of city being generated and the placement of additional assets; post-boxes, vegetation, bins etc. This extra information can be utilised by not only the visual inspection and realism of a scene, but also used by council and private officials. Post office workers can analyse the routes taken to gather assets, and see cause and effect of altering postal routes.
According to Dhonju [67], building outlines can be determined more accurately than that of LiDAR and aerial laser scanning. This is due to two issues. The angle that the laser is shot from the aircraft added with the angles and orientations of a building’s roof or sides. This issue can add noise to the data. And low resolution laser techniques in relation to the distance between lasers, not capturing close enough to a rooftops edge. We agree with these issues, and with LiDAR data which we have analysed, this is a large problem with LiDAR, especially LiDAR data with is captured at low resolutions. We present initial techniques later to reduce this error.
The use of photogrammetric methods is determined to be out of the scope of this research due to the benefits in which modern LiDAR data provides.
3.6 LiDAR
To counter the claims of Dhonju [67] about photogrammetry, within the paper of [68], claims that LiDAR is rapidly replacing the photogrammetric approach. We add to this claim with the research of
[69] Montoya et.al. whom use LiDAR equipment attached to drones. This removes the huge cost of capturing aerial imagery needed by photogrammetry. Due to this low cost, data capturing can be completed on a smaller budget, and can capture high resolution contours of buildings and other real-world artefacts; something photogrammetry techniques currently cannot do.
LiDAR can be accurate to a few centimetres when captured from 800 meters above ground. Using building locations from OSM, we can extract the height of said building from the LiDAR data-set, doing away with complex photogrammetric procedures. Combining the two data-sets can bode well for each; the LiDAR is used to create height values for the OSM building, while the OSM boundaries of buildings can be used to check the accuracy of the LiDAR data points.
LiDAR has been used within many analysis, and visualisation projects such as the project stated in [70]. Within this paper the authors use Mannings' coefficient of ground texture and roughness to determine water flow for flood control. Using LiDAR data removes the need to visit sites in person, proving the relevance that LiDAR can bring to crisis management, visualisation, and scene analysis, and giving an insight into real-world environments.
Errors within LiDAR capturing is presented in the survey paper [71]. The multiple authors present the errors within different domains which contain the use of LiDAR. The errors stated within our background research of the use of LiDAR, and within the later sections discussing the issues of big geospatial data. The errors within the LiDAR data is an issue for our work, and this is why we introduce procedural algorithms to remove the errors.
3.7 Conclusion
Within this section we have discussed the relevant projects and research of others which our work can either improve, or we can use as a comparison for evaluation, or as a starting point for our own research. We have covered the use of game engines and why to use them for this project, and the research and uses of visualisation, specifically the frameworks and projects which are using visualisation techniques to view real-world big data-sets. We have discussed the standards of PCG in relation of GIS and visualisations of real-world locations. We have also presented issues surrounding photogrammetry and the techniques which have been used for. The successor, and popular alternative to photogrammetry is LiDAR which is cheaper to produce and accurate to a few centimetres when captured from 800meters above ground, and a few millimetres when using handheld equipment capturing technology. This proves well to create realistic virtual scenes for a modern GIS.
To summarise the issues stated within the literature review, photogrammetry has issues which can be removed by the use of LiDAR. LiDAR has issues and errors which can be filled by the use of OS data. OS data has issues due to low resolution and thusly the need for interpolation techniques and algorithms are needed to increment the low resolution to a higher resolution to combine with LiDAR to create a complete terrain data set. This is a form of PCG. Other forms of PCG have been utilised for building generation of Pompeii, but this work has issues. The issues can be overcome by the utilisation of real-world modern data describing properties of the assets being procedurally generated, i.e. buildings and highways. Visualising these assets within large scenes, scenes as large as a modern city has issues with rendering within real-time constraints. Techniques and algorithms are needed to overcome these issues. Techniques such as, LoD, advanced rendering categorisations, and scene organisations. The SAVE project utilises Eigen vectors to encode user specified interests. This is encoded into effect parameters, but are done offline. We iterate the need to allow this functionality at runtime.
The literature reviewed in this section have all been single instances of algorithms, or techniques. None tackle the issues within a single framework, processing the datasets to produce accurate real- world model sets for visualisation and interactions.
The next section covers the big-geospatial challenges. The chapter delves deeper into the data parameters and issues with each of the geospatial data-sets we have decided to utilise.
We wish to include spatial analysis techniques into the framework but for use within a data- inference algorithm which will calculate specific attributes about assets within a scene; e.g. calculating a buildings height from OSM if only the number of floors are present within the attribute description. Using a pre-defined value for the average height of a floor, the height can be estimated, improving data visualisations.