3. Motivation for new data structure creation

In image synthesis software, terrain is an often used object. Examples of applications are architecture, advertising, computer art, computer games, virtual environments etc. Here we do not need accurate terrain model, we are interested in appearance only. Due to interactivity of software or big number of rendered images it is necessary to achieve maximal possible speed, so almost always data structures with regular (almost always square) lattice are used, even if they have bigger memory requirements. This is possible because in listed applications we do not visualize large areas (mainly at most several km^2).

Here we get first problem that appears if we use regular sampling of terrain. Virtual camera is usually perspective, polygons that lie in the front are bigger than those in the back. If we choose linear (bilinear) interpolation of heights, we get very ugly ``teeth'' in the front. When we refine sampling we get two problems: size of data quadratically increases (the biggest commonly used height fields contain about 1000x1000 heights) while in the back, size of polygons decreases to subpixel size, causing aliasing problems. Time needed for rendering also quadratically increases (except of ray casting based algorithms).

We can solve this problem in several ways. First of them is not to use bilinear interpolation. Instead we can use approximation with e.g. Coons B-spline patches (let us recall that in our application it is not needed for sampled points to lie on the surface, we do not need exact model). Using this approach e.g. for height field of size 256x256 we get about 65,000 bicubic patches---it is sure this will slow down rendering. Next, if we use bad textures, terrain in the front will look unnaturally smooth.

Another choice is to use true displacement---this method works similar to bump mapping but geometry of the object is really changed. Its use can be for example such that in the front bilinear patch will be changed to ``bicubic'' (we can add some random height to increase number of details) and this change will smoothly disappear in the direction to the background; from some distance there will be no changes to geometry. Advance of this approach is adding procedurally generated details of arbitrary small size, this cannot be done simply in other methods; see [2]. Unfortunately only small number of rendering engines support this ability (e.g. Photorealistic RenderMan) because its correct implementation is not trivial.

Next approach is based on using several models of parts of the same terrain. It is for example possible to use rough sampling for the whole terrain, in the neighbourhood of camera we cut it off and replace it with finer representation. This cutting can be done by using methods of constructive solid geometry (CSG) or with special textures (rough terrain will be invisible in the neighbourhood of camera causing the finer model to be visible). Structure of nesting these models is stored outside the height fields. Nesting can be of course recursive. If we do not work systematically there can appear problems with overlaping models at the same level of nesting. One opportunity how to avoid these problems is to constrain what part of terrain will be replaced with finer one. It can be done for example with quadtree data structure or with its extension, structured grid (area is not divided into 4 parts but into m x n parts). Problems with this data structure are obvious---much more complicated work with it, parts of terrain must be connected continuously.

If an application needs to work with simple terrain only it can use one of the modifications noted above. Constraint that follows from that there is defined just one height above every point will not appear in this case. However, in advertising off-road vehicle will look better in the complicated, hard accessible terrain rather than on the meadow. Here we can do nothing with height field representation---it cannot store highly inclined slopes (it depends on density of sampling), overhangs are not possible. Again, there are ways how to overcome this drawback.

If we want to represent walls of at most perpendicular slope we can slightly modify height field. Information about height will be extended with two bits---one for (for example) north, second for east direction. If one of these bits will be set to 1 it means that heights between current point and point in appropriate direction are not continuous, there is a jump. If a bigger perpendicular wall is created in this way it is necessary to use good texture for it to hide that this part of surface is smooth (it holds in general in height fields---the more steep surface the worse it looks). This modification needs of course special renderer that supports this extension, or to break terrain into triangles before rendering---doing this we loose possibility to render it (as a special object) faster.

Second possibility, often used, is to use height field as an ordinary object and to work with it. For example a simple cave can be created using two height fields, ``convex'' and ``concave'' one. Space between them is quite a good approximation of cave, we can add some objects into it to hide artifacts. If we define height field in some way as an object enclosing some volume (for example by cutting a cube with this height field) we can use CSG. Then we can create overhang or another complicated feature using CSG difference operation. As it was said, this technique is often used. Its drawback is that CSG has not any relation to a terrain and so algorithms that modify terrain (e.g. erosion) cannot be used in this case.

Next problem that must be solved is definition of attributes of terrain in its different parts. Namely these are textures (or materials), relation between terrain and another objects (both solids like vegetation or stones and particles like sand or water). Materials can have optical properties only, they can also influence algorithms for terrain modification (rivers will have steeper banks in softer rocks). In currently usually used algorithms there is considered only one material in the whole area---this is quite unreal even in the small scale.

Let us sum up previous information: for general model of terrain a data structure is needed that can describe every shape (like general TIN), memory requirements as well as complexity of work should be small for simple terrains (the best would be height field like complexity). It should be able to store terrain in different resolutions in different parts to achieve level of detail effect. Next it is necessary to have relations to volume properties of terrain and to objects that are connected with it. Existing algorithms for modifications, generation and rendering of terrain should be easily convertible to work with new data structure. Mainly this should hold for rendering algorithms so that it would be possible to use some existing (good) renderer. Currently there is no structure that fulfills all of these parameters.

Before we derive such a structure we must give brief overview of basic methods for generating and rendering terrains.

Previous chapter Main Page Next chapter