How to achieve consistency for 3D city models

Abstract

Consistency is a crucial prerequisite for a large number of relevant applications of 3D city models, which have become more and more important in GIS. Users need efficient and reliable consistency checking tools in order to be able to assess the suitability of spatial data for their applications. In this paper we provide the theoretical foundations for such tools by defining an axiomatic characterization of 3D city models. These axioms are effective and efficiently supported by recent spatial database management systems and methods of Computational Geometry or Computer Graphics. They are equivalent to the topological concept of the 3D city model presented in this paper, thereby guaranteeing the reliability of the method. Hence, each error is detected by the axioms, and each violation of the axioms is in fact an error. This property, which is proven formally, is not guaranteed by existing approaches. The efficiency of the method stems from its locality: in most cases, consistency checks can safely be restricted to single components, which are defined topologically. We show how a 3D city model can be decomposed into such components which are either topologically equivalent to a disk, a sphere, or a torus, enabling the modeling of the terrain, of buildings and other constructions, and of bridges and tunnels, which are handles from a mathematical point of view. This enables a modular design of the axioms by defining axioms for each topological component and for the aggregation of the components. Finally, a sound, consistent concept for aggregating features, i.e. semantical objects like buildings or rooms, to complex features is presented.

Introduction

3D city models play a more and more important role in GIS. These models are needed for an increasing number of GIS applications, e.g. telecommunications planning, noise emission simulation and mapping, urban planning, vehicle navigation, indoor–outdoor navigation, or escape route derivation in disaster management. Typically, providers and users of data are different. One the one hand, the user has to check whether the data is suitable for his purposes. Thus he needs models, methods and tools to specify his requirements and to check whether they are fulfilled. On the other hand, the provider has an interest to demonstrate the quality of his data—not only with regard to geometrical accuracy, but also with regard to semantics and consistency. Hence, both the providers and the users need models and methods to verify desired properties of the data. Error freeness and particularly consistency—compliance of data with the assumptions of the underlying model—are essential prerequisites for the usability of data and the viability of a spatial data infrastructure. This paper deals with models and methods for checking the consistency of 3D city models.

3D city models differ with regard to their structural complexity. For some applications of 3D city models, e.g. telecommunications planning or visualization, the representation of the (geometry of the) visible surface of the terrain and of urban structures is sufficient. Digital surface models [38] are appropriate for these tasks. From a mathematical point of view, such surfaces are 2-manifolds, i.e. connected, purely areal objects, which do neither penetrate nor intersect themselves. Bridges, tunnels and arcades, which are called handles in mathematics [2], make such surfaces more complex [48].

For more advanced applications of 3D GIS, surface models are not sufficient. These applications require among others the computation of the volumes of the objects. Volumes are needed for many purposes: heating costs, the amount of oxygen in an emergency case, etc. Thus, an explicit representation of solids is required. Neighboring solids have common boundaries which have to be represented. Furthermore, rooms are connected by doors, stairs etc. The explicit representation is fundamental for indoor applications, e.g. the derivation of escape routes. Again, surface models are not appropriate for these purposes. They require the representation of rooms as volume objects, of storeys as aggregation of rooms together with doors, storeys and staircases. Subsurface structures like cellars have to be considered as well, and all buildings have to be integrated smoothly in the surface representing the terrain. In such solid models that represent cities two aspects are closely connected: the GIS viewpoint, modeling the terrain and the visible hull of cities, and the CAD viewpoint, representing internal structures of buildings.

The problem of integrating GIS and CAD has been discussed in the last years [e.g., 31, 49, 53]. Languages for the representation of 3D city models such as CityGML [17, 30] cover both aspects, thereby enabling indoor as well as outdoor applications and combinations of both, e.g. planning of rescue actions in disaster scenarios.

Languages for 3D city models such as CityGML provide several options for the representation of topology. The same is true for the standard ISO 19107 ‘Spatial Schema’ [24]. However, these models do not consider the question of a formal representation and verification of topological consistency. This is the major motivation for this paper.

In order to specify consistency, spatial relations between the components of a 3D city model have to be identified, formalized, and verified. Two questions arise: First, what are the spatial relations between components of a 3D city model which have to be assured? And second, how are those relations specified and formalized? One possible answer to the second question is the well-known 4-intersection model developed by Max Egenhofer in the early nineties [8]. It provides a formalism for the representation of topological relations, which is also employed in standards for spatial query languages [26] and in commercial databases, e.g. in Oracle Spatial [39]. It is entirely based on two notions from point set topology: the interior and the boundary of point sets. At first, mainly applied to the 2D case, it has been generalized to 3D solids which have bounding surfaces and interiors as well [54]. Both notions have an intuitive interpretation when surfaces embedded in the 2D Euclidean plane or solids embedded in the 3D Euclidean space are considered.

Rooms and staircases, for instance, are either disjoint or they touch. The same is true for pairs of storeys and for pairs of buildings. Between storeys and buildings, and between rooms and storeys, one of the relations inside or coveredBy holds.

For checking consistency, however, this characterization which uses the notions of the 4-intersection model cannot be implemented directly. It involves the notions of boundary and interior, which are defined as infinite point sets. Appropriate finite representations are needed. The verification of consistency requires effective conditions (also called axioms) which may effectively—better efficiently—be checked. Such axioms, however, must be equivalent to the mathematical notion, which is not effectively implementable to guarantee the reliability of the method. Hence, the formulation of the axioms must be transparent and comprehensible in order to be able to proof this equivalency. The equivalency consists of two opposite aspects: completeness and correctness. Completeness means, that the validity of the axioms implies the mathematical notion, while vice versa axioms are correct if they are implied by the mathematical notion.

Another requirement for city models is space coverage. The space of a building is completely filled by rooms, doorways and other internal substructures. While disjointness is covered by Egenhofer’s relations, space coverage is not. The volumes of the interior objects could be balanced, but apart from practical difficulties such as specification the size of the walls it is not satisfactory from a theoretical point of view. It provides only necessary, but not sufficient conditions. It can prove the presence, but not the absence of errors.

The problem of checking the consistency of 3D models in the context of GIS, Computer Graphics and Computational Geometry has been addressed by several authors in the last 20 years. The methods presented by [34] and [37] are restricted to single solids as component of 3D models. However, not all corresponding errors are detected by these methods. The approach by Molenaar [36] is more comprehensive; he gives conventions to check whole 3D models, but again this method provides necessary but not sufficient conditions. Euler Operators [34], which are discussed in Solid Modeling and CAD, preserve the topological consistency of local modifications once this consistency is given, but do not provide general rules to check consistency. The same is true for the adoption of Euler Operators to GIS [14, 48].

The contribution of this paper is a model and method for the verification of the consistency of 3D city models. We identify the components of 3D city models—surfaces of different topology—and describe how those components interact. The single components and the whole city model are characterized by well-established mathematical, mainly topological notions on one hand, and by effective axioms on the other. Both characterizations are provably equivalent—complete and correct—guaranteeing the reliability of the method. The efficiency of the method stems from the fact that most of the axioms can be checked locally, separately for each component. This is a surprise since consistency checking in general is a global problem: each solid, surface, line or point may penetrate each other.

