# 2. Currently used data structures

We can divide models of terrain into two types, real and virtual. In GIS, there is of course interesting first case only, that is real terrain. Data can be obtained either by taking photographs from airplane or satellites, or by direct measuring in terrain. In both cases, we obtain data about terrain in finite number of representative points (usually from thousands to hundreds of thousands points), next we use a hypothesis that these data (e.g. height) are varying continuously, so we use some kind of interpolation (e.g. bilinear, bicubic). Note that points that are derived from representative ones via interpolation are just an approximation of real terrain.

If we use direct terrain measuring, representative points are distributed ``randomly'', that is they do not create any regular geometric pattern. In fact, these points should be distributed more dense in places where bigger accuracy is needed (e.g. steep slopes, river banks). Natural data structure for such a data is triangulated irregular network (TIN), where vertices of triangles are representative (measured) points, edges give information how to interpolate between these points. This data structure can be modified to hierarchical version to achieve a) faster point location in terrain b) storing of several representations of the same terrain in various resolutions (level of detail), mainly for speeding up rendering. TIN is able to describe any terrain feature (but almost nowhere perpendicular slopes or overhangs are considered), point location can be done quite fast (especially with hierarchical modification). Opposite to this, modifications are not simple, with every change we must check (and possibly modify) the triangulation. If we do this with simple (and fast) methods, we can obtain thin triangles that are very unsuitable for interpolations.

If we measure from bird's eye view we get representative points in regular pattern, for example square grid, no matter how locally complicated terrain is. With this view, we can of course measure only one piece of information (e.g. height) above one point of ideal earth surface, model is then in the form of function of earth coordinates. If we have representative points in square grid we can store data efficiently in two dimensional array. Most often stored data are heights and so this data structure is called height field. Pros and cons are near inverse against TIN. It is not possible to describe every terrain feature (Sometimes height field is modified so that it can describe perpendicular slopes, but more complicated features are still not possible), there is no adaptivity if a terrain is locally more complicated (sampling is the same in the whole height field). On the other hand, modification of such a model is trivial (in sense of work with data; modification itself, e.g. erosion, can be a complex task), point location is very fast. Thanks to listed purposes this data structure is used if it is necessary to modify it often, if information from it is extremely often needed (collision detection), if we do not require high accuracy (terrains of area of thousands km^2) or if a focus point of application lies somewhere else (image synthesis software).

To choose what data structure to use for virtual terrain model depends on (besides others) how do we want to generate it and what manipulations do we want to do. Most of algorithms work with common height field; there are also algorithms that work with TIN or with regular lattice different from square (triangles, hexagons); see [1].

The last criterium how we can choose data structure is algorithm for rendering (hidden surface elimination). Algorithms such as ray casting prefer structures based on regular lattices, hierarchical if it is possible (for speeding up ray---object intersection test). Combination of painter's algorithm with regular lattice is very fast and often used (it is not necessary to sort polygons, arrangement is obvious from the lattice). In algorithms such as scan line or z-buffer it does not too depend what data structure is used, but if we want to avoid aliasing problems we choose structure that leads to bigger polygons. It is similar in case of continuous (vector, non-raster) algorithms that cannot use information about arrangement, we choose structure with less number of polygons (decimated TIN).