Transaction rules for updating surfaces in 3D GIS

https://doi.org/10.1016/j.isprsjprs.2012.03.004Get rights and content

Abstract

Three-dimensional surface models representing the terrain and the outer hull of objects such as buildings and bridges support important 3D GIS applications, for example telecommunication planning and noise emission simulation. Updates of surface models often introduce errors which violate basic assumptions of users and their applications. The notion of geometric-topological consistency covers many of these assumptions. It guarantees that objects do not penetrate mutually or that objects completely cover other objects. Assuring that updates do not violate geometric-topological consistency constitutes a major challenge for 3D GIS which has not been satisfactorily met so far. This article presents a solution which is based on efficient transaction rules for updating 3D surface models. We show that these rules are safe (consistency is preserved by any rule application) and complete (any consistent surface model can be generated by successive rule applications). For both properties rigorous mathematic proofs are given.

Introduction

There is a rapidly increasing demand for three-dimensional applications of geographical information systems (GIS). Prominent examples are noise emission simulation and mapping (Czerwinski et al., 2007), urban and telecommunication planning (Köninger and Bartel, 1998), or disaster management (Zlatanova and Holweg, 2004, Kolbe et al., 2008, Gröger and Plümer, 2010). Most commercial GIS currently available are, however, limited to two or two and a half dimensions, and are not able to cope with these applications adequately. Three-dimensional systems originating from computer aided design (CAD) (Mäntylä, 1988) or computer graphics (Foley et al., 1995) do not handle semantic properties of objects adequately and do in most cases not provide the required GIS functionality. The corresponding models, boundary representation (B-Rep) or constructive solid geometry (CSG) (Mäntylä, 1988, Foley et al., 1995) are complex and difficult to handle from an algorithmic perspective.

Three-dimensional surface models are sufficient for many important 3D applications while preserving to a large degree the algorithmic and conceptual simplicity of the 2D. In those surface models, the outer hull of man-made objects like buildings, bridges, or tunnels are integrated into the terrain (see Fig. 1). In Gröger and Plümer, 2003, Gröger and Plümer, 2005, Gröger and Plümer, 2011a, Gröger and Plümer, 2011b, we introduced the concept of a 2.8D map, which extends digital terrain models (Okabe et al., 2000). They are often called 2.5D and are restricted because (x,y)-locations have exactly one height value. This restriction is omitted in 2.8D maps, allowing for the representation of vertical walls and protrusions like balconies, ledges or roof overhangs. Hence, the outer hull of most urban objects can be represented. The geometry is three-dimensional, whereas topology remains two-dimensional. From a mathematical point of view, a 2.8D map basically is a 2-manifold (for details, see Mäntylä, 1988 and Hatcher, 2001). In addition, 2.8D maps allow for the modeling of overpasses like bridges, viaducts, tunnels and pedestrian underpasses, which are captured by the topological notion of a handle. The term ‘2.8D map’ wants to express that the model exceeds 2.5D, but is less than three-dimensional.

In many cases data sets which claim to be 2.8D maps in fact do not fulfill these requirements. Well-known errors are mutually intersecting, self-intersecting or self-penetrating boundaries of objects, gaps in boundaries of objects, or objects like buildings floating above the terrain. Hence, there is an urgent need for methods and tools for checking effectively and efficiently whether data sets are geometric-topologically consistent, i.e. are 2.8D maps. The declarative mathematical definition of a 2.8D map in terms of a 2-manifold, however, is not suitable to be checked effectively by automatic procedures. Hence, we have provided an alternative axiomatic characterization of 2.8D maps (Gröger and Plümer, 2003, Gröger and Plümer, 2005, Gröger and Plümer, 2011b). These axioms can readily be implemented in available database systems and are equivalent to the declarative mathematical definition of a 2.8D map: axioms have been proven to be complete (each violation of the declarative mathematical definition of a 2.8D map is detected by the axioms) and correct (each violation of an axiom is in fact a violation of the definition).

