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

Les systèmes d'information géographique (SIG) sont employés couramment pour la représentation, la gestion et l'analyse des données spatiales dans un grand nombre de disciplines, notamment les sciences de la terre, l'agriculture, la sylviculture, la météorologie, l'océanographie et plusieurs autres. Plus particulièrement, les géoscientifiques utilisent de plus en plus ces outils pour l'intégration et la gestion de données dans différents types d'applications environnementales, allant de la gestion des ressources en eau à l'étude du réchauffement climatique. Au delà de ces possibilités, les géoscientifiques doivent modéliser et simuler des champs spatiaux dynamiques et 3D et intégrer aisément les résultats de simulation à d'autres informations spatiales associées afin d'avoir une meilleure compréhension de l'environnement. Cependant, les SIG demeurent extrêmement limités pour la modélisation et la simulation des champs spatiaux qui sont habituellement tridimensionnels et dynamiques. Ces limitations sont principalement reliées aux structures de données spatiales actuelles des SIG qui sont bidimensionnelles et statiques et ne sont pas conçues pour aborder le 3D et les aspects dynamiques des champs spatiaux 3D. Par conséquent, l'objectif principal de ce travail de recherche est d'améliorer la capacité actuelle des SIG concernant la modélisation et la simulation des champs spatiaux dynamiques et 3D par le développement d'une structure de données spatiale 3D cinétique. Selon notre revue de littérature, la tetraèdrisation Delaunay dynamique 3D (DT) et sa structure duale, le diagramme Voronoi 3D (VD), ont un potentiel intéressant pour manipuler la nature tridimensionnelle et dynamique de ce genre de phénomène. Cependant, en raison de l'échantillonnage particulier des données utilisées dans les applications en géosciences, la tetraèdrisation Delaunay de telles données est souvent inadéquate pour l'intégration et la simulation numériques de champs dynamiques. Par exemple, dans une simulation hydrogéologique, les données sont réparties irrégulièrement i.e. verticalement denses et horizontalement clairsemées, ce qui peut résulter en une tessellation inadéquate dont les éléments seront soit très grands, soit très petits, soit très minces. La taille et la forme des éléments formant la tessellation ont un impact important sur l'exactitude des résultats de la simulation, ainsi que sur les coûts de calcul qui y sont reliés. Par conséquent, la première étape de notre travail de recherche est consacrée au développement d’une méthode de raffinement adaptative basée sur la structure de données Delaunay dynamique 3D et à la construction d’une tessellation 3D adaptative pour la représentation et la simulation de champs dynamiques. Cette tessellation s’ajuste à la complexité des champs, en considérant les discontinuités et les critères de forme et de taille. Afin de traiter le comportement dynamique des champs 3D dynamiques dans SIG, nous étendons dans la deuxième étape de cette recherche le VD 3D dynamique au VD 3D cinématique pour pouvoir mettre à jour en temps réel la tessellation 3D lors des procédés de simulation dynamique. Puis, nous montrons comment une telle structure de données spatiale peut soutenir les éléments en mouvement à l’intérieur de la tessellation ainsi que leurs interactions. La structure de données cinétique proposée dans cette recherche permet de gérer de manière élégante les changements de connectivité entre les éléments en mouvement dans la tessellation. En outre, les problèmes résultant de l'utilisation d’intervalles de temps fixes, tels que les dépassements et les collisions non détectées, sont abordés en fournissant des mécanismes très flexibles permettant de détecter et contrôler différents changements (événements) dans la tessellation Delaunay 3D. Enfin, nous étudions le potentiel de la structure de données spatiale cinétique 3D pour la simulation de champs dynamiques dans l'espace tridimensionnel. À cette fin, nous décrivons en détail les différentes étapes menant à l'adaptation de cette structure de données, de sa discrétisation pour des champs 3D continus à son intégration numérique basée sur une méthode événementielle. Nous démontrons également comment la tessellation se déplace et comment la topologie, la connectivité, et les paramètres physiques des cellules de la tessellation sont localement mis à jour suite à un événement topologique survenant dans la tessellation. Trois études de cas sont présentées dans la thèse pour la validation de la structure de données spatiale proposée, et de son potentiel pour la simulation de champs spatiaux 3D et dynamiques. Selon nos observations, pendant le procédé de simulation, la structure de données est préservée et l'information 3D spatiale est gérée adéquatement. En outre, les résultats calculés à partir des expérimentations sont très satisfaisants et sont comparables aux résultats obtenus à partir d'autres méthodes existantes, pour la simulation des mêmes champs dynamiques. En conclusion, certaines des limites de l'approche proposée liées au développement de la structure de données 3D cinétique et à son adaptation pour la représentation et la simulation d'un champ spatial 3D et dynamique sont discutées, et quelques solutions sont suggérées pour l'amélioration de l'approche proposée.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