The rest of this paper is organized as follows: The second section defines basic notions from point set and algebraic topology as well as from graph theory, and gives a short survey on existing 3D models in GIS and on existing methods to check the consistency of those models. The third section presents the components of 3D city models: surfaces for the representation of the terrain, which are topologically equivalent to a disk, and surfaces bounding solids, which are topologically equivalent to a sphere. Both types are characterized axiomatically. The case of handles, which does not cause any problems with regard to consistency checking, is discussed separately. In the fourth section, both types of surfaces are combined to define a 3D city model. This model is described both on a mathematical level, which is not implementable immediately, and by effective axioms, where both representations are proven to be equivalent. Based on these models, features are defined which specify the semantics of objects. This is the topic of the fifth section. This paper ends with concluding remarks and a discussion of open questions and further work.

Basic notions and concepts

This section recapitulates mathematical notions from graph theory [22] and mathematical topology [1, 2, 34] as base of the concepts and methods presented in this paper, and fixes terminology.

Topology

Topology as a branch of mathematics provides the appropriate notions for classifying surfaces¹ and solids to model urban objects. A fundamental notion in topology is the topological space which is a set M together with a set N of subsets of M, called neighborhoods, where i) each element m ∈ M is in a neighborhood n ∈ N, and ii) the intersection of two neighborhoods of m ∈ M is or contains a neighborhood of m. On topological spaces, topological invariants are defined, which are preserved by applying topological transformations, that are called homeomorphisms. These are continuous, bijective mappings between topological spaces, whose inverse mapping is continuous, too. Homeomorphisms map neighborhoods to neighborhoods.

Homeomorphisms are related to topological spaces in general. In this paper, the focus is on Euclidean spaces as special cases, where a metric, i.e. a distance between points of the underlying set ${\mathbb{R}^2}$, resp. ${\mathbb{R}^3}$, is defined. In 3D Euclidean space, a surface embedded in ${\mathbb{R}^3}$ is defined as a continuous, differentiable mapping from ${\mathbb{R}^2}$ to ${\mathbb{R}^3}$. 2-manifold surfaces play a decisive role in geometrical and topological modeling [12, 23, 34, 36, 37]. A 2-manifold is a topological space, where each point has a neighborhood which is topologically equivalent to an open two-dimensional disk. An example for an open disk is depicted in Fig. 1a). Examples for 2-manifolds are given in Fig. 1: an open disk itself (a) is a 2-manifold, as well as a sphere (b) and an open cylinder surface (c). The surfaces d) and e) are counterexamples: the neighborhoods of the points on the black line in d) and of the black point in e) are not topologically equivalent to an open disk.

Fig. 1

a open disk, b sphere and c open cylinder surface as examples for 2-manifolds. d and e are non 2-manifold surfaces

An important topological invariant is the number of boundaries of a surface. An open disk (Fig. 1a) has one boundary, whereas the number of boundaries of an open cylinder surface (Fig. 1c) is two and of a sphere (b) zero. Surfaces with two or more boundaries can be used to model tunnels or bridges, since they may—if they are integrated in a larger surface—form so-called handles (see next paragraph). Surfaces without boundaries are closed ²; they enclose a volume completely and hence are used in geometrical modeling to represent solids [34, 37]. An example for a closed surface is the sphere (the shell of a ball) or a cuboid (the shell of a three-dimensional, rectangular box).

The number of handles is another topological invariant of surfaces. Handles in surfaces are used to model bridges, tunnels and arcades. The number of handles is given by the maximal number of closed, continuous, non self intersecting and mutually non-intersecting curves on surfaces, the cutting of which preserves the connectivity of the surface. This number is also called the genus of the surface.

Figure 2 illustrates this concept. The sphere (a) is divided into two parts by each cutting curve, thus the genus and the number of handles is zero. If the torus (b) is cut by one curve as depicted in the figure its connectivity is preserved. Each additional curve cutting the surface, however, destroys its connectivity: The genus is one. Hence, a torus has (or is) one handle.

Fig. 2

Characterization of handles by counting the maximal number of cutting curves preserving the connectivity of the surface. a Sphere: zero cutting curves, zero handles. b Torus: one cutting curve, one handle

The genus of a surface can be computed by Euler’s formula [37] effectively under the assumption that the surface has a graph structure (c.f. Section 2.2). Let $\left| V \right|,\,\left| E \right|,\,{\text{and}}\,\left| F \right|$ be the numbers of vertices, edges and faces of the connected graph representing the surface. For graphs which are connected and surrounded by one unbounded outer face (c.f. Section 2.2), the genus G, which is equal to the number of handles, can be derived by the formula

$$ G = \left( {2 - \left| V \right| + \left| E \right| - \left| F \right|} \right)/2 $$

The same formula is valid for closed surfaces, i.e. surfaces enclosing a volume completely. Another case is a surface which is not closed, and where the unbounded outer face is missing. The term composite surface will be used later in this paper to denote such 2D point sets. For such surfaces, the following version of Euler’s formula holds:

$$ G = \left( {1 - \left| V \right| + \left| E \right| - \left| F \right|} \right)/2 $$

A surface is orientable, if two opposite sides of the surface can be distinguished. For the general case a more formal definition of orientability is given in [2]. Well-known examples for non-orientable surfaces are the Möbius strip and the Klein bottle. Both are depicted in Fig. 3.

Fig. 3

Non-orientable surfaces: a Möbius strip. b Klein bottle

For surfaces which are composed of faces bounded by edges, orientability means that the orientations of incident faces coincide. Orientability of such surfaces can be checked by a simple algorithm called Möbius procedure [3, 37], which is as follows: First, the set of edges is duplicated, such that each face gets its own edges in its boundary. Then for each face the edges are orientated consistently, either clockwise or counter-clockwise. If there exists such an orientation for each face such that all pairs of coincident edges have opposite orientation, the surface is orientable, otherwise it is not orientable. This procedure is referred to as Algorithm 1 in this paper.

In the case of closed surfaces, a result from mathematical topology states a correlation between orientability of surfaces and its penetration-free embedding in Euclidean 3D space. This theorem generalizes the observation that the Klein bottle has no penetration-free embedding in ${\mathbb{R}^3}$:

Theorem 1

Each closed surface, which has a penetration-free embedding in${\mathbb{R}^3}$, is orientable [3].

This proposition is implied by the well-known classification theorem for closed surfaces [46] which states that each closed surface is homeomorphic to either a sphere, a closed surface with k handles, or the projective plane. The projective plane is a surface which is not orientable, and has no penetration-free embedding in ${\mathbb{R}^3}$, similar to the Klein bottle. It can be deduced that a closed surface is determined completely, up to homeomorphism, by its genus and its orientability. Since the sphere and closed surfaces with k handles are orientable and have penetration-free embeddings in ${\mathbb{R}^3}$, Theorem 1 is implied.

The Möbius strip, which was already discussed in Section 2.1, is embeddable in ${\mathbb{R}^3}$ without penetrations, but is not a closed surface, thus the preconditions of Theorem 1 are not met.