The axioms for 2.8D maps are suitable for checking the consistency of a data set as whole. Assuring that an update of data does not affect consistency is a different problem. Since our natural and man-made environment changes frequently, data representing this environment have to be updated accordingly in order to reflect those changes. Of course, up-to-dateness is an important quality element of spatial data, and the usage of out-dated data sets may lead to erroneous results that do not correspond to reality. More local and more specific concepts are required to assure that updates, which typically have local impacts, maintain consistency. Globally checking consistency of a large dataset after each local update is not feasible from an efficiency point of view. Instead, we propose to employ transaction rules to obtain consistent updates. Transaction rules, which initially emerged from the field of active databases (Widom and Ceri, 1996), locally check local updates by restricting the axioms to that part of the data set which is actually affected by the changes. Furthermore, transaction rules complete imperfect update requests in a consistent way and reject inconsistent updates. Hence, a crucial property of transaction rules is that consistency is preserved for arbitrary applications of the rule. Such rules are called safe. Another important property is the usability and flexibility of rules in the sense that each (consistent) 3D city model can be generated by rule applications. Such a set of rules is called complete.

Safe and complete transaction rules for updates of 2D datasets have been introduced in Gröger and Plümer (1997). Likewise, rules covering the case of updating three-dimensional solid models (Gröger and Plümer, 2011a) have already been developed (Gröger and Plümer, 2012). Solid models extend surface models since they enable the modeling of interior structures (e.g., stories, rooms). However, surfaces are an important component for solid models, since a solid is bounded by a surface and since solid models require the representation of the terrain as a surface. The transaction rules for solids (Gröger and Plümer, 2012), however, do not cover the case of 3D surfaces. These rules split a solid by the insertion of a 3D surface into two solids. An example for such a rule application is the splitting of a room into two rooms. An inverse rule merges two neighboring solids by deleting a 3D surface. In contrast, the rules for 3D surfaces presented in this paper maintain a single, 2-manifold 3D surface, which does not delimit a solid. In the rules for solids, the question how to obtain a 3D surface for splitting a solid is explicitly left open. Likewise, the completeness of the rules for solids (Proposition 7 in Gröger and Plümer, 2012) is based on the completeness result for 3D surfaces, which has not been proven yet. Hence, the issue of safe and complete transaction rules for surfaces in 3D has so far remained unsolved. This solution is presented by the paper at hand. The main contribution is a rigorous mathematical derivation of a set of transaction rules for the generation of arbitrary 3D surfaces. Safety and completeness of all rules is proven mathematically, guaranteeing the reliability and the flexibility of our method. Some of these rules have already been mentioned in Gröger and Plümer (2009), but no mathematical derivation has been given so far.

The topological concept of a handle, which allows representing objects like bridges, tunnels or arcades in 3D surface models (c.f. Fig. 1), plays a crucial role for surface models and transaction rules. In Gröger and Plümer (2012) we have characterized handle objects in terms of different types of cycles of the surface. In the paper at hand, we transfer that static characterization of handles to the dynamic case of the insertion and deletion of handles.

Identifying the adequate level of granularity poses a major challenge when creating transaction rules. If the rules are too fine-grained, the proof of the safety is simple, but not all operations preserving consistency are permitted. Hence, those rules are not complete. The rules defined by Gold (2003) and Tse and Gold (2002), for example, are restricted to inserting prism-shaped, straight tunnels (see Section 5). If due to an obstacle a non-straight tunnel, i.e. a tunnel with an angle, has to be constructed, the rules fail and completeness is affected. On the other hand, if rules are too coarse, they will be too complex to handle and will not permit an efficient safety check. We define the right level of granularity by the notion of a composite surface, which is flexible with regard to geometry, but restricted topologically. In this approach, the occurrence of nested structures, and particularly of nested handles, is a major source of complexity. The proofs of completeness in Section 4.5 cope with this complexity.

The focus of the transaction rules presented in this paper is set on topology and geometry. Concepts for the definition of semantical objects based on surface models have been presented for non-handle objects like buildings in Gröger and Plümer (2005), and for handle objects (tunnels, bridges) in Gröger and Plümer (2011b). The contents of the semantical model, e.g., the object type (residential building or industrial building for example), or attributes (e.g., the year of construction or the building function) are defined in semantic 3D city models such as CityGML (Gröger et al., 2008, Kolbe et al., 2008).

