Development of a 3D Kinetic Data Structure adapted for a 3D Spatial Dynamic Field Simulation

Authors: Hashemi Beni, Leila
Advisor: Mostafavi, Mir AbolfazlPouliot, Jacynthe
Abstract: Geographic information systems (GIS) are widely used for representation, management and analysis of spatial data in many disciplines including geosciences, agriculture, forestry, metrology and oceanography etc. In particular, geoscientists have increasingly used these tools for data integration and management purposes in many environmental applications ranging from water resources management to global warming study. Beyond these capabilities, geoscientists need to model and simulate 3D dynamic spatial fields and readily integrate those results with other relevant spatial information in order to have a better understating of the environment. However, GIS are very limited for modeling and simulation of spatial fields which are mostly three dimensional and dynamic. These limitations are mainly related to the existing GIS spatial data structures which are 2D and static and are not designed to address the 3D and dynamic aspects of continuous fields. Hence, the main objective of this research work is to improve the current GIS capabilities for modeling and simulation of 3D spatial dynamic fields by development of a 3D kinetic data structure. Based on our literature review, 3D dynamic Delaunay tetrahedralization (DT) and its dual, 3D Voronoi diagram (VD), have many interesting potentials for handling the 3D and dynamic nature of those kind of phenomena. However, because of the special configurations of datasets in geosciences applications, the DT of such data is often inadequate for numerical integration and simulation of dynamic field. For example, in a hydrogeological simulation, the data form highly irregular set of points aligned in vertical direction and very sparse horizontally which may result in very large, small or thin tessellation elements. The size and shape of tessellation elements have an important impact on the accuracy of the results of the simulation of a field as well as the related computational costs. Therefore, in the first step of the research work, we develop an adaptive refinement method based on 3D dynamic Delaunay data structure, and construct a 3D adaptive tessellation for the representation and simulation of a dynamic field. This tessellation is conformed to represent the complexity of fields, considering the discontinuities and the shape and size criteria. In order to deal with the dynamic behavior of 3D spatial fields in a moving framework within GIS, in the second step, we extend 3D dynamic VD to 3D kinetic VD in the sense of being capable of keeping update the 3D spatial tessellation during a dynamic simulation process. Then, we show how such a spatial data structure can support moving elements within the tessellation and their interactions. The proposed kinetic data structure provides an elegant way for the management of the connectivity changes between moving elements within the tessellation. In addition, the problems resulting from using a fixed time step, such as overshoots and undetected collisions, are addressed by providing very flexible mechanisms to detect and manage different changes (events) in the spatial tessellation by 3D DT. Finally, we study the potentials of the kinetic 3D spatial data structure for the simulation of a dynamic field in 3D space. For this purpose, we describe in detail different steps for the adaption of this data structure from its discretization for a 3D continuous field to its numerical integration based on an event driven method, and show how the tessellation moves and the topology, connectivity, and physical parameters of the tessellation cells are locally updated following any event in the tessellation. For the validation of the proposed spatial data structure itself and its potentials for the simulation of a dynamic field, three case studies are presented in the thesis. According to our observations during the simulation process, the data structure is maintained and the 3D spatial information is managed adequately. Furthermore, the results obtained from the experimentations are very satisfactory and are comparable with results obtained from other existing methods for the simulation of the same dynamic field. Finally, some of the limitations of the proposed approach related to the development of the 3D kinetic data structure itself and its adaptation for the representation and simulation of a 3D dynamic spatial field are discussed and some solutions are suggested for the improvement of the proposed approach.
Document Type: Thèse de doctorat
Issue Date: 2009
Open Access Date: 16 April 2018
Permalink: http://hdl.handle.net/20.500.11794/21293
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
SizeFormat 
26532.pdf7.77 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.