MFHQTERRAINS

Mathematical Foundations of High-Quality Terrain Models

 Partecipanti

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'A digital terrain model is a representation of a real-world terrain in a computer. Terrain models play an important role in geographic information systems, where they are used for numerous purposes, like path planning, visualization, and terrain analysis. One of the main ways to represent a terrain is by a triangulation: some points are sampled from the real terrain, and they are connected by triangles that cover the whole terrain area. This results in a subdivision into triangles. There are many ways to triangulate the points, and choosing the right one is essential to obtain terrain models that represent the real terrain faithfully. In particular, the shape of the triangles is very important: long and skinny triangles should be avoided. However, that is not enough. The current approach to triangulating terrains does not take the elevation of the points into account. This can create artifacts---like spurious pits, interrupted valley lines and artificial dams---, a serious obstacle for performing terrain analysis tasks, especially for hydrology or erosion simulations. This research will study combinatorial and geometric properties of triangulations, in order to design new automated methods to find triangulations with well-shaped triangles and---at the same time---as few artifacts as possible.'

Introduzione (Teaser)

Digital terrain models are widely used in applications from planning transportation infrastructure to land-use management and from geographic information systems to computer games. EU-funded researchers developed new triangulation methods to reconstruct pieces of Earth's surface more accurately.

Descrizione progetto (Article)

Digital terrains are the graphs of continuous functions that assign a height to every point on a plane. Terrains model landscapes with mountains, gorges and plains. Trees, buildings and other man-made features are removed, leaving just the underlying land surface. Modelling a piece of Earth's surface as such a 3D graph is, however, difficult because it is not possible to know the height of every point.

From the height of sparse, unevenly distributed sample points, researchers approximate the height at other points. The sample points are used to draw triangles and get a polyhedral terrain resembling the original terrain. The EU-funded 'Mathematical foundations of high-quality terrain models' (MFHQTERRAINS) project focused on how to triangulate sample points to get the most realistic terrain.

The problem with triangulation is that the height of each point is determined by two sample points relatively far away from each other. MFHQTERRAINS researchers addressed the skinniness of triangles. Among the different triangulations of a given set of points, they found a family of Delaunay triangulations that maximises the minimum angle.

Specifically, these higher-order Delaunay triangulations are alternatives to conventional Delaunay triangulations, which can be easily computed to produce high-quality terrain models. The MFHQTERRAINS researchers studied the implications of the inherent imprecision of all digital models to water flow computations.

Different approaches to assigning the water flow direction to every point of terrain models were compared. Water flow is used in computations of the water drainage network and watersheds that are in turn used to model various hydrological and biological processes. The results are, therefore, expected to be applicable to various aspects of terrain analysis, including soil erosion potential and plant species distribution.

The problem of triangulating a set of sample points is well known beyond computational geometry. A deeper understanding of the mathematical properties of triangulated terrains gained by the MFHQTERRAINS project will open the door to solving challenges in numerical analysis, as well as computer graphics.