5. Methods of terrain rendering

Each used algorithm of visualizing terrain in raster space is a modification of known algorithms---ray casting and painter's algorithm. Thanks to nature of applications with new data structure, we will not have to consider vector algorithms at all. We will also discuss algorithms for rendering on the screen only (into memory, resp.), no special devices like plotters are assumed.

Terrain can be rendered with original, non-modified algorithm as well but by breaking terrain into primitives we loose information that can be used in rendering. In following paragraphs we will talk about algorithms that work with height fields only. Visualization of TIN works in similar way but thanks to irregularity, algorithms are much more complex.

Basic method for rendering terrain is painter's algorithm, forward or backward (known also as floating horizon method). If we know that heights are arranged in square grid we can easily decide what patch created with bilinear interpolation of four heights is nearer to the eye (instead of bilinear patch approximation with two triangles is often used). Then if we render patches in an order that can be easily constructed in dependance on camera type and view, surface visibility is automatically solved. Improvement of this method is to draw first patches into temporary buffer (every one with different colour) and to do texturing in second pass only on the patches that are really visible.

Backward algorithm works in similar way, first it renders primitives in the front and then in the back. It can draw only such pixels that have background colour. Algorithm is slightly more complex than previous but there is no need for two passes to reduce texturing.

Second type of algorithms is based on ray casting method. Basic method is grid tracing, see [3]. Here a ray is cast and perpendicular projection on the plane with height field is done. Then raster algorithm goes through all cells of height field (cell is formed by four adjacent heights, is is ``a small square'') that incide with this projection of ray. While this is done, it detects if a ray is still above terrain. Test of ray---primitive intersection is done if and only if a ray goes from the state ``above terrain'' to ``below terrain'' and vice versa.

Speedup of this algorithm is based on temporary hierarchy of bounding boxes. Box that bounds the whole object (height field) includes four bounding boxes inside that (like in quadtree) bound appropriate parts of height field. Name of this method is derived from the data structure idea---quad tracing; see [3]. If a height field is large this algorithm can lead to big speedup.

Previous chapter Main Page Next chapter