In geometrical modeling, solids representing buildings, rooms or other volume objects are described mathematically by rigid bodies. A rigid body is a bounded, regular and semi-analytical subset of ${\mathbb{R}^3}$. Regularity excludes non-volume elements like point or line enclaves, while semi-analytical sets are constructed by combining analytical sets—which are the range of analytical functions, particularly polynomials—by the set operations difference, intersection and union. In boundary representation schemes, which are widely used in Geometrical Modeling, CAD and GIS, solids are represented by their bounding surfaces. Rigid bodies are exactly those bodies which are bounded by a single, closed 2-manifold [3].

Graph theory

A graph G(V, E) consists of a set V of vertices and a set E of edges. An (undirected) edge e is defined by a two-element set {v ₁, v ₂} of end vertices; e is called incident to v ₁ resp. v ₂ and vice versa. The vertex v ₁ is adjacent to v ₂ and vice versa. The degree of a vertex, degree(v), is the number of incident edges. A sequence of edges where two consecutive edges are incident to a common vertex is called a path. The vertex where the path starts is called start vertex, while the last vertex is the end vertex of the path. A cycle is a path where start and end vertex are identical. It is simple, if beside the start and the end vertex no other vertex occurs more than once. A graph is called connected, if there is a connecting path for each pair of vertices. A graph is non-separable, if it is connected and remains connected after the removal of an arbitrary vertex.

A graph can be embedded in the Euclidian plane ${\mathbb{R}^2}$ by assigning a 2D position to each vertex. Edges are represented by straight line segments. A graph is plane, if each intersection point of two edges is a common end vertex of both edges. Such an embedding defines faces as atomic areal entities. A face f is mathematically defined by the following property: f is a maximal part of the plane such that for any two points p ₁ and p ₂ in f there is a continuous (not necessarily straight) line from p ₁ to p ₂ which does neither cross nor touch any edge of the graph. Faces are bounded by simple cycles of the graph. The edges in the boundary are incident to the face and vice versa. By assigning a 3D position to a vertex, a graph is embedded in the Euclidean space ${\mathbb{R}^3}$. The notion of a face can be generalized to this case by forcing the edges incident to a face to be located in the same plane; such faces are planar.

Algebraic topology: cell complexes

Algebraic topology [1, 23] is the base of many data models in GIS, CAD and Computer Graphics. This branch of mathematics provides rules to construct complex objects from primitive ones, modeling the touching of spatial objects explicitly, thereby providing a clean interface between objects without any penetrations. Primitives are nodes, edges, faces and solids, also called 0-cells, 1-cells, 2-cells and 3-cells, respectively. Each n-cell is bounded by (n - 1)-cells, which are the boundary of the cell. A cell complex [1, 23] is an aggregation of cells where the following condition holds: The intersection of two cells in the cell complex is either empty, or it is a cell which is part of the boundaries of both cells.

Figure 4 gives two examples of cell complexes. In a), the intersection of the 2-cells A and B is the 1-cell depicted thick. It is part of the boundary of both A and B. The intersection of the two 3-cells in b) is given by the 2-cell, which is colored dark, and by the gray 0- and 1-cells; both are part of the boundaries of both 3-cells.

Fig. 4

Cell complexes, consisting of a two 2-cells, and b two 3-cells

3D models in GIS

Three-dimensional models have been considered in GIS for about fifteen years. All those models are boundary representations (see Section 2.1), which differ mainly with regard to the primitives used—node, edge, face, and body/solid. Topological models are mostly based on the mathematical concept of cell complexes (cf. Section 2.3), while geometrical models neglect the explicit representation of topological relations between primitives and allow for primitives whose interiors or boundaries may penetrate mutually.

A survey of topological models for GIS can be found in [53], whereas in [9] the requirements and benefits of such models for GIS applications are identified. The first data model from a historical perspective was the Formal Data Structure (FDS) presented by Molenaar [34]. He distinguishes the primitives nodes, arcs/edges, and faces. Volumes are called bodies and exist on a feature level. Faces are bounded by edges/arcs, and each arc has a start and an end node. Each face has a body on the left and a body on the right side. Flick [11] extends the FDS by introducing bodies as topological primitives. The Urban Data Model (UDM) [5] and the Simplified Spatial Schema [54] modify this model by omitting the explicit representation of edges. The topology model of the standard ISO 19107 Spatial Schema [24], which is particularly implemented by the exchange format Geography Markup Language (GML 3) [44], supports topological primitives for all dimensions and realizes the topological relations of cell complexes. In contrast to all other models mentioned so far, the aggregation of solids to composite solids is supported. A topological model which is based on simplicial complexes—the restriction of cell complexes to triangles and tetrahedrons—is the TEN structure [41]. It can be implemented in relational databases very efficiently [40].

These topological models are defined in a non-algorithmic fashion. Effective axioms have been given by [35]. In this paper the conventions claim to assure the consistency. There are examples, however, which demonstrate that this is not the case [15, 16]: The conventions are correct, but not complete, since the mutual penetration of bodies is not avoided. The same holds true for the conditions defined by [34], which were developed in the context of solid modeling. These conditions are restricted to single solids bounded by a 2-manifold surface, and do not cover the consistency of complexes of solids.

Prominent examples for geometrical models in GIS are the Simple Features [25] issued by the Open Geospatial Consortium (OGC), which are implemented in the exchange language GML 2, 3D Shapefiles, a data format used in tools from ESRI, and the geometry model of the standard ISO 19107 Spatial Schema [24], which GML 3 is based on. In contrast, there are purely geometrical or graphical models without any semantical information. Examples are VRML [50], X3D [52], KML [21] and Collada which is used by Google Earth, and U3D [7], which is used for embedding 3D graphics in pdf documents.

Consistency of components of 3D city models: solids and surfaces

A 3D city model is built from surfaces and solids, which again are bounded by surfaces. The terrain and the visible hull of urban structures are represented by a surface, while buildings—above and below surface—and internal structures like rooms, cellars, storeys and staircases are modeled by solids. This section discusses both components separately by giving a mathematical characterization which is not effectively checkable as well as an axiomatic characterization, which both are proven to be equivalent. The consistent combination of both kinds of surfaces which yield a 3D city model, is presented in Section 4.

Surfaces representing the terrain

Surfaces provided by most commercial GIS are restricted to 2D or 2.5D, i.e., each position on the earth’s surface has at most one elevation value. Such surfaces are not sufficient for modeling mountainous regions with scarps and overhangs or urban scenarios, where vertical walls, balconies, projections and roof overhangs have to be represented. Extensions of 2.5D surfaces coping with these phenomena are Digital Surface Models (DSM) [38]. An approach characterizing the mathematical concept of a DSM is the 2.8D map [19, 20, 33]. A 2.8D map is a 2D surface embedded in 3D space. This is suitable to model the visible surface of the terrain and of urban objects. It can be considered as a rubber sheet which is draped over the urban landscape. This sheet may not be torn or folded; this property is specified mathematically by the concept of a 2-manifold (c.f. Section 2.1), which avoids self-intersections, holes or gaps in the surface. The topological structure of a 2.8D map is represented by vertices, edges and planar faces of a graph embedded in ${\mathbb{R}^3}$. Formally, a 2.8D map is specified as follows [20]:

Definition 1

