论文部分内容阅读
随着三维扫描、计算机辅助设计和科学仿真等技术的发展和应用需求的拉动,包含上千万甚至数十亿几何图元的三维网格模型变得十分普遍,如何实现这些模型的交互式绘制成为迫切需要解决的难题。多分辨率技术作为一种非常有效的绘制加速技术,一直得到广泛的应用。但是对于大型三维网格模型而言,这种技术的设计和实现本身存在诸多难点。受限于内存容量,网格模型的几何数据及其辅助数据结构不能完全装载进内存,无法直接应用传统的多分辨率构建与绘制算法;受限于总线带宽和CPU处理能力,大型三维网格模型的多分辨率构建普遍耗时很长。本文在深入研究近年来大型三维网格模型简化和多分辨率技术的基础上,通过分析比较各种方法的关键思想及其优缺点,提出并实现了能够有效减少大型三维网格模型多分辨率构建时间的并行构建算法,以及兼顾构建速度和绘制质量的大型三维网格模型多分辨率构建与绘制算法,研究并实现了适用于拓扑复杂、局部深度相差较大模型的大型三维网格模型多分辨率构建与绘制算法,最后把上述成果扩展到网格(Grid)环境上。本文的贡献和创新点主要体现在以下四个方面:1.针对基于外存八叉树的大型三维网格模型多分辨率构建算法,提出了基于子树的任务分割策略和基于基准测试的动态构建任务管理机制,实现大型三维网格模型的多分辨率并行构建和负载平衡,有效地提高了大型三维网格模型的多分辨率构建速度。2.完成了基于自适应空间聚类的大型三维网格模型多分辨率构建与绘制算法,既提高了简化质量,又保持了空间聚类算法的高效性。本文采用适应性八叉树对模型的包围盒进行划分,自顶向下构建模型的多分辨率层次结构,较好地保持了原模型的细节分布;并对多分辨率层次结构中每个节点所包含的三角形片段进行网格排布优化,降低缓存的平均失配率;在实时绘制时,采用基于视点的细节层次选择策略进行模型的细化,以及通过数据预取机制来隐藏磁盘I/O延时,进一步提高绘制性能。3.完成了基于表面分割的大型三维网格模型多分辨率构建与绘制算法,提供最精细的顶点粒度细化选择,保证最佳的绘制质量。该算法采用双层次结构,由渐进网格簇来表示模型的簇层次结构,用于视点相关的粗粒度细化,而由簇节点内渐进网格构建顶点树层次结构,用于精细粒度的局部细化。本文采用GPU实现渐进网格顶点树的视点相关并行细化,极大地提高了模型的局部细化速度,减轻了CPU的负载,使其能够在GPU进行局部细化时并行执行数据的预取,从而更为有效地隐藏数据的I/O延迟。4.在前期的交互式可视化网格(Grid)系统的实现基础上,通过扩展其运行时环境层,为大型三维网格模型的多分辨率并行构建提供网格(Grid)环境支持,实现资源的动态配置与调度,增强并行构建过程的灵活性、容错性和可扩展性;并通过扩展网格(Grid)门户,为用户提供大规模数据集的可视化服务。