Nội dung

CHAPTER 15 Beyond Digital Terrain Modeling Chapter 14 discusses the more traditional development and applications of terrain models. Here, we look at some extensions of these models for specific problems. 15.1 15.1.1 DIGITAL TERRAIN MODELING WITH COMPLEX CONSTRUCTION Manual Addition of Constructions on Terrain Surface For simplicity it is usually assumed that terrain models are monotonic in X and Y — there is only one possible Z for each XY location. This is often true in the real world, but not always — occasionally there are caves, tunnels, overhanging cliffs, bridges, and overpasses. In the work by Tse and Gold (2002), the standard TIN model is extended by merging some aspects of terrain modeling (TINs), computational geometry (the Quad-Edge data structure), and computer aided design or CAD (Euler operators, which guarantee to preserve the connectivity of the surface after they are applied). They found it easy to combine them to give the usual operations on a 2D triangulation — as well as add an operator that generates a hole between any two nonadjacent triangles (which is really the same thing as adding a bridge or handle to the surface). Figure 15.1, Figure 15.2, and Figure 15.3 give simple examples, and Figure 15.4 and Figure 15.5 show part of a Hong Kong city model. Thus, a simple modification of the basic triangulation algorithm allows one to interactively modify the terrain model to add complex features that are otherwise unavailable. Because one is still forming a connected surface, a variety of topological operations, such as neighborhood selection and flow modeling, may be performed. Clearly another, even higher, layer of operations would permit one to add predesigned features such as buildings, dams, tunnels, etc. to our terrain model. 297 © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 297 — #1 298 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY (a) (b) Figure 15.1 (a) TIN model of a surface with a tunnel: (a) a tunnel on a TIN model and (b) the enlarged tunnel. (b) Figure 15.2 (a) TIN model of a surface with bridges: (a) two bridges on a TIN model and (b) the enlarged bridge. (b) Figure 15.3 15.1.2 TIN model of a ground surface with buildings and bridge: (a) a building on a TIN model and (b) a bridge connecting two buildings. Semiautomated Modification of the Terrain Surface Section 15.1.1 showed simple terrain modification based on modifying the TIN by adding and deleting individual points with (X, Y , Z) coordinates. This is effective but slow to do by hand. An alternative approach is to “cut” the triangulated surface with a “knife” in order to sculpt it to the form desired. One first sets the knife size, location, and orientation and then performs the cut (or intersect) operation. One may © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 298 — #2 BEYOND DIGITAL TERRAIN MODELING Figure 15.4 A partial view of Hong Kong harbor. Figure 15.5 Part of the Hong Kong city model. 299 either lower the terrain surface to the knife position, for example, cutting into the side of a hill, or else raise the surface to the knife position, creating an embankment or dam. More points are added to the triangulation to form the intersection lines between the knife and the original terrain, and one assumes a maximum slope (less than vertical) for the edges of the cut or embankment. Figure 15.6(a) shows a simple TIN model with the knife in place. Figure 15.6(b) shows the result after the surface is lowered to the knife (with a 45◦ embankment specified). Figure 15.6(c) shows the knife positioned across a valley, and Figure 15.6(d) shows the result of raising the terrain surface to the knife, forming a dam structure across the valley. © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 299 — #3 300 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY (a) (b) (c) (d) Figure 15.6 Terrain modification by “cutting” the triangulated surface with a “knife.” (a) The knife positioned on the terrain. (b) Modified terrain after lowering the surface to the knife blade. (c) The knife positioned across a valley. (d) The dam created after raising the surface to the knife blade. 15.2 DIGITAL TERRAIN MODELING ON THE SPHERE With the introduction of the concept digital earth, global modeling of the Earth’s surface (Gold and Mostafavi 2000) has become a hot topic. The digital terrain modeling techniques described in this book can also be extended to spherical terrain modeling. 15.2.1 Generation of TIN and Voronoi Diagram on Sphere In planimetric terrain modeling, as discussed in Chapter 4, grids and TINs have been widely used to tessellate the terrain. On the sphere, a similar tessellation model needs to be used. The concept of spherical surface tessellation was presented by Fuller, a German cartographer, for map projection in the 1940s (Dutton 1996). Since then, many researchers have approached this problem to project, analyze, and index global data. Many methods are based on inscribed polyhedrons, such as the tetrahedron, the cube (Snyder 1992), the octahedron (Dutton 1989, 1996; Goodchild et al. 1991; Goodchild and Yang 1992; Otoo and Zhu 1993; Clarke and Mulcahy 1995), the dodecahedron (Wickman and Elvers 1974), and the icosahedron (Fekete 1990; White et al. 1992; Lee and Samet 2000), as shown in Figure 15.7. The edges of the polyhedron are projected to the spherical surface and form the edges of spherical triangles. The octahedron-based tessellation is a regular triangular mesh on the sphere, called the octahedral quaternary triangular mesh (O-QTM). Figure 15.8 shows an © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 300 — #4 BEYOND DIGITAL TERRAIN MODELING 301 (a) (b) Figure 15.7 (a) Spherical surface tessellation based on inscribed polyhedra (Reprinted with permission from White et al. 1992): (a) five polyhedra and (b) projected to the spherical surface. (b) Figure 15.8 (c) Hierarchical tessellation of the spherical facet based on octahedron (Dutton 1996): (a) level 1; (b) level 2; and (c) level 3. example of O-QTM at three difference levels (Dutton 1996). Terrain modeling can then be applied to the QTM. The QTM can also be used as a coordinate system on the sphere, just like the regular grid or triangular network on a 2D plane. In the QTM, a point is represented by a triangle, an arc is represented by a series of neighbor triangles, and a region is represented by a series of neighbor triangles on and within its boundary trace. From the QTM, a TIN can then be constructed. Alternatively, spherical TINs can also be derived from spherical Voronoi diagrams (Augenbaum 1985; Robert 1997; Chen et al. 2003). Figure 15.9 shows an example of spherical Voronoi diagram and its dual — the spherical TIN. 15.2.2 Voronoi Diagram for Modeling Changes in Sea Level on Sphere Mostafavi and Gold (2004) used the dynamic Voronoi diagram on the sphere to model the continually changing height of the sea, rather than of terrain. Figure 15.10(a) shows an initial set of cells, each representing a fixed mass of water, and uses the free Lagrange method to simulate flow under lunar gravitational influence, and hence the sea height. Coastlines were modeled by a double line of fixed Voronoi cell generators. Figure 15.10(b) shows the result after simulation started: high water (HW) is indicated by smaller, and therefore higher, cells, while low water (LW) is shown by larger, © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 301 — #5 302 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY (a) Figure 15.9 (b) Spherical TIN formation: (a) Voronoi diagram and (b) Delaunay triangulation. (a) (b) LW HW Figure 15.10 Dynamic Voronoi diagram on sphere to model the continually changing heights of sea: (a) initial configuration of Voronoi cells and (b) Voronoi cell configuration indicating lunar tides. lower cells. Figure 15.11 is a Mercator projection showing the flow directions and velocities of each cell. 15.3 THREE-DIMENSIONAL VOLUMETRIC MODELING Two dimensions are required in terrain modeling to generate the underlying triangulation or grid. Once elevations are added as an attribute, the result is usually known as “2.5D” modeling, although the data structures remain 2D. Once the topology (or connectedness) can no longer be represented on the plane (as in 3D objects in CAD or games), a surface representation, composed usually of triangles, is often used, as in Section 15.1. However, for some applications a surface model is inappropriate, and a full 3D volumetric model is needed. Examples include geological, atmospheric, and oceanographic models, where attributes need to be assigned to arbitrary locations in 3D space. In some cases a 3D grid may be used, or an octree where nodes represent volumes. A more flexible approach is to replace the 2D triangulation structure © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 302 — #6 BEYOND DIGITAL TERRAIN MODELING Figure 15.11 Mercator projection showing cell velocities and directions. Figure 15.12 Delaunay and Voronoi cells in three dimensions. © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 303 — #7 303 304 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY Figure 15.13 A three-dimensional isosurface. The color plate can be viewed at http://www. crcpress.com/e_products/downloads/download.asp?cat_no=TF1732. with a 3D Delaunay tetrahedral model, thus allowing the connection of arbitrarily located observations, and then to add the 3D Voronoi cells. While conceptually simple, the implementation is often difficult, due to the large number of degenerate (coplanar, cocircular) cases. Figure 15.12 shows a 3D data set with one Delaunay cell and its neighbors shown on the left and a Voronoi cell on the right. Various interpolation techniques, such as the equivalent of the 2D Sibson or natural neighbor interpolation, may be used, and these behave well for the anisotropic distributions of data that are often found in three dimensions. For visualization purposes the individual tetrahedral may be sliced, based on the values at the corner vertices, to give the 3D equivalent of 2D contours. Figure 15.13 shows a single 3D isosurface constructed in this way. © 2005 by CRC Press DITM: “tf1732_c015” — 2004/10/25 — 12:48 — page 304 — #8 Epilogue It was natural that we felt relieved and excited somehow after having completed the final draft of this book and having uploaded the materials onto the ftp site of the publisher. However, soon we started to feel obliged to write this epilogue because there are a few issues confronting us. We thought it is really a pity that no authored book in this discipline had been made after over 40 years of development although there are two edited works, Terrain Modelling in Surveying and Civil Engineering by Petrie and Kennie (1990) and Digital Elevation Model Techniques and Applications: The DEM User Manual by Maune (2001). Our aim was to write a book systematically covering a wide range of topics in digital terrain modeling so as to fill in the gap in this area. While writing, we were faced with a number of challenges. The first challenge was related to the selective omission of materials. It was difficult to make decisions. This is because the term “digital terrain modeling” would mean different things to different groups of terrain specialists and practitioners. To the producers (including photogrammetrists and surveyors), data acquisition and terrain surface modeling are of most concern; to geographers, terrain analysis and applications are the most important; to geologists, interpolation techniques seem to be critical; . . . . It is really hard to satisfy all these groups. In the end, we decided that those topics are simplified if they have rich bodies of literature available. For example, we did not include many algorithms and techniques for interpolation and triangulation as there is a huge body of literature (e.g., Su 1989; Chin 1995; Sakhnovich 1997; de Berg 2000; Phillips 2003) in these areas covering the techniques developed in computational geometry and geosciences. Contouring is a traditional topic in digital terrain modeling but is only briefly discussed in this book because a book authored by Watson (1992) has been dedicated to this topic. Similarly, DTM-based terrain analysis is briefly discussed because of a recent book edited by Wilson and Gallant (2000). The second challenge was related to the depth of discussion. We may disappoint those readers who are interested in mathematics because we present neither mathematical proofs nor technical details. Indeed, it is the main aim of this book to present a systematic accounting of stories in digital terrain modeling at the level of principles and methodology, as the title of the book suggests. 305 © 2005 by CRC Press DITM: “tf1732_c016” — 2004/10/20 — 15:45 — page 305 — #1 306 DIGITAL TERRAIN MODELING: PRINCIPLES AND METHODOLOGY The third challenge was related to the boundary of the discipline. Because the terrain surface is of concern to all geosciences and a huge body of related modeling methodology and applications is available, we have to cut down the contents somewhere. Therefore, we did not cover much on Voronoi diagrams (e.g., Davies 2000; Okabe et al. 2000) although we are very interested in this topic. Similarly, we did not cover much on geostatistics (e.g., Olea 1999) and even omitted the famous Kriging technique. We only simply mentioned the surface modeling on sphere and with construction in Chapter 15. All in all, we are pleased with the compilation of some materials presented to you, but also feel guilty about the imperfection. Your comments are appreciated so that we could make improvements in another edition, if possible. © 2005 by CRC Press DITM: “tf1732_c016” — 2004/10/20 — 15:45 — page 306 — #2