Home | Business News | Browse by Publication | C | Cartography and Geographic Information Science

Towards a 3D feature overlay through a tetrahedral mesh data structure.

Article Excerpt
Introduction

Current developments in three-dimensional (3D) sensors and measuring devices, such as terrestrial lasers canners, make it possible to model and represent real-world features so that they more closely resemble their actual shape. Until recently, geographic information science and cartography have been utilizing 3D models primarily for geo-visualization. Although visualization is useful for obtaining visual insight and performing qualitative analysis, for most applications a more quantitative analysis is needed.

We can distinguish between geometric queries performed for each 3D model separately (compute area, volume) and relational queries. The latter are more or less topological in nature, used to inquire whether or not geometrical representations overlap, and if they do, where and to which extent. These overlay calculations are well known and implemented in two dimensions (2D) between two or more planar partitions with the geometrical intersection and the propagation of the identifiers.

The overlay operation between 3D features, or between 3D volumetric partitions, is more complex. The geometric intersection has its challenges, and it should be performed within reasonable computational time. One way to manage that task is by decomposing the feature into a set of cells, such that a feature is defined as the union of all cells. In most applications this cell is a voxel, a 3D cubic primitive. Feature decomposition has the disadvantage that the representation of the feature is directly related to the measure of the voxel, giving it a rough appearance; but it has the benefit of requiring no intersection calculation when the spatial resolution of the objects to be overlaid is the same.

Another approach is to use a tetrahedral network (TEN) as the modeling environment in which the overlay is performed. The features are defined by their boundary representation as a 3D triangular irregular network (3D TIN). By inserting the features one by one into the overlay TEN, the geometrical overlay is performed on the fly, and the process is supported by the internal neighborhood search possibilities of the TEN. The characteristics, given by the identifier of the features, are propagated to the tetrahedron primitives within the overlay TEN. The overlay TEN then acts as a container in which all the features are stored. One can retrieve the features as a volume representation given by a set of tetrahedra with the same identifier, or as a surface representation given by the set of boundary facets of the tetrahedra. An overlap is detected by finding tetrahedra that belong to more than one feature, querying the tetrahedra and creating the overlay using these identifiers.

This paper first addresses the use of TIN/TEN data models with respect to boundary representations. Then we give some definitions and provide a background to triangulations in general, focusing on Cavalcanti and Mello's (1999) approach to decomposing a polygon boundary representation by a conformal triangulation. An overview of existing map overlay methods is given in the following section to explain the need for the overlay of 2D and 3D features, which are described in the next two sections. A short description of the implementation of the 2D counterpart of this method is followed by a summary of the 3D results. We conclude by highlighting some other possibilities of the proposed method.

TIN/TEN Data Models for Boundary Representations

In topographical modeling, real-world objects are characterized by a certain representation and stored in a geo-database. The representation depends on the purpose of the geo-database but also on the identification and data capture process. In this section we will introduce 2D TIN and 3D TEN data models, as they will be used in the subsequent overlay computations.

Two-dimensional (2D) Boundary Representation

We can describe a 2D boundary explicitly by its polygon geometry through an ordered list of points connected to one another by straight-line segments, with the last point connecting to the first. We could also use topology, where points are identified as numbered nodes and the nodes define a polygon. The geometric description of polygons and other simple features within 2D space is defined by the Simple Feature Specification (SFS) of the Open GeoSpatial Consortium (OGC 2005). Validation functions are available to determine whether or not a given feature is valid, i.e., a polygon is not self-intersecting. Although the validation process is not complicated, many implementation and definition problems exist (see Van Oosterom et al 2004; Van Oosterom et al 2005).

If the boundary of the object is defined, then the interior is also, in some way, given. This interior could also be made explicit or materialized, i.e., when the boundary polygon is triangulated in a set of triangles and stored within a 2D Triangular Irregular Network (2D TIN) data structure. Because boundary edges can be derived from a set of triangles, it is no longer necessary to store the boundary polygon per sai. The TIN acts as the base data structure for the feature representation. The embedded space between two or more objects could also be defined by a triangulation of the covering polygon, where all objects are enclosed by sets of interior triangulations. The space is thus fully partitioned by triangular meshes.

3D Boundary Representation

The identification and capture of real-world objects is far more complicated when we move to full 3D applications. In 3D, opposed to 2.5D, it is not possible to assume that objects can be flattened and defined as polygon footprints on a surface. Instead, a proper 3D boundary representation of the object is needed, meaning more than one Z-value is attached to a 2D polygon, and also more information is needed than one Z-value attached to the vertices of the 2D polygon.

In 3D, the definition of the geometric and/or topological description and validation of the correctness is far more complicated than in 2D. The polyhedral approach, as described in, among others, Teunissen and Van Oosterom (1988) and Stoter (2004) defines the boundary as...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!