A subdivision algorithm for smooth 3D terrain models

Current terrain modelling algorithms are not capable of reconstructing 3D surfaces, but are restricted to so-called 2.5D surfaces: for one planimetric position only one height may exist. The objective of this paper is to extend terrain relief modelling to 3D. In a 3D terrain model overhangs and caves, cliffs and tunnels will be presented correctly. Random measurement errors, limitations in data sampling and the requirement for a smooth surface rule out a triangulation of the original measurements as the final terrain model. A new algorithm, starting from a triangular mesh in 3D and following the subdivision paradigm will be presented. It is a stepwise refinement of a polygonal mesh, in which the location of the vertices on the next level is computed from the vertices on the current level. This yields a series of triangulated terrain surfaces with increasing point density and smaller angles between adjacent triangles, converging to a smooth surface. With the proposed algorithm, the special requirements in terrain modelling, e.g. breaklines can be considered. The refinement process can be stopped as soon as a resolution suitable for a specific application is obtained. Examples of an overhang, a bridge which is modelled as part of the terrain surface and for a 2.5D terrain surface are presented. The implications of extending modelling to 3D are discussed for typical terrain model applications.