(2.8D map) A 2.8D map is a non-separable graph G(E,V), which is embedded in ${\mathbb{R}^3}$. Edges are represented by straight line segments of non-zero length, which are mutually non-intersecting. The embedding defines a set F of faces. There is exactly one unbounded face in F (called OUT); all other faces are planar and bounded. The set of all faces, edges and vertices forms a tessellation of a surface, which is a single, orientable 2-manifold of genus zero.

Non-separability of the graph asserts that all faces have an outer boundary which is a simple cycle (c.f. Section 2.2). The face OUT is a special case; it has an inner boundary which is a simple cycle, and which surrounds the other faces, edges and vertices of the map. Note that OUT is the only face in which the boundary does not have to be planar.

Operational, reliable procedures are needed in order to check whether a data set satisfies the requirements of Definition 1, and to detect violations thereof. The mathematical concept given in the definition is not suitable for this task, since it does not provide a base for effective procedures. This is mainly due to the notion of a 2-manifold as an infinite point set. We propose an alternative characterization of 2.8D maps, which are called axioms or consistency constraints, which may be implemented immediately to check consistency. These axioms are complete and correct, i.e. equivalent to the mathematical concept of a 2.8D map (Definition 1). Hence, each error is detected by the axioms, and each violation of the axioms is in fact an error, i.e. a violation of the 2.8D map properties.

The axioms for 2.8D maps are given in Table 1 (c.f. [20]). They can be implemented by using standard techniques from computer graphics [12], computational geometry [45] or graph theory [22, 28]. The axioms 1, 2, 4, 7, 11 and 13 can be implemented by counting the numbers of graph elements that are related by incidence associations. Axioms 3 and 8 require graph-theoretical methods to traverse the boundaries of faces [22], and again the connectedness is a graph-theoretical property which can be checked by simple graph algorithms like the Dijkstra’s algorithm [6]. Geometrical methods have to be employed to check axioms 6, 9 and 10, e.g. the 3D version of the scan-line algorithm [45] for the detection of intersections between edges, ray tracing methods [12] for checking whether edges penetrate faces, and linear algebra methods for checking the planarity of faces. Orientability (axiom 14) can be stated by using the Möbius procedure (c.f. Section 2.1).

Table 1 Complete and correct axioms for 2.8D maps

Note that axiom 3 excludes two 2-manifolds joining in a single, common node, thereby yielding a non-manifold surface. This error case is the 3D generalization of two manifold surfaces embedded in ${\mathbb{R}^2}$ which touch in a single node; an example was already given in Fig. 1e).

The equivalence of the axioms and the definition of 2.8D maps is stated by the following theorem:

Theorem 2

The axioms given in Table 1 are complete and correct for 2.8D maps.

For the completeness part, the tessellation and 2-manifold properties are implied by axioms 8 and 10 for faces, by axioms 4 and 6 for edges and their neighborhoods, and by 1 and 3 for vertices and their neighborhoods. Particularly, the disjointness of faces is a consequence of axiom 10, since faces are planar (axiom 9). Note that the mutual penetration of the interiors of faces is prevented by axiom 10: since faces are planar (axiom 9), only penetrations of edges and the interiors of faces have to be considered. For the detailed proof of some important aspects of this theorem the reader is referred to [20].³

Apart from being correct and complete, the axioms are minimal in the sense that no axiom can be omitted or substantially be weakened without loosing the property of completeness; details may again be found in [20].

Note that the existence of handles in surfaces does not cause any problems for the concepts described in this paper. The 2-manifold-property is a local one, which is not affected by handles, as well as the tessellation property. Surfaces without and with handles differ only from a global point of view: they are topologically equivalent to a sphere in the first case, but not in the second. This is why handles are excluded in Definition 1 and in the axioms: If both, the restriction to surfaces of genus zero and axiom 13 are omitted, the results proved in this section hold as well. The absence of handles can easily be verified by the Euler equation (see Section 2.1).

The face concept can be extended from plane to curved surfaces like Bezier-surfaces, B-spline-surfaces or NURBS (non-uniform rational B-splines) [12]. In that case, the disjointness of face’s interiors must be checked explicitly [20]; it is no longer sufficient to test whether a point of an edge touches the interior of a face (axiom 10).

Solids

In a Boundary Representation, a solid is represented by the surface which bounds it. Similar to the surfaces dealt with in the last section, this surface is a 2-manifold, which prevents gaps and self-intersections. However, the topology of both types of surfaces differs: a surface bounding a solid is topologically equivalent to a sphere (c.f. Fig. 1b), while a surface representing the terrain is topologically equivalent to a disk (c.f. Fig. 1a). Despite this discrepancy, both types differ topologically only in the existence of a single face, the unbounded face OUT, which is missing in solid boundaries. The transformation from a 2.8D map to a surface bounding a solid and vice versa is illustrated in Fig. 5. The 2.8D map in a) has a single unbounded face OUT, which can easily be everted to become a bounded face, which seals a solid. Due to this correspondence the definitions and axiomatic characterization of solids and its representation by surfaces can mainly be based on the results for 2.8D maps presented in the last section; thus, we concentrate on the differences.

Fig. 5

Conversion of a 2.8D surface (a) to a surface bounding a solid (d). The models in a) and d) differ in one single face (f resp. f′) only

A surface bounding a solid is called Closed Composite Surface [24]. It differs from a 2.8D map (Definition 1) only in the omission of the unbounded face OUT: all faces are bounded. Hence, the 2-manifold describing such surfaces mathematically has no boundary.

Definition 2

(Closed Composite Surface) A Closed Composite Surface is a non-separable graph G(E,V) embedded in ${\mathbb{R}^3}$ whose edges are represented by straight line segments of non-zero length which are mutually non-intersecting. The embedding defines a set F of faces. Each face is bounded by a simple, planar cycle of the graph. The aggregation of all faces, edges and vertices is an orientable 2-manifold of genus zero without boundary.

The corresponding axioms for closed composite surfaces are given in Table 2; they emerge from the axioms in Table 1 by adapting axiom 11 (none instead of one unbounded face). For 2.8D maps, orientability has to be stated explicitly as an axiom. Due to the results in [3] (see section 2.1), orientability is implied by non-penetrating faces for closed surfaces. Hence, axiom 14 can safely be omitted in Table 2. The following proposition is immediate from Theorem 1 and 2:

Table 2 Complete and correct axioms for closed composite surfaces. The difference to the axioms for 2.8D maps (Table 1) is in italics

Theorem 3

The axioms given in Table 2 are complete and correct for closed composite surfaces.

The results presented in this section hold for Closed Composite Surfaces with handles as well—by omitting the restriction to surfaces of genus zero—similar to the case of 2.8D maps. A corresponding solid is topologically equivalent to a Torus or in general to a n-Torus [1] in the case of n handles; the number of handles may be counted by using the Euler equation.

Consistency of 3D city models

In the last section, solids bounded by surfaces and surfaces representing the terrain were modeled and characterized by axioms, which are complete and correct. The topic of this section is the consistent and clean aggregation and combination of these components in order to obtain 3D city models, which include buildings above and below the surface, inner structures like rooms, staircases and subsurface structures.

