This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Lecture Notes in Geoinformation and Cartography Series Editors: William Cartwright, Georg Gartner, Liqiu Meng, Michael P. Peterson
For further volumes: http://www.springer.com/series/7418
.
Thomas H. Kolbe (Eds.)
l
Gerhard Ko¨nig
l
Claus Nagel
Advances in 3D Geo-Information Sciences
Editors Thomas H. Kolbe Technische Universita¨t Berlin Fachgebiet Methodik der Geoinformationstechnik Sekr. H 12 Strabe des 17. Juni 135 10623 Berlin Germany [email protected]
Gerhard Ko¨nig Technische Universita¨t Berlin Fachgebiet Methodik der Geoinformationstechnik Sekr. H 12 Straße des 17. Juni 135 10623 Berlin Germany [email protected]
Claus Nagel Technische Universita¨t Berlin Fachgebiet Methodik der Geoinformationstechnik Sekr. H 12 Strabe des 17. Juni 135 10623 Berlin Germany [email protected]
ISSN 1863-2246 e-ISSN 1863-2351 ISBN 978-3-642-12669-7 e-ISBN 978-3-642-12670-3 DOI 10.1007/978-3-642-12670-3 Springer Heidelberg Dordrecht London New York Library of Congress Control Number: 2011921705 # Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: deblik, Berlin Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
Preface
The shape, extent, and location of spatial objects and environmental phenomena as well as the spatial distribution of physical and environmental characteristics are increasingly being described using three-dimensional (3D) geospatial representations today. In general, 3D modeling does not only affect the dimensionality of the spatial representation but also introduces the thematic structuring and decomposition of objects and phenomena along an additional – often the vertical – axis, leading to models that are typically much higher structured than 2D models. However, building modeling, urban and landscape modeling, modeling of the lithosphere and topography of the Earth, and Earth system modeling all have different requirements on the specific spatial representation and have brought forward a multitude of different 3D modeling frameworks and paradigms. With the additional consideration of temporal aspects another representational dimension is reflected, often being referred to as 4D modeling. One of the most active research fields has been recently the integration of spatial and spatio-temporal aspects together with thematic information from diverse application domains. Semantic 3D modeling addresses the thematic attributation and thematic interrelationships according to multiple domains. Representing the 3D/4D spatio-temporal properties along with the thematic aspects of the different domains is sometimes also called n-dimensional (nD) modeling. The complex structuring of geospatial information according both to spatial representations and semantic representations raises issues of spatio-semantic coherence that the scientific community has started to investigate only recently. Three-dimensional, four-dimensional, and n-dimensional models require efficient methods for the storage, retrieval, analysis, and visualization. Furthermore, standards are required that ensure the lossless exchange of information between the distributed components of spatial data infrastructures. New application domains require the development of new concepts for the representation of 3D space and three-dimensional spatial properties of real world entities and phenomena. In order to present the current state of the art in 3D geoinformation science and to further discuss these research topics the International Conference on 3D GeoInformation 2010 was held in Berlin, Germany. It is the successor of the four workshops on 3D GeoInformation that were carried out in the years 2009
v
vi
Preface
(Ghent, Belgium), 2008 (Seoul, South Korea), 2007 (Delft, The Netherlands), and 2006 (Kuala Lumpur, Malaysia). The 3D GeoInfo 2010 conference was conducted under the auspices of Working Group IV/8 of the International Society for Photogrammetry and Remote Sensing (ISPRS), the Open Geospatial Consortium (OGC), European Spatial Data Research (EuroSDR), the German Society for Photogrammetry, Remote Sensing, and Geoinformation (DGPF), and Berlin University of Technology. With more than 150 participants the 3D GeoInfo Conference 2010 offered an extensive interdisciplinary forum for international researchers from academia, industry, and government in the field of 3D geoinformation. In two keynote talks given by Maik Thomas from the GeoForschungsZentrum Potsdam (GFZ) and Ron Lake from Galdos Inc., 30 oral and 19 poster presentations, and an industry exhibition many different aspects of 3D geoinformation science were addressed and discussed. This book contains selected papers of highest quality that were presented at the conference. They have gone through a rigorous double-blind review process and were examined by three members of the program committee each. Afterwards the papers have been edited by the authors again in order to reflect the comments and suggestions of the reviewers. All other conference papers and extended abstracts that were accepted for oral and poster presentation are provided in a separate proceedings volume published by ISPRS within their International Archives of Photogrammetry and Remote Sensing (IAPRS), Vol. XXXVIII-4, Part W/15. Such a big event could not be realised without the help of many people. We thank the organising committee chaired by Bernd Stary (in alphabetical order): Thomas Becker, Andreas Fuls, Javier Herreruela, Robert Kaden, Andreas Kru¨ger, Rosemarie Kunkel, Hartmut Lehmann, Alexandra Lorenz, Sven Weisbrich. We owe special gratitude to Herbert Krauß from DGPF for taking care of the financial transactions and accounting. We would also like to thank Sisi Zlatanova for her advice and help in setting up the conference. We appreciate very much the support of Mrs. Agata Oelschla¨ger from Springer Verlag in the planning and preparation of this book. We further thank the scientific organisations ISPRS, EuroSDR, DGPF, and the international standardisation body OGC for taking over patronage of this event. Thanks go also to the program committee and the additional reviewers. We express our gratitude to the sponsors whose contributions helped us much in keeping the registration fees at a reasonable height. Last but not least we thank the invited speakers and all colleagues who have submitted papers about their research and especially those who finally joined the conference and presented their work in either oral or poster presentations. Berlin Germany October 2010
Thomas H. Kolbe Gerhard Ko¨nig Claus Nagel
Organisation
Program Chair Thomas H. Kolbe
Technische Universita¨t Berlin
Scientific Committee Alias Abdul-Rahman Roland Billen Lars Bodum Martin Breunig Eliseo Clementini Volker Coors Ju¨rgen Do¨llner Thomas H. Kolbe Philippe de Maeyer Claudine Me´tral Christopher M. Gold Gerhard Gro¨ger Gerhard Joos Hugo Ledoux Jiyeong Lee Ki-Joune Li Fred Limp Marc-Oliver Lo¨wner Hui Lin Stephan Nebiker ¨ stman Anders O Norbert Pfeifer Jacynthe Pouliot Carl Reed Massimo Rumor Monika Sester Uwe Stilla Andre´ Streilein Rod Thompson
Universiti Teknologi, Malaysia University of Lie`ge, Belgium Aalborg University, Denmark University of Osnabru¨ck, Germany University of L’Aquila, Italy University of Applied Sciences Stuttgart, Germany University of Potsdam, Germany Technische Universita¨t Berlin, Germany Ghent University, Belgium University of Geneva, Switzerland University of Glamorgan, United Kingdom University of Bonn, Germany NATO C3 Agency, The Netherlands Delft University of Technology, The Netherlands University of Seoul, South Korea Pusan National University, South Korea University of Arkansas, Fayetteville, NC, USA Technische Universita¨t Braunschweig Chinese University of Hong Kong, China University of Applied Sciences, Switzerland University of Ga¨vle, Sweden Vienna University of Technology, Austria Universite´ Laval, Que´bec, Canada Open Geospatial Consortium, USA University of Padova, Italy University of Hannover, Germany Technische Universita¨t Mu¨nchen, Germany Swisstopo, Switzerland Queensland Government, Australia
vii
viii Peter van Oosterom George Vosselman Peter Woodsford Mike Worboys Qing Zhu Alexander Zipf Sisi Zlatanova
Organisation Delft University of Technology, The Netherlands ITC Enschede, The Netherlands Snowflake Software, United Kingdom University of Maine, Orono, ME, USA Wuhan University, China University of Heidelberg, Germany Delft University of Technology, The Netherlands
Additional Reviewers Thomas Becker Robert Kaden Claus Nagel
Local Organizing Committee Thomas Becker Andreas Fuls Javier Herreruela Robert Kaden Gerhard Ko¨nig Andreas Kru¨ger Rosemarie Kunkel Hartmut Lehmann Alexandra Lorenz Claus Nagel Bernd Stary Sven Weisbrich
3D Cadastre in the Province of Quebec: A First Experiment for the Construction of a Volumetric Representation . . . . . . . . . . . . . . . . . . . . . 149 Jacynthe Pouliot, Tania Roy, Guillaume Fouquet-Asselin, and Joanie Desgroseilliers 3D Modeling for Mobile Augmented Reality in Unprepared Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Vincent Thomas, Sylvie Daniel, and Jacynthe Pouliot Integrated Representation of (Potentially Unbounded) 2D and 3D Spatial Objects for Rigorously Correct Query and Manipulation . . . . . . . 179 Rodney James Thompson and Peter van Oosterom Interactive Rendering Techniques for Highlighting in 3D Geovirtual Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Matthias Trapp, Christian Beesk, Sebastian Pasewaldt, and Ju¨rgen Do¨llner Integration of BIM and GIS: The Development of the CityGML GeoBIM Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 Ruben de Laat and Le´on van Berlo Modelling Three-Dimensional Geoscientific Datasets with the Discrete Voronoi Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 Tom van der Putte and Hugo Ledoux Challenges in 3D Geo Information and Participatory Design and Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Jan B.F. van Erp, Anita H.M. Cremers, and Judith M. Kessens An Integrated Framework for Reconstructing Full 3D Building Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Langyue Wang and Gunho Sohn Towards Semantic 3D City Modeling and Visual Explorations . . . . . . . . . . 275 Qing Zhu, Junqiao Zhao, Zhiqiang Du, Yeting Zhang, Weiping Xu, Xiao Xie, Yulin Ding, Fei Wang, and Tingsong Wang
Contributors
Thomas Becker Institute for Geodesy and Geoinformation Science, Technische Universita¨t Berlin, Berlin, Germany, [email protected] Christian Beesk Hasso-Plattner-Institute, University of Potsdam, Potsdam, Germany, [email protected] W.L. (Pim) Bil Gemeente Amstelveen, Amstelveen, The Netherlands, p.bil@ amstelveen.nl Pawel Boguslawski Department of Computing and Mathematics, University of Glamorgan, Pontypridd, United Kingdom, [email protected] Ju¨rgen Bollmann Cartography, University of Trier, Trier, Germany, [email protected] Martin Christen Institute of Geomatics Engineering, University of Applied Sciences Northwestern Switzerland, Muttenz, Switzerland, [email protected] Anita H.M. Cremers Human Factors, Netherlands Organisation for Applied Scientific Research TNO, Delft, The Netherlands, [email protected] Sylvie Daniel Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] Ruben de Laat Netherlands Organisation for Applied Scientific Research TNO, Delft, The Netherlands, [email protected] Joanie Desgroseilliers Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] Yulin Ding State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] xi
xii
Contributors
Ju¨rgen Do¨llner Hasso-Plattner-Institute, University of Potsdam, Potsdam, Germany, [email protected] Zhiqiang Du State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Manfred Ehlers Institute for Geoinformatics and Remote Sensing, University of Osnabru¨ck, Osnabru¨ck, Germany, [email protected] Mohamed Sobih El-Mekawy Future Position X, Ga¨vle, Sweden, [email protected] Guillaume Fouquet-Asselin Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] Christopher Gold Department of Computing and Mathematics, University of Glamorgan, Pontypridd, United Kingdom; Department of Geoinformatics, Universiti Teknologi, Johor Bahru, Johor, Malaysia, [email protected] Ihab Hijazi Institute for Geoinformatics and Remote Sensing, University of Osnabru¨ck, Osnabru¨ck, Germany, [email protected] Judith M. Kessens Human Factors, Netherlands Organisation for Applied Scientific Research TNO, Delft, The Netherlands, [email protected] Thomas H. Kolbe Institute for Geodesy and Geoinformation Science, Technische Universita¨t Berlin, Berlin, Germany, [email protected] Anis Korchi Vicomtech, Donostia-San Sebastin, Spain, [email protected] Hugo Ledoux GIS Technology Group, Delft University of Technology, Delft, The Netherlands, [email protected] Anja Matatko Cartography, University of Trier, Trier, Germany, [email protected] Aitor Moreno Vicomtech, Donostia-San Sebastin, Spain, [email protected] Andreas Mu¨ller Cartography, University of Trier, Trier, Germany, [email protected] Claus Nagel Institute for Geodesy and Geoinformation Science, Technische Universita¨t Berlin, Berlin, Germany, [email protected]
Contributors
xiii
Stephan Nebiker Institute of Geomatics Engineering, University of Applied Sciences Northwestern Switzerland, Muttenz, Switzerland, [email protected] ¨ stman GIS Institute, University of Ga¨vle, Ga¨vle, Sweden, Anders. Anders O [email protected] Oihana Otaegui Vicomtech, Donostia-San Sebastin, Spain, ootaegui@ vicomtech.org Sebastian Pasewaldt Hasso-Plattner-Institute, University of Potsdam, Potsdam, Germany, [email protected] Jorge Posada Vicomtech, Donostia-San Sebastin, Spain, [email protected] Jacynthe Pouliot Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] Tania Roy Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] ´ lvaro Segura Vicomtech, Donostia-San Sebastin, Spain, [email protected] A Khurram Shahzad Department of Computer and System Sciences, Royal Institute of Technology, Stockholm, Sweden, [email protected] Gunho Sohn GeoICT Laboratory, York University, Toronto, ON, Canada, [email protected] Vincent Thomas Geomatics Department, Universite´ Laval, Que´bec, QC, Canada G1V 0A6, [email protected] Rodney James Thompson Department of Environment and Resource Management, Indooroopilly, Queensland, Australia; OTB, GIS Technology, Delft University of Technology, Delft, The Netherlands, [email protected] Matthias Trapp Hasso-Plattner-Institute, University of Potsdam, Potsdam, Germany, [email protected] Le´on van Berlo Netherlands Organisation for Applied Scientific Research TNO, Delft, The Netherlands, [email protected] Tom van der Putte Netherlands Organisation for Applied Scientific Research TNO, Geological Survey of the Netherlands, Utrecht, The Netherlands, tom. [email protected]
xiv
Contributors
Jan B.F. Van Erp Human Factors, Netherlands Organisation for Applied Scientific Research TNO, Delft, The Netherlands, [email protected] Peter van Oosterom OTB, GIS Technology, Delft University of Technology, Delft, The Netherlands, [email protected] Fei Wang State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Langyue Wang GeoICT Laboratory, York University, Toronto, ON, Canada, [email protected] Tingsong Wang State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Xiao Xie State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Weiping Xu State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Yeting Zhang State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Junqiao Zhao State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Qing Zhu State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan, People’s Republic of China, [email protected] Sisi Zlatanova OTB, Research Institute for Housing, Urban and Mobility Studies, Delft University of Technology, Delft, The Netherlands, [email protected]
.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies for Critical Infrastructure Analysis T. Becker, C. Nagel, and T.H. Kolbe
Abstract In today’s technologically advanced society the dependency of every citizen and company on working infrastructures is extremely high. Failures of critical infrastructures, such as the Italian blackout in 2003 or the failure of power supply in wide parts of Europe in 2006, demonstrate the strong linkage of networks across borders. However, also infrastructures within the same geographic region but of different types have strong interdependencies and failures in one type of network can have cascading effects onto the other networks. In order to support risk analysis and planning of emergency response actions the modeling of critical infrastructures and their mutual dependencies in 3D space is required. Decision makers need a comprehensive view of the disaster situation to be able to estimate the consequences of their action. For this purpose, a comprehensive understanding and simulation of cascading or looping effects as well as the propagation of the disaster extend is needed. But neither the existing utility networks models nor the international standards for modeling cities or buildings map the mutual interrelationships between different infrastructures or between the city and its infrastructures. In this paper the requirements and a novel framework for the integrated 3D modeling of critical infrastructures within cities is presented. By giving a dual representation utility network components are modeled both according to their 3D topography and by a complementary graph structure embedded into 3D space.
1 Introduction The field of critical infrastructures, the simulation of their failure and breakdown, and possible occurrences of cascading or looping effects are examined by researchers worldwide.
T. Becker (*), C. Nagel, and T.H. Kolbe Institute for Geodesy and Geoinformation Science, Technische Universit€at Berlin, Strasse des 17, Juni, 10623 Berlin, Germany e-mail: [email protected]; [email protected]; [email protected]
T.H. Kolbe et al. (eds.), Advances in 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, DOI 10.1007/978-3-642-12670-3_1, # Springer-Verlag Berlin Heidelberg 2011
1
2
T. Becker et al.
The European Union, Germany, United Kingdom, and the USA have criticalinfrastructure programmes which mostly define electricity generation, transmission, and distribution as well as gas production, transport and distribution, telecommunication, water supply, transportation and heating, and many more as critical infrastructures (see Pederson et al. 2006). These programmes address the identification of important objects, risk analysis based on threat scenarios (Johnson 2007; Dudenhoefer et al. 2006) and the vulnerability of each object as well as the identification, selection, and priorisation of counter-measures and procedures. As it is shown by Johnson (2007), a small fault can trigger a blackout of a whole power supply network across the borders of different countries, leading to a domino effect that has separated, in the discussed case Italy from the whole European grid. It is easily conceivable that many other infrastructures are critically depending on electrical energy. A wide failure of energy supply would have for example the consequence that telecommunications, water supply, sewage disposal and many other infrastructures would also fail, assuming that they do not dispose of a backup system. However, it is completely unknown whether, e.g., by the failure of water supply (which may include uncontrolled leakage of water) failures in other infrastructures can be induced (cascade effect) or even are amplified and reflected (loop effect), or which effects or damages will be caused on the city structures. In order to be able to estimate the consequences of their action, decision makers have to get a comprehensive view of the disaster situation. A very detailed understanding and simulation of cascading or looping effects as well as the propagation of the disaster extend is needed. The base for such a common simulation and an all comprehensive common operational picture (COP) of the actual situation of a disaster is an integrated 3D topographic model of critical infrastructures and their inherent spatial relations to the city. In Sect. 2 the requirements on modeling 3D multi-utility networks as well as modeling of interdependencies between critical infrastructures are discussed in detail. Hence, in Sect. 3, an overview of related models like the Industry Foundation Classes (IFC) (Liebich 2009), ArcGIS and INSPIRE is given, whereas in Sect. 4 our conceptual approach of modeling utilities with respect to the identified requirements is presented. In Sect. 5 it is shown how the UtilityNetworkADE is implemented as an extension of the international standard CityGML (Gr€oger et al. 2008). In Sect. 6 we draw conclusions and give an outlook to future work.
2 Requirements on Modeling 3D Multi-utility Networks Pederson et al. (2006) and Tolone et al. (2004) present some scenarios and approaches to model and simulate critical infrastructures and their complex interdependencies. Tolone et al. further demonstrate that the behavior of critical infrastructures can be better understood through multi-infrastructure simulations. In order to understand the dynamics and dependencies of utility networks and to allow the propagation and visualization of effects (see Johnson 2007) a first identified requirement
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
3
on multi-utility networks is that a geometrical, topological, and functional embedding of critical infrastructures into the urban space must be done. This will also allow the joint visualization of virtual 3D city models and 3D utility networks, which would be very helpful to understand the locations and spatial relations of infrastructures in the context of city objects. A better understanding facilitated by a joint 3D visualization would result in a better decision making process and coordination between decision makers and actors such as fire fighters. Moreover, an integrated modeling of utilities and city topography facilitates the visualization and analysis of dependencies between city objects and network components, such as which city object depends on which infrastructure. Complex analyses or simulations such as collision detection (e.g. excavator vs. pipe), determination of explosion impact (determination of damaged objects), and simulations predicting, for example, the spread of water in a flood scenario above and below the ground require the 3D topographic representation and description of the components of the utility network of a city. The structural description of the entire network by graph structures with a 3D embedding is suitable to calculate the relative position between network objects of different commodities, their spatial relation to each other as well as their spatial relation to other objects of the city, such as buildings, city furniture, or roads. Due to the fact that the different types of infrastructure of the city lie above and in between each other the embedding into the 3D space plays an important role. Furthermore, 3D visual inspection helps in getting a better understanding of the spatial relations of the networks relative to each other. Network analyses such as the calculation of slope or slope change becomes possible. Thus, it is conceivable that a 3-dimensional description of the city (see Gr€ oger et al. 2008) as well as a suitable 3D description of the underlying utility network has to be realized. The 3D objects of the network must be integrated into the 3D space of the city and thus they can be queried in the context of a disaster management. An investigation of existing utility network models (ESRI 2003, 2007; INSPIRE Data Specifications Drafting Team 2009; INSPIRE Thematic Working Group Transport Networks 2009; Meehan 2007; Liebich 2009; Becker et al. 2010) shows that different types of hierarchies are used to decompose networks into sub networks or single features into their components. On the one hand hierarchies are suitable to express different kind of pressure levels, flow rates as well as voltage levels. On the other hand hierarchies are suitable for realizing different kinds of feature aggregation within the same sub network. While for the evaluation of the connectivity of network objects a very general view of the network connectivity is sufficient, simulating the failure of network components and resulting cascading effects may require a more detailed description of the interior of a network component. For example, a switch gear cabinet may consist of different switches, transformers, and fuses. Each of these components of the switch gear cabinet may trigger a network failure and may lead to a cascading effect across different networks. Thus, it is mandatory for an integrated network model that both the whole network can be expressed as an aggregation of different sub networks with homogeneous commodity and those individual network components, such as
4
T. Becker et al.
a pump or switch gear cabinet can be represented as an aggregation of a set of network components. In the context of disaster management and the analysis of critical infrastructures it is important to understand that critical infrastructures interact with each other, either by direct connection, or due to effects resulting from their spatial proximity. These interactions are called interdependencies and can be classified in different types. Some type definitions for interdependencies are given by Dudenhoefer et al. (2006). They categorize interdependencies as physical – direct linkage, geospatial – infrastructure components at the same location (only 2D!), policy – binding of infrastructure components due to policy or high level decisions as well as, informational – a binding of information flow between infrastructures. The interactions between infrastructures are often very complex and may cause cascading effects which can lead to disasters. Therefore the modeling and development of models that accurately simulate critical infrastructure behavior and their interdependencies and vulnerabilities is important (see Laprie et al. 2007; Klein 2009; Klein et al. 2009; Setola and Geretshuber 2008; Liebich 2009). Other research groups have developed various modeling approaches including agent based modeling (Usov and Beyel 2008; Klein 2009; Klein et al. 2009), effects-based operations modeling (Johnson 2007; Dudenhoefer et al. 2006), mathematical models and models based on risk (Pederson et al. 2006; Setola and Geretshuber 2008). But as mentioned before, in chaotic situations like disasters or emergencies, decision makers should understand the dynamics and dependencies of infrastructures. Failure to understand those dynamics will result in ineffective response, domino effects (see Johnson 2007) and poor coordination between decision makers and emergency actors. Thus, Dudenhoefer et al. (2006) present in their paper the issues of interdependency modeling, simulation, and analysis. They examine the infrastructure interdependency and provide additionally some formalism for these dependencies. Even though it is the most comprehensive work concerning interdependencies and critical infrastructures (to the best of our knowledge), the linkage to objects and topography of the city and its resulting effects to the city are neglected. As a result of the previous discussion an integrated 3D model of heterogeneous utility networks has to meet the following requirements: 1. Utility networks must be embedded into 3D space and need to be integrated with 3D representations of urban entities, i.e. 3D city models. 2. Network components must be represented both by 3D topographic descriptions and by a topological and structural description of all network components with an embedding in 3D space. 3. In general, the model must support both types of hierarchical modeling: the modeling of feature hierarchies (as an aggregation of many features) and the modeling of network hierarchies (as an aggregation of sub networks of the same type of commodity). 4. An integrated model for multi-utility networks must support the simultaneous representation of heterogeneous networks.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
5
5. Special attention has to be paid to the modeling of interdependencies, which establish explicit relations between the network entities of different utility types and can be of spatial, non-spatial, logical, informal, and policy kind (cf. Dudenhoefer et al. 2006). These requirements form the basis for the examination of existing concepts, systems, and the development of a new comprehensive framework in the following sections.
3 Related Models Several models for utility networks on the urban and building scale have been developed in the past. In the following, we will examine the utility models of the Industry Foundation Classes (IFC), the commercial GIS ArcGIS, and the recently presented network core model of the European INSPIRE initiative.
3.1
Modeling Utilities in IFC
The most important standard for data exchange of buildings in the field of architecture and civil engineering are the Industry Foundation Classes (IFC) (Grise et al. 2001). The IFC represent logical building structures, accompanying properties, optional 2D and 3D geometry as well as utilities. The module “Shared building service elements” is defined in the interoperability layer and defines the basic concepts for interoperability between building service domain extensions, such as electrical and control domains or heating, ventilation, air conditioning, etc. This module includes basic type definitions as subtype of IfcTypeProduct, for instance sanitary types, boiler types, etc. and occurrence definitions for flow and distribution systems which specify the placement (position) data, instance specific data, references the type and finally the connectivity with other elements and systems. In order to build up a network the IFC offer two different ways of connectivity. A connection between building service elements may be physical or logical. In general, a logical connection realizes the connection of two components via Ports, whereas a physical connection realizes the connection via a realizing element such as IfcFlowFitting. The connectivity concept of IFC comprises both the physical connection between elements (IfcRelConnectsElements) and the logical connection of building service items on the level of their ports (IfcRelConnectsPorts). An IfcPort can have a placement and a representation and occurs at each connection point between IfcElements. The connectivity is realized through the use of IfcRelConnectsPorts and only compatible elements are allowed to connect to each other. If the optional attribute RealizingElement of IfcRelConnectsPorts is used the connectivity is switched from a logical connectivity to a physical connectivity
6
T. Becker et al.
Fig. 1 Connectivity example between two building service elements (Liebich 2009)
(see Fig. 1). In order to define the flow direction it is possible to use the IfcFlowDirectionEnum, which defines a connection point as a “source of flow”, a “flow sink”, as a “source and sink”, or as “undefined”. Element hierarchies can be expressed by using the IfcRelDecomposes relationship which supports the concept of elements being composed or decomposed. This realizes a whole/part hierarchy which allows traversing from the whole to the parts and vice-versa. Thus, a pump may be the aggregation of IfcFlowFitting, IfcFlowController, and IfcFlowMovingDevice. While it is possible to express feature hierarchies, network hierarchies cannot be represented. This may be due to the fact that IFC is focused on the representation of single buildings (or building complexes). However, it is possible to model the interdependencies between different networks by using the logical connection of IfcRelConnectsPorts (see Liebich 2009, p. 88). In summary, IFC supports the representation of the 3D topography of network elements and the logical connectivity on the level of ports within a graph structure. However, there is no explicit embedding of the graph in 3D space; the location is only given implicitly, if network components have a 3D geometry. The utility network model focuses on structures within sites and does not address networks on the city level interconnecting sites/buildings.
3.2
Modeling Utilities in ArcGIS
In ArcGIS the different types of utility networks are mapped to a core model which is based on geometric networks, being labeled graphs with a spatial embedding. This core model represents the basic structure for all kinds of utilities. A network is constructed from edges and junctions as line and point features. Each real world utility object can be represented as one feature in the network whereas same kinds of
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
7
Main line
features can be represented by a feature class (Bedford 2004; ESRI 2003, 2007; Grise et al. 2001). The geometric part of a utility network (see Fig. 2) is a single graph structure consisting of Edge and Junction elements and can have any number of participating feature classes. The graph is composed of features from one or more feature class in a feature data set (ESRI 2003). It binds together feature classes which form a network and contains all attributes, relationships, and validation rules. The logical network (see Fig. 2) is a special data structure to store the connectivity between features of the network and is implemented by a set of tables. This network is automatically set up and maintained when the geometric network is created or edited. In contrast to ESRI’s street network model all feature classes can take part in the networks as one of the four network types: simple edge, simple junction, complex edge, and complex junction. A simple edge has a one-to-one relation between the feature and the edge element and connects always two junctions. However, a complex edge may connect more than two junctions in order to represent a sequence of edge elements divided by junctions. While they realize a logically connected sequence of
Meter vault Service lateral
Pump
Main line Valve
Tap
Hydrant Geometric network
Valve 2
Valve Tee
Valve 3
Pump Check Valve 1
Hydrant
logical network
Fig. 2 Example of a feature dataset consisting of a geometric and a logical network
8
T. Becker et al.
edges, they geometrically represent a single feature – and in this respect it is a kind of feature hierarchy. Simple junctions have a one-to-one correspondence between the feature and the junction element and are represented only by one point in the network. In order to enhance the feature hierarchy approach a complex junction can be represented as an object in the geometric network and as multiple objects including junctions and edges in the logical network. A pump for example may be represented as a box in the geometric network with one input line and two output lines. However in the logical network this box is represented as a set of valves, tees, pumps (represented by nodes), and pipes (represented by edges); see lower part of Fig. 2. In order to support the flow of commodity a junction feature can have the attribute AncillaryRole, representing its role as source, sink, or neither. To prevent that non-suitable network components are linked to each other, connectivity rules can be specified. The modeling of network hierarchies as well as the modeling of interdependent utility networks within the framework (as it is possible in the transportation network model of ArcGIS which supports multi-modal networks) is not supported yet.
3.3
The Generic Network Model of INSPIRE
The “Network” package of the INSPIRE application schemas (INSPIRE Data Specifications Drafting Team 2009) defines the basic application schema for networks which is extended by additional, domain specific spatial data schemas (INSPIRE Thematic Working Group Transport Networks 2009). The central class is NetworkElement which may be any entity that is relevant for a network. The network package consists of further classes, which are required for modeling networks, such as Network, Link, and Node. A Network is a collection of NetworkElements which is the superclass for elements like Area, Node, and some special classes such as GeneralisedLink, LinkSet and GradeSeparatedCrossing (see Fig. 3). Thus, a simple network may only consist of Nodes and Links, where a Link must be bounded by exactly two nodes. The clear distinction of NetworkElements into point like (Node) and line like (Link) objects and the lack of a feature aggregation schema does not allow for hierarchical decompositions of network components. For example, a point like object cannot consist of other point like or line like objects. The hierarchical modeling of a line like object is supported by the class LinkSet. A hierarchical modeling of a network and the modeling of interdependencies is possible by using the class NetworkConnection. NetworkConnections are also NetworkElements relating two or more arbitrary NetworkElements facilitating the modeling also of hierarchical networks (see INSPIRE Thematic Working Group Transport Networks 2009, p. 93). Since the INSPIRE data model specifications do not make use of 3D geometries, the graph can only be embedded in 2D. Also the INSPIRE core network model does not consider a dual representation of network entities by a 3D topographic and 3D network model.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
9
Fig. 3 Network Application schema of INSPIRE (Adapted from INSPIRE Data Specifications Drafting Team 2009)
4 3D Multi-utility Network Model In this chapter we propose a novel framework for the representation of 3D multi-utility networks which overcomes the limitations of existing modeling approaches discussed in the previous chapter and addresses the requirements for critical infrastructure models as identified in Chap. 2. The entire data model will be given in UML in Chap. 5.
4.1
Conceptual Modeling
We define a utility network as abstraction of the collection of all topographic realworld objects being relevant network components such as pipes, pumps, or switchgear cabinets. The conceptual modeling of a utility network and its components employs the ISO 19100 series of geographic information standards for the modeling of geographic features issued by ISO/TC 211. According to the General Feature Model (GFM) specified in ISO 19109 (ISO/TC 211 2008), geographic features are defined as abstractions of real world objects. The GFM is a metamodel that
10
T. Becker et al.
introduces general concepts for the classification of geographic features and their relations as well as the modeling of spatial and non-spatial attributes and operations. Object oriented modeling principles can be applied in order to create specialization and aggregation hierarchies.
4.1.1
NetworkFeature and FeatureGraph
The basic unit for modeling utility networks within the proposed framework is NetworkFeature. NetworkFeature is an abstract concept which maps topographic network components onto respective GFM feature types. It allows for the modeling of thematic properties as well as the definition of taxonomies and partonomies of network components. Hence, it forms the base for the semantic modeling of concrete network features in various infrastructures such as gas, power, or water supply networks. A main concept of our modeling approach is the dual representation of a NetworkFeature according to which each network component can be represented both by its 3D topography and by means of a complementary graph structure called FeatureGraph. The dual representation addresses the need for both types of representation as discussed in Chap. 2. The modeling of 3D topography is realized in compliance with ISO 19109 as spatial aspect of a NetworkFeature. The value domain for spatial attributes is defined by the Spatial Schema specified in ISO 19107 (Herring 2001) which allows for describing the geometry of a NetworkFeature in up to three dimensions. In addition to its 3D geospatial representation, each network component is mapped by FeatureGraph onto a separate graph structure representing its functional, structural, and topological aspects. This concept differs substantially from previous modeling approaches which usually map the entire utility network onto a single topological network graph derived from a classification of network components into point-like and line-like objects. For example, pipes within a water supply infrastructure are usually given as line-like features and thus mapped onto edges. A T-fitting element is consequently to be mapped onto a node at the intersection of its connected pipes. Functional or structural aspects of the T-fitting are not taken into account. For example, its pipe-connecting ends could also be represented as individual edges, especially if they have a considerable geometric extent or in order to model structural changes such as differing pipe diameters. However, existing approaches lack the possibility to map a single network component onto a set of nodes and edges. In contrast, the proposed FeatureGraph explicitly allows for a graph-based representation of each NetworkFeature. The resulting graph structure follows the general principles of graph theory (Diestel 2005) and has clear semantics. We distinguish two types of nodes: exterior and interior nodes. An exterior node represents a topological connection point where other network components may be attached. Interior nodes are used to model internal structural, physical, or logical aspects of the network component. For example, an interior node may represent the
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
11
narrowing of a water pipe which results in changes of flow speed and pressure. In contrast to exterior nodes, no other network component may be topologically connected to an interior node. In order to link a pair of nodes within the graph structure of a NetworkFeature, a special type of edge called InteriorFeatureLink is introduced which is only allowed to relate two nodes belonging to the same FeatureGraph instance. Figure 4 exemplifies two valid FeatureGraph representations for a T-fitting element. The first alternative results from a functional description of the T-fitting and represents its pipe-connecting ends as individual edges. Each connection point is explicitly marked by an exterior node. An interior node is added where the two axis of the T-fitting meet. The second alternative maps the entire T-fitting to a single exterior node which is the minimum possible FeatureGraph representation. Modeling a single InteriorFeatureLink is not allowed because an edge has always to be bounded by exactly two nodes. In order to support sophisticated graph-based analyses and simulations, both nodes and edges may carry additional attributes, e.g. to model weights or the FlowControl of a NetworkFeature. Examples for FlowControl are the on/off state of a switch within an electrical circuit or the gradual impact of a valve on the flow of water. Furthermore, the exterior nodes of the FeatureGraph may denote a ConnectionSignature. Only those network components having an identical or compatible ConnectionSignature are allowed to connect. A ConnectionSignature is to be seen as set of connectivity constraints addressing arbitrary aspects of a NetworkFeature such as functional, physical, logical, or even geometric properties. For example, the exterior nodes of a T-fitting could define a certain pipe diameter as
Alternative A:
Legend FeatureGraph
Node (type: exterior) Node (type: interior)
Alternative B:
InteriorFeatureLink NetworkFeature
FeatureGraph
Fig. 4 Two alternative FeatureGraph representations for the same object
12
T. Becker et al.
required connection signature for connecting elements. Both FlowControl and ConnectionSignature are abstract concepts which have to be specified within the context of a concrete utility network model. Additionally, each FeatureGraph can have a geometric embedding in 3D space which allows for 3D analyses of the FeatureGraph instances and introduces metric information such as edge lengths into the graph. Due to the semantic differentiation of nodes and edges and the possibility to model attributes, the resulting graph can be classified as both typed and attributed. This requires the conceptual modeling of nodes and edges as semantic objects. Consequently, the topological primitives TP_Node and TP_Edge specified by ISO 19107 are infeasible for their representation. Nodes and edges are rather mapped onto two corresponding GFM feature types called Node and Edge. By this means, nodes and edges can be semantically classified and augmented by spatial and nonspatial attributes. The geometric embedding of both Node and Edge is realized as spatial realization association to a GM_Point respectively a GM_Curve primitive. A FeatureGraph is modeled as feature collection of Node and Edge instances.
4.1.2
Network and NetworkGraph
The aggregation of NetworkFeature instances to an entire utility network is called Network. A Network is characterized by a homogeneous type of commodity such as water, electricity, or gas. Analogously to NetworkFeature, a Network employs the concept of dual representation. Whereas its 3D topography is implicitly given by the 3D topography of its components, the graph-based mapping is explicitly modeled as NetworkGraph. A NetworkGraph represents the graph structure of the entire utility network. For this purpose, it links the FeatureGraph instances of the aggregated network features. Thus, a NetworkGraph conceptually is to be seen as graph of graphs. It results from the pair-wise linking of exterior nodes in different FeatureGraph instances being parts of the same Network. For this purpose, a special subtype of Edge is introduced called InterFeatureLink. The following figure depicts two valid excerpts of NetworkGraph representations. For illustration purposes, the connected pipe elements are shown in a detached way. The main purpose of InterFeatureLink is to establish a topological connection between two network features. Since it is derived from Edge, it can additionally be embedded into 3D space. However, a further spatial representation of an InterFeatureLink is not required if both exterior nodes linked by the InterFeatureLink geometrically collapse (see the first alternative of Fig. 5). Network and NetworkGraph are the central concepts within our framework allowing for analyses and simulations of an entire utility network based on its 3D topography and graph-based representation. Both are realized as GFM feature collections.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
Fig. 5 Two different modeling alternatives for a NetworkGraph connecting two FeatureGraphs using an InterFeatureLink
4.1.3
Modeling Hierarchies
Our framework supports hierarchical modeling for both network components and entire utility networks. A component hierarchy allows for the decomposition of a NetworkFeature into its parts which again are components of the utility network. Thus, it represents a consists-of-relation between two or more NetworkFeature instances of the same Network and is conceptually realized through an aggregation association of NetworkFeature with itself. This recursive modeling approach enables hierarchies of arbitrary depth. For example, a switchgear cabinet is a NetworkFeature of a power supply network which provides connectors to attach other network components. At the same time, it is internally built from further devices such as switches controlling the flow of electricity. These internal components are both connected to the switchgear cabinet and to each other, and may themselves consist of further internal devices. Figure 6 sketches this example. For its graph-based representation, a feature hierarchy is simply a set of FeatureGraph instances which have to be topologically connected at their exterior nodes. Again, this is to be seen as a graph of graphs. For linking FeatureGraph instances, the InterFeatureLink has been introduced in the previous section. However, the concept of the InterFeatureLink has to be augmented such that it additionally provides information about whether the network components are connected on the same level or over different levels of the hierarchy. Graph traversal algorithms
Fig. 6 Feature aggregation and use of InterFeatureLinks
can evaluate this information in order to decide whether or not to traverse down a hierarchy. The modeling of hierarchies of utility networks follows the same concepts. A network hierarchy is used to semantically and topologically decompose a Network into sub networks all of which share a homogeneous type of commodity. For example, a gas supply network can be separated into three sub networks for high pressure, medium pressure, and low pressure. However, in order to establish a link between two FeatureGraph representations within different parts of the hierarchy, an InterFeatureLink is infeasible since it may only connect network features within the same Network (cf. previous section). For this reason, a third subtype of Edge called NetworkLink is defined which has to be used to connect the exterior nodes of two FeatureGraph instances when crossing Network borders.
4.1.4
Multi-utility Networks and Interdependencies
In contrast to the existing modeling approaches introduced in Chap. 3, the proposed model explicitly facilitates the integration of multiple utility networks with heterogeneous type of commodity. Each utility network is modeled as separate instance of Network following the general concepts introduced in the previous sections. As shown in Chap. 2, interdependencies between infrastructures may result from various reasons such as physical linkage, geospatial adjacency or closeness, or policy. The different types of interdependencies can be introduced into our model through the concept of dual representation and, thus, are available for cross-network simulations and analyses. First, geospatial effects can be implicitly evaluated based on the 3D topography representations of both network features and networks. Second, interdependencies can be made explicit within the graph-based
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
15
representation of the multi-utility network as additional link between FeatureGraph instances belonging to different utility networks. Conceptually, this link is modeled as NetworkLink. Since NetworkLink is realized as GFM feature type, it may carry arbitrary further spatial and non-spatial properties. By this means, a NetworkLink can be augmented by additional information in order to model a specific type of interdependency such as a physical, informational, or policybased interdependency.
5 Mapping to a CityGML Application Domain Extension The integration of utility network models into their 3D urban context in order to capture their mutual impact on urban objects has been identified a crucial requirement for simulations and emergency studies in the field of disaster management (cf. Chap. 2). Semantic 3D city models provide the corresponding integration platform. CityGML (Gr€oger et al. 2008) is an international standard for the representation and exchange of virtual 3D city and landscape models issued by the Open Geospatial Consortium (OGC). CityGML defines an Urban Information Model which represents the semantics and ontological structure of the most relevant topographic objects in cities and regional models in addition to their 3D geometry, topology and appearance information. The conceptual model of CityGML is based on the ISO 19100 standards family and is implemented as an application schema for OGC’s Geography Markup Language (GML 3.1.1) (Cox et al. 2004). CityGML has been designed as a universal topographic information model that defines the feature classes and attributes which are useful for a broad range of applications. It provides thematic models for the representation of buildings, digital terrain models, city furniture, land use, water body, and transportation, etc. For extra information to be modeled and exchanged which is not covered by the thematic models CityGML offers an extension mechanism called Application Domain Extensions (ADE). An ADE specifies a systematic extension of the CityGML data model comprising the introduction of new properties to existing CityGML classes as well as the definition of new feature types or entire conceptual models based on the general concepts of CityGML. In order to embed the 3D multi-utility network model into the context of a 3D city model and to enrich CityGML by the possibility to represent utility networks, we have mapped our conceptual model onto a CityGML ADE called UtilityNetworkADE. Figure 7 illustrates the structure of the ADE by means of a UML package diagram. The proposed conceptual model for 3D multi-utility networks is contained in the core package NetworkCore. It has a dependency relation to CityGML and to the GML3 geometry model which implements the ISO 19107 standard and is used for modeling the 3D topography of network features. Based on the abstract concepts of the NetworkCore package, further concrete packages for different types of utility networks can be implemented such as GasNetwork or FreshWaterNetwork.
Common types of network features which can be reused within these packages are grouped into NetworkComponents. Future steps will include the specification of these packages. Finally, Fig. 8 shows the 3D multi-utility network model as UML class diagram. The class names follow the names of the respective concept they implement as introduced in Chap. 4. Prefixes are used to denote both CityGML and GML classes whereas the stereotypes <> and <> indicate the corresponding general concepts from ISO 19109 and 19107. The abstract base class _NetworkFeature for modeling network components is derived from the thematic CityGML root class core::_CityObject. First, by these means the UtilityNetworkADE is embedded into the CityGML data model. Second, the general modeling concepts of CityGML for the representation of topographic objects also apply to _NetworkFeature. An entire utility network is represented by the class Network as an aggregation of _NetworkFeature objects and is realized as gml::_FeatureCollection. The proposed UtilityNetworkADE has already been successfully employed by Hijazi et al. (2010) for mapping interior utility structures modeled in IFC to our conceptual framework without information loss. For this purpose concrete network feature classes based on the NetworkCore package have been defined.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies <> core::_CityObject
Constraints: 1. Each node must belong to a different FeatureGraph 2. Each node type must be exterior 3. The connectionSignature of both nodes must be compatible / identical 4. Both nodes must belong to the same Network
Constraints: 1. Each node must belong to a different FeatureGraph 2. Each node type must be exterior 3. The connectionSignature of both nodes must be compatible / identical 4. Each node must belong to a different Network
Fig. 8 UML class diagram of the UtilityNeworkADE core model
6 Conclusions and Outlook Comprehensive analyses of critical infrastructure require the integrated and simultaneous consideration of multiple heterogeneous utility networks within a common framework. Only by these means mutual dependencies between infrastructures can be evaluated that may cause cascading effects across different networks. A key prerequisite for corresponding network models is the possibility to link critical infrastructures in order to denote interdependencies explicitly. Furthermore, the model must support geospatial analyses in order to determine the implicit interdependencies based on spatial relations like proximity between network components within the same or different infrastructures. For example, the burst of a water
18
T. Becker et al.
pipe may cause damage to nearby or underlying components of a power supply network. Such geospatial analyses require the embedding of network structures into 3D space as well as the 3D topographic representation of network components in addition to a graph-based model. Moreover, the topographic representation allows for the integration of network components into their 3D urban context in order to capture the mutual influence of urban objects. None of the existing models for utility networks examined in Chap. 3 supports all of these aspects. For this reason, in Chap. 4 of this paper we have presented a novel framework for the integrated 3D modeling of critical infrastructures which meets the requirements. Its fundamental concept of dual representation facilities the representation of a utility network component both by its 3D topography and by a complementary graph structure which can be embedded into 3D space. In contrast to other approaches, this graph structure is not derived from a classification of network components into either point-like or line-like objects. We rather employ a stronger concept which allows the mapping of each component onto its own separate graph structure in order to be able to model further structural, physical, or logical aspects. The graph representation of the entire utility network results from topologically connecting these componentbased graphs. The modeling of hierarchies of arbitrary depth is supported on the level of both single network objects and entire utility networks. Mutual dependencies between infrastructures can be introduced as further edges between the graph representations of heterogeneous networks. Finally, we have mapped the proposed conceptual model onto a CityGML Application Domain Extension called UtilityNetworkADE in order to integrate the utility networks with 3D city models (cf. Chap. 5). The proposed framework forms a common core for multi-utility simulations and analysis of interdependent critical infrastructures. As it is a superset of the utility network models examined in Chap. 3, datasets represented according to these models can be converted into the new framework without information loss. As for future work, we will show how existing datasets modeled according to these approaches can be mapped onto our framework. For this purpose, we will augment the developed core model of the UtilityNetworkADE with packages for concrete network objects of the different types of utilities such as water and gas pipes, cables, valves, pumps, and switchgear cabinets. Moreover, we will further investigate different types of network interdependencies, e.g. policy-based or informational, as well as their modeling requirements in order to map them onto the abstract concepts of our framework. It is planned to bring the UtilityNetworkADE into the future revision process of CityGML in order to make it an official module of this international standard. Acknowledgements The presented work was mainly carried out within the collaboration project “SIMKAS 3D” funded by the Federal Ministry of Education and Research of Germany. Additionally, we would like to thank the modeling group of the Special Interest Group 3D of the German National Spatial Data Infrastructure (GDI-DE) for the cooperation and fruitful discussions. We also thank Hartmut Lehmann for his help with the illustrations.
Integrated 3D Modeling of Multi-utility Networks and Their Interdependencies
19
References T. Becker, C. Nagel, T. H. Kolbe (2010): UtilityNetworkADE – Core Model. Draft version. Online available at http://www.citygmlwiki.org/index.php/CityGML_UtilityNetworkADE, last access 7. 5. 2010. M. Bedford (2004): GIS for water management in Europe. ESRI Press, Redlands, CA. S. Cox, P. Daisy, R. Lake, C. Portele, A. Whiteside (2004): OpenGIS Geography Markup Language (GML) Implementation Specification V3.1.0, OGC Doc. No. 03-105r1. R. Diestel (2005): Graph theory. 3rd edition, Series on Graduate Texts in Mathematics 173, Springer, Berlin. D. Dudenhoefer, M. Permann, M. Manic (2006): CIMS: A Framework for Infrastructure Interdependency Modeling and Analysis. In: L. F. Perrone, F. P. Wieland, J. Liu, B. G. Lawson, D. M. Nicol, R. M. Fujimoto (eds.), Proceedings of the 38th Conference on Winter Simulation, Monterey, CA. ESRI (2003): ArcGIS Water Utility Data Model. Published by Environmental Systems Research Institute, Redlands, CA. Online available at http://www.downloads2.esri.com/resources/ datamodels/ArcGISWaterUtilityDataModel.pdf, last access 13. 4. 2010. ESRI (2007): GIS Technology for Water, Wastewater, and Storm Water Utilities. Published by Environmental Systems Research Institute. Online available at www.esri.com/library/ brochures/pdfs/water-wastewater.pdf. S. Grise, E. Idolyantes, E. Brinton, B. Booth, M. Zeiler (2001): Water Utilities. ArcGIS™ Data Models. Environmental Systems Research Institute. http://www.downloads2.esri.com/ resources/datamodels/ArcGIS_Water_Utilities.zip, last access 13. 4. 2010. G. Gr€oger, T. H. Kolbe, A. Czerwinski, C. Nagel (2008): OpenGIS City Geography Markup Language (CityGML) Encoding Standard. Version: 1.0.0, OGC Doc. No. 08-007r1, Open Geospatial Consortium. J. Herring (2001): The OpenGIS Abstract Specification. Topic 1: Feature Geometry (ISO 19107 Spatial Schema). Version 5. OGC Doc. No. 01-101. I. Hijazi, M. Ehlers, S. Zlatanova, T. Becker, L. van Berlo (2010): Initial Investigations for Modeling Interior Utilities Within 3D Geo Context: Transforming IFC Interior Utility to CityGML UtilityNetworkADE. In: T. H. Kolbe, G. K€onig, C. Nagel (eds.), Advances in 3D GeoInformation Science, LNG&C Series, Springer, Berlin (this book). INSPIRE Data Specifications Drafting Team (2009): INSPIRE Generic Conceptual Model (D2.5: Generic Conceptual Model, V3.2). Online available at http://www.inspire.jrc.ec.europa.eu/ documents/Data_Specifications/D2.5_v3.2.pdf, last access 13.04.2010. INSPIRE Thematic Working Group Transport Networks (2009): D2.8.I.7 INSPIRE Data Specification on Transport Networks – Guidelines. Online http://www.inspire.jrc.ec.europa.eu/documents/ Data_Specifications/INSPIRE_DataSpecification_TN_v3.0.pdf, last access 13.04.2010. ISO/TC 211 (2008): Geographic Information – Rules for application schema. ISO 19109:2005. International Organization for Standardization (ISO). C. W. Johnson (2007): Analysing the Causes of the Italian and Swiss Blackout, 28th September 2003. In: T. Cant (ed.), Proceedings of the 12th Australian Conference on Safety-Related Programmable Systems (SCS 2007), Adelaide, Australia (30–31 August 2007), Conferences Research and Practice in Information Technology (CRPIT) Vol. 86, pp 21–30. R. Klein (2009): Information Modelling and Simulation in Large Dependent Critical Infrastructures. An Overview on the European Integrated Project IRRIIS. In: Proceedings of the 3rd International Workshop on Critical Information Infrastructures Security, CRITIS 2008, Rome, Italy, October 13–15, 2008, LNCS 5508, Springer, Berlin. R. Klein, E. Rome, C. Beyel, R. Linnemann, W. Reinhardt, A. Usov (2009): Information Modelling and Simulation in Large Interdependent Critical Infrastructures in IRRIIS. In: Proceedings of the 3rd International Workshop on Critical Information Infrastructures Security, CRITIS 2008, Rome, Italy, October 13–15, 2008, LNCS 5508, Springer, Berlin.
20
T. Becker et al.
J. -C. Laprie, K. Kanoun, M. Kaaˆniche (2007): Modelling Interdependencies Between the Electricity and Information Infrastructures. In: Proceedings of the Computer Safety, Reliability, and Security. 26th International Conference on SAFECOMP 2007, Nuremberg, Germany, September 18–21, 2007, LNCS 4680, Springer, Berlin. T. Liebich (2009): IFC 2x Edition 3. Model Implementation Guide. Version 2.0. AEC3 Ltd. Online from http://www.iai-tech.org, last access 13. 4. 2010. B. Meehan (2007): Empowering electric and gas utilities with GIS. Series on Case Studies in GIS, ESRI Press, Redlands, CA. P. Pederson, D. Dudenhoefer, S. Hartley, M. Permann (2006): Critical Infrastructure Interdependency Modeling. A Survey of U.S. and International Research. Published by Idaho National Laboratory, US Department of Energy (INL/EXT-06-11464). R. Setola, S. Geretshuber (eds.) (2008): Proceedings of the 3rd International Workshop on Critical Information Infrastructures Security, CRITIS 2008, Rome, Italy, October 13–15, 2008, LNCS 5508, Springer, Berlin. W. J. Tolone, D. Wilson, A. Raja, W. Xiang, H. Hao, S. Phelps, E. W. Johnson (2004): Critical Infrastructure Integration Modeling and Simulation. In: Proceedings of the 2nd Symposium on Intelligence and Security Informatics, ISI 2004, Tucson, AZ, USA, June 10–11, 2004, LNCS 3073, Springer, Berlin. A. Usov, C. Beyel (2008): Simulating Interdependent Critical Infrastructures with SimCIP. In: ECN und European CIIP Newsletter. Online available at http://www.irriis.org/ecn/SimCIP_ Usov_Beyel.pdf, last access 27. 4. 2010.
Modeling Space by Stereographic Rejection W.L. (Pim) Bil
Abstract 3D geo-information analyses topological and metrical relationships between spatial objects. This analysis needs a suitable representation of the threedimensional world. This paper proposes to use the 4D unit sphere as a model. In essence this model is already present in mathematical theories like Lie sphere geometry, Moebius geometry and Geometric Algebra. The forementioned theories use the stereographic projection implicitely to build the model. This paper explicitely uses this geometric transformation to introduce the model as simply as possible following both an intuitive geometric and a formal algebraic self-contained way. The calculation in a CAD-environment of 3D Voronoi cells around given 3D points gives a straightforward example of the topological and metrical capabilities of this model. The addition of geometrical meaningful algebraic operations to the model will increase its computational power.
1 Introduction 1.1
Statement and Significance of the Problem
3D geo-information analyses topological and metrical relationships between spatial objects. A first order analysis is a linear one: planar forms represent the spatial objects and linear algebra describes the relations. This paper proposes a second order approach: the addition of spherical forms to the representation of spatial objects while retaining efficient computations. The stereographic projection is the geometric transformation that does the work. Earlier work described the linearized representation of 3D-spheres on the 4D unit sphere to facilitate geodetic calculations (Bil 1992).
W.L. (Pim) Bil Gemeente Amstelveen, Amstelveen, The Netherlands e-mail: [email protected]
T.H. Kolbe et al. (eds.), Advances in 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, DOI 10.1007/978-3-642-12670-3_2, # Springer-Verlag Berlin Heidelberg 2011
21
22
1.2
W.L. (Pim) Bil
Sources
A representation of the stereographic projection on the unit sphere in terms of homogeneous coordinates was found by Hestenes and Sobczyk in a study of the spinor representation of the conformal group (Hestenes and Sobczyk 1984, Sect. 8.3). For efficient computation in manipulating geometric objects Hestenes et al. developed a unified algebraic framework and mathematical tools called Geometric Algebra (Hestenes et al. 1999). Dorst et al. implemented Geometric Algebra as a high-level language for geometric programming (Dorst et al. 2007). Lie sphere geometry represents points as spheres with radius zero (Blaschke 1929; Cecil 1992). The idea to use stereographic projection for the determination of Voronoi cells from the convex hull is found in Brown (1979). The construction of the Voronoi Diagram in the model is pointed out in Dorst et al. (2007). Ledoux mentioned the problem of using a dynamic Voronoi Diagram in a geographical information system (Ledoux 2008).
1.3
Historic Notes
The use of the stereographic projection to perform spherical calculations and to make maps has a long history. Already the Greek astronomer Hipparchus (180–128 BC) was aware of the projection. Around the first century the Alexandrian Claudius Ptolemaeus wrote on it in the book Planisphaerium. The construction of ancient Greek and medieval arab astrolabes uses its properties. Around the millennium in the Arab world Al-Bı¯ru¯nı¯ applied the stereographic projection to the making of maps. In 1587 the cartographer Gerhard Mercator invented conformality in his mappings of the eastern and western half spheres in stereographic projection. The Jesuit Aguilonius (1566–1617) is the first to use the name stereographic projection in his books on optics (Rosenfeld 1988; Grafarend and Krumm 2006).
1.4
Overview
For a first introduction the standard description of the (conformal) model in the literature on Geometric Algebra is too abstract, defining algebraic operations on coordinate free geometric objects on a null cone in five dimensions. The entrance to the model on the 4D unit sphere by the stereographic projection with just linear algebra seems simpler and because of the spherical symmetry has also an aesthetic appeal. The central thought is the idea to consider 3D linear space to be the stereographic projection of a four-dimensional unit sphere. This elementary introduction to the model is both on an analytic and a synthetic level. In the first part the analysis of drawings stimulates geometric intuition.
Modeling Space by Stereographic Rejection
23
With some concepts from projective and inversive geometry the stereographic projection of points, planes, and real and imaginary spheres is studied. One can look at the figures in two ways: as plane drawings on paper of the stereographic projection of a circle on a line, but also more in general as a mnemonic device showing the properties of the stereographic projection of a sphere on a linear space one dimension lower. In the second part vectors (i.e. coordinates) describe the position of geometric objects in the vector spaces Rn and Rnþ1, and linear algebra deduces the metrical and topological properties of the objects and their relations. In the end the construction of Voronoi cells around points in space exemplifies the use of the model.
2 Mathematical Preliminaries The explanation relies in the first place on the intuitive interpretation of drawings. Therefore this is not a mathematical text, although the goal is to be as precise as possible and to get acquainted with mathematical concepts. In mathematical terms the stereographic projection is an inversion, i.e. a special projective transformation. See for inversive geometrical concepts for instance (Pedoe 1979) and (Brannan et al. 1999). The core of projective geometry is the duality between point and plane, and the crux of inversive geometry is the concept of harmonic conjugacy. Figure 1 illustrates in the plane some inversive concepts to be used. For example the points P1 and I are inverses, i.e. OI OP1 ¼ 1. Indeed the triangles OTP1 and IOT are similar.
T
P3 r p3
P1
pola
1 I O
po
P2
p2
r p1
a pol
lar
Fig. 1 Construction of pole and polar with regard to the unit sphere
24
W.L. (Pim) Bil
OI OT 1 So OT ¼ OP , OI 1 ¼ OP1 , OI OP1 ¼ 1. In the following the inversive 1 concepts pole and polar play a central role. A point P is the pole of a linear space (its polar) with regard to a conic. Recipes for the geometric construction of the polar of a point Pi with regard to the unit sphere are: l
l
l
P1 outside the unit sphere: construct the tangents from P1 to the unit sphere. The polar is the linear space containing the tangent points on the unit sphere P2 inside the unit sphere: consider P2 as bundle of polars. Each polar has a pole. The polar of P2 is the collection of these poles P3 on the unit sphere: the polar is the tangent to P3
To keep the figure readable tangents are only drawn between the pole and the point of tangency. Homogeneous coordinates are suited to describe the duality between point and plane. See for this concept an elementary text on projective geometry, for instance (Ayres 1967). Homogeneous coordinates of a point or plane are the set of numbers that fulfill a homogeneous linear equation. Introduction of extra dimensions (coordinates) makes equations homogeneous. Consider for instance the equation vi au1 þ bu2 ¼ c. With the substitution ui ¼ ;i ¼ 1;2 this equation becomes homov 3 v1 v2 geneous: a þ b ¼ c , av1 þ bv2 cv3 ¼ 0, and after substitution the quadra 2 2 v3 v3 tic equation u1 2 þ u2 2 ¼ 1 becomes vv13 þ vv23 ¼ 1 , v1 2 þ v2 2 v3 2 ¼ 0. If a triple of coordinates ðv1 ; v1 ; v3 Þ fulfils a homogeneous equation, so does the triple ðlv1 ; lv2 ; lv3 Þ; l 2 R. The equivalence class of the relation ðlv1 ; lv2 ; lv3 Þ ðv1 ; v2 ; v3 Þ; l 6¼ 0, with not every vi ¼ 0, constitutes the homogeneous coordinates of a point or plane. The symbolism ~ x2 ¼~ x ~ x ¼ k~ xk2 stems from Geometric Algebra: the square denotes the inner product of a vector with itself and is equal to the square of the length of the vector.
3 Geometric Analysis of the Stereographic Rejection To get a better grasp on concepts such as stereographic projection, pole and polar it is instructive to first study some drawings. The notation Sn signifies the n-dimensional unit sphere in the (n þ 1)-dimensional vector space Rnþ1.
3.1
Points
Consider the south pole of the unit sphere Sn to be a bundle of lines (see Fig. 2). Every vector ~ x in the vector space Rn is on a line in the bundle. This line contains
Modeling Space by Stereographic Rejection
25
Fig. 2 The stereographic x rejection U on Sn of vector ~ in Rn
U
o Sn
Rn
→
x
→
0
∞
another point U of Sn. Point U is called the stereographic rejection1 of ~ x, and ~ x the x on Sn other points of Rnþ1 are on stereographic projection of U.2 Beside the point ~ the line in the bundle through the center of projection and point ~ x in Rn. ~ x is called the stereographic projection of all these other points. The north pole is the stereographic rejection of the origin. The center of projection is a representation of infinity, called the point at infinity and denoted by 1: the greater the distance of a point in Rn to the origin, the closer the stereographic rejection of the point on the unit sphere to the center of projection. 1 0 0 1 ~ ~ 0 0 C B B C In homogeneous coordinates: o ¼ @ 1 A, 1 ¼ @ 1 A. 1 1 Note that the lines on the polar of the center of projection, parallel to Rn, have neither an intersection with Rn nor a second intersection point with Sn.
3.2
Real Spheres
A n-sphere in Rn is stereographically rejected on a (n þ1)-sphere on Sn that is part of a (n þ1)-plane in Rnþ1 (see Fig. 3). The stereographic rejections of points inside the n-sphere are all on the same side of the (n þ1)-plane. This (n þ1)-plane is polar of a point P. Pole P is geometrically determined as the intersection point of all tangent planes to Sn at the rejection of the n-sphere. The stereographic projection of P gives back the center of the n-sphere in Rn. All points outside Sn can be considered as 1
Here rejection is used in the sense of ‘back’ projection. In Geometric Algebra the rejection of a vector has a different meaning: the component complementary to its projection on another vector. 2 For a better symbolic discrimination of the elements in Rnþ1 in stead of the letter X the letter U is used for a general element, and the letter P denotes a pole. Consequently coordinates in Rnþ1 are denoted by ui .
26
W.L. (Pim) Bil
Fig. 3 Stereographic rejection to Sn of a sphere in Rn around m ~
P
U1
Rn
→ x1
→ m
∞
→ x2
U2
Sn
poles, corresponding to polars cutting Sn in (nþ1)-spheres that are stereographic rejections of n-spheres.
3.3
Planes
If point P is on the polar of 1, it can not be the stereographic rejection of a point in Rn, as shown in Sect. 3.1. The center of projection 1 is on the polar. The polar is a (nþ1)-plane and its intersection with Rn a n-plane. Thus pole P dually represents a n-plane. Figure 4 is a two dimensional cross section through the axis of the unit n is the normal vector of the plane. The sphere. Figure 5a is a section through Rn. ~ equation of the plane is ~ n ~ x¼~ n~ n. From the inversive relation, shown also in Fig. 1, follows: k~ nkkl~ nk ¼ 1 , l ¼ ~n12 . 0 1 ~ n So the pole has coordinates @ ~ n2 A . 1 The more the distance of pole P to the origin increases, the more ~ n tends to ~ 0 (Fig. 5b) and in the end the polar will contain the axis of the unit sphere. The normal vector of the plane in Rn will then also be the normal vector of the plane in Rnþ1.
3.4
Position of Pole and Length of Radius
A n-point is the stereographic projection of all poles corresponding to n-spheres around this n-point (see Fig. 6). The greater the radius of the n-sphere, the greater the distance of its corresponding pole to the stereographic rejection of the n-point on Sn. The n-sphere with radius zero corresponds to the stereographic rejection of the n-point on Sn, equal to the pole of the tangent. So all points in Rn, considered as circles with radius zero, are stereographic projected on S.
Modeling Space by Stereographic Rejection
27
p
Fig. 4 Pole P on the polar of 1 dually represents a plane in Rn
Sn →
n
→
Rn
0
2
→ →
n /n
p
∞
Fig. 5 (a) Cross section looking from the north pole. (b) The limiting case: pole P infinitely far from the origin, ~ n becoming ~ 0, polar p containing north and south pole
p
P
a
b Rn
Sn
P p
p →
0
n→
P
→
0
p
p P
Fig. 6 The poles corresponding to spheres around a fixed point with different positive radii
Rn
∞
Sn Rn
∞
3.5
Imaginary Spheres
Thus far points in Rnþ1 on and outside Sn are seen to represent points and spheres in Rn (see Fig. 7). What about points of Rnþ1 inside Sn? Point P is dually defined as
28
W.L. (Pim) Bil pola
r of P
PC–λ
PCm
PCλ
PCμ
P
→
m
Rn
C–λ Cm CλCμ
C–λCm Cλ
Cμ
Sn ∞
Fig. 7 Point P defined as a bundle of (n þ 1)-planes corresponding to a collection of real n-spheres Ci
extra dimension Ua
Rn
→
m C–λ Cm Cλ Cμ
r r
C–λ Cm Cλ
Cμ
Ub
Fig. 8 Intersections, represented in the figure as Ua – Ub, that the n-spheres in the collection shown in Fig. 7, have in common in the extra dimension
a bundle of planes cutting Sn in (n þ 1)-spheres, with the PCi as the poles of these planes, together forming the polar of P. The (n þ 1)-spheres on Sn stereographically project on n-spheres. Embedding Rn in Rnþ1 all the extended n-spheres intersect in points in Rnþ1 at a ~ of P (see Figs. 8 and 9).3 certain distance of the stereographic projection m
3
See also Sect. 4.5.
s
s
sp here
e radius
∞ planes
sitiv
spheres with imaginary radius
iu
po
i
ints)
sph
w
po
sp
re
s
radius ze ith r (po
eres with
ius sphere
th
w
he
3.6
rad
e ti v
o
Fig. 9 Points in Rnþ1 dually represent points, planes and real and imaginary spheres in Rn depending on their position with regard to the unit sphere
29
si
Modeling Space by Stereographic Rejection
ra s w e ith positiv
d
Rnþ1 Representing Spheres in Rn
Summarizing our analysis of the polar representation of spheres in Rn as points in Rnþ1: l l l l l
The center of the stereographic projection represents infinity: 1 Points on the polar of 1represent planes Other points outside the unit sphere represent real spheres Other points on the unit sphere represent points Points inside the unit sphere represent imaginary spheres
4 Algebraic Synthesis of the Stereographic Rejection Practical applications need quantities. In the following sections linear algebra revisits the results found earlier and quantifies the relations between the coordinates of the points in the vector spaces Rn and Rnþ1.
4.1
Pole and Polar
The polar relationship can be expressed in terms of linear algebra as follows. Point A is on the unit sphere, so ~ a~ a ¼ 1 (see Fig. 10). If a point is on the tangent to A, then ~ x~ a is perpendicular to ~ a, i.e. ð~ x~ aÞ ~ a ¼ 0. So ~ x~ a¼~ a~ a ¼ 1. In R2: Let P be the polar of the line AB. P is on the tangent through A, * so ~ p~ a ¼ 1, and P is on the tangent through B, so also p b~ ¼ 1. Let X be ~ another point of the line AB. If ~ x¼~ a þ lðb ~ aÞ; l 2 R then ~ p ~ x¼~ p~ aþ ~ lð~ pb~ p~ aÞ ¼ 1. So the equation of the polar of P is ~ p ~ x ¼ 1.
30
W.L. (Pim) Bil
Fig. 10 Pole P and its polar ~ p ~ x¼1
→ →
p.
p .x >1
x= 1
→→
P
→→
p . x <1
A → → a
.x =
=1
po
→
b.x
la ro
1
→
fP
B
This result generalizes to Rn. If P is the intersection of the tangents to the points Vi, the linear space with equation ~ p ~ x ¼ 1is the polar of P. This polar ~ p ~ x¼1 divides space in two: ~ p ~ x > 1 and ~ p ~ x < 1.
4.2
Points
The line of projection from the south pole has equation (see Fig. 11): !! ! ! ~ ~ ~ x x 0 ~ ð1 lÞ~ x u ; l 2 R: ¼ þl ¼ l unþ1 0 0 1 Now ~ u 2 þ unþ1 2 ¼ 1, so ð1 lÞ2~ x 2 þ l2 ¼ 1 , 2 2~ x2 þ 2 ¼ 1: x 2 2l~ x 1 ¼ 0 , l1 ¼ x2 þ ~ l2 1 þ ~ 2 1 þ~ x2 This gives the south pole, and the other solution is: 2 2~ x2 2 ~ x 1 ¼ : l2 ¼ 2 1 þ~ x2 1 þ~ x2 Using this value gives for the coordinates of the stereographic rejection U of ~ x: 0
2 1 0 1 ~ x 1 2~ x ~ x 1 B C B 1 þ~ 1 þ~ x2 x2 C ~ u C B C B ¼B ¼ C: B C unþ1 @ A @ 1 ~ x2 A ~ x2 1 1 þ~ x2 1 þ~ x2
Modeling Space by Stereographic Rejection
31
Fig. 11 The stereographic rejection in coordinates
Sn : → u 2 + u2n+1 = 1
un+1
Rn
→
x
→
u 1 ∞
Fig. 12 The vector representation of the stereographic projection
→ u un+1
un+1 → x
Rn
→
u
1
Sn ∞
In homogeneous coordinates this is4: 1 1 0 2~ x ~ x B C B 1 þ~ x2 C 1 ~ x2 C C B B B C C B C ¼ Sð~ x2 C B xÞ; B 1 ~ 2 B C C B B C 2 A 2 @ 1 þ~ x @ 1 þ~ x A 1 2 0
(1)
in which the function S : Rn ! Rnþ2 defined by (1) is the stereographic rejection expressed in homogeneous coordinates. ~ u See Fig. 12, the stereographic projection of 2 Rnþ1 on Rn is: unþ1
See Sect. 2: substitute ui ¼
4
vi and scale to get a suitable representation. vnþ2
32
W.L. (Pim) Bil
2 2~ x ~ x ~ u 1 þ~ x2 1 þ~ x2 ~ ¼ x¼ ¼ : 2 2 unþ1 þ 1 1 ~ x þ1 1 þ~ x2 1 þ~ x2
4.3
(2)
Real Spheres
~Þ2 ¼ r2 . In Rn the equation of a sphere around a point M is ð~ xm ~ u Using (2), substitution of ~ x¼ gives: 1 þ unþ1 2 ~ ~ 2~ m~ u u u2 ~ ¼ r2 , ~2 ¼ r 2 , m þm 1 þ unþ1 ð1 þ unþ1 Þ2 1 þ unþ1 1 unþ1 2 2~ m~ u ~2 ¼ r 2 , þm ð1 þ unþ1 Þð1 þ unþ1 Þ 1 þ unþ1 ð1 þ unþ1 Þð1 unþ1 Þ 2~ m~ u ~2 ¼ r 2 , þm ð1 þ unþ1 Þð1 þ unþ1 Þ 1 þ unþ1 2 ~ 1 r 2 unþ1 ¼ ~ m2 1 þ r 2 , 2~ m~ uþ m
(3)
~2 r2 1 m 2~ m~ u ~2 ¼ m ~ m ~2R þ unþ1 ¼ 1; with m ~ m2 1 þ r 2 ~ m2 1 þ r 2
(4)
1. According to Sect. 4 we read off from this equation of the and ~ u 2 þ u2 nþ1 ¼ 0 1 2~ m B C m2 1 þ r 2 C B ~ plane in Rnþ1 that B 2 C is pole of it. @ m ~ 1 r2 A ~ m2 1 þ r 2 The stereographic projection of this pole on Rn gives (2): 2~ m 2 ~ u * ~ m 1 þ r 2 ¼ m: ¼ 2 1 þ unþ1 ~ 1 r2 þ ~ m m2 1 þ r 2 ~ m2 1 þ r 2 ~Þ2 < r 2 , in the same way: Starting from the equation ð~ xm 2 ~2 1 þ r 2 : ~ 1 r2 unþ1 < m 2~ m~ uþ m
(5)
Equation (5) is always valid, because unþ1 þ 1 0. However, the sign of the equation corresponding to (4) is depending on the values of the parameters in the ~2 1 þ r 2 . expression m
Modeling Space by Stereographic Rejection
4.4
33
Planes
Consider a plane in Rn with normal vector ~ n:~ n ~ x¼~ n 2 . The equation of the plane nþ1 in R containing stereographic rejected points is: ~ ~ u n ¼~ n2 , ~ n ~ x~ n 2 xnþ1 ¼ ~ n2 , 2 ~ u unþ1 ¼ 1: ~ n 1 þ unþ1 0 1 ! ~ n ~ 0 2 is on the (n þ 1)-plane. The pole is @ ~ n A, and the center of projection 1 1 ~ n
4.5
Position of Pole and Length of Radius
It has been made clear the position of the pole depends on the radius of the n-sphere (see Fig. 6). The homogeneous coordinates of the pole of the (nþ1)-plane that contains the stereographic rejection are deduced from (4): 1 0 2~ m 1 0 2 2 C B ~ 2~ m B m 1 þr C C C B 2 B ~2 1 r 2 C @ m ~ 1 r2 A B m C B @ ~ m2 1 þ r 2 A ~ m2 1 þ r 2 1 0
~ m
1
1 0 B ~ 2C 0 C 1 B1 m ~ 1 C B C B B 2 C r 2 @ 1 A ¼ Sðm ~Þ r2 1: C 2 B 2 @1 þ m 1 ~2 A 2
(6)
In (6) the equivalence class of homogeneous coordinates of the pole is represented by the coordinate tuple that encodes the stereographic rejection of the midpoint [see (1)]. This way the homogeneous vector of the pole, a (n þ 2)-vector, carries the quantitative information about the corresponding n-sphere. Because on the model no metric and geometric algebra operations are defined, it is not possible to exploit this result here.
4.6
Imaginary Spheres
Having found an algebraic relation between points on Sn and points in Rn, and between points outside Sn and n-planes and n-spheres with positive radius, motivated by the geometric analysis in Sect. 3.5 the next search is for the algebraic
34
W.L. (Pim) Bil
Fig. 13 The simplest case: an imaginary 1-sphere (point pair) UaUb at imaginary distance r from M is part of the imaginary 2-sphere Cl with midpoint L and radius R containing the 1-sphere (point pair) x1 x2 on the line n
extra dimension
R x1
n
L
r M
m-l Cl
Ua
x2
n
r Ub
relationship between points inside Sn and n-spheres with an imaginary radius (see Fig. 9). Consider the line n in R1 as simplest case (see Figs. 8 and 13). Embed this line in a space one dimension higher. If a midpoint M is given, determine the points with orthogonal distance r to M: the two-sphere with imaginary radius r. For all other point on 2D line n: draw the two-sphere (circle) containing the imaginary points Ua and Ub. This means on line n there are points x1 and x2 fulfilling the equation: ðm xÞ2 ¼ R2 ¼ ðm lÞ2 þ r 2 .5 Take such a one-sphere with point L, having coordinate value l, as center. According to (3) the equation of the two-line that is the stereographic rejection of the one-sphere is: 2lu1 þ ððl2 ðl mÞ2 þ r2 Þ 1Þu2 ¼ ðl mÞ2 þ r 2 l2 1:
(7)
The intersection point of this two-line with the two-line that is corresponding with the two-sphere through the imaginary points Ua and Ub with center l gives 2m 1 m2 r2 and u ¼ . This expression is indeas coordinates u1 ¼ 2 1 þ m2 þ r2 1 þ m2 þ r2 pendent of l. Repeat the construction in Rn by considering the points related to m ~ by * lÞ2 þ r 2 fulfilling the equation equivalent to (7): the equation: ð~ m ~ xÞ2 ¼ ðm ~ ~Þ2 þ r 2 Þ 1Þunþ1 ¼ ðð~ ~Þ2 þ r2 Þ2 ~ 2~ l~ u þ ð~ l 2 ð~ lm lm l 2 1:
(8)
0
1 2~ m B1 þ m ~2 þ r2 C C is true, for P fulfils (7), The conjecture all planes contain P ¼ B @1 m ~2 r2 A ~2 þ r2 1þm * n independent of l . So if a sphere Ci in R cuts the imaginary sphere with center M, P is on the plane in Rnþ1 that contains the stereographic rejection of Ci (see also 5
Historic aside: this is in fact the ancient construction of the mean proportional from Proposition 13 of book VI in The Elements of Euclid.
Modeling Space by Stereographic Rejection
35
Figs. 7 and 8). The representant of the homogeneous coordinates of pole P [compare this with (6)] is: 1 0 2~ m 1 0 B 1þm 2~ m ~2 þ r 2 C C B C B B C ~2 r 2 C @ 1 m ~2 r 2 A B 1m C B 2 @ 1þm ~ þ r2 A ~2 þ r 2 1þm 1 0
~ m
1
1 0 B ~ 2C 0 C 1 B1 m ~ 1 C C B B ~Þ ðir Þ2 1 B 2 C þ r2 @ 1 A ¼ Sðm C 2 B 2 @1 þ m 1 ~2 A 2 (nþ1)-point P lies inside Sn. Indeed, given the fact that ~2 þ r2 Þ2 ð1 m ~2 r 2 Þ2 ¼ ð2~ ð1 þ m m2 þ 2r 2 Þð1 þ 1Þ ¼ 4~ m2 þ 4r 2 ; ~2 r2 Þ2 þ 4r2 ¼ ð1 þ m ~2 þ r2 Þ2 . it follows that 4~ m2 þ ð1 m 2 2 ~2 r 2 2~ m 1m So, because 4r2 > 0 , P2 ¼ þ < 1. ~2 þ r 2 ~2 þ r2 1þm 1þm ~, for from (2) follows: Again this pole P is projected on m 2~ m ~2 þ r 2 ¼ m 1þm ~: ~2 r2 1m 1 ~2 þ r2 1þm
5 Example: Spatial Partitioning by Voronoi Cells 5.1
Introduction
The calculation of a partition of nD with the help of the topological and metrical properties of its rejection on the (nþ1)D unit sphere shows the model at work. In a number of random points ~ p 2 S Rn a quantity is measured. A natural p. approach is to attribute to a point ~ q 2 Rn the measurement of the nearest point ~ The Voronoi cell is the region of points that are closest to ~ p. The mathematical definition of the Voronoi cell is: Vp ¼ f~ x 2 Rn j8~ q 2 S : jj~ x~ p jj jj~ x~ qjjg:
36
5.2
W.L. (Pim) Bil
Analysis of the Voronoi Diagram in Two Dimensions
A planar analysis shows this to be a spherical construction. The black points are randomly given (see Fig. 14). The edges of the Voronoi cells around the black points consist of points with equal distance to two nearest black points. The branch points (open circles in the drawing) consist of points with equal distance to three nearest black points. That is to say the branch point is the center of the circle to the three nearest neighbouring black points. These three black points form triangle with the property that no other black point lies inside the circumcircle, a Delaunay triangle. The plane is triangulated. The edges connecting the midpoints of the triangles around a black point make up the convex Voronoi cell (Fig. 15).
Fig. 14 Voronoi Diagram (of white points) and Delaunay triangulation (of black points)
Fig. 15 Detail around a black given point. Five Delaunay triangles meet in this point. The circumcenters of the triangles are the vertices of the convex Voronoi cell around the point
Modeling Space by Stereographic Rejection
5.3
37
The 2D Voronoi Diagram on the 3D Unit Sphere
See the scheme in Fig. 16. The stereographic rejections of the given points are on the 3D unit sphere. A Delaunay triangle of these points has the topological property that its circumcircle does not contain another given point. This property is equivalent to the topological property on the unit sphere that all stereographic rejections of the given points lie on the same side of the plane formed by the three points. In other words the Delaunay triangulation in the plane corresponds to the convex hull on the 3D unit sphere. The pole of the plane formed by the three points on the 3D sphere gives the stereographic rejection of the center of the circumcircle of these points. The mouthful formulation of the conclusion of the plane analysis is: the Voronoi cell of a given point is the convex hull of the stereographic projection of the poles of the facets around the stereographic rejection of the given point of the convex hull of the stereographic rejection of all given points.
5.4
Calculation of the 3D Voronoi Diagram
The abovementioned formulation is valid for the creation of a Voronoi Diagram in all dimensions. The following focuses on the construction in R3. The algorithm for the construction of Voronoi cells in R3 is: 1. Input random points in space 2. Stereographically reject these points on the 4D unit sphere 3. Calculate the convex hull of these points in 4D. In non degenerate cases the convex hull consists of n facets of four vertices. The number n depends on the configuration of the given points in space 4
Sn 2
3 2 1
Rn
5
1
1
5 4
4
3 1
5
1
5
3 2 2 4
3 2
3
3 4
∞
4
Fig. 16 The relation between the Voronoi and Delaunay tessellation, both in Rn and in Rnþ1
38
W.L. (Pim) Bil
4. Calculate the poles of the n planes incident with these facets 5. The stereographic projections of these n poles are the midpoints of the circumspheres of four given points (tetraeders), building blocks of the Voronoi cell around a given point in 3D 6. Calculate the convex hull of the stereographic projection of these n points around the given point in 3D. This gives the 3D facets of the Voronoi cell around a given 3D point
5.5
Neighbouring 3D Voronoi Cells
Neigbouring 3D Voronoi cells share a 2D facet. To find the connection of a Voronoi cell, first compare for all facets the number of vertices between all other calculated facets. In case of equality next compare the equality of the vertices of the facet with equal number of vertices. The order of the vertices of the matching facet is reversed. The connectivity of the Voronoi cells follows.
5.6
Moving Points
See Fig. 17 and also Sect. 4.1. If the given points move, so do their stereographic rejections, the facets/polars they are part of, the corresponding poles and the 3D Voronoi vertices. Sometimes the topology of the configuration changes. Having P1
P3
P2
U2
U3
U4
U1
Fig. 17 Check of consistency on S1: the vertices U1, U2, U3 and U4, on the polars of P1 and P3, disturb the convex hull structure
P4 U5 P5
Modeling Space by Stereographic Rejection
39
available the positions of the moving points in real time, the following test checks the consistency of the configuration. Given the fact the configuration must be a convex hull, no point on the unit sphere should lie outside the polars formed by the facets of this hull. So for all poles all coordinate vectors of points Ui on the unit sphere ought to satisfy either the equations ~ pj ~ ui 1, or ~ pj ~ ui 1. For example in Fig. 17. the movements of points U2 and U3 have distorted the original convex hull U1-U2-U3-U4-U5-U1. For pole P1 the sign of points U3 is different from U4 and U5, and for pole P3 the sign of U2 is different from the points U1 and U5. In this case not only the position of the points and poles has to be updated, but also (part of) the topology.
6 Implementation As proof of principle this theory has been implemented in software.
6.1
CAD
Given input is an ASCII-file with coordinates of points. The given points are then represented in a 3D Microstation designfile. Visual Basic for Applications for Microstation is the programming environment. The coordinates are read from the designfile and stored in the array of vertex structures that is kept in memory to speed up calculations. All coordinates are translated and scaled towards the 3D unit sphere. In this process the maximum distance of the vertices to the origin is determined. After the coordinates of the given points are read the 3D coordinates of an icosahedron are added to enclose all the given points. The 12 vertices ð0; tRmax ; Rmax Þ; ð tRmax ;0; Rmax Þ and ð Rmax ; of the icosahedron are: pffiffi 5þ1 tRmax ;0Þ; with t ¼ 2 the divine proportion (Coxeter 1969). The addition of the south pole of the 4D unit sphere to the stereographically rejected 3D points closes the set of 4D points on the sphere. Pointers from within the vertex structures address the Voronoi coordinates (derived from the data in the array of facet structures).
6.2
Convex Hull Software
An introduction into the convex hull computation is given in (de Berg et al. 1998). In the application the calculations of the convex hull are done using QHull. Information on QHull can be found on http://www.qhull.org/. The input for the qconvex executable is formed by writing 4D or 3D coordinates from the Microstation 3D designfile to an ASCII-file. After execution of the command the outputted ASCII-file is read. The following command lines were used:
40
W.L. (Pim) Bil
Fig. 18 CAD drawing of a Voronoi cell around a 3D point
1. qconvex o to calculate the 3D and 4D convex hulls. It outputs on the first line the dimension, on the second line the number of vertices, facets and ridges, then lines with vertex coordinates and finally the facet lines. Each facet line starts with the number of vertices. The vertex indices follow. In general for the convex hull on the 4D unit sphere the facets are simplices and made up by four vertices, corresponding with the 3D counterpart: four vertices determine a sphere in 3D. If more vertices are encountered this signals a degenerate configuration of the points and calculation measures can be taken, for instance by a little shift of a point concerned. 2. qconvex FN to list the number of facets on the first line and the neighbouring facet indices for each facet on the next lines. The line starts with the number of neighbouring facets (Fig. 18).
7 Conclusion, Caveat and Developments The paper proposes to model space on the four-dimensional unit sphere, described by five homogeneous coordinates. Space is considered to be the stereographic projection of the 4D unit sphere. Points on the 4D unit sphere thus represent 3D points, i.e. spheres with radius zero. The 4D center of projection is the representation of the point at infinity and on its polar lie the 4D points that represent 3D planes. Points outside the 4D unit sphere dually represent 3D spheres with positive radius, and 4D points inside represent 3D spheres with imaginary radius, which are given a clear geometric interpretation. The expression of the 4D points in 5D homogeneous coordinates contains quantitative information on the center and radius of the dually represented 3D spheres and planes. The first part of the paper introduces the concepts in an informal way analyzing the geometry in an intuitive manner. Next the conjectures are deduced in explicit formulae of elementary linear algebra. As a straightforward example, useful in geographical information systems, Voronoi cells around given points in space are determined from the convex hull in the model.
Modeling Space by Stereographic Rejection
41
As a proof of principle the theory has been implemented in software. Because the main objective of the author is to introduce the model, and because he is not fully aware of the state-of-the-art of the construction of Voronoi Diagrams and use of data structures, the software was not developed to the point it processes dynamic input. Nevertheless algorithms to calculate the connectivity of the Voronoi Diagram and to validate the configuration were indicated. Microstation offers the possibility for event-driven programming. So it is possible to monitor the position of the given points and calculate the stereographic rejections of the given points and values depending on them, in real time. The validation test of the configuration of the Voronoi cells could trigger the recalculation of the topology while running a program. Although, as we have seen in the example of the calculation of the Voronoi Diagram, spheres and planes are represented on an equal footing in the model and we have linear algebra at our disposal, the model is not yet fully operational. At present the obtained methods are of limited use, for geometric meaningful algebraic operations are still lacking. To have the model at one’s disposal without operations defined on it, is like having hardware without software. Now that 3D space is beamed up along the rays of the stereographic projection to the four-dimensional unit sphere “one must so to speak throw away the ladder, after he has climbed up on it”6 and wander around in this copy of the world. Geometric Algebra provides a unified coordinate-free algebraic framework for both multidimensional geometric objects and geometric operations in this model. The conformal model of Geometric Algebra goes one dimension up and models the 4D unit sphere in 5D as a null cone, isometrically embedding 3D. As an algebra Geometric Algebra is closed, i.e. every geometric product of (geometric) elements gives another element in the algebra. A main advantage is that only one formula is sufficient to describe a geometric situation. No “special case” processing is needed. For instance two spheres will always intersect. Imaginary spheres have, as is shown in this paper, a clear geometric interpretation. To learn about the foundation of Geometric Algebra see (Hestenes and Sobczyk 1984) and about the conformal model see for instance (Hestenes et al. 1999), (Dorst et al. 2007), (Perwass 2008). Some communities have adapted the conformal model of Geometric Algebra as a computational tool. New applications of the model are frequently a topic at the International Workshops on Computer Graphics, Vision and Mathematics (GraVisMa) and the conferences on Applied Geometric Algebras in Computer Science and Engineering (AGACSE). It remains to be seen whether or not the GA conformal model of Euclidean 3D geometry has killer applications in 3D geo-information.
6
Satz 6.54 from the Tractatus logico-philosophicus of Ludwig Wittgenstein.
42
W.L. (Pim) Bil
References Ayres, F. (1967) Theory and Problems of Projective Geometry, Schaum’s Outline Series, McGraw-Hill, New York Bil, W.L. (1992) Sectie en Projectie, Nederlands Geodetisch Tijdschrift Geodesia, 10:405–411 Blaschke, W. (1929) Vorlesungen € uber Differentialgeometrie III, Springer, Berlin Brannan, D.A., Matthew, F.E., Gray, J. (1999) Geometry, Cambridge University Press, Cambridge Brown, K.Q. (1979) Voronoi diagrams from convex hulls, Information Processing Letters, 9:223–228 Cecil, T. (1992) Lie Sphere Geometry, Springer, New York Coxeter, H.S.M. (1969) Introduction to Geometry: De Divina Proportione, John Wiley & Sons, New York de Berg, M., van Kreveld, M., Overmars, M. and Schwarzkopf, O. (1998) Computational Geometry: Algorithms and Applications, 2nd edn, Springer, Berlin, Germany Dorst, L., Fontijne, D. Mann, S. (2007) Geometric Algebra for Computer Science, An Object Oriented Approach to Geometry, Morgan Kaufmann, Massachutas, USA Grafarend, E.W., Krumm, F.W. (2006) Map Projections, p. 72: Historical Aside: Stereographic Projection, Springer, New York Hestenes, D., Sobczyk, G. (1984) Clifford Algebra to Geometric Calculus, Reidel, Dordrecht Hestenes, D., Li, H., Rockwood, A. (1999) A unified algebraic framework for classical geometry: (1) A Unified Algebraic Approach for Classical Geometries. (2) Generalized Homogeneous Coordinates for Computational Geometry. (3) Spherical Conformal Geometry with Geometric Algebra. (4) A Universal Model for Conformal Geometries of Euclidean, Spherical and Double-Hyperbolic Spaces, in: Sommer, G. (ed), Geometric Computing with Clifford Algebra, Springer, London Ledoux, H. (2008) The Kinetic 3D Voronoi Diagram: A Tool for Simulating Environmental Processes, in: Oosterom, P.V., Zlatanova, S., Penninga, F., and Fendel E. (eds): Advances in 3D Geo Information Systems, Proceedings of the 2nd International Workshop on 3D Geoinformation, December 12–14, 2007, Delft, The Netherlands, Lecture Notes in Geoinformation and Cartography, Springer, pp. 361–380 Pedoe, D. (1979) Circles, a Mathematical View, Dover, New York Perwass, C.B.U. (2008) Geometric Algebra with Applications in Engineering, Springer, Berlin Rosenfeld, B.A. (1988) A History of Non-Euclidean Geometry, pp. 121–130: Stereographic Projection, Springer, New York
Rapid Modelling of Complex Building Interiors Pawel Boguslawski and Christopher Gold
Abstract Great progress has been made on building exterior modelling in recent years, largely driven by the availability of laser scanning techniques. However, the complementary modelling of building interiors has been handicapped both by the limited availability of data and by the limited analytic ability of available 3D data structures. Earlier papers of ours have discussed our progress in developing an appropriate data structure: this paper reports our final results, and demonstrates their feasibility with the modelling of two complex, linked buildings at the University of Glamorgan.
1 Introduction This paper completes the discussion of the development of a new data structure for full 3D building modelling, complete with interior volume elements and dual-graph connectivity between rooms. The initial paper (Boguslawski et al. 2009) gave the background of earlier structures, including the Quad-Edge (QE) of Guibas and Stolfi (1985) and the Augmented Quad-Edge (AQE) of Ledoux and Gold (2007). The first provided a 2D primal/dual structure on the surface of a simple shell, while the second gave a 3D primal/dual structure for cell complexes, with the dual graph providing the connectivity between the volume elements. Unfortunately the AQE, while providing the desired connectivity, did not have easy incremental construction operations, so (Boguslawski and Gold 2009) proposed an atomic element of two permanently linked
P. Boguslawski (*) Department of Computing and Mathematics, University of Glamorgan, Wales, UK e-mail: [email protected] C. Gold Department of Computing and Mathematics, University of Glamorgan, Wales, UK and Department of Geoinformatics, Universiti Teknologi Malaysia (UTM), Johor Bahru, Johor, Malaysia e-mail: [email protected]
T.H. Kolbe et al. (eds.), Advances in 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, DOI 10.1007/978-3-642-12670-3_3, # Springer-Verlag Berlin Heidelberg 2011
43
44
P. Boguslawski and C. Gold
half-edges (the Dual Half-Edge or DHE), one in the primal space and a matching one in the dual space. It also proposed a construction mechanism (‘Cardboard and Tape’) where individual walls were constructed with DHEs and then ‘taped’ together. The second paper (Boguslawski et al. 2010a) elaborated on this, showing the four ways of combining a pair of DHEs and discussing the requirements for a set of ‘Euler Operators’ (EOs) that would work for cell complexes and not just individual shells. As EOs operate on individual edges, a system that operated on cell complexes (and not just the single shell of traditional EOs) needed to be able to connect both primal and dual edges simultaneously in order to preserve the dual navigation framework. The paper demonstrated that this was possible if the global model (such as a building) always had an exterior shell separating the building from ‘the rest of the world’. It described the construction of simple boxes, where faces and volumes were constructed automatically as edges were added, and also extensions where separate boxes were joined (sharing a common face but with individual volume elements and connectivity) and when they were merged (the face was removed and the two volume elements became one). There was a brief mention of escape route planning. Ledoux and Gold (2007), Boguslawski and Gold (2009, 2010a) all describe the work of other authors of manifold and non-manifold data structures, and they will not be repeated here. Briefly, only the AQE and the DHE permit full navigation within cell complexes and between volume elements. This paper completes the analysis by discussing manifold and non-manifold modelling in CAD, gives a clearer description of the DHE pointer structure, and discusses the assignment of attributes to the primal or dual manifestations of an edge or vertex. The DHE is compared with a related structure of Yamaguchi and Kimura (1995) and it is shown that not all non-manifold cases can be handled by their Coupling-Entity: in particular, cells connected by only a common vertex cannot be traversed successfully, as can be done with the ‘full’ model of the DHE. (Awkward non-manifold cases are important in advanced CAD systems, as they often arise as intermediate stages in the construction process.) The Coupling-Entity model is shown to have equivalent properties to the ‘simplified’ case of the DHE (where the dual graph is suppressed and the primal pointer that would have addressed it connects to an edge of the adjacent cell instead). Thus the full DHE is a more complete structure, justifying the inclusion (and extra storage) of the dual graph. In addition, it is shown to handle holes in cells as well as cavities. The paper concludes with a real-life example, two complex buildings connected by an overpass and containing some 1,300 cells when doorway and similar elements are included. Implementation of Dijkstra’s algorithm on the dual graph provides a real example of escape route planning, for which this project was originally developed.
2 Background: Manifold and Non-manifold Models Building exteriors are usually modelled as a set of connected tiles – often triangular. This ‘B-Rep’ (Boundary Representation) is similar to the TIN (Triangulated Irregular Network) models used in GIS for terrain modelling. As originally developed
Rapid Modelling of Complex Building Interiors
45
for CAD systems, the B-Rep and its set of associated Euler operators permits the incremental construction of complex single-shell entities: e.g. engine parts – or building exteriors (e.g. Kolbe et al. 2009). When this approach is applied to building interiors, problems arise. Building interiors may be thought of as a set of spaces (rooms or hallways) that are adjacent and connected: thus the model is no longer a single shell, or even a set of unconnected shells for the rooms, but a cellular complex whose boundaries are not a ‘twomanifold’, but something that requires a ‘non-manifold’ model, where, for example, more than two faces may meet at an edge. CAD developers have designed several systems to handle these cases, but they have been found to be complex to implement and they do not always handle every special case. This is particularly difficult during the construction process: Euler operators are designed to add one edge at a time, and this leaves temporary awkward structures that will usually disappear as the model is completed. Nevertheless, the connectivity of these cases must be fully defined in order to provide a stable and topologically complete data structure. Some non-manifold models are presented in Fig. 1. Two shells joined by a shared edge (Fig. 1a) or vertex (Fig. 1b) are typical examples. In two-manifold models an edge is coincident with exactly two faces, but in non-manifold models more than two faces can be joined to an edge. In Fig. 1b example there is one common vertex for two shells; edges sharing this vertex create two separate cycles (one for each cell) which is not allowed in two-manifolds. There are more examples: open volumes, mixture of shells, faces, separate edges and vertices, etc. Several of these non-manifold CAD models have been described in our previous papers (Boguslawski and Gold 2009, 2010a). In general they are complex and difficult to implement, and may not have all the properties one might desire. In our project we are particularly interested in escape route planning, which requires both volume entities (rooms) and the dual graph (connectivity between rooms). While these can always be obtained from the primal (geometric) graph describing the cell complex, this is an awkward way to proceed when they are of key interest, with in some cases rapidly changing attributes. No previous models included the dual graph as part of the structure [as is achieved in 2D, for example, by the Quad-Edge (QE) structure of Guibas and Stolfi (1985)]. In addition, we found it useful to have a well defined and permanent ‘outside’ or exterior shell, corresponding to the exterior building models obtained from laser scanning methods.
Fig. 1 Examples of non-manifold models
46
P. Boguslawski and C. Gold
3 The Dual Half-Edge Data Structure As described in our earlier papers we found that the most satisfactory approach was to incorporate both the primal (geometric) and dual graph structures within our basic model, following the inspiration of Guibas and Stolfi (1985), the half-edge of M€antyl€a (1988) and the AQE of Ledoux and Gold (2007). It uses the half-edges to represent each polyhedron, but like the AQE adds the dual to each element. Thus we have pairs of half-edges, one in primal space and one in dual space, which are permanently linked together. Each half-edge has pointers: to a vertex; to the paired half-edge that forms the opposite side of the edge; to the next half edge around the associated vertex; and to the next half edge around its own face – so the primal part contains a loop pointer around the face of a single cell and the dual part contains a pointer around the face in dual space – which is equivalent to a loop around an edge in the primal space (see Fig. 2). This simplifies the overall structure considerably. It is interesting to note that the original half-edge structure consists of twinned pairs of half-edges in 2D, and the same would be true for a model of the dual. The Quad-Edge combines these two into an element containing four half-edges, with improved navigation features. The DHE splits these four half-edges in a different way: one primal and one dual in each element. This preserves the two-manifold navigation properties of the QE and the easy navigation between cells of the AQE – while allowing flexible ‘twinning’ of half-edges in the construction process. Thus each half edge may be linked to a single other half edge, forming part of a simple shell, as with b-rep models. To access adjacent shells one goes to the dual of one of these edges and moves around the dual face until the adjacent primal shell is found.
Fig. 2 DHE pointer based data structure; primal graph (solid lines) is connected permanently with the dual graph (dashed lines); he – original half-edge; S, NV, NF, D, V – pointers; Sym, NextV, NextF, Dual – navigation operators
Rapid Modelling of Complex Building Interiors
47
There are no shells without an adjacent shell: the boundaries of the model are enclosed by an exterior shell, as described below. A complete primal (‘geometric’ or ‘building’) model involves vertices, edges, faces and volumes. Primal vertices and edges are equivalent to volumes and faces in the dual model. Primal faces and volumes are equivalent to edges and vertices in the dual model. Thus all elements may be represented by a graph structure consisting of vertices and edges – half in primal space and half in dual space. Observe that each element has a dual role: attributes may be assigned to its primal and/or dual meaning. In terms of storage, whether in a graph structure or a data base, there are only two atomic element types, vertices and edges. Both may have attribute information associated with their primal or dual roles, but only edges have topological pointer information: to the second half of the edge, to the dual edge, to the next edge around a vertex, to the next edge around a face, and to its associated vertex. Exterior shell – While this model is complete in the interior of a model, there could be problems at the exterior boundary. Each room has a simple QE type shell. The dual edge for each face connects the interior ‘room’ node with that of an adjacent room. If there is no adjacent room the dual graph structure – itself a collection of simple shells – will be incomplete, and some navigation operations could fail by ‘falling off the edge of the world’. To prevent this, and to make all the required Euler operators viable, a simple rule of the DHE is that there is always a single exterior shell – the ‘exterior’ or the ‘rest of the world’. Thus an exterior face of a room will have a dual edge connecting the ‘room’ vertex with a single universal ‘exterior’ vertex: all exterior faces will have dual edges connecting to this vertex. This property is particularly useful when joining initially-separate buildings (cell complexes). Without the external cell it is not possible to create dangling edges, and thus the incremental construction of models, as explained in the Sect. 5, would not be possible. Connection of two half-edges in primal space (geometry) does not cause a problem, but in the dual not-paired halves prohibit navigation within the model. However since the external cell is kept along with the internal cells, every half-edge has its counterpart in the adjacent cell: in the external or internal cell. We also note that a ‘simplified’ model may be developed from the DHE, where the dual graph is replaced by a pointer directly to an edge of each adjacent shell. This may suffice for some applications but, as described previously, volume and dual-edge entities are missing. In addition it fails to manage the case where two shells are connected only by a vertex – see Fig. 1. All other cases can be handled. If the application does not require these features then the simplified structure significantly reduces the storage space required. The published system closest to our way of thinking is that of Yamaguchi and Kimura (1995) who described a ‘coupling entity’ data structure to link the individual edges of each shell (room) so that navigation was possible both within and between rooms. However, we have found no example of large-scale models produced by their approach, although they claim that Euler operators may be developed on their structure. We have shown (Boguslawski and Gold 2010b) that their model is equivalent to our ‘simplified’ one – with the same limitations.
48
P. Boguslawski and C. Gold
4 The Coupling Entity Data Structure and the Dual Half-Edge Yamaguchi et al. (1991) and Yamaguchi and Kimura (1995) introduced the coupling-entity data structure for representing non-manifold topology of threedimensional models. They are focused on the boundary representation. They introduced the feather – a new coupling-entity. There are two groups of pointers present in this structure: mate pointers and cyclic pointers. They describe relations between neighbouring entities. Three types of the mate pointers, shown in the Fig. 3a), points at another feathers in a model: fan mate (FM), blade mate (BM) and wedge mate (WM). Given the feather entity e, the fan mate of e is the feather on the matching face which shares just a vertex with e, the blade mate of e is the feather on the matching face which shares both a vertex and an edge with e, and the wedge mate of e is the feather on the same shell which shares an edge with e. The three cycles of feathers are defined: a disk – the next feather around a shared vertex, a loop – the next feather around a face, and a radial – the next feather around a shared edge. There is also a cycle orientation taken into account: clockwise (C) and counter-clockwise (CC). Thus six cyclic pointers are necessary – counter-clockwise: disk (CCD), loop (CCL), radial (CCR), and clockwise: disk (CD), loop (CL), radial (CR). These cycle pointers can be deduced from the mate pointers (1–6) as shown in Fig. 3b) (only counter-clockwise cycles are shown). Thus the full set of nine pointers can be reduced to three and mate pointers are used exclusively. CCL(e) = FM(BM(e))
(1)
CCR(e) = WM(BM(e))
(2)
CCD(e) = WM(BM(FM(e)))
(3)
Fig. 3 The feather entity: (a) mates; (b) cycles
Rapid Modelling of Complex Building Interiors
49
CL(e) = BM(FM(e))
(4)
CR(e) = BM(WM(e))
(5)
CDðeÞ ¼ FMðBMðWMðeÞÞÞ
(6)
Because of this reduction, the functionality of the model is limited – no more than one disc cycle can be represented with the feather data structure (Yamaguchi and Kimura 1995). Thus some topological relations are not possible in a model, for example joining two objects at a vertex (see Fig. 4). There are two disc cycles that need to be joined (e1!e2!e3 and e4!e5!e6) – one disc cycle from each cell. But this is not possible with the mate pointers only – all mate pointers are already used to connect the neighbouring entities of a single cell. The solution of that problem that allows for this non-manifold case can be adding the disc cycle pointers back to the feather (CCD and CD). Thus navigation around shared vertex would be explicit and the loop and radial cycles could be still deduced using the mate pointers. The DHE is a more flexible data structure than the coupling-entity: non-manifold cases like the one presented in Fig. 4 can be modelled. It is also possible to simulate the feather. All the pointers can be derived from DHE. The wedge mate pointer WM (e) is explicitly represented with Sym (S pointer) (7); fan FM(e) and blade BM(e) mates can be represented as a sequence of basic DHE pointers or navigation operators [(8) and (9)]: FM(e) = e:Dual.Sym:Dual : e:D:S:D
(7)
BM(e) = e:Adjacent : e:D:NF :D:S
(8)
WM(e) = e:Sym : e:S
(9)
Fig. 4 Joining two cells at a shared vertex
50
P. Boguslawski and C. Gold
The cycle pointers can be derived (10–15) from mate pointers, but there are also DHE pointers that can be used explicitly: CCL(e) = e:NextF : e:NF
(10)
CCR(e) = e:NextE : e:D:NF :D (e:Adjacent.Sym)
(11)
CCD(e) = e:NextV : e:NV
(12)
CL(e) = e:PrevF : e.D.S.NF .D.S
(13)
CR(e) = e:PrevE : e.S.D:NF .D.S (e.Sym.Adjacent)
(14)
CD(e) = e:PrevV : e.D:NV .D
(15)
It has been shown that models using the feather as a basic element can be simulated with the DHE data structure. It is also possible to show that a simplified version of DHE exists and this is an equivalent of the feather. Thus the feather is a subset of DHE. In the simplified version there is no dual and the NF pointer is removed from the structure – there are NV, S and D pointers left (the V pointer is not taken into consideration, because it does not have any topological function). Because the dual is no longer available in a model, the D pointer has a different meaning and does not point at the dual half-edge – it points at a half-edge in the adjacent face. This connection is the same as the fan mate connection in the feather. Equations (16)–(18) show the relations between two models. The mate pointers can be defined with DHE pointers: FM(e) ¼ e.Dual : e.D
(16)
BM(e) = e.Adjacent : e.D:NV .S
(17)
WM(e) = e:Sym : e.S
(18)
The cycle pointers can be derived from the mate pointers as shown in (1)–(6) replacing the mate pointers with DHE equivalents (16–18). Because the simplified version is an equivalent of the feather – a reverse translation is possible [(19)–(21)]: e.D = FM(e)
(19)
e:NV ¼ WM(BM(FM(e)))
(20)
e.S = WM(e)
(21)
Rapid Modelling of Complex Building Interiors
51
Unfortunately the simplified DHE has similar limitations as the feather. Joining two cells at a shared vertex produce a model which is not valid. However all edges sharing the same vertex can be joined in one cycle using the NV pointer: e1!e2!e3!e4!e5!e6 (see Fig. 4). But navigation is not valid. For example the CL (clockwise around a face) cycle is defined in (4). The fan and blade mates can be replaced with the DHE equivalents [(19) and (20)]. Thus CL is defined as NV.S. The incapability to navigate around a face appears in two places: e3 and e6. The e3 edge will be used in the example. e3.NV.S points at the opposite end of e4. But in the valid face loop the next element is the other end of e1. This error is caused by defining the loop cycle using the disc cycle. Unfortunately it does not work for the case presented in Fig. 4 – the disc and loop cycles should be independent. However, in a cell complex decomposing 3D space where all the cells are joined by shared faces (eight cube cells connected in a big 2 2 2 cube complex), other methods can be used to navigate between edges sharing the same vertex. A single cell in a complex is two-manifold, and only one disk cycle is necessary to navigate around a shared vertex. Disk cycles in other cells are not joined together, but navigation through shared faces is possible, and access to these cycles is possible. It was shown in this section that the DHE data structure can be simplified to an equivalent of the feather coupling-entity. Not all non-manifold cases can be managed with this simplified version: two cells joined at a vertex are not allowed. An extra cycle pointer and the dual are necessary for valid navigation in a model. Another difference and a big advantage over the coupling-entity is that DHE (the full version) is able to represent cell/volume with a single dual vertex, and a face with a bundle (of edges). We also demonstrate (Boguslawski et al. 2010b) that our full system (with the dual) can represent certain 3D degeneracies in the model. Adding a ‘bridging edge’ in each face permits the construction of a hole through a shell (e.g. a torus) and adding a ‘bridging face’ permits the modelling of a completely enclosed cavity. (Adding these elements means we have a single connected graph, and may navigate, query and edit it.)
5 Construction of Models with Euler Operators Using standard Euler operators we can easily build polyhedra of any shape. Figure 5 shows the sequence used to create a cube from individual edge elements (this is one of many possible sequences). For clarity the dual is not shown, but it is present at each step, as with the external cell. The dual connects the internal and external cells together into one cell complex. Faces are defined automatically upon closure of the edges, and volumes are determined whenever a closed set of faces is completed. Holes and cavities (shown in Fig. 6) are allowed: we use a so-called ‘bridge edge’ (eb in Fig. 6a, b) to connect internal rings (holes) to the outside ring (the face); and a ‘bridge face’ (fb in Fig. 6b) to connect an internal cell (a cavity) with the outside cell. These permit us to represent many real-world situations.
52
P. Boguslawski and C. Gold
Fig. 5 One of many possible ways to construct a cube using Euler operators
Fig. 6 Holes and cavities: (a) hole through polyhedra needs two faces with holes connected by bridge edges eb; (b) the front face with a hole – bridge edge eb connects internal loop lINT with the outside loop lOUT; (c) cavity in a cell – bridge face fb connects internal cell cINT with the outside cell cOUT
Rapid Modelling of Complex Building Interiors
53
Fig. 7 Operators for a cell complex construction: (a) join/separate; (b) merge/split
To construct non-manifold models like two cells joined by a shared face an extension of the standard Euler operators set is necessary. Masuda (1993) presented a spanning set of extended Euler operators that allows for construction of complexbased non-manifold models. This set preserves topological consistency of the models. We use this idea to develop Euler operators to build a cell complex: we can join/separate (Fig. 7a) or merge/split (Fig. 7b) cells of the complex. Joining is an operation that glues two separate cells together. As result there are two connected cells with a double-sided face in between. Merging removes this shared face and the union of the two cells forms one volume. We perform a sequence of simple, atomic operations, the same as with standard Euler operators. ‘Join’ removes two adjacent faces from external cells; and combines two cells. Internal primal cells stay unchanged. ‘Merge’ removes the adjacent faces of two internal cells to form a single cell. Thus ‘Join’ operates on external cells while ‘Merge’ operates on internal ones. Lee (1999) shows a similar example using standard Euler operators (with no dual) for joining or separating cells.
6 Construction of Complex Building Interiors Our full model is capable of being used for rapid 3D building modelling, with full navigation and analysis. We take as our example two linked buildings on the University of Glamorgan campus. In total there are over 1,300 cells. (Cells may be rooms, doors or corridors.) The model, and its use for escape route planning, was prepared within 2 weeks. First the floor plans were scanned, and then manually traced (vectorised) using AutoCad, and then the doors were added. Then the rooms were extruded for each floor, within AutoCad. This produced a set of individual
54
P. Boguslawski and C. Gold
Fig. 8 A building model with paths between two locations: (a) two rooms on the same corridor; (b) escape route from a room on the top floor; (c) connectivity via stairway
Rapid Modelling of Complex Building Interiors
55
cells, one for each room – but not connected together. The various floors were adjusted to fit on top of each other, and exported as OBJ files to our software. Geometric intersection testing routines were used to check for adjacency. The results were used to construct the building models using our standard Euler operators, with both the primal and the dual graph being updated simultaneously. Because of our interest in escape route planning, as also in the case of Lee (2007), all doors on the plans were added as ‘flat’ (zero volume) cells, complete with their own centroids, to allow specification of navigation routes and to allow attributes, such as locking times, to be added. Corridors were broken into manageable sections by inserting ‘virtual doors’ appropriately. The resulting models functioned as desired. Figure 8 shows some views of the model with the shortest path visualized as grey cells (rooms, corridors, doors) along the path. These paths can be calculated ‘from room to room’ (Fig. 8a) – useful in building management for finding paths between two locations, or ‘from a room to an assembly point’ – [an escape route (Fig. 8b)]. Navigation between floors is via stairways (Fig. 8c); a stairway on one floor is connected to stairways below and above with horizontal ‘virtual doors’. As our original objective was escape route planning, we needed to describe the local terrain close to the buildings – e.g. for assembly points. This was achieved by adding thin cells (perhaps concrete paving) to the model, allowing navigation outside the building (Fig. 9). Applying Dijkstra’s algorithm to the dual graph allows the real-time calculation of the shortest path from any location to an assembly point.
Fig. 9 A building with an external terrain. (The exterior is composed of thin 3D cells, allowing navigation through them in the same way as with rooms)
56
P. Boguslawski and C. Gold
7 Conclusions We have demonstrated that our new data structure, the dual half-edge, is flexible enough to permit rapid building model construction using Euler operators. Our illustrative application is escape route planning, where real-time navigation may be performed, the results changing as new accessibility information arrives during the emergency. The ability to apply attribute information to any model element (node, edge, face or volume – in either primal or dual space) opens a wide range of applications beyond disaster management. Examples include sound and radio wave propagation, virtual museums (with pictures/textures on each wall face), shopping centre assistance (with shop-face textures applied) and many more. Acknowledgements The first author’s research was supported by the Ordnance Survey and an EPSRC New CASE award.
References Boguslawski, P. and C. Gold, Construction Operators for Modelling 3D Objects and Dual Navigation Structures, in 3D Geo-Information Sciences. Lectures Notes in Geoinformation and Cartography. 2009, Springer, Berlin. pp. 47–59. Boguslawski, P. and C. Gold, Euler Operators and Navigation of Multi-shell Building Models, in Developments in 3D Geo-Information Sciences. Lecture Notes in Geoinformation and Cartography. 2010, Springer, Berlin. pp. 1–16. Boguslawski, P., C.M. Gold, and H. Ledoux, Modelling and analysing 3D buildings with a primal/ dual data structure. ISPRS Journal of Photogrammetry and Remote Sensing, 2010. Accepted (Scale, quality, and analysis aspects of city models), Article in Press. Guibas, L. and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi. ACM Transactions on Graphics, 1985. 4(2): pp. 74–123. Kolbe, T.H., Representing and Exchanging 3D City Models with CityGML, in 3D Geo-Information Sciences, J. Lee and S. Zlatanova, Editors. 2009, Springer, Berlin, Heidelberg, pp. 15–31. Ledoux, H. and C.M. Gold, Simultaneous storage of primal and dual three-dimensional subdivisions. Computers, Environment and Urban Systems, 2007. 31(4): pp. 393–408. Lee, J., A three-dimensional navigable data model to support emergency response in microspatial built-environments. Annals of the Association of American Geographers, 2007. 97(3): pp. 512–529. Lee, K., Principles of CAD/CAM/CAE Systems. 1999, Addison-Wesley Longman, Reading. p. 582. M€antyl€a, M., Introduction to Solid Modeling. 1988, Computer Science Press, Rockville. p. 401. Masuda, H., Topological operators and Boolean operations for complex-based nonmanifold geometric models. Computer-Aided Design, 1993. 25(2): pp. 119–129. Yamaguchi, Y. and F. Kimura, Nonmanifold topology based on coupling entities. IEEE Computer Graphics and Applications, 1995. 15(1): pp. 42–50. Yamaguchi, Y., K. Kobayashi, and F. Kimura, Geometric Modeling with Generalized Topology and Geometry for Product Engineering, in Product Modeling for Computer-Aided Design and Manufacturing, J. Peger and J. Turner, Editors. 1991, Elsevier Science Publishers B.V., North-Holland.
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering M. Christen and S. Nebiker
Abstract A technique to create a Delaunay triangulation for terrain visualization on a virtual globe is presented. This method can be used to process large scale elevation datasets with billions of points by using little RAM during data processing. All data is being transformed to a global spatial reference system. If grid based elevation data is used as input, a reduced TIN can be calculated. Furthermore, a level of detail approach for large scale out-of-core spherical terrain rendering for virtual globes is presented using the previously created TIN.
1 Introduction Terrain Rendering with very large and dense height data sets have become very popular due to the progression of geospatial imaging sensors such as airborne LiDAR (Fowler et al. 1997; Shan and Toth 2009). Terrain point densities from such sensors can be in the range of one or several points per square meter leading to massive data sets when applied to entire states or countries. Even for small countries, such a LiDAR data set could easily comprise of several hundred billions of points or several TB of data respectively. Despite the wide-spread use of TINbased elevation models in the GIS community, there are hardly any software solutions capable of efficiently processing such large data sets on the one hand of and also supporting the generation of levels of detail on the other. However, both capabilities are required to exploit such large TIN-based data sets in scalable and interactive 3D geoinformation environments. Virtual globes have a high impact on geographical 3D information systems and reality based games. They were mostly based on grid-based elevation data but will increasingly incorporate high-density elevation data sets in the multi-TB range. This paper shows an approach of how
M. Christen (*) and S. Nebiker Institute of Geomatics Engineering, University of Applied Sciences Northwestern Switzerland, Gr€undenstr. 40, 4132 Muttenz, Switzerland e-mail: [email protected], [email protected]
T.H. Kolbe et al. (eds.), Advances in 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, DOI 10.1007/978-3-642-12670-3_4, # Springer-Verlag Berlin Heidelberg 2011
57
58
M. Christen and S. Nebiker
very large irregulary spaced high-density elevation datasets can efficiently be preprocessed for ellipsoidal rendering on a virtual globe.
2 Previous Work A virtual globe has been implemented at the University of Applied Sciences Northwestern Switzerland. This virtual globe is called i3D. Virtual globes can be implemented (Nebiker et al. 2007) using grid based geometry for the terrain. However, using regular grids has several drawbacks. For one the grid is limited to contain points aligned to the grid only: break-lines and spot heights are not supported since they are generally not grid-aligned. Another drawback is that when creating a polygonal representation from a grid representation many coplanar polygonneighbors may result, especially in flat areas like lakes, leading to expensive redundancy and unneeded geometry, which leads to wasted memory transfer between the CPU and GPU. Furthermore, if grid points are transformed from a local to a global spatial reference system the alignment of the grid changes to a new grid layout which requires height interpolations and thus leads to quality loss.
3 Related Work Numerous interactive terrain rendering methods have been proposed. A thorough survey on different approaches was recently made by Pajarola and Gobbetti (2007). Basically there are hierarchical level of detail approches using regular grids and others using irregular data sets (Hoppe et al. 1998; Pajarola et al. 2002). Lately there was more focus on GPU optimized techniques (Livny et al. 2009) and related topics like data compression between the CPU and GPU (Dick et al. 2009; Lindstrom et al. 2010). Most proposed works assume a planar reference – restricted to flat earth terrain rendering. Only few literature is considering spherical or even ellipsoidal planetary rendering or data processing, for example references (Gerstner et al. 1999; Szalay et al. 2007; Zhou et al. 2008). For data preprocessing, a streaming Delaunay computation of very large height data sets was introduced by Isenburg et al. (2006). Their approach calculates Delaunay triangulations by using the spatial coherence of the dataset itself – without previously sorting the data. However, their approach does not consider storing the resulting triangulation in a spatial data structure suitable for the virtual globe and applying further processing steps to the resulting TIN, like thinning out and calculating level of detail. Furthermore, an alternative way for visualizing large amount of LIDAR data in Google Earth has been presented by Isenburg et al. (2009). Their approach creates rasterized contour lines to visualize the data and not the actual geometry.
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
59
The Google Earth API (Google: Google Earth API Developer’s Guide) currently doesn’t have a mechanism to stream custom elevation data.
4 Virtual Globes 4.1
Overview of Virtual Globes
Virtual globes, sometimes also referred to as 3D geobrowsers, consist of virtual 3D environments capable of streaming and interactively displaying large amounts of geo-referenced spatial contents over the Internet (Nebiker et al. 2010). With the availability of the commercial products Google Earth (Google: Google Earth API Developer’s Guide) and Microsoft: Bing Maps 3d virtual globes gained enourmously in popularity. A virtual globe stores its data on servers that can be accessed by a client software. This software can either be a stand-alone executable file (Google Earth), or running from a browser plugin (Bing Maps, Google Earth). There is little reliable information available on how these commercial products create their large scale elevation models. This may be one of the reasons, why adding large custom-built elevation models is not possible with these globes.
4.2
Preprocessing Data for Virtual Globes
A virtual globe can have several data categories like image data, elevation data, points of interest, vector data, and 3D objects. Before streaming over the Internet this data must be preprocessed. This preprocessing usually comprises a transformation from a local to a global reference system, creation of pyramid layers or level of detail, tiling of the data, and optionally compression and encryption of the data.
4.3
Virtual Globe Tile Systems
Bing Maps, Google Earth, and i3D tiles are indexed using quadtree keys (quadkeys). Each quadkey number identifies a single tile at a single zoom level (see Fig. 1). Typically, the Mercator projection is used to map image and elevation data to a square area. The Mercator projection is mainly used to minimize distortions in processed images and elevation data. The meridians of the Mercator projection are vertical parallel equally spaced lines, cut at right angles by horizontal straight parallels which are increasingly spaced toward each pole so that conformality is preserved (Snyder 1987). The maximum latitude is chosen so that the resulting map fits into a square. For the spherical Mercator projection this maximum latitude is
approximately 85.05 and for the ellipsoidal Mercator projection it is approximately 85.08 . The projection is normalized to values in the range (1,1) to (1,1) to ensure increased numerical stability during the triangulation and thinning process. Bing Maps 3D uses the spherical Mercator projection and i3D supports both the spherical and ellipsoidal Mercator projection. Such an ellipsoidal geodetic reference model is required, in order to minimise geometric transformation errors and to enable position accuracies within the Virtual Globe at the sub-meter level. Listing 1 shows the implementation used in i3D. Points are transformed from the Mercator projection to WGS84 by using the respective algorithm described in Snyder (1987). 1 void EllipsoidToMercator (const double lngRad, const double latRad, double& out_x, double& out_y, const double e) 2{ 3 const double a ¼ 1.0 / M_PI; 4 const double lngRad0 ¼ 0; 5 6 if (e ¼¼ 0.0) // spherical case 7{ 8 out_x ¼ a* (lngRad-lngRad0); 9 out_y ¼ log(tan(M_PI/4.0 + latRad/2)); 10 } 11 else // ellipsoidal case, first eccentricity not 0. 12 { 13 out_x ¼ a*(lngRad-lngRad0);
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
Listing 1 Transformation to normalized Mercator coordinates
5 Creating Large TIN for Virtual Globes In the design of elevation support for a Virtual Globe a number of requirements must be taken into account, many of which are distinctly different from those applicable to DEM support in standard GIS environments. These DEM requirements in Virtual Globes include: the support for highly accurate regional to global elevation models with a preservation of the original precision at a global scale; the possibility to add spot heights and breaklines – either during preprocessing or at runtime; the adaptive data reduction or data thinning in order to optimise storage space, transmission performance and memory utilisation in the rendering process; the support for level of detail and view-dependent multiple resolutions; the need for highly efficient processing of very large terrain models supporting parallelisation approaches; a streamable delivery and rendering of terrain data, and finally, the capability of merging and displaying multiple DEMs, e.g., a global model and a high-resolution local model, at run-time. In this section we document an approach addressing these specific requirements.
5.1
Choosing a Data Structure for Large Scale Triangulation
There are many possible data structures for representing triangulations. Thus, a triangulation data structure should be chosen in view of the needs and requirements of the actual application (Hjelle and Daehlen 2006). Popular data structures for triangulations are: triangle-based data structure with neighbors, vertex-based data structure with neighbors, half-edge data structure (Weiler 1985), and the quad-edge data structure (Guibas et al. 1983). For our large scale implementation of the Delaunay triangulation a trianglebased data structure is used. One of the reasons for that is that the triangle neighbor must support a mechanism to temporarily remove neighbor triangles from memory to simplify our large scale triangulation and to calculate level of detail which is easier to implement in a triangle based structure. The main characteristic of a triangle-based data structure is that edges are not stored directly – only vertices and triangles which are always stored in counterclockwise orientation as we can see in Listings 2 and 3.
62
M. Christen and S. Nebiker
The triangle structure is defined by using two structures, one for the vertex (also called elevation point) and a second structure for the triangle. 1 struct Vertex 2{ 3 double x, y; // position in mercator projection 4 double elv; // elevation above WGS84 ellipsoid [m] 5 double weight; // weight/importance of this point 6 }; Listing 2 Definition of an elevation point
All values of the vertex structure are held as double precision floating point to support precision in the millimeter range. Besides the position parameters a weight parameter is used which can be used to define the importance of the point. This is useful in the preservation of characteristic mountain peaks when calculating the level of detail. 1 struct Triangle 2{ 3 Vertex* pVertex0 ; 4 Vertex* pVertex1 ; 5 Vertex* pVertex2 ; 6 Triangle* pTriangle0 ; 7 Triangle* pTriangle1 ; 8 Triangle* pTriangle2 ; 9};
Listing 3 Definition of a triangle
The triangle structure holds pointers to vertices and neighbor triangles as shown in Fig. 2. Because vertex-pointers and triangle-pointers are shared among different triangles a reference count mechanism is implemented. Because the triangulation must be large scale, it is necessary to remove triangles in a special way by deleting them from memory without affecting the Delaunay condition. This can be done by deleting unused triangles from memory and by setting the appropriate triangle neighbor pointers to 0. This allows creating disconnected areas with islands in the triangle structure as shown in Fig. 3. Furthermore for thinning out data a mechanism must be available for removing points from the triangulation, for example by using the removal algorithm described in Mostafavi et al. (2003). The Delaunay triangulation itself is created using an incremental approach. In summary, the supported basic operations of the triangulation must be:
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
63
Fig. 2 Triangle data structure
Fig. 3 Disconnected area with island
l l l
Insert a new point into triangulation (for incremental construction) Remove a triangle from memory (for large scale support) Remove a point from triangulation (for thinning out data)
5.2
Incremental Delaunay Construction
Incremental Delaunay trigulation has been presented by Guibas and Stolfi (1985). For reasons of clarity it is described briefly below.
64
M. Christen and S. Nebiker
Fig. 4 Adding a new vertex to triangulation
The construction of an incremental Delaunay triangulation consists of adding new vertices to an already existing triangulation. When adding a new vertex to the triangulation, there are some cases to be distinguished (Fig. 4): 1. The new vertex is inside an existing triangle. In this case three new triangles are created. 2. The new vertex is on an edge of an existing triangle. In this case the triangles containing this edge are removed and four new triangles are created. 3. The new vertex has the same position as an existing vertex in the triangulation. In this case the new vertex is rejected. 4. The new vertex is outside a previously defined boundary. In this case the vertex is rejected. To maintain the Delaunay condition when inserting new points, invalid edges must be flipped, so that the circumcircle of a triangle never contains another point of the triangulation (Fig. 5).
5.3
Numerical Stability in a Global Spatial Reference System
Because the triangulation is done in a global spatial reference system, numerical stability is an important issue, as triangles may become very small in relation to the global system. When inserting a new vertex into the triangulation, cases 2 and 3 of the incremental Delaunay construction described above bear numerical limitations. If all points of the triangles are almost collinear (“skinny triangle”), numerical problems will occur when using standard floating point arithmetic. Exact computation of the incircle and orientation predicates makes the algorithm robust, but slow. More speed can be gained by using arithmetic filtering approaches (Shewchuk 1996; Devillers et al. 2003) (Fig. 5).
5.4
Large Scale Triangulation
Our algorithm is divided into three passes: 1. Geodetic transformation 2. Spatial subdivision 3. Triangulation and cell split
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
65
Fig. 5 Flipping edges to satisfy the Delaunay condition
First Pass: The first pass transforms points from the source spatial reference system to a normalized Mercator projection using any custom rotational ellipsoid or sphere as described in Listing 1. During this pass a new file containing all transformed points in Mercator projection is created. In addition, the axis aligned bounding box (in Mercator projection) of the dataset is calculated. In summary, at the end of the first pass, the total number of points and the axis aligned bounding box is known, and all transformed points are stored in a binary file. Second Pass: The second pass creates a spatial subdivision of the points. This spatial subdivision is the same global quadtree of the Mercator projection which is later used for out-of-core rendering of the terrain. All points are stored in tiles of the lowest level of detail of this dataset. The maximum number of points per tile can be specified and according to that number the lowest level of detail is calculated. At the end of the second pass the original dataset is spatially subdivided and for each tile a file exists. The filename of the tile is generated using its quad-code – a unique identifier for each cell in the quadtree (Fig. 6). Third Pass: The third pass actually calculates the triangulation. By traversing the quadtree structure in a Morton order(Morton 1966), the triangulation is calculated step by step. When creating tiles, new points are added to the triangulation, the border points of the tiles (see Fig. 7). These points are stored in an edge file. “Edge points” are usually shared by two neighbor tiles and “corner points” are shared by up to four neighbor tiles. Every tile has at least four corner points. If a corner is not part of the triangulation, a point with elevation 0 will be added and marked as “no data value”, otherwise points are calculated by doing a linear interpolation of the elevation points at the corresponding position in the triangle containing the point. These points are treated as a constraint in the Delaunay triangulation, so that a rectangular tile border exists for all tiles. Tiles are stored by saving corner points, divided into north edge points, east edge points, south edge points, west edge points, and interior points separately. This way the Delaunay triangulation can be recreated for every tile and therefore additional points or break-lines may be added at a later time or even interactively during visualization.
66
M. Christen and S. Nebiker
Fig. 6 Calculating triangulation: output of processing three levels. (Only white triangles of max. four tiles are kept in memory)
Fig. 7 Calculating “tile edges” and “tile corner points”
5.5
Creating Level of Detail Tiles
Once all tiles are stored, the level of detail for all remaining pyramid layers can be calculated. The maximum number of points per tile must be maintained through all levels of detail. The algorithm used is an adapted version of the mesh simplification method presented by Heller (1990). For each level of detail tile all points of the four parent tiles are loaded and merged together in a new tile. The interior of the new tile and the corner and edge points of the parent tiles are disregarded. The new tile is being triangulated and thinned out by using the algorithm described by Lee (1989): for each point in the new triangulation an error value is calculated. This error value
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
67
holds the elevation difference which results when the point is removed from the triangulation. Points with small error are removed first. This procedure is repeated until the number of points in the tile is smaller than or equal to the maximum allowed number of points per tile. If the error value is still smaller than a previously defined epsilon value the points may even be thinned out more, which allows thinning out flat areas like lakes in an early stage of the level of detail.
6 Rendering the Virtual Globe Because visualization may consist of terabytes of orthophoto and elevation data, out-of-core rendering with a level of detail approach must be used. Data can be streamed over the Internet, a local network or a local hard drive. This is done by using download threads as shown in Fig. 8. Using a least recently used caching approach (LRU), the most recently requested data remains in the most expensive and fastest memory layer. For the level of detail approach a quadtree is used. The quadtree can be mapped to the WGS84 ellipsoid and an error metric adapted to ellipsoids decides which resolution is suitable for the current view. Depending on the error per pixel, a new resolution is requested from another data storage layer. The data itself is stored in tiles based on a quadtree. Tiles with neighbors of a different level of detail must be stitched together to avoid visualization artifacts. This usually involves updating the geometry of the tile with higher resolution to match the neighbor resolution, or using a curtaining method to hide stitching problems in a more efficient manner as it is not necessary to figure out the resolution of neighbors and to avoid retriangulations during visualisation.
Fig. 8 Elevation tile data is being downloaded while the rendering thread remains running at constant speed
68
M. Christen and S. Nebiker
7 Results The presented approach for large scale constraint Delauney triangulation has been implemented in our own i3D virtual globe technology.
7.1
Streaming Data
The propoposed algorithm produces tiled data that can be streamed from a harddisk, local area network, or from the Internet. Depending on the number of cores of the client machine, up to eight download threads are created to retrieve the data while the main thread is responsible for rendering data available in best resolution as shown in Fig. 8.
7.2
Quality
The error metric allows to change a quality parameter in real-time. This can be used to force level of detail to a specific setting, as shown in Fig. 9.
Fig. 9 Interactive change of quality parameters. Using swisstopo DHM25 dataset. Base data # swisstopo (JA100071)
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
69
Computers or mobile devices with lower memory or low-end graphics hardware can be set to a lower quality while maintaining a certain quality. Lower quality is also preferred in a slower network as it results in faster streaming.
7.3
Combining Image Data
The produced elevation tiles can be combined with image data, the result is shown in Fig. 10. Image data is being tiled using the same quadtree tiling structure as the elevation data. Image and elevation tiles are not stored together to be independent. It is possible to exchange image tiles without updating elevation tiles. In Fig. 11 elevation tiles and image tiles are blended together to see the resolution difference between image and elevation data.
8 Conclusion An approach for creating large scale elevation data processing has been introduced. With this approach it is possible to process global and local elevation datasets for visualization on a virtual globe. It permits the efficient processing of very large scale regularly and irregularly spaced terrain data sets on standard computer
Fig. 10 Rendering a TIN (original DEM point spacing of 25 m) on the virtual globe with and areal imagery with 50 cm per pixel resolution. Using SWISSIMAGE and DHM25 datasets. Base data # swisstopo (JA100071)
70
M. Christen and S. Nebiker
Fig. 11 TIN wireframe and image data blended together. Using SWISSIMAGE and DHM25 datasets. Base data # swisstopo (JA100071)
hardware. The presented triangulation approach is well suited for a future parallelisation of the triangulation of national to continental high-resolution elevation data sets. The presented TIN-based approach offers a number of advantages over gridbased terrain rendering in earlier versions of virtual globes, namely a significantly improved terrain representation with a simultaneous dramatic reduction in data size and streaming performance. The approach also supports the on-the-fly integration of spot heights and break-lines at runtime. This on-the-fly integration of breaklines, including special geospatial features such as Terrain Intersection Curves (TIS) of the CityGML standard (2010), will be a prerequisite for enabling future applications in Virtual Globes requiring more accurate and higher fidelity representations of urban environments (Nebiker et al. 2010).
References Devillers, O., Devillers, Pion, S., Pion, S., Prisme, P.: Efficient exact geometric predicates for Delaunay triangulations. In: Proceedings of the 5th Workshop Algorithm Engineering and Experiments. pp. 37–44. Baltimore (2003) Dick, C., Schneider, J., Westermann, R.: Efficient geometry compression for GPU- based decoding in realtime terrain rendering. Comp. Graph. Forum 28(1), 67–83 (2009)
Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering
71
Fowler, R.E., Samberg, A., Flood, M., Greaves, T.J.: Modeling mobile terrestrial LiDAR to vector based models. In: Maune, D. F. (ed.) Digital Elevation Model Technologies and Applications: The DEM Users Manual, chap. Topographic and Terrestrial Lidar. pp. 199–252. American Society of Photogrammetry and Remote Sensing, Bethesda (1997) Gerstner, T.: Multiresolution visualization and compression of global topographic data. Tech. rep., GeoInformatica (1999) Google: Earth, http://earth.google.com Google: Google Earth API Developer’s Guide, http://code.google.com/apis/earth/documentation/ Guibas, L.J., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams. In: STOC’ 83: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. pp. 221–234. ACM, New York (1983) Guibas, L.J., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 74–123 (1985) Heller, M.: Triangulation algorithms for adaptive terrain modeling. In: Proceedings of the 4th International Symposium on Spatial Data Handling. pp. 163–174. Zurich, Switzerland (1990) Hjelle, O., Daehlen, M.: Triangulations and Applications (Mathematics and Visualization). Springer-Verlag New York, Secaucus, NJ (2006) Hoppe, H.: Smooth view-dependent level-of-detail control and its application to terrain rendering. In: VIS ’98: Proceedings of the Conference on Visualization ’98. pp. 35–42. IEEE Computer Society Press, Los Alamitos (1998) Isenburg, M., Liu, Y., Shewchuk, J., Snoeyink, J.: Streaming computation of Delaunay triangulations. ACM Trans. Graph. 25(3), 1049–1056 (2006) Isenburg, M., Shewchuk, J.: Visualizing LIDAR in Google Earth. In: Proceedings of the 17th International Conference on Geoinformatics. Fairfax (2009) Lee, J.: A drop heuristic conversion method for extracting irregular networks for digital elevation models. In: Proceedings of the GIS/LIS ’89. pp. 30–39. Orlando (1989) Lindstrom, P., Cohen, J.D.: On-the-fly decompression and rendering of multiresolution terrain. In: I3D ’10: Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. pp. 65–73. ACM, New York (2010) Livny, Y., Kogan, Z., El-Sana, J.: Seamless patches for GPU-based terrain rendering. Vis. Comput. 25(3), 197–208 (2009) Microsoft: Bing Maps 3d, http://www.bing.com/maps Microsoft: Bing Maps Tile System, http://msdn.microsoft.com/en-us/library/bb259689.aspx Morton, G.: A computer oriented geodetic data base and a new technique in file sequencing. Tech. Rep. IBM Ltd., Ottawa, Ontario, Canada (1966) Mostafavi, M.A., Gold, C., Dakowicz, M.: Delete and insert operations in Voronoi/Delaunay methods and applications. Comput. Geosci. 29(4), 523–530 (2003) Nebiker, S., Christen, M., Eugster, H., Fl€ uckiger, K., Stierli, C.: Integrating mobile geo sensors into collaborative virtual globes – design and implementation issues. Paper presented at the Mobile Mapping Technologies Symposium MMT 2007, Padua (2007) Nebiker, S., Bleisch, S., Christen, M.: Rich point clouds in virtual globes a new paradigm in city modeling? Computers, Environment and Urban Systems (June 2010), http://dx.doi.org/ 10.1016/j.compenvurbsys.2010.05.002 Open Geospatial Consortium, Inc: OpenGIS® city geography markup language (CityGML) – encoding standard (ogc 08-007r1). (p. 218): Open Geospatial Consortium Inc. (2010) Pajarola, R., Gobbetti, E.: Survey of semi-regular multiresolution models for interactive terrain rendering. Vis. Comput. 23(8), 583–605 (2007) Pajarola, R., Antonijuan, M., Lario, R.: Quadtin: quadtree based triangulated irregular networks. In: VIS ’02: Proceedings of the Conference on Visualization ’02. pp. 395–402. IEEE Computer Society, Washington, DC (2002) Shan, J., Toth, C.: Topographic laser ranging and scanning. CRC Press, Boca Raton (2009) Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geometry 18, 305–363 (1996)
72
M. Christen and S. Nebiker
Snyder, J.P.: Map Projections: A Working Manual. U.S. Geological Survey Professional Paper 1395, U.S. Geological Survey, http://pubs.er.usgs.gov/usgspubs/pp/pp1395 (1987) Szalay, A.S., Gray, J., Fekete, G., Kunszt, P.Z., Kukol, P., Thakar, A.: Indexing the sphere with the hierarchical triangular mesh. CoRR abs/cs/0701164 (2007) Weiler, K.: Edge-based data structures for solid modeling in curved-surface environments. IEEE Comput. Graph. Appl. 5(1), 21–40 (1985) Zhou, Q., Lees, B., Tang, G.A.: Lecture Notes in Geoinformation and Cartography, chap. A Seamless and Adaptive LOD Model of the Global Terrain Based on the QTM. pp. 85–103. Springer Berlin Heidelberg, New York (2008)
Towards Interoperating CityGML and IFC Building Models: A Unified Model Based Approach ¨ stman, and Khurram Shahzad Mohamed El-Mekawy, Anders O
Abstract CityGML represents 3D urban objects that can be shared over different applications, whereas, IFC provides a very detailed semantic model for 3D building representations using constructive elements like beams, walls, etc. Attempts have been made to interoperate CityGML and IFC for seeking useful common applications. However, these efforts use a unidirectional method (mostly from IFC to CityGML) for conversion processes. A bidirectional method can lead to development of unified applications in the areas of urban planning, building construction analysis, homeland security, etc. The benefits of these applications clearly appear at the operational level (e.g., cost reduction, unified data-view), and at the strategic level (e.g., crisis management and increasing the analyses capabilities). In this paper, we present an approach for interoperating CityGML and IFC based on development of a unified building model for converting IFC to CityGML and vice versa. The conversion is a two-steps process in which a model is firstly converted to the unified model and secondly to the target model. Finally, we demonstrate the approach and outcome of each step by a hospital building case that is located in Norrt€alje City, north of Stockholm, Sweden.
M. El-Mekawy (*) Future Position X, G€avle, Sweden e-mail: [email protected] ¨ stman A. O GIS Institute, University of G€avle, G€avle, Sweden e-mail: [email protected] K. Shahzad Department of Computer and System Sciences, Royal Institute of Technology (KTH), Stockholm, Sweden e-mail: [email protected]
T.H. Kolbe et al. (eds.), Advances in 3D Geo-Information Sciences, Lecture Notes in Geoinformation and Cartography, DOI 10.1007/978-3-642-12670-3_5, # Springer-Verlag Berlin Heidelberg 2011
73
74
M. El-Mekawy et al.
1 Introduction By merging building models and geographic information models, public and private enterprises are attempting to fulfil the application demands in construction analysis, urban planning, homeland security, etc. (Benner et al. 2005; Isikdag and Zlatanova 2009a). Geometric models have been developed in both domains but semantic models are relatively few. The two most prominent semantic models are Industry Foundation Classes (IFC) and City Geography Markup Language (CityGML) (Isikdag and Zlatanova 2009a). The goal of IFC is to specify a common language for building industry technology that improves communication, productivity, delivery time, cost, and quality throughout the design, construction and maintenance life cycle of buildings (Hallberg and Tarandi 2009). IFC is then used to assemble computer readable models that contain related information to different parts of a building (Karola et al. 2002; IFC Model, http://www.iai-tech.org/ifc/IFC2x3/TC1/html/, accessed 01-2011). CityGML is however used to define information related to topological and semantic properties of a geographical area including buildings (OGC, http:// www.opengeospatial.org/; Gr€ oger et al. 2008). On one hand, IFC has been developed as an ISO standard and it has been largely accepted for the building industry (Isikdag and Zlatanova 2009a). On the other hand, CityGML has been recently adopted as an international standard for modelling cities in the Open Geospatial Consortium (OGC) and the EU (OGC, http://www.opengeospatial.org/; Gr€oger et al. 2008). This has led to major increase in the development of new application areas, software tool kits and extensions to existing systems for supporting IFC as well as CityGML. The integration of IFC and CityGML is seen today as a needed step for getting a more complete picture of 3D modelling at different levels of detail, i.e., sharing and exchanging information between building industry objects (represented in IFC) and geospatial object (represented in CityGML). Several efforts have been made to integrate CityGML and IFC. All these efforts are mainly in form of developing frameworks, extended discussion for addressing requirements, or developing conversion tools. For frameworks, the IFC for GIS (IFG) project was initiated by The Norwegian Strate Planning Authority (Statens Bygningstekniske Etat) and completed in 2007. This framework aimed to exchange building information between CAD systems and GIS using IFC. The project succeeded to create a mapping specification from XML version of IFG geometry to GML and vice versa (IFG, http://www.iai.no/ifg/index_history.html). Looking specifically on technical aspects, another framework was proposed by Nagel (2007) and aimed for algorithms that automatically transform IFC building models into CityGML models (Nagel 2007). In 2009, Isikdag and Zlatanova did complement Nagel’s framework by proposing a framework for automatic generation of buildings in CityGML using BIM based on definition of building semantics and components (Isikdag and Zlatanova 2009a). Following the holistic view of 3D city modelling aspects, an
Towards Interoperating CityGML and IFC Building Models
75
extended discussion on conceptual requirements for converting CityGML to IFC models was proposed in 2009 by a team led by Thomas Kolbe at the Technical University of Berlin (Nagel et al. 2009). They proposed a framework that integrates 3D graphics/data of buildings and urban areas (X3D, DXF, KML, COLLADA, etc.) with semantic data in a CityGML target schema. Additional to that, a few conversion environments can be seen in this area. Le´on (2009) demonstrated his team’s latest Application Domain Extensions (ADE) that integrates Building Information Model (BIM) data based on the open standard IFC into CityGML (Van Berlo 2009). Not only research efforts, but commercial software products for conversion from IFC to CityGML [e.g., IfcExplorer (http://www.ifcwiki.org/index.php/IfcExplorer_ CityGML_Export) and Safe Software (http://www.safe.com/products/desktop/ formats.php)] also contribute to the development of 3D city modelling integration. However, these attempts have either; (a) an approach for a unidirectional conversion with a focus on converting geometries (mostly from IFC to CityGML), (b) a discussion about what should be done in terms of integration, i.e., how it should be done is not sufficiently implemented yet, (c) focused on down-grading IFC to lower LoDs (LoDs) in CityGML, or (d) a discussion on the interest of rich semantics of IFC. Several studies (Benner et al. 2005; Isikdag and Zlatanova 2009a; Nagel et al. 2009) have emphasized that a formal framework for strict semantic and geometry conversion is required for a complete integration of CityGML and IFC. As a consequence, the purpose of this paper is to propose and describe a unified model oriented approach that can be used for bidirectional conversion between IFC and CityGML. The proposed approach thereby contributes towards increasing integration of CityGML and IFC for extending 3D city model applications. Geometry is highlighted as one of the main problematic concerns for integrating IFC and CityGML (Nagel et al. 2009; Isikdag and Zlatanova 2009b). However, most of the recent efforts have focused on the conceptual integration or conversion processes. Considering the vast amount of efforts for defining geometric differences and developing conversion algorithms (Lapierre and Cote 2008), this type of problem is not in our objectives. In this study we instead focus our discussion on the conceptual integration and mapping of different objects in both IFC and CityGML standards. The rest of the paper is organized as follows: Sect. 2 discusses how we approach the research problem. Building models for CityGML and IFC are presented in Sect. 3, followed by detailed discussion on UBM in Sect. 4. In Sect. 5 the two-steps approach for conversion of IFC to CityGML and CityGML to IFC is presented along with an illustrative case study.
2 Research Approach A unified model is here defined as a superset model concept that is extended to contain all the features and objects from both IFC and CityGML building models. It is an intermediate model relating objects from both models. The unified model
76
M. El-Mekawy et al.
Fig. 1 The research approach
is originally derived from the superset concepts of mathematics in 1970s led by Thomas J. Jech and other researchers (Jech 1971; Miguel et al. 2002). It has also been used in software engineering from the mid 1990s. Due to its wide acceptance, Unified Modelling Language (UML) has been selected as the modelling language for our Unified Building Model (UBM) approach. The requirements on the proposed UBM are that conversion is done with a minimum information loss and an efficient schema matching and mapping process. The approach consists of the following steps as shown in Fig. 1: (1) elicitation of IFC building model, (2) development of the UBM, (3) conversion between IFC building model and UBM, and (4) conversion between UBM and CityGML building model. Prior to discussing CityGML and IFC conversion, it is necessary to discuss each model separately.
3 CityGML and IFC Building Models In order to interoperate CityGML and IFC it is essential to develop building models for both. This section discusses the development of building models for IFC and CityGML.
3.1
IFC Building Model
IFC is an object oriented format developed by the International Alliance for Interoperability (IAI) (http://www.iai-tech.org/). It is used to facilitate interoperability in
Towards Interoperating CityGML and IFC Building Models
77
the building industry and sharing information among participants. IFCs are used to assemble computer readable models that contain data elements that represent parts of buildings and their relevant information (Lapierre and Cote 2007). There is no universally accepted building model for IFC (Kolbe et al. 2008). In this section we, however, present an IFC building model that is primarily based on the work done by the IAI and ISO in form of IFC standard documentation (IAI, http://www.iai-tech.org/), the ISO 16739 standard (http://www.iso.org/iso/iso_catalogue/catalogue_tc/ catalogue_detail.htm?csnumber¼38056) and Benner et al. (2005). From the standards we identify important concepts (Fig. 2). UML standard notations are used for developing the IFC building model. A building should have at least one storey and may have multiple storeys. Each building storey may have zero or more spaces related to it, i.e., a building structure which has only one wall is a building with zero spaces. Building elements and opening elements are subtypes of structural element. Each building element has zero or more opening elements, i.e., a wall without any door or window has zero openings, whereas each opening element (like door, window) is attached to only one building element. Figure 2 shows 12 types of building elements that can represent a building structure in IFC standard. The scope of this study is limited to building models that only represent constructed parts of buildings.
3.2
CityGML Building Model
CityGML is an open standard that has been implemented as an application schema for GML3 (OGC, http://www.opengeospatial.org/; Gr€oger et al., Open Geospatial Consortium). GML3 is the extendible international standard for spatial data exchange that has been developed and issued by the Open Geospatial Consortium
(OGC) (Cox et al. 2004) and the ISO TC211 (http://www.isotc211.org/). CityGML is developed as an open data model expressed by an XML schema. CityGML files can store and exchange virtual 3D objects and city models among applications (CityGML, http://www.citygml.org). Based on ISO 19107 (http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_ detail.htm?csnumber¼26012) and ISO 19109 (http://www.iso.org/iso/catalogue_ detail.htm?csnumber¼39891), a CityGML Building Model has been produced in the CityGML standard (Kolbe 2008). The building model (shown in Fig. 3) is an excerpted version from the CityGML standard in which only the used conversion concepts to IFC are represented, i.e., BuildingFurniture, and IntBuildingInstallation are not represented. UML standard notations are used for developing CityGML building model. CityGML is developed in five levels of detail (LoDs) which are used to represent city model objects according to required details’ level in different applications. LoDs are numbered from LoD0 to LoD4 and they have different accuracies and minimum dimensions of spatial objects that can be represented in each LoD. Individual buildings start to appear at LoD1. Therefore, we have presented CityGML building model from LoD1 to LoD4. Figure 3 represents the LoDs by different colours.
4 The Unified Building Model IFC holds more detailed information about building objects than CityGML. Therefore, IFC to CityGML conversion is a less complex task as compared to CityGML
Towards Interoperating CityGML and IFC Building Models
79
to IFC conversion. Due to that, most of previous work has aimed at IFC to CityGML conversion. However, two-ways conversion approach between CityGML and IFC has not been sufficiently explored. In this section, we present the proposed Unified Building Model (UBM) and justify the inclusion of its elements. The UBM is capable of capturing information about spatial structures and building objects from both IFC and CityGML building models. The model is, therefore, used as an intermediate step for conversion of IFC to CityGML and vice versa. UBM can be used as a starting point to support applications where information from both views (CityGML and IFC) is required for analyses. It can also facilitate modelling a database schema that is capable of capturing information that is required for all level of details. In the absence of UBM, if the application is designed at a specific LoD (e.g., LoD2) the information about higher level of detail (e.g., LoD4) cannot be acquired. To build the UBM, all classes with their concepts were initially collected from both models while omitting their relationships. Overlapping concepts were merged and new objects were created in such a way that both indoor and outdoor objects are captured. Finally, relationships between the objects were redefined to produce our UBM. UML notations are used for representing its objects and relationships between them. Figure 4 shows the UBM where different colours are used to represent different LoDs. The UBM is briefly described below. As the study is limited to building structure, the objects beyond building (such as project and site) are not represented in the model. As building is a common object for both IFC and CityGML, UBMbuilding object has been used as a starting point for the model. A building in CityGML consists of rooms, where a room is a space surrounded by different boundary surfaces. Storeys are not explicitly defined but they can be represented as an explicit aggregation of all building features on a
Fig. 4 The unified building model
80
M. El-Mekawy et al.
certain height level (Gr€ oger et al. 2008). However, in IFC, the structure is smoothly organized by breaking down a building into storeys and then into spaces that form a specific storey. In the UBM, we consider concepts from IFC as well as CityGML. A building in the UBM consists of explicit definition of storeys, at least one storey in a building. Each building storey may have zero or more spaces related to it. A space can be either opened or closed as shown in Fig. 4. The closed space represents a room which corresponds to the room definition in CityGML. In CityGML, boundary surfaces are used by the class (_BoundarySurface) for structuring the exterior shell of a building and visible surfaces of a room. However, in IFC, a room or space is built by building elements that structure and surround it. We can then highlight that some of the IFC classes (e.g., IfcWall, IfcDoor and IfcWindow) are (or handled as) boundary surfaces in CityGML. In the UBM we have used concepts from both CityGML and IFC. We propose that a boundary surface is only used when it is needed to extract the box model of a complete building, part of a building or a specific storey. Building elements, however, are used to represent the elements which exist in the building structure. As every spatial place in a building (storey or space) may have a door or a window, opening is connected to both boundary surface and building element objects. For building elements, we have defined some new concepts in such a way that all concepts from both IFC and CityGML can be covered. The main difference between building elements in CityGML and IFC is the representation of different surfaces, interior and exterior parts of a building (wall, roof and ground). Because of the need for different LoD representations and definitions of elements like (roof, ceiling, and slab) and (ground, floor and slab), we have defined the building elements as follows: l
l
l
Covering is a closing level that covers a space from the top side. It has two types; Roof for the top covering of a building or the top storey which gives the external shape of a building from above, and Ceiling for the covering of any space in a building. In both subtypes only constructed parts for a space are considered in the covering representation. Level is a walkable (not only horizontal) level that represents bottom level of a space. It has two types; Ground for the bottom level of ground floor which has a connection to the outer ground to give the external shape of a building from bottom level, and Floor for the bottom level of a space in any space of a building except the bottom (lowest) storey. Wall is a vertical/semi-vertical element that surrounds or subdivides spaces. It has three subtypes; (a) CurtainWall for the outer wall that covers a complete facade of a building or a part of it. It is usually not limited or attached to only one storey, (b) Interior for an internal wall between rooms or spaces (none of its faces has connection with the outer environment), and (c) Exterior for an external wall that has connection with the outer environment and represents a part of external facades of a building.
Towards Interoperating CityGML and IFC Building Models <
