论文部分内容阅读
随着计算机图形学的发展,3D几何模型已成为继声音、图像和视频之后又一重要的数字媒体。三维建模是一种利用三维数据将现实世界中三维物体在计算机中进行重建并最终模拟出逼真的三维物体或场景的技术。三维数据就是使用三维扫描设备得到的数据,它记录了有限体表面在离散点上的各种物理参量。它包括的最基本信息是物体在各离散点上的三维坐标。三维建模在建筑设计、文物保护、三维动画、电脑游戏、电影特技等领域起着重要的作用。
随着现代扫描设备分辨率的大幅度提升,对现实世界复杂模型进行逼真表示的需求日益突出。然而在动画制作以及游戏等追求速度和变化的领域,提供原始模型的一系列简化版本具有非常重要的意义。在数字几何处理中,模型简化同样处于基础而重要的地位。三维模型简化经历了从传统的网格简化向点集简化的转变过程。直接基于点图元进行模型简化,可以避免传统网格简化中针对不同的网格表示形式(如曲面片、平面片、三角片、二次曲面等)研究特定的简化算法。
本文在研究前人关于点集模型简化工作的基础上,分别提出一种基于局部曲面分析和Level Set方法的点采样几何模型简化算法。在基于局部曲面分析技术的简化算法中,通过引入局部邻域和局部采样密度概念,结合空间二叉树数据结构—k-d树和Bounds Overlap Ball Test技术加速查询每个采样点的最近邻近点和局部采样密度。采用堆排序算法对所有采样点根据局部采样密度进行排序,每次选取局部采样密度最大的点,若局部采样密度相等时,则选择最近邻近距离较小的点并将其删除。算法支持模型的多分辨率表达,可应用于带宽有限的点集模型的网络传输。其效率和有效性已通过案例说明且获得了验证。
在基于最远点重采样思想的点集模型简化算法中,根据随机产生的初始采样点集合,结合Level Set方法以及Fast Marching技术,运用Voronoi图增量构造法,重复地构建已有重采样点集的最远点,并将其作为新的重采样点加入已有重采样点集合中,从而渐进地生成均匀分布的目标简化模型;通过用户交互式地控制目标模型的采样密度,构建点集模型的多分辨率表达。实验结果表明,该算法稳定、快速且易于实现。