Topology

The combination of solids and surfaces has got several implications from a topological point of view. The first is the transition from 2-manifold to non-manifold structures [51]. A simple example is depicted in Fig. 6b), where the neighborhood of an edge, namely e, is not topologically equivalent to an open disk. This edge is incident to three faces, whereas the number of incident faces in 2-manifold models is two (see Fig. 6a). We discuss how consistency of such non-manifold models can be achieved. A further problem is how to handle adjacent solids. The building with a garage given in Fig. 4b) is an example for two solids which are adjacent. The surface separating the building from the garage is represented explicitly, thereby allowing for calculating the volume of the garage separately, for example. Such surfaces are called separating surfaces; they bound solids on both sides.

Fig. 6

Two different models of a building, depicted from below. a 2-manifold. b Not a 2-manifold: edge e has a neighborhood which is not topologically equivalent to an open disk

In order to guarantee that solids, surfaces and edges are disjoint and only touch at common boundaries, 3D city models are represented as a special cell complex (c.f. Section 2.3). An example is shown in Fig. 7. Three solids, s ₁, s ₂ and s ₃, which are defined by the closed composite surfaces c ₁, c ₂ and c ₃, and whose interiors are disjoint, share common faces, edges and vertices. Hence, the face in the boundary c ₁ of solid s ₁ is divided into three smaller faces: one, f ₁, is shared with the boundary of s ₂, one, f ₂, with the boundary of s ₃, and one bounds only s ₁.

Fig. 7

A cell complex, consisting of three solids. The solids touch in common faces, edges and vertices

The concept of a cell complex does not meet our requirements since it allows for unwanted voids inside the model, for space which is not covered by solids. In order to exclude such voids, the model presented here provides a complete covering of space by solids, a so-called 3D tessellation. This is achieved by introducing two special solids: one, called above-surface solid (s _as ), represents the airspace, while the other, the below-surface solid (s _bs ), models the mass of the earth.⁴ Note that both are only partially bounded by a surface (a 2.8D map), similar to a half space in 3D which is partially bounded by a plane. In this model, each point in space is represented explicitly. Figure 8 depicts an example cross profile of a 3D city model. Bounded solids are bounded by closed composite surfaces, and likewise, partially bounded solids are bounded by 2.8D surfaces. Hence, the visible surface of a city model is a 2.8D surface, and symmetrically, the model seen from below, from a mole perspective, is again a 2.8D map.

Fig. 8

Sketch of a cross profile of a geometric-topological 3D city model

Partially bounded solids are the generalization of the concept of an unbounded face OUT, which is employed in 2D or 2.8D maps to yield a 2D tessellation, a complete covering of the plane with faces.

This model is called Geometric-Topological 3D City Model, or simply 3D city model when no confusion arises. It will be discussed in the following, and characterized by axioms afterwards. The completeness and correctness of the axioms is proven formally.

A representation of 3D city models using the object-oriented, graphical modeling language UML (Unified Modeling Language) (cf. [4]), is given in Fig. 9: A 3D city model consists of solids, which are either bounded or partially bounded. The bounded solids are bounded by closed composite surfaces (cf. Definition 2), while the others, s _as and s _bs , are only partially bounded by 2.8D maps. Each face in each map or closed composite surface bounds exactly two solids. Faces are bounded by edges, and an edge is defined by exactly two vertices. The location of each vertex is given by a 3D-coordinate.

Fig. 9

UML class diagram for geometric-topological 3D city models

The formal definition of a geometric-topological 3D city model is as follows:

Definition 3

(Geometric-Topological 3D City Model) A geometric-topological 3D city model is a graph G(V, E, F, S), where V, E, F, and S are sets of vertices, edges, faces and solids respectively. For G, the following conditions hold:

• 1. G has two 2.8D maps m _bs und m _as as sub-graphs of which each separates a partially bounded below-surface solid s _bs ∈ S resp. above-surface solid s _as ∈ S. Both m _bs und m _as are incident to an unbounded face OUT.

• 2. All solids s ∈ S apart from s _bs ∈ S resp. s _as ∈ S are bounded by a closed composite surface which is a sub-graph of G.

• 3. The solids in S tessellate the space completely.

• 4. The vertices, edges, faces and solids in G constitute a cell complex, i.e. the intersection of two such primitives is either empty, or a primitive which is part of the boundaries of both primitives.

Error cases for 3D city models

Data sets representing urban scenes often violate the consistency rules of definition 3, thereby yielding severe errors if these data sets are used by applications which rely on these rules. A prominent example is the mutual penetration of solids; an example is depicted in Fig. 10. Note that the penetration of solids is a global phenomenon; potentially, the interiors of each pair of solids in the data set may be overlapping. Another error case involving overlapping solids is depicted in Fig. 11. A solid representing a building and the partially bounded solid s _as penetrate. A face, f, bounds three solids; one from above, and two, the building solid and s _as from below.

Fig. 10

Penetration of two solids

Fig. 11

Error case: mutual penetration of two solids, one representing the building, the other the air space. The horizontal face f (ground face of the first floor, depicted hatched) bounds the airspace solid

An error with local impacts is a gap in the boundary of a solid. Fig. 12b) shows an example where the composite surface bounding the building solid is not completely closed. Hence, the 2.8D map m bounding the partially bounded solid s _as has a gap. The consistent version is shown in Fig. 12a).

Fig. 12

Error case in b: the closed composite surface c ₁ bounding the building and the 2.8D map m bounding the airspace solid both have a gap. a): corrected situation

Axioms: checking consistency effectively and efficiently

In order to detect the errors discussed in the last section reliable procedures are required. The formalization of 3D city models in Definition 3, however, is mathematically precise, but not suitable as base for effective procedures. This is mainly due to the notion of the tessellation of space with solids; no means are given how to check this property. Furthermore, the cell complex property may not be implemented effectively and efficiently; particularly, the test whether all pairs of solids are non-penetrating is very time-consuming.

Similar to our approach for checking consistency of 2.8D maps and closed composite surfaces, we now give axioms for 3D city models, which are equivalent to the mathematical definition; this property will be formally proven in the next section. These axioms are given in Table 3. The first as well as the second axiom refer to the set of axioms for 2.8D maps (Table 1), and axiom 3 refers to the axioms for closed composite surfaces bounding a solid (Table 2). Axiom 4 simply states that each face must bound two solids, one on each side. The fifth axiom again is very simple. It forces each vertex and each edge to be part of the boundary of at least one face. The last axiom states that all solids apart from the partially bounded solids s _as and s _bs must be bounded.

Table 3 Axioms for geometric-topological 3D city models, which are complete and correct

For the implementation of the first three axioms, the reader is referred to Sections 3.1 and 3.2. The remaining three axioms can be realized easily and efficiently by counting incidences between vertices, edges, faces and solids.

Although consistency is a global property, the axioms are local, as they are restricted to the boundary of a single solid. Particularly, the test for mutual penetrations of solids, which is computationally very expensive, is not necessary. In Section 4.4 we will prove that this property is implied by the axioms. Similarly, checking of mutual intersections of line segments and faces can be restricted to the boundary of a single solid.

Correctness and completeness

