logo NCGeo

3D Topography. A Simplicial Complex-based Solution in a Spatial DBMS

PoG 66, Friso Penninga, 3D Topography. A Simplicial Complex-based Solution in a Spatial DBMS

Friso Penninga

Publications on Geodesy 66
Delft, 2008. 204 pagina's. ISBN: 978 90 6132 304 4.


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 (TEtrahedronised irregular Networks) 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 tetrahedronised 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 integration 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 simplexes, 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 1: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 overcome 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.


Contents

Acknowledgements  iii
1. Introduction  1
2. Research background  9
I. Conceptual modelling of 3D Topography  39
3. Two triangular data models for 3D topography  41
II. A Data structure for 3D Topography  55
4. Theoretical foundations: Poincaré simplicial homology  57
5. A simplicial complex-based solution for 3D topography  71
6. Updating features in the Data Structure  87
III. Evaluation and conclusions  111
7. Evaluation and discussion  113
8. Conclusions  135
Bibliography  145
Appendix I - Implementation: Functions and procedures  155
Appendix II - Implementation: Creating the data structure  171
Appendix III - Converting to Oracle Spatial 11g polyhedrons  175
Appendix IV - TetGen files  177
Summary  181
Samenvatting  187
Curriculum Vitae  193


Conclusies

Dit proefschrift beschrijft een nieuwe topologische aanpak van datamodellering die uitgaat van tetraëdernetwerken. Operatoren en definities uit de simpliciale homologie worden toegepast in het definiëren en bewerken van deze structuur van tetraëders. De simpliciale homologie biedt een solide wiskundige onderbouwing van de datastructuur, volledige controle over oriëntatie van simplexen en maakt het mogelijk om grote delen van de datastructuur af te leiden in plaats van expliciet op te slaan. Databasefunctionaliteit zoals het gebruik van views, functies en functiegebaseerde indexen worden toegepast om het potentieel van de datastructuur te realiseren. Een experimentele implementatie is ontwikkeld en tests met verschillende datasets tonen aan dat de heersende opvatting dat tetraëders meer opslagruimte vergen dan polyëders, achterhaald is. De vereiste opslagruimte voor 3D objecten in getetraëdriseerde vorm (het modelleren van tussenliggende ruimtes niet meegerekend) en voor 3D objecten in polyërderformaat, liggen in dezelfde orde van grootte.

Het gebruik van een TEN (TEtrahedronised irregular Networks) biedt een aantal rekenkundige voordelen. Elk element in een TEN bestaat uit platte vlakken, elk element is convex en alle elementen zijn goed gedefinieerd. Validatie van 3D objecten wordt ook eenvoudiger wanneer er gebruik gemaakt wordt van tetraëdernetwerken. Daarnaast biedt de volledig 3D modellering ruimte voor toekomstige integratie van topografie met andere 3D data zoals geologie, vervuilde aardlagen en straalpaden. De prijs van het volledig in 3D modelleren is hoog (ongeveer 75% van de tetraëders beschrijft lucht of aarde); toch kan deze aanpak gerechtvaardigd worden, gezien de huidige ontwikkelingen richting duurzame stedelijke ontwikkeling en toegenomen aandacht voor milieukwesties.

Nu kunnen ook de vernieuwende aspecten van de voorgestelde methode worden bepaald. Noch het idee om een TEN structuur te gebruiken voor 3D data, noch het idee om simplexen (zoals in de simpliciale homologie) in een database structuur te gebruiken, is nieuw. Desondanks brengt de voorgestelde methode de vereiste opslagruimte terug en maakt het expliciete bijhouding van zowel topologie als van simplexen van lagere dimensie overbodig. Hiermee ondervangt de nieuwe methode de 'klassieke' nadelen van een tetraëderstructuur. Daarnaast biedt het toepassen van simpliciale homologie volledige controle over oriëntatie van simplexen, wat met name in 3D een enorm voordeel is. Bovendien biedt simpliciale homologie een solide wiskundige onderbouwing voor zowel de datastructuur als voor de operaties erop. Het integreren van deze concepten in een databaseomgeving resulteert in een vernieuwende aanpak van 3D datamodellering.

Een vaakgenoemd nadeel van een TEN aanpak is de veronderstelde complexiteit. Immers, er bestaat een 1:n relatie tussen objecten en hun tetraëderrepresentatie. Hoe dan ook, zolang een gebruiker alleen objecten manipuleert en algoritmes zorgdragen voor de bijbehorende wijzigingen in de datastructuur, wordt dit nadeel volledig ondervangen. Daarnaast is aangetoond dat een TEN aanpak niet meer opslagruimte vergt dan een polyëderaanpak, waarmee omvang dus niet meer bijdraagt aan eventuele complexiteit.

Afsluitend kan gesteld worden dat de simpliciale complex-gebaseerde aanpak een bewijsbaar correcte modelleermethode is. Het gebruik van tetraëders wordt gelegitimeerd door wiskundige voordelen en acceptabele opslagvereisten. Natuurlijk leidt het expliciet opnemen van lucht en aarde tot een aanzienlijke toename in datavolume, maar - zoals eerder reeds opgemerkt - toch kan deze aanpak gerechtvaardigd worden, gezien de huidige ontwikkelingen op duurzaamheid- en milieugebied. De keuze om de datastructuur in een ruimtelijke database te implementeren draagt bij aan de algehele bruikbaarheid, aangezien het gebruik van een database onvermijdelijk zal worden gezien de verwachte datavolumes.

Ga naar boven
JSN Boot template designed by JoomlaShine.com