地形合成技术在游戏、电影特效、战场模拟等场景中有着广泛的应用需求。地形合成技术以追求结果更真实、过程更高效、控制更方便灵活为目标,先后出现了基于分形模型、物理侵蚀模型和基于样本的地形合成方法。在三种方法中,基于样本的地形合成方法合成结果最具真实感。基于DEM(Digital Elevation Model,数字高程模型)的地形合成是以真实地形的数字高程模型为样本,根据用户绘制的草图,从样本中选择特征匹配的块进行合成,以此来得到具有样本地形风格又符合用户期望的地形模型。本文旨在针对现有方法中的特征区域合成与非特征区域合成进行算法改进,研究一种更加高效的基于DEM的地形合成方法。本文主要研究内容如下:(1)对特征区域的合成,引入传播辅助的KD树用于提高匹配块查找效率。从样本中查找匹配块是基于DEM的地形合成的重要工作,传播辅助的KD树可以帮助更加高效地查找到匹配块。利用传播辅助的KD树可以将好的匹配关系向各自相邻的区域传播,同时省去了KD树查找中时间代价较大的回溯操作。基于传播辅助KD树的特征区域合成实现了在地形合成中特征曲线走向变化的条件下,沿着特征曲线走向传播。合成效率方面,在保证合成结果效果的前提下,合成耗时缩减了一半。(2)对非特征区域的合成,采用并行随机采样加传播的方法。其核心思想是:在小块数量较大时,随机采样可以构建一部分好的匹配关系,通过传播可以将这部分好的匹配扩散开来。借鉴纹理合成的思想,非特征区域的合成并行执行。采用随机采样的方式快速建立匹配关系,根据匹配代价决定随机采样的候选块被拒绝还是接受,通过传播将好的匹配关系向四周传播。将两个步骤反复迭代,实现从一个粗糙结果开始,不断迭代更新优化的过程。通过以上改进,非特征区域的合成效率提升了5-10倍。(3)将本文研究得到的特征区域合成算法和非特征区域合成算法应用于基于DEM的地形合成系统,开发实现新的基于DEM的地形合成系统。同时,设计实验对系统进行测试验证并评判合成效果。通过系统测试,系统功能健全,合成效果良好。