The rest of this paper is organized as follows: The second section will define basic mathematical notions which are relevant for surface modeling. The third section will specify the surface model (termed 2.8D maps) and provide an axiomatic characterization of such models, which provide the base of the transaction rules. The rules for 2.8D maps will be introduced in Section 4. First the rules for the 2D case (which have been published earlier) will be briefly recalled. Second we will outline the 2.8D rules and introduce two rules that generate and modify 2.8D maps, at the same time retaining the number of handles. Afterwards, rules for generating and removing handles will be developed. The safety of each rule as well as the completeness of the whole set of rules will be formally proven. After having compared our approach to related work on checking consistency of updates in GIS in Section 6, this paper will end with concluding remarks and a discussion of open questions and further work.

Section snippets

Basic mathematical notions

In this section, we recall notions from mathematical topology (Alexandroff, 1961, Mäntylä, 1988, Armstrong, 1997, Hatcher, 2001) to fix terminology. Particularly used are standard notions from graph theory (Harary, 1969). We consider graphs that are embedded in Euclidean space R3 by assigning a 3D position to each vertex. Such an embedding defines faces as atomic areal entities, which in our case are planar, i.e. are located in the same plane. In our case, faces are bounded by simple cycles.

Consistency of surfaces in 3D

In Gröger and Plümer, 2003, Gröger and Plümer, 2005, we have introduced the concept of 2.8D maps for the representation of the terrain and the outer hull of buildings, including vertical walls and overhangs. In Gröger and Plümer (2011b) the model is extended to handle objects like tunnels and bridges. Intuitively, a 2.8D map can be imagined as a cloth draped over the terrain and man made structures. More formally, a 2.8D map is a 2-manifold, connected cell complex embedded in 3D space, which

Transaction rules for 2.8D surfaces

This section introduces the transaction rules which enable consistent updates of 2.8D surfaces, e.g., the deletion or insertion of a building, the addition of a balcony to a building or the modification of the roof shape of a building. The transaction rules exploit the locality of updates, identify the region where violations may occur and restrict the consistency checks to that region. In that sense, a transaction rule is a specific, regionally restricted version of the axioms, tailored for a

Related work

Transaction rules for the 2D case have been developed in Gröger and Plümer, 1997, Kufoniyi, 1995 and Kufoniyi et al. (1995), and for the special case of simplicial complexes (i.e. cell complexes consisting of triangles) in Egenhofer et al. (1989). For constructing 3D surface models stepwise, the well-known Euler Operators (Mäntylä, 1988, Mortenson, 1997) have been introduced. However, Euler Operators only preserve topological consistency and do not focus on geometric-topological consistency:

Conclusions

This paper provides a rigorous mathematical treatment of a set of transaction rules that enables updates of 3D surface models which reflect changes of our urban and rural environment. These rules maintain consistency of the surface model once given (safety) and provide the flexibility to generate arbitrary consistent surface models (completeness). They aim at constructing and updating surfaces embedded in 3D space and modeling the terrain and the outer hull of objects. They allow for the

Acknowledgements

We would like to thank Michael Kneuper for his assistance in preparing the illustrations.

