One of the most important scientific challenges of digital elevation modeling is the development of numerical representations of large areas with a high resolution. Although there have been many studies on the accuracy of interpolation techniques for the generation of digital elevation models (DEMs) in relation to landform types and data quantity or density, there is still a need to evaluate the performance of these techniques on natural landscapes of differing morphologies and over a large range of scales. To perform such an evaluation, we investigated a total of six sites, three in the mountainous region of northern Laos and three in the more gentle landscape of western France, with various surface areas from micro-plots, hillslopes, and catchments. The techniques used for the interpolation of point height data with density values from 4 to 109 points/km2 include: inverse distance weighting (IDW), ordinary kriging (OK), universal kriging (UK), multiquadratic radial basis function (MRBF), and regularized spline with tension (RST). The study sites exhibited coefficients of variation (CV) of altitude between 12% and 78%, and isotropic to anisotropic spatial structures with strengths from weak (with a nugget/sill ratio of 0.8) to strong (0.01). Irrespective of the spatial scales or the variability and spatial structure of altitude, few differences existed between the interpolation methods if the sampling density was high, although MRBF performed slightly better. However, at lower sampling densities, kriging yielded the best estimations for landscapes with strong spatial structure, low CV and low anisotropy, while RST yielded the best estimations for landscapes with low CV and weak spatial structure. Under conditions of high CV, strong spatial structure and strong anisotropy, IDW performed slightly better than the other method. The prediction errors in height estimation are discussed in relation to the possible interactions with spatial scale, landform types, and data density. These results indicate that the accuracy of interpolation techniques for DEM generation should be tested not only in relation to landform types and data density but also to their applicability to multi-scales.