The equivalence between the axioms and the mathematical definition of geometric-topological 3D city models, i.e. the completeness and correctness, is formally proven in three consecutive steps. The first intermediate result states that the unbounded face OUT only exists once, i.e. is unique, and that both sides of OUT cannot be connected by a curve which does not cross any face, edge or node. Based on this lemma, it is proven that the interiors of solids are mutually non-penetrating. Note that this property is not stated explicitly in the axioms. This result is a main part of the completeness and correctness proof, which will be given in the third step. We start with the first step:

Lemma 4

Let the axioms for 3D city models be valid. Then a) there exists only one unbounded face, and b) there does not exist a continuous curve which connects both sides of an unbounded face and does not cross any face, edge or node.

Proof

First, we show by contradiction that there exists exactly one unbounded face (a). Suppose there are at least two such faces, say f ₁ and f ₂. According to axiom 4, each of them has two references to solids; since f ₁ and f ₂ are unbounded, these solids must be partially bounded. According to axiom 6, there are exactly two partially bounded solids s _as and s _bs . Hence, either f ₁ ( f ₂) reference the same solid s _as (s _bs ) on both sides, or f ₁ resp. f ₂ reference s _bs on one side and s _as on the other. In any case, s _as (s _bs ) is bounded by more than one 2.8D map, thereby contradicting axiom 1 resp. axiom 2, which force partially bounded solids to be bounded by exactly one 2.8D map.

Now we are able to proof b). Suppose, there exists a continuous curve c connecting both sides of an unbounded face. Since there is exactly one unbounded face OUT, OUT is part of the 2.8D map bounding s _bs , which separates ${\mathbb{R}^3}$ in two half spaces. Since both sides of OUT are in different half spaces, the curve c cannot exist. ■

This result is used in the proof of the following theorem:

Theorem 5

Let the axioms for 3D city models be valid. Then the interiors of solids are disjoint.

Proof

By contradiction. Suppose there is a penetration of two solids s ₁ and s ₁′. Construct a half line h which starts at a point in the overlapping space of s ₁ and s ₁′. The half line does not touch any edge or vertex, and touches a face at most in a point. Since the numbers of edges, vertices and faces are finite, such a half line must exist.

Consider the faces which are penetrated by h. At each penetration one solid is left and another is entered. Figure 13 illustrates the half line h and its face penetrations. We now show that at any point of h is in the interior of at least two different solids. At the start point, h is in s ₁ and s ₁′. At each face penetration of h, one solid s _k is left and another s _{k + 1} is entered; this is implied by axiom 4. The one which is entered is not identical to the other solid, in whose interior this part of h is already located. This follows from the 2-manifold-property of boundaries of solids: a solid is either left or entered, but not both. Hence, each point of h is in the interior of at least two different solids. Since one side of the half line h is unbounded, and since the number of solids is finite, a part h _t of h is in the interior of two different partially bounded solids, i.e. of s _∞ and s _∞ ′.

Fig. 13

Proof of the disjointness of solid’s interiors. The half line h is partitioned into segments h ₁ ,..,h _t by face penetrations. Each segment h _i is the interior of two solids, so is h _t in the interior of two partially bounded solids

Since s _∞ and s _∞ ′ are bounded by 2.8D maps, both of which contain the unbounded face OUT, the axioms 1 and 2 imply the existence of a continuous curve c connecting h with the s _∞ side of OUT, and one curve c′ connecting h with the s _∞ ′ side of OUT. Neither c nor c′ crosses or touches any face, edge or vertex. The union of c and c′ yields a continuous curve connecting both sides of OUT, thereby contradicting Lemma 4. Hence, the assumption that the interiors of solids penetrate is false. ■

Now the equivalence between the axioms and the mathematical concept of 3D city models can be shown:

Theorem 6

The axioms for geometric-topological 3D city models are correct and complete.

Proof

For the completeness, we have to show that the four conditions of Definition 3 hold:

• 1. Condition 1 is immediate from axioms 1 and 2, together with the uniqueness of face OUT (Lemma 4).

• 2. The second condition is implied by axiom 3.

• 3. For the tessellation property of solids, the disjointness is stated in Theorem 5, whereas the complete coverage is a consequence of the axiom 3, which forces each face to bound two solids.

• 4. In order to proof that the graph is a cell complex, it is sufficient to show that the interiors of all primitives are pair-wise disjoint. This is done by reducing each mutual penetration of the interiors of primitives to the penetration of solid’s interiors, which contradicts Theorem 5. It is sufficient to consider the disjointness of the interiors to proof the cell complex property, since each touching of boundaries not sharing common primitives implies a penetration of interiors of the boundary.

  We consider all possible cases of penetrations of interiors:

  • a) The penetration of the interiors of two solids contradicts Theorem 5.

  • b) When the interiors of two faces f ₁ und f ₂ are not disjoint, we have two cases (note that f ₁ and f ₂ both bound two solids according to axiom 4): if f ₁ and f ₂ bound the same solid s, one of the axioms 1, 2 or 3 is violated. This depends on s which may be partially bounded (axiom 1 or 2) or bounded (axiom 3). If f ₁ and f ₂ bound different solids, then one pair of these solids’ interiors penetrates, thereby contradicting Theorem 5.

  • c) When the interiors of two edges e ₁ and e ₂ touch, we have two cases again: if e ₁ and e ₂ are incident to the same face f, the axiom avoiding edge intersections (axiom 6 in Table 1 or 2) referred to in axiom 1, 2, or 3 is violated. If e ₁ and e ₂ are not incident to a common face, then axiom 5 implies that e ₁ and e ₂ are incident to faces which are incident to solids (axiom 4). Hence, both e ₁ and e ₂ are surrounded by an alternating sequence of faces and solids, and two of these solids’ interiors penetrate, thereby contradicting Theorem 5.

  • d) Each vertex is completely surrounded by edges, faces and solids (axiom 5). Hence, two vertices with identical coordinates imply penetrating solids.

  • e) When the boundaries of two solids touch without sharing a common face, edge or vertex, we have three cases, each of which can be reduced to b), c), or d): If the intersection is two-dimensional, b) is implied, while an one-dimensional intersection implies c) and a zero-dimensional intersection implies d).

  • f) When the boundaries of two faces touch without sharing a common edge or vertex, c) is implied for a one-dimensional intersection, and d) for a zero-dimensional intersection.

  • g) When the boundaries, i.e. the end nodes of two edges, touch without sharing a common node, d) is implied.

For the correctness part, we have to show that the axioms are implied by Definition 3. Axiom 1 and 2 are a consequence of the first condition, and axiom 3 is identical to the second condition of the definition. Axiom 4 is implied by the tessellation property, and the fifth follows from the tessellation and cell complex properties, which prohibit isolated vertices and edges. Axiom 6 is immediate from the definition. ■

Complex features

Based on geometric-topological 3D city models, semantical spatial objects, often called features [27], can be defined. As a rule, features are arranged in a hierarchy. A building feature, for example, consists of a garage feature, an outbuilding feature, and a main house feature. The main house may be divided in parts, e.g. storeys, which again consist of rooms. This aggregation hierarchy of features has to be reflected in the city model. Figure 14 depicts an example for the aggregation of atomic solids, where a building feature is constructed from simpler features which represent a garage and a main house. These features are composed from storey features again, which consist of room features. Note that each feature has a 2-manifold boundary.

