硬件加速的等值面提取与绘制

2009-9-16 作者: 陈鹏 杨超 吴玲达 来源: 万方数据

关键字: 值面 移动四面体 硬件加速 

图形硬件的发展为通用计算提供了新的平台.利用图形硬件的高密集和并行运算能力,将非规则四面体同格数据映射为纹理,在GPU中从每个四面体提取等值面片,并将其绘制到纹理而得到最终等值面.基于Cg着色器编程语言实现三维雷达作用范围表现的实验结果表明:该方法有效的减轻了CPU负担,提高了等值面提取速度,适于实时应用.

  1、引言

  等值面提取在生物学、医学、物理学、地质学、气象学、电磁学以及系统仿真、游戏等众多领域都有着非常广泛的应用.随着技术的发展,三维数据场的数据量和精度都在不断增加,为了从中动态提取出等值面并实时交互地绘制到屏幕,必须提高算法效率.自从1987年Bill Lorensen提出第一个等值面提取算法Marching Cubes(MC)[1]以来,国内外学者对其进行了深入广泛的研究,取得了很大进展.1991年Gallagher提出了基于数据值区间划分的span—filtering方法[2],1992年Westermann又提出了基于空间坐标划分的八叉树分解方法[3],这两种方法都能有效地减少与等值面相交单元的搜索时间,从而提高了等值面提取的速度.[4,5]等则基于曲面的一致性,利用曲面的邻接关系从一个很小的种子集(在预处理阶段生成)开始不断增长生成最终等值面.

  上面提到的所有算法都是基于CPU来实现的,而随着GPU(Graphics Processing Units,图形处理器)的发展,其原始计算能力超出CPU峰值性能至少一个数量级,而且GPU性能提高的速度比CPU更快,可编程能力和浮点支持能力在不断提高,GPU不再仅仅限于处理特定的图形绘制任务,利用其SIMD(single instruction multiple data)的高度并行计算和多数据流处理能力,逐步成为能够辅助CPU计算的通用计算单元.实时绘制语言的出现无疑更是加快了GPU在通用计算上的应用,如Cg,HLSL以及GLSL或者其他更高级的面向通用计算的绘制语言[6]的出现,使得人们更容易编程实现这些运算.采用图形硬件来做通用计算的动力来自这些新硬件所具有的以下优势:一定的并行性,高密集的运算,减少了GPU与CPU的数据通信.

  过去的几年中,很多人利用GPU提供的并行性,将它作为流处理器来做一些通用计算方面的工作,甚至用来求解有限差分方程组.如Matsumura[8]和Klein[9]分别在2003和2004年尝试利用GPU提取和绘制等值面,但是当时由于显存以及GPU功能的限制,等值面提取和绘制的过程并不能完全在图形硬件上实现.本文将基于非规则四面体的等值面提取和绘制过程完全移到GPU上去执行,从而降低CPU计算负荷,提高了等值面提取和绘制速度.接下来的第二节将对等值面提取算法作一个简单分析,第三节将详细描述硬件加速的等值面提取和绘制算法;第四、五节分别给出实验结果和结论.

  2、等值面提取算法分析

  MC算法[1]以及Doi和Koide提出的Marching Tetrahedra(MT)算法[”1处理的基本单位是逻辑立方体(四面体),基本思想是逐一处理数据场中的每个立方体(四面体),找出与等值面相交的所有立方体(四面体),采用线性插值计算出等值面与立方体(四面体)边的交点.根据立方体(四面体)每一个顶点与等值面的相对位置,将等值面与立方体(四面体)边的交点按一定方式连接生成等值面,作为整个等值面在该立方体(四面体)内的一个逼近表示,将所有的单元连接在一起就形成最终的等值面.MT和MC算法相比,有两大优势,一是与等值面相交的情况只有16种,而MC则有256种;二是不需要考虑连接的二义性.所以为简单起见,本文主要基于MT算法来实现,但该方法同样也可用于MC算法.

  等值面提取在本质上分为两个阶段:第一个阶段是搜索与查询阈值相交的单元;第二个阶段是生成等值面几何图元.为了提高等值面提取的速度.减少所占用的内存空间,许多人提出了多种不同的改进办法.针对第一阶段,按照所使用数据结构和搜索算法的不同,基本上可以分为三类:第一种是基于空间坐标进行数据划分的方法;第二种是基于值范围进行数据划分的方法。第三种则是基于曲面一致性的方法.而对于第二个阶段,通常是以查找表的方式来提高速度,如果仅仅从软件的角度考虑,其可以提升的空间很小,因此很少有人从第二个阶段去研究如何提高效率.然而在等值面提取的第二个阶段,几何图元索引生成、坐标点插值以及法向量插值等关键运算目前基本都是在CPU和内存中进行的.随着图形硬件的发展,利用其高度的并行性和高密集的运算能力来做通用计算方面的工作已不再是什么新奇的事情,而且各种等值面提取算法都需要对大量体元进行独立的处理,这是非常适合于并行运算的.本文正是从这一点出发.充分利用GPU高密集和高并行的运算能力,从硬件的角度针对第二个阶段来加速等值面提取和绘制,减少CPU的负担,提高整体效率.接下来将描述如何将这些运算移植到GPU上去.




<<首页 <上一页  1  2  3  4  下一页>  末页>>  
责任编辑:熊东旭