CG models for fast visualisation1.4 Research objectives
3D spatial (topological) models
3D GIS models
The commonly established systems dealing with spatial information are 2D GISs and 3D CAD systems. CAD systems, originally designed to create, edit and display small 3D graphics models, show weaknesses in the 3D visualisation of large models. Recent developments (power processors, graphics accelerators and standard hardware-implemented graphics libraries) have opened up new horizons for 3D visualisation, which are called Virtual Reality (VR) techniques. Sophisticated devices or conventional equipment allow complete immersion with the model, simulating actions and observing reactions similar to those in the real world. Nowadays computer technologies are capable of handling, processing and displaying more graphics entities than ever before. Despite the various tools for manipulating data, CAD and VR systems have two conceptual specifics that result in insufficient means for GIS analysis:
The generic idea of GISs is to incorporate geometric and semantic information in one system and to support analysis in both domains (see Maguire et al 1991, Aronoff 1995). However, current commercial GIS's support 2D topology (ESRI, 1999) and face problems supplying 3D spatial analysis. The existing possibility to create separate vertical layers with explicitly recorded 2D topology only per layer (e.g. ArcCAD, ATKIS, SPRAD) gives some extensions to 3D, yet spatial operations between two layers create problems. 3D display and real-time navigation is supported for 2.5D data. (e.g. 3D Analyst, ESRI) or 3D data.
The current status regarding maintenance and analysis of 3D spatial data can then be characterised as: a lack of appropriate commercial software and an increasing demand for systems that process and analyse 3D spatial information gathered from urban environments. Software developers and researchers are challenged to search for extensions toward the third dimension. Some vendors co-ordinate their efforts in order to offer a suitable solution based on their own products. Typical example is the integrated software package of the ESRI and AutoDesk companies ArcCAD, AutoCAD and ArcVIEW. Despite the improved capabilities of such hybrid systems, the maintenance of separate databases remains problematic and either comprehensive 3D spatial analysis cannot be performed or efficient 3D visualisation cannot be offered.
Computer graphics and GIS researches are heavily involved in the investigations on 3D spatial models. The research in 3D computer graphics is especially extensive as regards algorithms and structures for processing large 3D data in real time (see Kofler 1998, Lindstrom et al 1996), photo-realistic visualisation (see Gruber et al 1995, Leberl et al 1994) and extended VR tools for interaction with the model (see Isdale 1998). The research in the GIS community is directed to more fundamental levels, i.e. the development of models for maintaining 3D topology as the basis of a 3D GIS (see Molenaar 1990, Pigot 1995, Pilouk 1996).
Moreover CAD and GIS tend to be conceived as a monolith, stand-alone or Intranet system, which however, does not correspond to the recent business trend to exchange information on a Web electronic market. The Web electronic market is considered by many as a new information revolution and tremendous amounts of money and manpower have been invested in Web-based commerce systems (see Bichler et al 1998). New technologies (HTTP, CORBA, Java) and standards (VRML, HTML) make possible the development of software kernels, which can be extended, linked and aggregated, in component-based systems on the Web. The significance of the electronic market is appreciated already by many GIS vendors: although with limited functionality, several extensions for the remote access and query of spatial data are already available. 3D GIS on the Web is the new challenge for GIS researchers and developers.
The design, utilisation and maintenance of a new 3D GIS comprises a wide spectrum of questions concerning a 3D model, data collection, analysis, manipulation, visualisation and the remote access of geo-referenced data. Some of the key research areas will be mentioned here.
Conceptual model: The common understanding is that the conceptual model (and its corresponding logical model) is the key element in a 3D GIS. The conceptual 3D model integrates information about semantics, 3D geometry and 3D spatial relationships (3D topology). The conceptual model provides the methods for describing real-world objects and spatial relationships between them. The design of a conceptual model is a subject of intensive investigations and several 3D models have already been reported (see Brisson 1990, Cambray 1993, Kofler 1998, Molenaar 1992, Pigot 1995, Pilouk 1996, Pilouk and Tempfli 1994a, van Oosterom et al 1994). The models, however, are thought to fulfil requirements of either 3D topology support or 3D real-time visualisation, and little evidence of investigation into both 3D spatial analysis and visualisation is discovered in the literature.
Data collection: Modelling in 3D drastically increases the cost of data acquisition, as compared with 2D. Despite the progress in automatic object detection and 3D reconstruction (see Gülch et al 1999, Hendrickx et al 1997, Henricsson and Baltsavias 1997, Lang and Förstner 1996), the manual work is still predominant. Methods for constructing the model combining data from various sources, automatic techniques for data acquisition (geometry and images for texturing), rules and algorithms for ensuring consistency of data, algorithms for the automatic building of 3D topology, etc., are the widely discussed topics in the literature.
Spatial analysis: Whilst thematic analysis and 2D spatial analysis are well studied, research on 3D spatial analysis is still at an intensive stage. Spatial relationships are the fundament of a large group of operations to be performed in GIS, e.g. inclusion, adjacency, equality, direction, intersection, connectivity, and their appropriate description and maintenance is inevitable. Similar to 2D variants, 3D GIS should be capable to perform metric (distance, length, area, volume, etc), logic (intersection, union, difference), generalisation, buffering, network (shortest way) and merging operations. Except metric operations, most of them require knowledge about spatial relationships. The third dimension increases drastically the number and complexity of all possible spatial relationships, compared with 2D GIS. A formalism for the detection of spatial relationships based on set topology notions has already been proposed by several authors (see Pullar and Egenhofer 1988, Egenhofer and Herring 1992, Molenaar 1998), however the description of 3D spatial relationships is not sufficiently studied. The design of a spatial query language or the extending of existing languages (see Mattos and DeMitchiel 1994), updating procedures to ensure topology consistency of database, etc., these are tasks that need further development.
Visualisation, navigation and user interface: Advances in the area of computer graphics have made visual media a major ingredient of the current interface and it is likely that graphics will play a dominant role in the communication and interaction with computers in the future. 3D visualisation within 3D GIS requires a number of specific issues to be investigated, e.g. appropriate means to visualise 3D spatial analysis, tools to effortlessly explore and navigate through large models in real time, and texture the geometry. Observations on the demand for 3D City models (see Gruber et al 1995) show user preferences for photo-true texturing, due to improved model performance in terms of of detail and orientation. Trading photo-true texture raises new topics for research, i.e. collection (methods, automation), storage (original images vs. separate pieces) and mapping onto the "geometry". Specific functions of objects modelled in VR systems, and referred to as behaviours, gain an increased popularity as tools for walking through the model, exploring particular phenomena and improving the cognitive perception (see Kraak 1998, Raper et al 1998). The organisation of behaviour at database level is hardly studied.
Internet access: Remote access to 3D spatial information is one of the newest research topics. The Web has already shown a great potential in improving accessibility to 2D spatial information (raster or vector maps) hosted in different computer systems over the Internet (e.g. http://www.visa.com, http://www.mapquest.com, http://www.mapguide.com, etc.). 3D graphics was not transferable across the Web until very recently. The new Web standard Virtual Reality Modelling Language (VRML) has created the ability to distribute and navigate in 3D virtual worlds. Many virtual towns, biological and geological structures, etc., become possible to explore on the Web in a short time. Most of the models, however, are uploaded on the servers as Web documents. The utilisation of VRML as a front-end visualisation engine to a database system is only at a very early stage. The research on spatial query and 3D visualisation in VRML has resulted in a few prototype systems (see Coors and Jung 1998, Lindenbeck and Ulmer 1998). The design criteria, however, are visualisation- rather than spatial analysis-oriented.
This research concentrates on a conceptual model for a 3D GIS. Several fundamental considerations outline the area of research as follows:
This thesis does not intend to develop an operational 3D GIS on the Web for a municipality, since this is not considered feasible for the time schedule of one research. The thesis aims at the development of concepts and their validation by prototyping key aspects.
Research on 3D models is quite extensive and rudimentary but fragmented. Being conducted by different specialists (GIS, CG, CAD), the investigations emphasise conceptual or performance issues. In this review, only the most directly related works will be summarised, i.e. 3D models intended for 3D GIS or representing spatial relationships by topology.
CG models
for fast visualisation
Concerned about the large amount of data of real-world
models, CG specialists explore models capable of maintaining these data
(geometry and texture) and performing so-called visualisation analysis
(i.e. query against the visualisation frustum) in real time. The utilisation
of different Levels of Detail (LOD) per object and their appropriate real-time
control is the most popular approach to reduce data during the visualisation
process. Although they are often called 3D GIS, little or no attention
is paid to the support of 3D topology for spatial queries. The models are
tailored to planning (design of urban landscapes), training (rescue, military
activities) and educational purposes.
The Virtual 3D GIS presented by Koller et al 1995 is not a real 3D GIS because the model built is actually a 2.5D system dealing with terrain data. The several buildings shown in the demonstration software are not part of the model. Query of semantic information per object is provided. The system is a good example of an interaction with virtual environments and demonstrates the dynamics of objects (e.g. explosions, deformations of terrain).
The "3D GIS" reported by Kofler 1998 is built on R-tree spatial model as the goal is the storage of data and a Graphic User Interface (GUI) for the fast 3D visualisation of large urban models. The research is a contribution to real-time navigation through large models that cannot be loaded in the memory, and the data for rendering have to be fetched from the database for each change in the viewing position. A discussion on the suitability of this data organisation for spatial analysis is not provided, nor is the organisation of semantic information about the objects mentioned. Again, the system hardly can be called a 3D GIS.
Among the urban 3D models accessible on the Web, only a few have some of the required 3D GIS functionality. Most of the urban data are organised only as VRML files for navigation. The system presented by Coors and Jung 1998 is the most significant achievement in this direction. The system developed on CORBA technology (see Orfali and Harkey 1998) and VRML provides means to visualise selectively 3D textured urban models and query thematic information. The focus, however, is on client-server communication rather than on a conceptual model for database organisation.
3D spatial
(topological) models
Another stream of investigations comprises models for
representing and manipulating geometric objects. The emphasis is on a formalism
(structure, ordering and operators) to construct a geometric object regardless
of the dimension. The cell-tuple model presented by Brisson 1990 and later
expanded by Pigot 1995 are two examples. Such models aim at the complete
representation of all the topological relationships among the cells. The
models inherit the "incident graph" idea of computational geometry to describe
relationships, i.e. each node of the incident graph corresponds to an n-cell
and each link between graph nodes represents the adjacency with (n-1)-cells.
In this respect, the models can be referred to as an implicit representation
of cells. The approach increases the size of the data for storage and requires
powerful techniques for restricted spatial search. Moreover, the cell-tuple
structures, being extensions of models used in computational geometry,
do not deal with the semantic characteristics of objects. Investigations
into adoptions of such models to describe geometry in GIS are reported
by Mesgary et al 1998.
3D GIS models
Research in the GIS community is trying to work out a
conceptual model capable of integrating geometric (position, shape and
size) and thematic characteristics of objects and mutual spatial relationships.
These models can be considered an explicit description of cells
(or objects). The concept of a 2D GIS introduced by Molenaar in 1989 as
"Formal Data Structure", and extended to comprise 3D information and texture
in several successor models, follows an integrated approach for describing
geometry, semantic and spatial relationships in one spatial model. The
model has been extensively studied (see Kofuniyi 1995, Pilouk 1996, Bishr
1997, Peng 1997, Cheng 1999). The investigations into 2D and 3D spatial
analysis promised results that have motivated the utilisation of 3D FDS
as a starting point of this research. A review of the 3D extensions and
implementations of the model are listed below.
A modification of the initial 2D FDS has led to an extension, called 3D FDS, allowing operations with body objects. An experimental 3D Vector GIS (TREVIS) has been used to test the model (see Bric et al 1994, Pilouk 1996). Despite the promising results, the study on suitability of 3D FDS for urban areas is still not sufficient. Developed software for visualisation is hardware-dependent, with limited possibilities, and does not offer texturing (only wire frame).
The next extension, achieved by including a tetrahedron as a fourth describing element, results in the Tetrahedral Network (TEN), which makes available new operations with volumes (e.g. in geo-sciences and environmental management). A package of programs for 3D raster conversion, creating 3D Voronoi polyhedrons and Delaunay tetrahedrons and basic query analysis have been developed and tested (see Pilouk and Tempfli 1994b).
Analysis of the various models based on FDS yields a generalised concept for an n-dimensional data model named Simplicial Network Data Model (SNDM). The implementation work on this data model is done using an object-oriented approach. The developed software, i.e. Integrated Simplicial Network Application Package (ISNAP), allows 2D and 3D triangulation (unconstrained and constrained), graphic display (orthogonal, perspective and stereo views, wire frame, surface illumination, etc.) of surface, query of point, line and face, derivation of contour lines and derivation of a regular grid DTM (see Pilouk 1996). Further investigations into the applicability of the model for more complex 3D analysis (e.g. intersection, buffering) are necessary. The software for visualisation of 3D data has to be extended. 3D tools for interactive editing still have to be developed.
Rikkers et al 1993 present a relational implementation of 3D FDS and give examples of SQL spatial queries. Pilouk and Tempfli 1994a report an object-oriented concept. An implementation of 3D FDS for urban areas can be seen in Shibasaki and Shimiso 1990. The reported results are on the applicability of FDS to describe complex geometry in large towns. Several additional studies are devoted to data collection. Wang 1994 and Paintsil 1997 have developed two procedures for a semi-automatic object reconstruction from aerial imagery that automatically create 3D FDS. Sitole 1997 have contributed to the research on the model by an extension toward the maintenance of multiple textures per face. Tempfli 1998a has presented a framework on data collection and automatic object reconstruction for 3D realistic urban models as 3D FDS is the proposed model to maintain data. The model is well studied in the spatial domain as well. Van der Meij 1992 and Bric 1993 have completed a study on binary topological relations that can be derived from 3D FDS. An expansion of 3D FDS is developed to fulfil the requirements of the Croatian National Electricity Company (see Baucic 1995), but only on a conceptual level.
The suitability of 3D FDS and its 3D extensions has still not been sufficiently studied for 3D visualisation and remote access. Despite some experiments with urban models, the results obtained are only preliminary: the models are mostly visualised in wire frame, no texture is applied and no real-time navigation is intended. The GIS models still deal only with spatial objects (with discernible and indiscernible boundaries) and do not provide a framework for the accommodation of non-spatial objects.
Van Oosterom et al 1994 describe a 3D GIS maintaining four Abstract Data Types (ADT), i.e. point, polyline, polygon and polyhedron as 3D geometric primitives. The model is implemented in DBMS Postgress, which is extended to combine the ADTs and provide a user interface based on the standard graphics package PEX (for UNIX). The model is capable of detecting five topological relationships (in, touch, cross, overlap and disjoint), which can be further propagated to investigate the intersections. The authors concentrate on spatial extent (descriptions and relationships) and do not deal with the semantics of objects.
Flick 1996 presents a framework for a 3D GIS, which maintains different views per object, e.g. point objects can be displayed by different symbols. The topology handled follows Molenaar's approach with several extensions: each point knows its adjacent lines, every face knows its bounding lines, and every line knows its bounding faces. Thus the bi-directional links between all the cells are stored. The model is intended for implementation in object-oriented DBMS as the GUI is built using OpenGL. The author warns about the large amount of data produced as a result of the explicit storage of many relationships.
Koehl 1997 presents an idea to incorporate Constructive Solid Geometry (CSG) primitives in the topological model in order to facilitate the data acquisition by CAD systems. The author introduces six ATDs for topographic objects and four ATDs for primitives and thematic classes. The CSG primitives are decomposed into defined ATD classes before storage in the database. The approach, with minor exceptions, is very similar to the one presented by Pilouk and Tempfli 1994a.
The objectives of the research are:
The prime focus of the research work is ensuring 3D GIS functionality. Offering fast 3D visualisation is confined to the requirements of the model. Performance optimisation is beyond the scope of the thesis. In this respect, the positive conceptual results obtained by the researches working on GIS models (i.e. 3D FDS, TEN, cell model) will be utilised and further evaluated for their suitability to host urban and visualisation data, and their performance in data traversal.
The second understanding refers to the concept regarding remote access of data. The municipal system has to provide access to a wide spectrum of users, and hence the system architecture must rely on standard, low-cost, hardware and software independent solutions on the client site. Therefore VRML and HTML are expected to be a good basis for visualisation means.
1.5 Organisation of the thesis
Although organised in nine chapters, the work presented by this thesis can be subdivided into four parts, i.e. introduction (Chapter 1 and Chapter 2), clarification of requirements (Chapter 3 and Chapter 4), conceptual design (Chapter 5 and Chapter 6), implementation (Chapter 7 and Chapter 8) and conclusions (Chapter 9).
Chapter 1 (this chapter) presents the problems in developing 3D GIS and specifies the scope and the objectives of the research.
Chapter 2 aims at clarifying some basic terms and concepts that are applied later in the thesis. Definitions of objects and methods to derive spatial relationships, fundamental concepts of set theory, object-oriented modelling, 3D visualisation, VR techniques and data access across the Internet are discussed. The chapter presents topics relevant for the subsequent chapters of the thesis.
Chapter 3 presents a study on user requirements. The chapter starts with an introduction on common methods to explore user requirements. The review of methods clarifies techniques to approach users (i.e. investigations into current activities, data and customers, and exploring desired activities, data and potential users). An example of a municipality in a representative town is utilised to clarify types of data, identify the most important objects and their characteristics, and specify potential users. Producers of 3D information are interviewed with the intention of clarifying requirements regarding 3D resolution, visualisation and spatial analysis.
Chapter 4 introduces the client-server approach for the query and retrieval of data. The chapter starts with a review of the capabilities and limitation of VRML and VR browsers, which are later used to specify parameters for the realistic visualisation and description of geometry. Next the system architecture is presented and methods of visualising, querying and editing data controlled by Common Gateway Interface (CGI) scripts are discussed. The importance of database protection of the information, the organisation of CGI scripts, and maintenance of individual files and scripts describing the dynamics of objects is underlined. The chapter outlines the specific requirements for both realistic visualisation and the system architecture.
Chapter 5 summarises the technology- and user-driven requirements and establishes database requirements with reference to both functionality and performance. An extended object definition is introduced. Notations for geometric behaviour, appearance and relationships are introduced and further elaborated. Next, three existing 3D spatial models are compared with respect to urban modelling and database performance. Analysis of 3D FDS motivates the introduction of the Simplified Spatial Model (SSM) for geometric description of spatial objects. The chapter continues with a formal definition of the model. A short discussion about the representation of urban objects in the model completes the chapter.
Chapter 6 elaborates on the capability of SSM to perform 3D spatial analysis. First, it investigates the topological binary relations between geometric objects (simple) according to the 9-intersection model and establishes the number of possible relations in 1, 2 and 3D space. The SSM is inspected then to perform all the 69 derived relations between geometric objects. At the end, the required binary relations according to the user's specification are deliberated.
Chapter 7 presents the mapping of the SSM, geometric behaviour, geometric attributes and theme in the Simplified Spatial Schema (SSS). An object-oriented semantic (conceptual) data model is used to describe the objects and their relationships and transform them into a relational model. Then a concept for spatial indexing and a dynamic creation of LOD on the basis of 3D R-tree are introduced and discussed. The chapter discusses the 3D reconstruction of several models concerning geometry and images for texturing, and clarifies the link to existent data collection procedures.
Chapter 8 deals with three case studies. Case study 1 gives examples of GUI for database query and the corresponding visualisation of the results in the form of text, raster, movie and 3D graphics. Case study 2 presents an algorithm for grouping objects in a 3D R-tree that is appropriate for LOD. Case study 3 discusses the results of the performance tests concerning database size and the speed of database traversing.
Chapter 9 summarises the
research and outlines topics for future work.