References (40)

  • G. Barequet et al.

    On triangulating three-dimensional polygons

    Computational Geometry: Theory and Applications (CGTA)

    (1998)
  • G. Gröger et al.

    Topology of surfaces modelling bridges and tunnels in 3D-GIS

    Computers, Environment and Urban Systems

    (2011)
  • P. Alexandroff

    Elementary concepts of topology

    (1961)
  • M.A. Armstrong

    Basic Topology, Corr. 5. printing

    (1997)
  • P. Boguslawski et al.

    Construction Operators for Modelling 3D Objects and Dual Navigation Structures

  • P. Boguslawski et al.

    Euler Operators and Navigation of Multi-shell Building Models

  • A. Czerwinski et al.

    Sustainable SDI for EU noise mapping in NRW – best practice for INSPIRE

    International Journal for Spatial Data Infrastructure Research

    (2007)
  • Egenhofer, M.J., 1989. A formal definition of binary topological relationships. In: Litwin, W., Schek, H.-J. (Eds.),...
  • Egenhofer, M.J., Frank, A.U., Jackson J. P., 1990. A Topological Data Model for Spatial Databases. In: Buchmann, A.P.,...
  • J.D. Foley et al.

    Computer Graphics: Principles and Practice

    (1995)
  • M. Garey et al.

    Computers and Intractability. A Guide to the Theory of NP-Completeness

    (1979)
  • C. Gold

    But is it GIS?

    Journal of Geospatial Engineering

    (2003)
  • Gröger, G., Kolbe, T.H., Czerwinski, A., Nagel, C. (Eds.), 2008. OpenGIS® City Geography Markup Language (CityGML)...
  • Gröger, G., Kolbe, T.H., Schmittwilken, J., Stroh, V., Plümer, L., 2005. Integrating versions, history and...
  • G. Gröger et al.

    Provably Correct and Complete Transaction Rules for GIS

  • Gröger, G., Plümer, L., 2003. Exploiting 2D Concepts to Achieve Consistency in 3D GIS Applications. In: Hoel, E.,...
  • G. Gröger et al.

    How to get 3-D for the price of 2-D-Topology and Consistency of 3-D Urban GIS

    Geoinformatica

    (2005)
  • Gröger, G., Plümer, L., 2009. Updating 3D City Models – how to preserve geometric-topological consistency. In: Agrawal,...
  • G. Gröger et al.

    Derivation of 3D indoor models by grammars for route planning

    Photogrammetrie, Fernerkundung, Geoinformation - PFG

    (2010)
  • G. Gröger et al.

    How to achieve consistency for 3D city models

    Geoinformatica

    (2011)
  • Cited by (15)

    • On the knowledge gain of urban morphology from space

      2022, Computers, Environment and Urban Systems
    • Combining CityGML files and data-driven models for microclimate simulations in a tropical city

      2020, Building and Environment
      Citation Excerpt :

      In this study, the STEVE tool was used to calculate the urban morphology data. As mentioned in Section 1, the original CityGML can be defined in five LODs [10]. The STEVE tool can accept LOD 1 models, including LOD 1.1, LOD 1.2, and LOD 1.3, but cannot calculate the urban morphology data of overly complex models [31].

    • A GIS-based method for modeling urban-climate parameters using automated recognition of shadows cast by buildings

      2016, Computers, Environment and Urban Systems
      Citation Excerpt :

      National mapping agencies and, on a local scale, city municipalities and regional councils, have manage to develop sophisticated national and local GIS geodatabases to maintain and update the representation of urban features. These geodatabases are used to support research and spatial analysis of urban phenomena, infrastructure management, urban planning, disaster management, visualization and decision-making (Breunig & Zlatanova, 2011; Gröger & Plümer, 2012). Sophisticated mapping technologies, such as laser scanning, solid modeling and remotely-sensed imagery are used for reconstructing buildings and other urban features in 3D (Heo et al., 2013; Sahin et al., 2012; Tong et al., 2012).

    • Development of validation rules to support digital lodgement of 3D cadastral plans

      2013, Computers, Environment and Urban Systems
      Citation Excerpt :

      To date, research on validation rules for spatial data has been based on the requirement to ensure that the data can be safely loaded into a specific database or format. Contemporary studies on validation have identified rules for the Oracle database management system (Kazar, Kothuri, van Oosterom, & Ravada, 2008), for 3D city models (Gröger & Plümer, 2012a, 2012b), and for a 3D boundary representation (Thompson & van Oosterom, 2011a). The axioms presented by the latter (see Table 2) can be used as validation rules, and provide a foundation for the validation processes required to assess the veracity of the often complex geometry that makes up 3D cadastral parcels.

    • CityGML - Interoperable semantic 3D city models

      2012, ISPRS Journal of Photogrammetry and Remote Sensing
    View all citing articles on Scopus
    1

    Tel.: +49 (0) 228 73 1750.

    View full text