Abstract: The paper presents a new algorithm for generating the terrains with a small number of scattered feature points. The feature point, which has a position vector and four incidence vectors and which can describe the position and form of a mountain, is defined. An interpolation algorithm, called Ellipse Terrain Interpolation, is proposed for calculating the height of vertices within the incidence of the feature point. The terrain area is divided into the quasi-uniform grid and the interpolation results in the terrain template. The fractal method is used to iterate the terrain template to get multilayer terrain details. The algorithm has the advantage over real-terrain-data-based algorithms that it needs fewer input data and that the local characteristic of the terrain can be changed arbitrarily and the advantage over simple fractal-based methods that it overcomes the difficulty of controlling the position and the form of the terrain. Our experiment proves that using a small number of scattered feature points, the form of the terrain can be controlled and realistic terrain can be obtained.

Key words: terrain generation, scattered feature point, quasi-uniform grid, ellipse terrain interpolation, fractal