（测试计量技术及仪器专业论文）基于gpu流计算模式的非凸体碰撞检测算法的研究.pdf

摘要 在机器人、虚拟现实及c a d c a m 等领域中，物体之间的碰撞检测是一个 关键问题，其基本任务是确定两个或多个物体彼此是否发生接触或穿透。 本论文在分析总结国内外各种碰撞检测算法的基础上，利用图形硬件的流计 算优势，把非凸体转为三角形面片结构，映射到g p u 的f r a g m e n ts h a d e r 中进行 碰撞检测计算，取得了较好的效果，为g p u 图形硬件通用计算的发展做出了一定 的贡献。同时还针对n u r b s 曲面的细分和修剪进行了分析应用，为进一步的深 入研究打下了良好基础。 本课题是四川绵阳异形工件检测项目的一部分，围绕着对孔、槽、腔、涡轮 等非凸异形工件的碰撞检测问题，主要进行了以下研究工作： 1 设计解析多种数据文件的框架，并实现了针对3 d s 格式文件的数据读 取和场景绘制。 2 在介绍g p u 图形硬件及开发语言的基础上，把分离轴检测算法映射到 f r a g m e n ts h a d e r 中，实现了基于g p u 流计算模式的非凸体碰撞检测算 法。 3 针对n u r b s 曲面的细分和修剪问题，分析比较了三种实现方法，并在 t n u r b s 库的基础上进行扩充修改，初步实现了n u r b s 曲面的细分修 剪要求。 关键词：碰撞检测非凸体g p u 图形硬件c gs h a d e r 语言n u r b s 曲面细分和 修剪 a b s t r a c t c o l l i s i o nd e t e c t i o ni so n eo fv i t a lp r o b l e m si nt h ef i e l d so fr o b o t i c s ，v i r t u a l r e a l i t ya n dc a d c a m ，e t c i t sf u n d a m e n t a lt a s k i st od e t e c tw h e t h e rt h e r ea r e c o n t a c t sa n dp e n e t r a t i o n sb e t w e e nt w oo ra m o n gm u l t i p l eo b j e c t s b a s e do nt h ei n t e n s i v ea n a l y s e sa n ds u m m a r i z a t i o n so fv a r i o u sa l g o r i t h m sa b o u t c o l l i s i o nd e t e c t i o n ，t a k i n ga d v a n t a g eo ft h eh i g hs t r e a mc o m p u t i n gp o w e ro fg r a p h i c s h a r d w a r e ，t h ed i s s e r t a t i o nc o n v e r t sn o n c o n v e xo b j e c t si n t ot r i a n g l es t r i p s ，m a p st h e g e o m e t r yc o m p u t a t i o no fc o l l i s i o nd e t e c t i o nb e t w e e nt w ot r i a n g l e si n t os h a d e r so ft h e p r o g r a m m a b l eg r a p h i c sp r o c e s s i n gu n i t ( g p u ) t om a t c ht h ep a r a l l e la r c h i t e c t u r eo f g r a p h i c sh a r d w a r e ，a n dp r o d u c e s f a s ta c c u r a t er e s u l t sv i ar e a lt i m e r e n d e r i n g a n a l y s e sa n da p p l i c a t i o n sf o r t h et e s s e l l a t i o no ft r i m m e dn u r b ss u r f a c e sa r e p r e s e n t e d ，w h i c hd og o o df o rt h ef u r t h e rr e l a t i v er e s e a r c h t h i ss u b j e c ti sap a r to f t h ea b n o r m a l w o r k p i e c em e a s u r i n gp r o j e c ti nm i a n y a n g ， s i c h u a np r o v i n c e a i m i n ga tt h ec o l l i s i o nd e t e c t i o np r o b l e m si nr e a l i s t i cs i m u l a t i o no f n o n - c o n v e xw o r k p i e c e s ，s u c ha sh o l e s ，g r o o v e s ，c a v i t i e so rt u r b i n e s ，w eh a v ed o n et h e f o l l o w i n gw o r k ： 1 d e s i g nt h ef r a m e w o r ko fa n a l y s i s i n gv a r i o u sf i l ef o r m a t s ，a n di m p l e m e n tt h e 3 d sf i l ep a r s e rt or e a ds c e n ed a t a 2 t h r o u g hi n t r o d u c i n gg p ug r a p h i c sh a r d w a r ea n di t sd e v e l o p m e n tl a n g u a g e ， r e a l i z et h e m i g r a t i o no fs a t ( s e p a r a t i n ga x i st h e o r e m ) a l g o r i t h mi n t o p r o g r a m m a b l eg p u sf r a g m e n ts h a d e r , i m p l e m e n tt h ec o l l i s i o nd e t e c t i o n a l g o r i t h mb e t w e e nn o n c o n v e xw o r k p i e c e sb a s e do nt h es t r e a mc o m p u t i n g m o d e l 3 c o m p a r et h r e es o l u t i o n sf o rt h et e s s e l l a t i o no f t h et r i m m e dn u r b s s u r f a c e s m o d i f ya n de x p a n dt h et n u r b sl i b r a r yt ob a s i c a l l yi m p l e m e n tt h ed e m a n d o f t h es u b j e c t k e yw o r d s ：c o l l i s i o nd e t e c t i o n ，n o n c o n v e xw o r k p i e c e ，g p ug r a p h i ch a r d w a r e ， c gs h a d e rl a n g u a g e ，n u r b ss u r f a c e ，t e s s e l l a t i o na n dt r i m 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨叠盘茎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：知私凯签字噍m 形年l z 月z 日 学位论文版权使用授权书 本学位论文作者完全了解盘凄盘堂有关保留、使用学位论文的规定。 特授权盘叠盘翌可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：备- 懈札 导师签名 诸版 签字日期： 哮年j 2 月l 2 日 签字日期：排i t 月2 厂日 灭津人学硕l 学位论文 第一章绪论 本章简单介绍碰撞检测的概念，说明了课题中应当解决的技术问题、相应的 方案设计和创新之处。 1 1 碰撞检测 碰撞检测是自动机器人、c a d c a m 、虚拟现实、动画仿真领域不可避免的问 题之一，其基本任务就是确定两个或多个物体间是否发生接触或穿透。随着计算 机图形学的不断发展及虚拟现实、c a d c a m 等领域的兴起，实际应用对碰撞技术 的要求越来越高，仍然存在许多迫待解决的问题，如处理大规模复杂场景、处理 非凸物体、面向特定领域碰撞检测算法的效率等。 多面体为凸的含义是多面体内部的任意两点连线完全处于该多面体的内部， 可将凸多面体简称为凸体。一些高效的碰撞检测算法主要局限于凸体间的碰撞检 测，比如基于特征类的碰撞检测算法和基于图像的碰撞检测算法仅能快速检测凸 体之间的碰撞，而在实际的虚拟场景中，多数物体均是非凸物体。虽然一些改进 算法提出采用表面凸分解技术组织非凸体，但这样做对算法性能会有很大影响。 在精密测试技术领域，三坐标测量机是近三十年来发展起来的一种集光学、 机械、数控技术和计算机技术为一体的大型高效率精密测量仪器。它广泛的应用 于机械制造、电子、汽车和航空航天等工业中。他可以进行零件和部件的尺寸、 形状及相互位置的检测，例如箱体、导轨、涡轮和叶片、刚体、凸轮、齿轮、形 体等空间型面的测量。此外，还可用于划线、定中心孔、光刻集成线路等，并可 以对连续曲面进行扫描及设备数控机床的加工程序等。 随着计算机技术，尤其是仿真技术的发展，虚拟智能三坐标测量系统应运而 生。虚拟三坐标测量系统根据c a d 工程图纸建立三维模型，自动选取有效测头运 动路径，并根据专家系统进行模拟测量，有效降低了c a d c a m 中从零件设计到实 际生产间的周期。测头路径规划、三维计算机模型的碰撞检测等一直是其中的关 键技术，尤其是后者贯穿于其它关键环节当中，特别是针对非凸体模型的实时碰 撞检测一直是工业c a d c a m 发展的瓶颈。 天津 学颂k 学位论立 1 2 论文主要工作 小课题足四川绵阳异形工件检测项目的一部分，重点解决三坐标测量机检测 孔、槽、腔、涡轮等非凸异彤工件的问题，以实现虚拟智能三坐标测量系统实时 仿真检测。 论文主要研究计算机图形学中针刘非凸体的实时碰撞检测的关键技术，将可 编程g p u 与传统的层次包围体树检测方法相结合，在解决非凸体精确碰撞检测的 前提下提高检测算法的效率。在此过程中需要解决以下问题： 1 ) 如何分析读取模型文件，获取模型顶点坐标等数据信息。 2 ) 针对复杂的大规模场景，如何快速确定碰撞的可能区域以减少精确碰 撞的计算量，并产生后期处理的参数数据。 3 ) 如何将非凸体阻三角形面片形式映射到可编程g p u 的图形绘制流水线， 以充分利用c , p u 图形硬件并行处理流数据的卓越性能。 4 ) 如何解决传统三角形相交检铡算法到可编程g p u 算法的转换。 5 ) 如何快速从g p u 缓存中得到检测结果，咀解决c p u 与6 p u 帧缓冲区之问 读、写数据速度不均衡的矛盾。 一般而言，碰撞检测算法在处理复杂场景时，需要经过初步检测阶段和详细 检测阶段。在初步检测阶段快速排除不相交的物体，确定潜在的相交区域；在详 细检测阶段细化检测的对象，直到最小单元间的碰撞检测。为了提高算法效率、 检测精度，还可以将详细检测阶段再进行细分。如下图： 图1 1 碰撞检测算法框架图 本课题拟采用如下研究方案； i ) 初始化阶段，读取分析3 d s 格式数据文件综台c s g 、多边形网格顶点 n 初始化阶段，读取分析3 d s 格式数据文件综合c s g 、多边形网格顶点 天津火学硕t - 学位隆文 表的表示模型，采用a a b b ( a x i s a l i g n e db o u n d i n gb o x e s ) 层次树组织场景。 2 ) 在初步检测阶段，根据分离轴定理( s a t , s e p a r a t i n g a x i s t h e o r e m ) 进行 a a b b 包围盒的碰撞检测，迅速排除不相交物体。由于物体运动的连续性，其包 围盒在投影轴上的投影变化不会太大，采用插入排序算法排序分析，以充分利用 该算法对基本有序序列进行排序的高效性。 3 ) 在精确检测阶段，将上一步中潜在碰撞物体的三角形面片数据进行变换 处理，创建索引纹理和顶点纹理，以将三角形每个顶点坐标送到g p u 的纹理缓 冲区。在f r a g m e n ts h a d e r 中进行纹理访问，变换得到两个三角形，进行s a t 碰 撞检测。将碰撞结果送到深度缓存或颜色缓存，以供c p u 查询最终检测结果。 4 ) 三角形与三角形是否相交的结果作为深度值( o 表示相交，1 表示不相交) 输出。c p u 通过检查深度缓冲区来判断碰撞情况。鉴于目前个人计算机采用异 步a g p 总线结构，从g p u 读取数据要比向其发送数据速度慢很多，因此采用 n v i d i a 的遮挡查询技术( 通过使用o p e n g l 的n v o e e l u s i o n _ q u e r y 扩展功能) 来提高从g p u 读取结果的速度。另外在程序调试阶段，可以将结果输出到颜色缓 冲区，根据输出图像进行调试判断。 课题创新之处有： 1 在解决方案中综合利用c s g 、a a b b 、s a t 等多种数据结构及算法， 由粗到精逐层检测，进一步提高检测效率。 2 首次提出创建索引纹理、顶点纹理双重纹理，将物体的三角形顶点数 据映射到图形硬件中，实现s h a d e r 程序的完整三角形坐标信息的输入。 3 将s a t 算法映射到g p u 的s h a d e r 中进行三角形的碰撞检测，以利用 图形硬件强大的并行流计算能力进行实时碰撞检测，在g p u 的通用编程领域进行 了有意义的探索。 天津大学硕二 学位论文 第二章碰撞检测算法及g p u 通用计算 本章主要介绍近三十年碰撞检测算法的发展情况，并列举s w i f t + + 、r a p i d 等几种较优秀的碰撞检测算法；通过介绍可编程g p u 图形硬件，阐明了s h a d e r 及流计算的基本概念：在s h a d e r 开发语言中，着重介绍c g 语言，为编写项目中 的s h a d e r 程序打下基础；最后，在g p u 的通用计算领域列举了近两年国内外的 一些研究成果。 2 1 碰撞检测算法 本节从时间、空间角度对碰撞检测算法进行分类，着重介绍面向凸体的 s w i f t + + 碰撞检测算法、面向c s g 模型的碰撞检测算法和基于层次包围树的算法。 2 1 1 算法分类 碰撞检测算法源于二十世纪七十年代机器人路径规划，自动装配规划领域； 随着计算机软硬件及网络条件日益发展，一些新兴领域如计算机动画仿真，虚拟 现实等，对交互的实时性，场景的真实性的要求越来越高，尤其是c a d d c a d v l 对 精确性的苛刻要求，使得三维碰撞检测成为研究的热点。三十多年来，研究人员 在碰撞检测领域做了很多卓有成效的工作。对于种类繁多的碰撞检测算法一般分 为两大类：一个是从时间域的角度来分，一个是从空间域的角度来分 1 。下面 进行简单介绍。 基于时间域的碰撞检测算法主要包括静态、离散、连续碰撞检测算法。静态 碰撞检测算法在计算几何中有着广泛研究，一般对算法没有时间要求，但对其算 法精度要求很高。离散碰撞算法近似静态碰撞算法，更注重效率，但存在刺穿， 遗漏情况，通过采取一些优化算法可以降低其影响。 基于空间域的碰撞检测算法一直是人们研究的重点，它与物体采用的表示模 型紧密相关。常见的表示模型有多边形模型，c s g 模型，b - r e p 模型，参数曲面 模型( 如n u r b s ) 等，相关碰撞算法如l i n c a n n y 的“最临近特征算法”等。另 垄堡查兰堡主兰篁堡兰 一 外，根据物体创建不同的包围体进行碰撞检测，包括a a b b 树，层次包围球树 o b b 树，混合层次包匿体树等，采用不同的层次包固体树，其相关碰撞检测各有 优劣。下图为基于空间域的碰撞检测算法分类总图 1 。 j 书纷洲j f 、 i 叫冀”t 、l u l i i ：j 3 ，臻j u ：骗? n 婿t 二一：fj ( ， 。一一r ；- 也i 。- ：s h r a y a t i i鞋 ：m 女i i x - ，j _ 。! 。 司 i 9 0 l ：b a c l 1 9 9 轴 旧：l “i 昏“。驺：，i 、 i - 。_ i 、 n i - ! i 1 协，+ 帅，；， h o e 二0 ： ： ( m 2 0 0 ：1：l o m b d o 一 ：一。t 9 9 9 。f j 靠；f l e t l _ i i i 奠i i 点 ? t ，- t f ：l波g - l 2 0 0 i ： h a d e , b1 0 0 3 7 ，j ：- 硬1 蔓 一”。 j j旧l 懈l 6 0 0 n d a r ! j ) j 、 、。 l i j | 融彤地一n n 。 。一 i ；问弹江 。；q 撬圩巍 ，i ： h u b b a r dt 呻如 lg o f f , c h a l k ：9 ；6 1 r 毡勰：j ；i a z a d g b 杠io b b 州l k d 。pi 雌 i 0 5 m r h9 9 5 弩。，。b s p 吨 ( b e r g e ：1 ( g o r , ：c h a ：k| ： k l o w 鳃日)l 、9 9 9 】 l 。z a 血e m n1 9 9 9 】) k - d 叩嘲 1 9 9 置 r滞 z 。d m ，z “ l o c t r e e 尊 s a n 持e f l a r s o 口i it 9 8 9 】瞰碘 2 0 0 t ：) ，! l甄铂川 1 9 啊，【b o u m i 傩鲥泼“j 奄势 1 9 9 1 1 ) 噬瞧髓( 乜砧q i l o s p ol j ! ；k 懈 j 一 【h et 窜9 粥瞄 k 扯 疆f b ( e h 。黜 警、 0 l 】雌疆t ；：k 也m 州q 骶o 2 l d j 心： 娃j 特“阑f 嘶 辘i 衅纯形鹩 衙向c s g 袅 _ i i i 向 琵融数 面向参数 嘲粕 小髓示 4 砸梭秘4 辩；土 6 j ! 橼梭测辩试 ， ：裹塑算缓 睚算法 幽馕i 罅撼模型尊城 n 出1 9 9 5 j ：l 锄l b m1 9 8 8 j ， 7 z d t l e rl 哪】， f 越。出1( 哪曲 ( h e l _ d e l b c o h e n1 9 9 乏 o t l t 埘t1 9 9 0 1【s u l 蛐6 1 9 5 9 】i 蛐t 1 9 9 9 n 2 0 0 3 j ， c b “g1 ：) 9 6 1 ， c m n 啪n1 9 9 7 1【p o u - 8 m ：2 0 0 1 ) l 9 9 ：【啦e 琏 b o y l e t 9 9 9 ) 【、扯j c h1 9 g j b e r 脚1 9 9 篱) 1 9 9 1 】) 匹b m 越m ! 泌1 1 ) 图2 - 1 基于空间域的碰撞检测算法分类总图 经过广大研究人员的研究完善，出现了一些优秀的碰撞检测算法，下边介绍 一些代表性的研究工作：面向凸体的s w i f t 十十碰撞检测算法、面向c s g 表示模型 的碰撞检测算法和基于层次包围树的算法。 面向凸体的s w i f t + + 碰撞检测算法 在前人的基础上，北卡罗来那大学e h m a n n 等开发的s w i f t ( s p e e d y w a l k i n g 天津人学俅! i 学位论文 v i a i m p r o v e df e a t u r e t e s t i n g ) 算法结合了基于v o r o n o i 区域( 个多面体的特征， 如顶点、边、面等，其v o r o n o i 区域是指那些距离当前特征比其它特征更近的点 所组成的区域。) 的特征跟踪算法和多层次细节表示两种技术，可适用于具有不 同连贯性程度的场景，它比同类算法速度更快、也更强壮。 2 0 0 1 年，针对s w i f t 算法只能处理凸体的缺陷，e n h a m m 等对其进行了扩 展提出了s w i f t + + 算法 3 。s w i f t + + 算法在预处理阶段将场景中所有物体进行表 面凸分解( 利用q h u l l 开发包 4 ) ，并重新组织凸分解产生的结果凸片，建构出 各个物体的凸块层次树，以实现将非凸体转为凸体的思想。与目前有名的r a p i d 等其它算法相比，s w 【f t + + 算法性能更加可靠，不受场景复杂度的影响；而且可 以处理任意形状物体间的碰撞，除了可以返回两物体对的相交检测结果，还可以 计算出最小距离和确定相交部分的信息( 如点、边、面等) ，但无法求出刺穿深 度。另外，由于进行对非凸体进行分解，随着物体非凸层次的增加，它们的速度 会迅速下降。 面向c s g 表示模型的碰撞检测算法 c s g ( c o n s t r u c t i v es o l i dg e o m e t r y ) 表示模型用一些基本体素如长方体、球 体、柱体和锥体等，通过交、并、差等集合运算来组合物体。它的优点之一就是 使得物体形状的建构更直观，可以通过剪切和粘贴简单形状来形成更复杂的物 体，使得它可以容易找到碰撞的确切位置。 z e i l l e r 9 提出的面向c s g 表示模型的碰撞检测算法分为三个部分。第一部 分求出c s g 树的每个节点的包围体用去快速确定可能的相交部分；然后针对所 有c s g 树表示的物体创建类似八叉树的层次结构，以找到同时包含两个物体体 素的子空间；第三部分，检测空间中基本体素之间的相交关系。另外一些类似的 技术都是结合c s g 模型，综合多种算法以实现碰撞检测。 基于层次包围树的算法 包围盒层次( b o u n d i n gv o l u m eh i e r a r c h y ) 基本思想是通过建立对象的包围盒 来逐渐逼近对象的几何模型，从而用体积略大而形状简单的包围盒代替复杂的几 何对象参加碰撞检测。通过包围盒之间地相交测试，快速排除不相交的基本几何 元素对，以减少相交测试的次数。这里介绍两种常见的包围盒：a a b b 和o b b 。 a a b b ( a x i s a l i g n e db o u n d i n gb o x e s ) ，指包含该对象且边平行于坐标轴的最 天津大学硕： = 学位论文 小的j e 六面体( 图2 - 2 a ) ，易于计算和存储，相交测试算法简单，但它的紧密性差 ( 图2 - 2 b 中细长物体旋转不同角度，其a a b b 包围盒也大小不同) 。针对具体模 型，可以设计相应改进算法，迭代生成a a b b 树，进行碰撞检测。b e r g e n 6 提 出了一种采用分离轴定理【7 力快a a b b 包围盒检测的算法，同时又利用a a b b 局部坐标轴不发生变化的特性来加速a a b b 树的碰撞检测。由于a a b b 树具有 建构简单，内存开销少的特点，所以，b e r g e n 又把它的算法用于进行可变形物体 问的相交检测。 困园因 斗 图2 - 2 a a a b b 包围盒图2 2 ba a b b 紧密性示意图 o b b ( o r i e n t e db o u n d i n gb o x e s ) ，指包含该对象且相对于坐标轴方向任意的 最小的正六面体( 图2 3 ) 。o b b 包围盒边矢量方向任意，使得它可以根据被包 围对象的形状特点尽可能紧密地包围对象。g o t t s c h a l k 等 8 3 提出的基于o b b 层 次树的碰撞检测算法，称为r a p i d 算法。他们采用o b b 层次树来快速剔除明显 不相交的物体，虽然o b b 的包围盒更加逼近物体，但是包围盒之间的求交检测 更费时。为此，他们利用分离轴定理来加速o b b 包围盒的求交速度。它的缺陷 在于无法判断两个三角形面片的距离，并且没有利用物体运动的连贯性，其算法 需要预处理时间。经过改进，r a p i d 算法已经成为一种常见的用来评价另一种 算法性能的通用算法。 图2 - 3o r b 树结构示意图 囫一塾 天津火学硕，l 学位论文 还有一类基于图像空间的碰撞检测算法，此类算法初期利用图形硬件( g p u ) 对物体的二维图像采样和相应的深度信息来判别两物体之间的相交情况。借助图 形硬件的深度缓冲、模板缓冲，有效利用图形硬件加速技术来减轻c p u 的计算负 荷，但是由于图像本身是空间离散采样，受到图像分辨率的限制，难以保证碰撞 检测的精度。近年来，计算机图形硬件的处理能力获得极大的提升，图形硬件体 系结构也正发生质的变革，以前由固化函数构成的图形流水线正被可编程的 v e r t e xs h a d e r f r a g m e n ts h a d e r 所取代，这种变革使g p u 不再是简单的进行三角 形传输与绘制，而正逐步成为可用于进行密集浮点运算的高性能计算引擎，具备 了处理更为通用、复杂科学问题的能力。因此我们可以充分利用可编程图形硬件 高效、并行的性能进行碰撞检测。浙江大学的范昭炜博士 1 对此进行了一定探 索性研究工作，分析认为基于可编程g p u 的碰撞检测算法相比传统的空间碰撞 检测算法在高复杂度场景中效率更高，检测时间更加平稳。 2 2g p u 通用计算 通过介绍可编程g p u 图形硬件，阐明了流计算、s h a d e r 等概念；在s h a d e r 开发语言中，着重介绍c g 语言，并举例说明c g 的语法；在o p u 的遂用计算方面， 列举了近几年s i g g r a p h 会议上的一些研究方向及成果，从中可以看出，可编程 g p u 的通用计算已成为众多学者研究的热点。 2 2 1 图形硬件 g p u 图形硬件早期仅作为图形绘制协处理器来加速三角形运算，近年来随 着高性能可编程g p u ( p r o g r a m m a b l eo e u ) 的发展，如n v i d i a g e f o r c e 系列、a t i r a d e o n 系列g p u ，它们能够处理更多不仅限于图形学的应用。与被设计为进行高 性能顺序操作的c p u 不同，g p u 对顶点( v e r t e x ) 和片断( f r a g m e n t ) 的并行处理进 行了优化。图形处理器执行图形任务要比多用途的中央处理器快许多，例如渲染 三维场景，新的图形处理器可以在一秒钟内处理几千万的顶点，光栅化几亿甚至 是几十亿片断。 而且新一代g p u 的更新速度明显超过c p u ，其制造工艺接近甚至超过c p u ， 天律人学顶十学位论文 额外的晶体管可以用来增大g p u 的处理性能：例如，i n t e l 公司在2 ，4 g t l z 奔腾4 处理器中封装了5 5 0 0 万个晶体管，而n v i d l a 公司在最初的g e f o r c e f x 图形处理 器中使用了超过1 2 5 亿晶体管。 另外，可编程g p u 相对便宜、性能稳定、兼容于多种操作系统和硬件架构。 其主要缺点就是难于进行程序开发调试，缺少高精度的片断操作及大容量存储， 这些缺陷会随着相应软硬件的发展逐步消失。 在2 8 6 的年代，少数c a d 软件的出现开始催发了p c 上图形卡的发展；直到 1 9 9 5 年3 d f x 公司发布了划时代的v o o d o o 卡，自此人们由2 d 跨入了3 d 的世界： 等到1 9 9 9 年，n v i d i a 推出了g e f o r c e 2 5 6 显示卡，通过硬件t l 技术，它将c p u 从繁重的3 d 管道几何运算中解放出来，所有的变形与光照等原来由c p u 处理的 工作都交由g p u 来运算，同时也把g p u 的概念推向了大众；2 0 0 1 年初，n v i d i a 公布了第一枚可编程的g p u 一g e f o r c e 3 ，首次加入了v e r t e xs h a d e r 和f r a g m e n t s h a d e r ，将传统的固定功能渲染流水线带入了革新的道路( 图2 6 ) 。图2 4 比较 了g e f o r c e 4t i 和g e f o r c ef x 两种n v i d i ag p u 的硬件指标，从中可以看出图形 硬件的发展方向以及目前仍存在的缺陷。 g e f o n c 掣l 1 1g e f o r c ef x h i 曲 o “k r 5 u r f t l s o m 曲r yd i a p l a c e m e n t 辨叩两g v e l l t e a ts b a 畦e r l ，12 o + - 慨至曲u d 夤 搏1 2 86 5 3 6 h a x5 舾t i c 憾味k l o n s 2 8 2 s 6 p 妇腻( 加g 切i t k孽62 吝5 t e r n p d r m yr e g i s t m 1 21 6 a x 汹0 602 s 6 s 武l cc o ! - l l l o o lf m w m n 删cc o a t i d1 1 0 f ， p i x ds h a d e r s 1 12 a + t e x t u r eh 日1 6 m a xt e x t t “ei n 螬z r u c n o n s啐1 0 2 啐 慨o ) l * 曲t 洲c r 81 0 2 畸 协x t e m p $ t o l a g e 6 4 献at c l x e 盯r 渊ap r e c i s ；。n3 2 b h1 2 8 - b 话 图2 - 4g e f o r c e 4t i 和6 e f o r c ef x 的g p u 结构比较 可编程g p u 本质上是一种s i m d 的并行模型，随着硬件技术发展越来越像 一个通用处理器。然而，g p u 要承担通用计算的最大挑战在于引入可编程特性后 天津人学硕：卜学位论文 不会使其性能受到大的影响；否则，可编程g p u 就只是一种新的c p u 而已，反而 丧失其自身的性能优势。为了保持可编程g p u 的高性能，关键要充分利用其并行 计算的特点。“流计算”概念的提出正是为了便于将相关应用有效地映射到这一 新的图形硬件体系上。相对于传统计算模式，g p u 流计算模式( 图2 5 ) 以数据 序列作为输入数据，采用同一段内核程序并行处理所有数据，最后将计算结果输 出到输出流，具有易于并行化、有效利用传输带宽等优点。 v e r t e x s h a d e r 一 田圈曰曰 口口口口 口口口口 i 一竺竺 i 竺竺竺一i 2 2 2s h a d e r 语言 2 2 2 1 原理和概念 在传统的绘制系统中，当用户构造好场景，并定义好光源和景物表面的各种 口口口曰口口曰口口 天津大学硕士学位论文 属性后就可以进行场景绘制了。如果改变任一属性参数，系统必须重新绘制整个 场景；实际上，坂有绘制过程中的许多中间计算结果仍然适用，无需重新计算。 为了提高绘制系统的交互性，有必要设计一个较好的用户界面，使得用户不仅能 选取场景绘制的光照明模型，而且可以不涉及细节的深入系统内部更灵活、细致 的控制绘制过程。基于这一认识，1 9 8 4 年r o b e r tl c o o k 在s i g g r a p h 上发表 论文( s h a d e t r e e s ) ，他在里边提出了对表面上每个点进行颜色控制的观点，并开 发了一种专门的s h a d et r e e 语言。s h a d et r e e 结构将景物表面上每一点处设置的 几种光照效果归结为一种统一的处理模式，这种处理模式从树的叶节点开始依次 向上组合，最后到达根节点，这是一个递归组合的过程。 s h a d e r 真正获得应用是1 9 9 0 年p i x a ra n i m a t i o ns t u d i o 公司开发的 r e n d e r m a n 系统，它主要是针对非实时的渲染，包括多种着色器类型，比如表面、 光源、d i s p l a c e m e n t 、t r a n s f o r m a t i o n 、v o l u m e 、i m a g e 等；目前的g e f o r c e f x , 、 r m d e o n 系列g p u 只支持v e r t e 舄f r a g m e n t 两种着色器( 面向的是实时渲染) 。在 计算处理上，r e n d e r m a n 没有严格的限制，它要给程序员的就是最大可能的灵活 性与创造性，然而，这个可编程特性是有一点限制的一一它是通过r e n d e r m a n 的 软件模拟来实现。 图2 7r e n d e r m a n 系统渲染的3 d 动画 究竟什么是s h a d e r ? 一些文献把它翻译成着色器，着色语言，或者实时绘制 语言，本论文把v e r t e xs h a d e r 译为顶点处理器，f r a g m e n ts h a d e r 译为片断处理 器。为了统一表达方式，论文中采用原英文单词。 从硬件角度讲，可编程v e r t e xs h a d e r 是一种用户可编程的流处理器，它能改 变送入到光栅转换器中顶点的属性；而可编程的f r a g m e n ts h a d e r 则能够在多个 纹理坐标下对单个象素进行算术操作及获取纹理采样数据，但这些单个象索上的 操作相对独立，不能同时访问存储在其他象素上的数据。 天津人学硕士学位论文 从程序角度讲，s h a d e r 是组指令代码，在相应的时候被g p u 执行来进行 具体的操作。从上边的图2 - 6 可以看出，v e r t e xs h a d e r 就是在顶点被处理的时 候，对顶点的属性( 坐标、法矢等) 进行操作；p i x e ls h a d e r f r a g m e n ts h a d e r ( 前者是微软在d i r e c t x 中的称呼，后者则是在o p e n g l 中的称呼，两者都实现 了相似的功能，本论文均用f r a g m e n ts h a d e r 的叫法) 则是在片断被处理的时候， 对片段属性( 颜色、纹理等) 进行操作。简单列举一组s h a d e r 指令见表2 - 1 ： 表2 - 1s h a d e r 汇编指令举例 指令参数说明 a d d d e s t ，s r c l ，s r e 2将s r c 2 加到s r c l ，可通过在s r e 2 前加一，选 择为减 d p 3 d e s t ，s r c l ，s r c 2三维点的乘积。d e s t x = d e s t y = d e s t z = d e s t w = ( s r c l x 木s r c 2 x ) + ( s r e l y 丰 s r e 2 y ) + ( s r c l z s r c 2 z ) s l t d e s t ，s r e l ，s r c 2 d e s t = ( s r c l 顶点纹理 创建纹理 3 3 1 纹理创建 、x ，、纹理访问 2 一二、 如何将模型数据映射成图像纹理? 第一个问题是由于g p u 的纹理数据特点造成的。图形学中，纹理中象素 ( r ，g ，b ，a ) 各个分量的取值范围是 o ，1 ，所以，在通用计算中要把输入数据变 换到【o ，1 域中。解决方法是在初始化阶段记录模型数据的晟大顶点m a x 、最小 顶点m i n ，对顶点( 】【，y ，z ) 进行平移、缩放变换，将所有数据映射到 0 ，1 域， 公式( 3 1 ) 为顶点变换公式。另外，为了g p u 中恢复实际顶点数据，需要保留 这个平移缩放矩阵，以作为参数传入f r a g m e n ts h a d e r 中。 1 m a x j 一衄j o 0 0 o l m a x 一l n l n o o o 0 l m 懿z m m o o n 衄x m 【x m m r - i n l n m 舣一i n l n 一m m z m 疆_ = 一m l n j 1 公式3 - 1 顶点坐标仿射变换公式，其中口= l j f l 对于第二个问题，结合g p u 流计算的特点和模型数据的结构特点( 参照图 3 4 ) ，将索引数组和顶点数组分别转换为索引纹理和顶点纹理。图3 一l o 描述了 采用二维纹理坐标，就可以通过先后访问索引纹理和顶点纹理得到物体的1 个三 角形的3 个顶点坐标。f r a g m e n ts h a d e r 输入索引纹理坐标参数 ，通过 天津人学硕十学位论文 纹理访问函数得到纹理象索( r ，g ，b ) ( 图示蓝色) ，由每个分量计算出顶点纹 理中的纹理坐标，如分量g 结合顶点纹理长、宽参数，得到纹理坐标( “：，v ：) ： 然后对顶点纹理进行纹理访问，得到纹理象素( 图示红色) 的值，然后根据平移 缩放变换矩阵，计算得到【如，y z ，z ：) ，此值n z n n - - 个顶点的坐标。 ( “，v ，) 索引纹理 顶点纹理 一一_ ) 表示访问纹理 专 表示索引值转为纹理坐标 + 表示仿射反变换 图3 1 0 通过纹理坐标获取三角形坐标的数据变换示意图 在精确检测阶段，物体模型以三角形面片的形式表达，只要将每个三角形都 映射为纹理象素，就可以解决第三个问题。在具体实现过程中，采用了多重纹理 和矩形纹理两项技术，以突破o p e n g l 标准库的一些限制。 参考图3 8 ，在f r a g m e n ts h a d e r 中需要访问三个纹理，而在o p e n g l 标准 库中纹理操作是一个纹理映射对应一个管道( p i p e l i n e ) ，即用一个管道不能对一 个物体进行多纹理映射。为了实现多重纹理映射，o p e n g l 对标准库进行了扩充， 允许从显卡驱动的动态链接库中加载扩展函数，提供了a r b _ m u l t i t e x t u r e 扩展 功能来实现多重纹理映射。注意，在程序初始化过程中，通过o p e n g l 参数查询， 确认g e f o r c ef x 5 7 0 0 卡支持多重纹理，否则该算法没有硬件支持，性能极大降 低，甚至无法执行。 天津人学硕十学位论文 默认的o p e n g l 纹理坐标范围是 0 ，1 ，并目纹理的宽度、高度必须是2 ”( n 为整数) ，而n v i d l a 的矩形纹理n v _ t e x t u r e _ r e c t a n l e 技术中纹理坐标范围是 0 ，w 、 0 ，h ( w 、h 为整数，是纹理的宽度和高度，没有2 的整数幂的限制) ， 下边代码展示了如何创建索引矩形纹理。通过整数纹理坐标和o p e n g l 参数设置， 既可以减少无效纹理象素，又可以准确根据纹理坐标得到相应顶点坐标，避免浮 点数运算造成的误差。 i n tn u n i t s n s i z e ； g l g e t i n t e g e r v ( g l m a x j e x t u r e u n i t sa r b ，& n u n i t s ) ； g l g e t i n t e g e r v ( g l - m a x _ r e c t a n g l e j e x t u r e - s i z e - n v ，& n $ i ze ) ： p 查询结果分别为n u n i t e s = 4 ，n s i z e = 4 0 9 6 ： 即当前显卡( g e f o m ep x 5 7 0 0 ) 支持最多4 个绽理，每个纹理最太尺寸为4 0 9 6 x 4 0 9 6 屠前主流显 卡均支持此规格) i 广t y p e