| Résumé : |
(Auteur) Current topographic products are limited to a real world representation in only two dimensions, with at best some additional point heights and contour lines. Modelling the real world in two dimensions implies a rather drastic simplification of three di-mensional real world elements. By representing these elements in two dimensions, loss of information is inevitable. Due to this simplification, accuracy of analysis results is limited and a meaningful, insightful representation of complex situations is hard to obtain. Environmental issues like high concentrations of particulate matter along highways in urban areas, the effects of noise and odour propagation and risk analysis of liquefied petroleum gas storage tanks are random examples of current issues in 3D urban planning in which more precision is required than 2D analyses can offer. In a time with increasing attention for these kind of environmental and sustainability issues, limitations of 2D models become real problematic and trigger the demand for 3D topography.
The development of 3D topography is also supply-driven, especially by the increasing availability of high density laser scan data. Height data becomes available with point densities -multiple height points per square meter- that were previously unthinkable with traditional photogrammetric stereo techniques. Direct 3D data ac-quisition by terrestrial laser scanning is emerging, thus providing detailed measure-ments of facades, tunnels and even indoor topography. The fast developments in this field are partly triggered by the emerging popularity of personal navigation devices, which will use 3D models in the future to simplify user interpretation of the (map) display.
Objective and research question
The objective of this research is to develop a data structure that is capable of han-dling large data volumes and offers support for loading, updating, querying, analysis and especially validation. To achieve this, a triangular approach will be used, due to its advantages in maintaining consistency, its robustness and editability. This tri-angular approach creates a network of triangles (in 2D) or tetrahedrons (in 3D), in which topographic features are represented by sets of triangles or tetrahedrons. Such a network is an example of an irregular tessellation, in which the real world is de--composed into smaller (triangle/tetrahedron-shaped) building blocks. The resulting networks are called TINs (Triangular Irregular Networks) or TENs (TEtrahedronised irregular Networks). The presence of boundaries of topographic features are ensured by the use of constraints, preventing the deletion of crucial boundary edges and trian-gles. Algorithms exist to calculate these constrained triangulations and constrained tetrahedronisations of topographic data.
In this research a two-step approach will be adopted. First one has to decide how real-world objects should be modelled into features, secondly one needs to store these features in such a way that the requirements in terms of querying, analysis and validation are met. An obvious step in dealing with large volumes of geographically referenced data, is to use a spatial database.
This objective is expressed in the main research question:
How can a 3D topographic representation be realised in a feature-based triangular data model?
Note that the term 'triangular' is used here in general dimension, so both triangle-and tetrahedron-based models will be considered. As mentioned before, a two-step approach will be adopted to achieve a solution to the main research question. In accordance with the two steps, two key questions can be distinguished:
How to develop a conceptual model that describes the real world phenomena (the topographic features), regarding the general purpose-characteristic of to-pographic data sets?
How to implement this conceptual model, i.e. how to develop a suitable DBMS data structure?
The results of this research will be summarised according to this two-step approach.
A conceptual data model for 3D topography
One of the basic assumptions within this research is the use of triangular data models. As a result, topographic features will be described as sets of triangles and these fea-tures will be connected by triangles as well, thus creating one triangular network. This research explored two different approaches to triangular modelling of 3D topography.
The first one is a very pragmatic hybrid approach that combines a 2.5D* sur-face with 3D objects for those cases where 2.5D modelling is not sufficient. In terms of triangular data structures, this approach combines a TIN with several TENs. These irregular data structures not only allow varying point density (de-pending on local model complexity), but extend this irregularity into varying even model dimensionality, thus offering the ultimate fit-for-purpose approach. Unfortunately, connecting TIN and TEN networks appeared to be very difficult at design level and during prototype implementation.
The second approach avoids these problems, since it is a full 3D approach using only a TEN. Two fundamental observations are of great importance:
Physical objects have by definition a volume. In reality, there are no point, line or polygon objects; only point, line or polygon representations exist (at a certain level of abstraction/generalisation).
The real world can be considered a volume partition: a set of nonoverlap-ping volumes that form a closed (i.e. no gaps within the domain) modelled space. Objects like 'earth' or 'air' are thus explicitly included in the model.
In topographic data models, planar features like walls or roofs are obviously very useful. They can be part of the volumetric data model as 'derived features', i.e. these features depend on the relationship between volume features. For example, the earth surface is the boundary between air and earth features, while a wall or a roof are the result of adjacent building and air features. In terms of UML, these planar features are modelled as association classes. As a result, planar features are lifetime dependent from the association between two volume features.
Among the advantages of the full volumetric approach are its explicit inclusion of air and earth (often subject of analysis), its extensibility (geology, air traf-fic/telecommunication corridors, etc.) and its strong mathematical definition (full connectivity enables the use of topology for query, analysis and validation). As a re-sult, topographic features will be modelled in a TEN. Each feature will be represented by a set of tetrahedrons.
A data structure for 3D topography
The newly developed data structure has three important characteristics:
It has a solid mathematical foundation. Operators and definitions from the mathematical field of Poincare simplicial homology (part of algebraic topology) are used to handle simplexes^, the basic elements in a triangular data structure. Simplexes are well defined, ordered and constructed of simplexes of lower di-mension. The boundary operator can be used to derive these less dimensional
*See section 2.2 for an overview of often-used dimension indicators
tA simplex can loosely be defined as the simplest shape in a dimension, in which simplest refers to minimising the number of points required to define such a shape, for instance a point, a line, a triangle and a tetrahedron. See section 4.1 for a proper mathematical definition simplexes. Based on the ordering of simplexes, one can determine orientation, a useful concept in GIS. Another important concept from simplicial homology is the simplicial complex, since such a set of connected simplexes will be used to model 3D topographic features.
It is developed as a spatial database data structure. Applying definitions and operators from simplicial homology enables one to store a TEN in a relatively compact way. The new simplicial complex-based method requires only explicit storage of tetrahedrons, while simplexes of lower dimensions (triangles, edges, nodes), constraints (which guarantee feature boundary presence) and topologi-cal relationships can be derived in views. Using functions to derive views from a table is typical database functionality. In this implementation, simplexes are en-coded by their vertices, similar to the annotation in simplicial homology. These simplex encodings are extended with a feature identifier, indicating which to-pographic feature is (partly) represented by this simplex. So, a tetrahedron is encoded as 83 =< vq, Vi, V2,v^, fid >. Two variants in simplex encoding have been developed: coordinate concatenation and identifier concatenation. The concept of coordinate concatenation is to concatenate x, y and z coordinates as node identifiers and to concatenate the resulting unique node codes to describe simplexes of higher dimension. The alternative approach, identifier concatena-tion, uses separate (meaningless) node identifiers to encode simplexes to reduce the number of coordinate repetitions, since a specific node will be part of multi-ple tetrahedrons. This approach requires an additional node table to store node geometries.
It is an editable data structure, which is a crucial prerequisite to be a feasible approach for topographic data storage. Incremental updates are required, since complete rebuilds of the TEN structure will be time-consuming due to the ex-pected data volumes. Whereas most existing update algorithms for constrained tetrahedronisations use node insertions, followed by edge reconstruction, this research presents edge insertion operators. Nine exhaustive and mutually exclusive cases are distinguished, based on the location in the TEN of the inserted edge's nodes. These operators guarantee the constrained edge's presence in the structure. Existing operators might fail to recover these edges, due to the pres-ence of nearby constrained edges, which would typically happen in topographic data sets.
Conclusions
This dissertation presents a new topological approach to data modelling, based on a tetrahedral network. Operators and definitions from the field of simplicial homology are used to define and handle this structure of tetrahedrons. Simplicial homology provides a solid mathematical foundation for the data structure and offers full control over orientation of simplexes and enables one to derive substantial parts of the TEN structure efficiently, instead of explicitly storing all primitives. DBMS characteristics as the usage of views, functions and function-based indexes are extensively used to realise this potential data reduction. A proof-of-concept implementation was created and tests with several data sets show that the prevailing view that tetrahedrons are more expensive in terms of storage when compared to polyhedrons, is not correct when using the proposed approach. Storage requirements for 3D objects in tetrahe-dronised form (excluding the space in between these objects) and 3D objects stored as polyhedrons, are in the same order of magnitude.
A TEN has favourable characteristics from a computational point of view. All elements of the tetrahedral network consist by definition of flat faces, all elements are convex and they are well defined. Validation of 3D objects is also simplified by tetrahedronisation. Furthermore, a full volumetric approach enables future integra-tion of topography with other 3D data like geological layers, polluted regions or air traffic and telecommunication corridors. The price of this full volumetric approach in terms of storage space is high (about 75% of the tetrahedrons models air or earth); nevertheless this approach is likely to become justifiable due to current developments towards sustainable urban development and increased focus on environmental issues.
Now the innovative aspects of the proposed method has to be identified. Neither the idea to use a TEN data structure for 3D data nor the idea to use simplexes (in terms of simplicial homology) in a DBMS implementation is new. However, the proposed approach reduces data storage and eliminates the need for explicit updates of both topology and simplexes of lower dimension. By doing so, the approach tackles common drawbacks as TEN extensiveness and laboriousness of maintaining topology. Furthermore, applying simplicial homology offers full control over orientation of sim-plexes, which is a significant advantage, especially in 3D. In addition to this aspect, the mathematical theory of simplicial homology offers a solid theoretical foundation for both the data structure and data operations. Integrating these concepts with database functionality results in a new innovative approach to 3D data modelling.
An often raised objection to a TEN approach is its presumed complexity. Obviously, a l:n relation exists between features and their tetrahedron representations. However, as long as a user handles only features (as polyhedrons) and implemented algorithms translate these polyhedrons into operations on the TEN, one can over-come the perceived complexity. Furthermore, the prevailing view that tetrahedrons are more expensive in terms of storage than polyhedrons has been falsified in this research.
Overall, the simplicial complex-based modelling approach provides a provable correct modelling method. The use of tetrahedrons is justified by the mathematical benefits and the acceptable storage requirements. Obviously, including air and earth within the model comes at a price, but -as stated earlier- this approach is likely to become justifiable, due to current sustainability and environmentally-driven developments. The decision to develop the data structure as a database structure contributes to the overall feasibility, since a database will become indispensable due to the expected data volumes. |
Ajouter le résultat dans votre panier Affiner la recherche Interroger des sources externesScalable surface reconstruction with Delaunay-Graph neural networks / Raphaël Sulzer in Computer graphics forum, vol 40 n° 5 (2021)
