FractLand Infinite virtual landscapes Project duration: 1995-1996 Contact: Thomas Schweighofer, Klaus Radatz, Dieter Schmalstieg
Description	Interactive applications that involve the display of outdoor scenes such as flight simulators often require a lot of graphical detail to be convincing.
Application	flight simulators, training applications, landscape visualization
Problems	The required amount of detail creates a number of problems: Modeling of details is tedious and even impossible to accomplish beyond a certain scale. Too many details overload even powerful rendering hardware. Lots of details require huge amounts of storage, both on disk and in main memory.
Approach	Luckily, not every details is of the same importance for perception. On the one hand, the user expects accurate representation of certain artifacts, e.g. famous buildings or other landmarks but on the other hand, details of the natural landscape, such as small-scale terrain features (small hills and holes) or individual trees are generally not so important. We can make use of this observation by implementing procedures that create the necessary details. These details can be computed on the fly, if they come in sight, and simply discarded, if they move behind the user or out of sight. In that way, the whole landscape is never represented at once, and the landscape's extent can be literally infinite. The only thing that we have to take care of is that the details are reproduced in the same way if the user visits the same location twice. This is done by using a deterministic random number generator. We have implemented a simple fly-over applications for an infinite virtual landscape consisting of hills, mountains and lakes.

T he basic procedure for the generation of terrain is called midpoint displacement. We start with a user-defined coarse elevation grid that defines the height of the terrain at regular grid points, similar to the color coding on a map.

F rom that grid, the midpoint displacement method generates more detailed terrain by repeatedly subdividing a rectangle between four grid points into four smaller rectangles. Elevation values are interpolated, and then a random offset (either positive or negative) is added according to a fractal formula. The space between the grid points is filled with 3-D triangles that can directly be displayed by the 3-D hardware in real time.

A s the user flies along and the visible portion of the world changes, new details are created using the midpoint displacement, and the data for regions that have become invisible, is discarded.

T o further reduce the number of geometric primitives that must be stored and displayed, levels of detail are introduced: With increasing distance to the user, each grid region is subdivided less often, resulting in a coarser representation of the terrain. Regions further away are smaller on the screen, so the absence of detail goes unnoticed. As a specific region comes nearer, its representation is refined. To avoid abrupt changes, the transition between two levels of detail is achieved by a blending (interpolation) over multiple frames.

F uture plans:

• add a procedural generator forrest, villages, and roads
• write a small drawing program to quickly "paint" landscapes in 2-D that can then be displayed with the FractLand program.

Download a movie of a sample flight (QuickTime, gzipped 832K) (QuickTime, 4.5M)

Page maintained by Dieter Schmalstieg