论文部分内容阅读
媒介在人类文明的发展过程中起到了至关重要的作用,是推动文化传播的重要因素,每一种新的媒介都是一个巨大的飞跃。随着计算机科学技术与网络技术的发展,数字网络传播逐渐成为了主要的文化传播方式,三维数字几何模型和文字、声音、图像和视频一样,作为一种新型的数字媒介已经逐渐走入人们的生产生活中,在诸如虚拟现实、影视娱乐、工业制造、地形模拟、医疗诊断、电子商务和艺术历史等各个领域得到广泛应用。三维数字模型最常用的表达方式是三角网格,而模型的质量往往对算法效率和稳定性都有很大影响。随着获取途径越来越多,模型的细节、数据量等也提升迅速,但是网格的顶点分布、规则性、连通性、三角形形状不一定会满足后续数字几何处理的要求。虽然简化技术可以被用来降低模型的复杂性,但是很多简化技术中的采样策略都缺乏灵活性,不能很好地保证简化后网格的质量,同时,一些其它几何建模或计算机图形学算法生成的网格质量也可能会较差,如通过Marching Cube算法、Image-based Visual Hulls算法等从体数据生成的三角网格,就有必要对原始模型通过重新网格化来保证后续算法的效率及稳定性。由于网格表面采样能够很大限度的改变顶点分布,从而大大改善网格质量,所以近些年网格表面采样研究成为热门课题,也是是本文工作的主要内容。
自随机采样技术引入到图形学中以后,近二十多年来采样理论在计算机图形学中已经得到了深入的研究,计算机图形学中很多的问题都涉及到采样,采样点分布的性质将大大影响其在光线跟踪、数字半色调、运动模糊、物体分布和数字几何处理中的应用效果。随着数字几何模型获取和处理技术的发展,近年来研究者也开始了直接在三维模型表面进行采样的算法,近两年又有了在网格表面进行并行采样的研究。但其并行划分并非基于网格表面,而是基于其所在的均匀三维空间,导致大多数子区域是无效的;另外由于网格表面的不确定性与复杂性,每个网格表面与其划分的子区域(cell,即一个小立方体所在的空间)相交的范围、大小、边界等需要复杂的计算,因此作者引入了一个妥协的算法,即使用采样点代替原网格模型。这样一来又引入几个问题:精度损失、预计算的时间与存储消耗、预采样导致的最终结果走样(Bias)、所采用的方法由于扔掉了原始模型,计算测地距离也是使用的近似方法,结果存在一定程度的偏差。
综合在网格表面采样和并行采样方面的研究工作可以发现,对流形表面的并行采样难点在于并行任务的划分。由于网格表面不能用欧氏距离精确划分为可以独立采样的子区域,导致多种划分方法的子区域之间有相互的关系,对采样时的冲突检测过程影响导致无法并行到GPU的各个线程上分别运行。本文提出了一种新的三维网格表面并行采样的方案,可以很好的解决这个问题。
本文的主要贡献有如下几点:
一、提出了一种在三维表面采样子区域的并行划分方法。并在此基础上研究与实现了并行的并行飞镖投掷采样算法,经比较分析,无论从算法效率还是采样点分布上,都得到了很好的结果。
二、提出了一种新的计算局部测地距离的快速算法。在许多应用场合能加快测地距离的计算时间。
三、提出了一种通用多GPU并行流水计算框架,解决在多GPU环境下任务的划分、内存与显存数据传输、绘制环境与设备竞争等问题。