Under the virtual battlefield environment background, aimed at the special request in the terrain visualization, this paper calculates the terrain data by using the Newton interpolation algorithm which should be supplemented, and carries on the optimized choice using the genetic algorithm in the interpolation data. The test result shows that this terrain data interpolation method is simple, fast, practical and without information distortion.