Fig. 14

Aggregation of solids defining features

Not every arbitrary combination of solids is a valid representation of a feature: non 2-manifold boundaries have to be avoided, as well as void spaces inside the feature. A building, for example, consists of storey features which have to fill the building feature completely. Note that a storey feature as well as a room feature covers the whole volume of the storey or room, including the walls and the air space inside the object. Hence, the conditions for solids of the 3D city model, which are called atomic solids henceforth, have to be valid for aggregated solids as well. Another problem is the unwanted penetration of features. While the disjointness of atomic solids is implied by the axioms for 3D city models, it is not implied for aggregated solids.

Examples for aggregations which are not considered as features are given in Fig. 15. In a), the boundary of the aggregated solid is not a 2-manifold, because of the edge e. The structure in b) is bounded by a 2-manifold, which has a genus of one, i.e. it has a handle. Such objects are excluded at the moment, but can be incorporated when handles are considered. The boundary of the structure in c) is not a closed composite surface, since it is not connected.

Fig. 15

Aggregation of Solids: Error Cases. The surface bounding the aggregated solids is not a 2-manifold without handles. a Non-manifold edge e, b handle, c disjoint solids

Beside the consistency of features, the efficiency of spatial analyses is another important issue. Particularly, the structure presented in this paper should support the efficient treatment of topological queries, e.g. whether two buildings are neighbors or not.

The hierarchical structure of aggregated solids is represented by trees, whose leaves correspond to atomic solids. Each (aggregated) feature which is part of an aggregated feature is defined by a sub-tree of the corresponding tree. All (aggregated) features of a 3D city model are represented by a set of disjoint trees. Such a structure is called forest [28].

In the following, aggregated solids are defined recursively. In order to guarantee that an aggregated solid has a 2-manifold boundary, the two solids which are part of the aggregate have to touch in a specific way: both have to touch in a structure which has a simple cycle as boundary. It may be a single face, or it may consist of many faces which are arranged in such a way that the boundary of the whole structure is a simple cycle. Such a structure is called composite surface [24]:

Definition 4

(Composite Surface) A Composite Surface is a non-separable graph G(E, V) which is embedded in ${\mathbb{R}^3}$. Edges are represented by straight line segments of non-zero length which are mutually non-intersecting. The embedding defines a set F of faces which are planar and bounded. The set of all faces, edges and vertices is a single, orientable 2-manifold of genus zero which has one simple boundary.

The concept of a composite surface is quite similar to the concept of a 2.8D map. The only difference is that the unbounded face OUT is missing in composite surfaces.

Before defining the aggregation structure of solids, we first consider how an aggregated solid is constructed from atomic solids:

Definition 5

(Aggregated solid and its boundary) Let G(V, E, F, S) be a 3D city model. An aggregated solid is defined recursively as follows:

• i) An atomic solid s ∈ S\{s _as , s _bs } is an aggregated solid. Its boundary is the boundary of s.

• ii) Let a be an aggregated solid with boundary r and s ∈ S\{s _as , s _bs } be an atomic solid. If

  • 1. the interiors of a and s are disjoint, and

  • 2. the intersection of the boundaries of a and s is a composite surface cs,

then the union of a and s is an aggregated solid a′. The boundary of a′ is the union of the boundaries of a and s, where the faces and internal vertices and edges of the common composite surface cs have been removed.

The stepwise construction of the structure in Fig. 14 is accomplished with regard to this definition: in each step, the intersection of the two boundaries is a composite surface. This is not the case in the three examples in Fig. 15. In a), the intersection of c ₁ and c ₂ is an edge, in b) two separated faces and in c) it is empty. In all three cases, it is not a composite surface.

An aggregated solid is homeomorphic to a solid. This is stated by the following theorem:

Theorem 7

An aggregated solid is bounded by a closed composite surface.

Proof

We have to show the validity of the axioms for closed composite surfaces in Table 2. We proceed by induction on the number n of solids in the aggregate. The case n = 1 is straightforward, since in this case the aggregate is an atomic solid. Let the proposition be valid for aggregates a _n with n solids; we show that it also holds for aggregates a _n+1 with n+1 solids. a _n and s touch in a common composite surface cs with a simple boundary c. The validity of the axioms 1, 2, 4, 5, 6, 8, 9, 10, 11 for a _n+1 is implied immediately by the induction hypothesis, i.e. the validity of the axioms for a _n and s.

Axiom 3 (umbrella-axiom) can only be violated if a _n and s meet in a single vertex. In contrast, both meet in a composite surface, therefore axiom 3 is valid. The consideration of axiom 7 can be restricted to the edges in the simple cycle c, which bounds the common composite surface cs. Let e be such an edge. In a _n as well as in s, e has two incident faces by the induction hypothesis. Two of these faces—those which are in cs—are identical and are removed in a _n+1. Hence, in a _n+1 e has exactly two incident faces. Axiom 12 (connectedness of a _n+1) is implied by the touching of a _n and s in a common composite surface.

In order to prove axiom 13, we have to show that the Euler formula (see Section 2.1) must hold for a _n+1 :

$$ 2 - \left( {\left| {V_n} \right| + \left| {V{\prime_n}} \right| - \left| {V_c} \right| - 2\left| {{V_{cs}}} \right|} \right) + \left( {\left| {E_n} \right| + \left| {E{\prime_n}} \right| - \left| {E_c} \right| - 2\left| {{E_{cs}}} \right|} \right) - \left( {\left| {F_n} \right| - \left| {F{\prime_n}} \right| - 2\left| {{F_{cs}}} \right|} \right) = 0 $$

The cardinalities of the sets of faces, edges and vertices are obtained by the sums of the cardinalities of the sets for a _n (V _n , E _n , F _n ) and s (V′ _n , E′ _n , F′ _n ), subtracting the cardinalities of the boundary cycle of cs (V _c , E _c ), and subtracting twice the cardinalities of the faces (F _cs ), internal edges (E _cs ) and internal vertices (V _cs ) of cs. These have to be subtracted twice since they are removed from both, a _n and s, while the cycle c is only removed once.

After rearranging and grouping, we obtain:

$$ \left( {2 - \left| {V_n} \right| + \left| {E_n} \right| - \left| {F_n} \right|} \right) + \left( {2 - \left| {V{\prime_n}} \right| + \left| {E{\prime_n}} \right| - \left| {F{\prime_n}} \right|} \right) + \left( {\left| {V_c} \right| - \left| {E_c} \right|} \right) - 2\left( {2 - \left| {{V_{cs}}} \right| + \left| {{E_{cs}}} \right| - 2\left| {{F_{cs}}} \right|} \right) + 2 = 0 $$

Now we apply the induction hypothesis to a _n and s, yielding

$$ 0 + 0 + \left( {\left| {V_c} \right| - \left| {E_c} \right|} \right) - 2\left( {2 - \left| {{V_{cs}}} \right| + \left| {{E_{cs}}} \right| - 2\left| {{F_{cs}}} \right|} \right) + 2 = 0 $$

Since the numbers of edges and vertices in a simple cycle are equal, $\left| {V_c} \right| - \left| {E_c} \right|$ vanishes. Now we apply the Euler formula to cs, thereby considering the fact that the boundary cycle c does not affect its validity and that a closed composite surface has no unbounded face OUT, i.e.: $2 - \left| {{V_{cs}}} \right| + \left| {{E_{cs}}} \right| - \left| {{F_{cs}}} \right| = 1$ . We finally obtain the valid equation

$$ 0 - 2(1) + 2 = 0 $$

Hence, the Euler formula is valid for a _n+1. ■

By using the concept of aggregated solids we can now define aggregated features in a 3D city model by applying the definition to each volume feature, and by arranging these features in a hierarchical tree structure.

Definition 6

(Aggregated feature, set of aggregated features) Let G(V, E, F, S) be a 3D city model. A set of aggregated features is a set of trees (a forest) T, where the following conditions hold:

• 1. Each leave node of each tree t ∈ T corresponds to an (atomic) solid s in S.

• 2. Each non-leave node n of a tree t corresponds to an aggregated solid which is derived from the sub tree nodes of n in t.

An aggregated feature is a tree t ∈ T.

The tree structure avoids overlapping features: either features are disjoint, features touch, or there is a containment relation.

The third condition refers to Definition 5; hence Theorem 7 implies that each non-leaf-node and hence each aggregated feature is bounded by a closed composite surfaced. This boundary can be derived by applying the definition recursively; in each step, the faces common to two solids which define the geometry of the feature are removed.

An example for a set of aggregated features is given in Fig. 16, which is based on the 3D city model in Fig. 14. Each leave node corresponds to an atomic solid, and each tree to a feature. The forest contains nine features: four features of type Room and one of type Garage correspond to atomic solids, i.e. trees of depth 1, while the Storey, Building and Complex Building features are represented by trees with a depth of 2, 3 or 4.

Fig. 16

Aggregated Features, based on the example in Fig. 14

For the following concept, the notions of predecessor and successor in a tree are needed which are defined as customary: A node A is a successor of node B, if there is a direct link down (from the root to the leaves) the tree from B to A, or if A is part of the sub-tree whose root is the node direct linked downwards from B. A is predecessor of B, if and only if B is successor of A. For example, the node labeled Building in Fig. 16 is predecessor of the six nodes labelled Storey and Room, and successor of the node Complex Building.

The explicit representation of the aggregation structure supports the efficient analysis of 3D city models. Particularly, topological queries referring to the topological relations of Egenhofer’s 4-Intersection-Model, may be answered very efficiently:

• Two Features A and B are disjoint, if one is not a predecessor of the other in the forest, and if there does not exist a face f which is in the boundary of a leaf solid of A and in the boundary of a leaf solid of B.

• Two Features A and B touch, if one is not a predecessor of the other in the forest, and if there exists a face f which is in the boundary of a leaf solid of A and in the boundary of a leaf solid of B.

• One Feature A is inside another feature B, if A is successor of B in the forest, and if there does not exist a face f which is in the boundary of a leaf solid of A and in the boundary of a leaf solid of B.

• One Feature A is coveredBy another feature B, if A is successor of B in the forest, and if there exists a face f which is in the boundary of a leaf solid of A and in the boundary of a leaf solid of B.

For these topological queries the consideration of the geometry is not required. The structural information represented by the tree makes the derivation of these relationships very efficient.

If lattices are used instead of trees, as in [29], the situation is more complex. In a lattice, an element can have more than one predecessor, hence a solid may belong to two or more overlapping features that are not related to an aggregation hierarchy.

The concept for handling aggregated solids is similar to two-dimensional nested maps [42, 43], which have been introduced to represent the areal aggregation hierarchy of administrative entities, for example: parcels are aggregated to municipalities, municipalities to districts, districts to federal states, and federal states to countries. Nested maps are also represented by a tree, whose leaves are the faces of a 2D map. The consistency of the model is guaranteed by a single rule: Each node, whose spatial extent is the spatial extent of its successors in the tree, must be bounded by a simple cycle. This rule is generalized by the rule for defining consistent aggregated features given in this paper.

Conclusions

This paper presents a method to check consistency—the conformance of data sets with the rules of the underlying model—for 3D GIS models. This method enables data providers as well as users to check and assure the usability and suitability of data for certain applications effectively and efficiently. The proposed approach is particularly appropriate for 3D city models which are represented, provided and exchanged in formats like CityGML. This method closes a gap, since there is a lack of effective and efficient procedures to check consistency. International standards like ISO 19107 “Spatial Schema” or the exchange language GML 3, which play an increasingly important role in GIS modeling, do not answer the question of consistency sufficiently. Our method consists of a system of axioms which are immediately implementable and hence the base of an efficient and effective procedure to check consistency. The reliability of the procedure is guaranteed by mathematical proofs of the correctness and completeness of the axioms: each error is detected, and each violation of the axioms is in fact an error. The axioms are designed in a modular way based on the partition of city models in topological surfaces which are either topological equivalent to a sphere, or to a disk. The first type of surfaces represents rooms, storeys or buildings, while the other models the terrain and the visible hull of urban structures. Both are described by 2-manifolds mathematically, thereby excluding self-intersections and gaps. We show how a 3D city model is composed of both types of surfaces, thereby yielding a system of axioms which guarantees the consistency of entire 3D city models. Checking consistency is a global problem: potentially, each spatial object may interact with each other. We show how this global problem is solved locally, by axioms which are safely restricted to check the consistency of single components individually. Particularly, we show that the test whether two solids penetrate, which is very elaborate and expensive from an algorithmic and running time point of view, is in fact not necessary; this property is already implied by other axioms which can be checked in a much cheaper way.

Based on 3D city models, we present a concept to define the spatial extent of features, i.e. semantical objects, by the aggregation of solids. These aggregations have the same properties as single solids: they are bounded by a closed 2-manifold. The hierarchical structure of features is defined by trees. This enables efficient topological queries.

Another topic is the consistent updating of 3D city models in order to represent changes which occur frequently in today’s cities. Specific rules have been designed to cover this dynamic aspect of consistency which focus on the updates locally. Such transaction rules are based on the axioms given in this paper or in [16] and can be based on the 2D case, which is treated in [19]. In this context, the treatment of handles to cover bridges, tunnels and arcades is essential. In contrast to the static aspects of consistency which are dealt with in this paper, consistent transactions require the localization of handles, since their involvement in updates may violate consistency severely. Transaction rules and the adequate treatment of handles, however, is a topic of a subsequent paper.

This paper focuses on the spatial aspects of consistency. Many consistency constraints depend on the semantics of features to formalize specific constraints, e.g. that doors have to be part of walls, not part of roofs, or that garages are located on the ground, or connected to roads by ramps or driveways, since they must be accessible by cars. The formalization of semantics is part of an ongoing research process in spatial ontologies [13, 32]. Spatio-semantical consistency rules for 3D city models can be based on the formalization of semantics by UML diagrams, which are provided by CityGML [17], for example, by using ontology languages like the Web Ontology Language (OWL) [47].