（计算机应用技术专业论文）真实感图形算法与实时绘制技术研究.pdf

首都师范丈学硕+ 学位论文 真实感图形算法与寅时绘制技术研究 摘要 真实感图形绘制是计算机图形学中的一个重要课题。本文从以下几个方面进行了一些探 索性的研究，包括双向光线跟踪算法、网格简化算法以及真实感草地的模拟。 光线跟踪是最早用来解决反射、折射的涉及非漫反射面参与的光能传递的算法，传统的 光线跟踪算法隐含的假设景物表面是完全光滑的，光在表面的反射遵循镜面反射和规则透射 规律，这一假设导致了光线跟踪算法不能处理镜面一漫射场景的光能传递。双向光线跟踪算法 在传统的逆向光线跟踪算法上进行扩展，从而能够较好的解决这一问题。本文第二章对双向 光线跟踪算法进行了研究讨论，实现了双向光线跟踪算法，取得了较好的实验效果。 面聚类网格简化算法是l o d 中常用的算法，本文第三章提出一种新的面聚类网格简化算 法，基于空间八叉剖分的面聚类网格简化算法，该算法先建立空间剖分的八叉树，对面片聚 类前进行预处理，把处在近似平面上的三角面片的范围缩小在一个个的小空间里，对应八叉 树的n t 结点内，从而减小面聚类的盲目性，提高了聚类速度，节省了网格模型简化的时间。 自然场景的模拟一直都是计算机图形学中的一大难题，而真实感草地的模拟就更加的困 难。本文第四章对动态真实感草地的模拟作了些尝试性的研究，通过提取边界轮廓建立草叶 子模型，并把粒子系统应用在草叶子上，使用粒了的特性和实时碰撞检测技术实现滚动的石 头和草p t 。了之间的瓦动效果。 关键词：双向光线跟踪八叉树面聚类网格简化真实感动态草地 首都师范大学硕+ 学位论文真实感图形算法与实时绘制技术研究 a b s t r a c t t h er e n d e r i n go f r e a l i s t i ci m a g e si sa l w a y sad i f f i c u l t j o bi nc o m p u t e rg r a p h i c i nt h i st h e s i s ，w c d o8 0 m es t u d i e s i n c l u d i n g b i d i r e c t i o n a l r a yt r a c i n g , a l g o r i t h mo fm e s hs i m p l i f i c a t i o na n d r e n d e r i n go f r e a l i s t i ca n i m a t e dg r a s s t h et r a d i t i o n a la l g o r i t h mo f r a yt r a c i n gc a l ls o l v et h e $ c 雠o f m i r r o r - m i r r o r w h i l ei tc a l l t s o l v et h es c 黜o f m i r r o r - d i f f u s e i no r d e rt os o l v et h i sp r o b l e m , w ci n t r o d u c et h ea l g o r i t h mo f b i d i r e c f i o n a lr a yt r a c i n g b a s e do nt h et r a d i t i o n a lr a yt r a c i n g , b i - d i r e c t i o n a lr a yt r a c i n ga d d p o s i t i v ed i r e c t i o nt ot h eo l do n e w ep r e s e n tt h eb i d i r e c t i o n a lr a yt r a c i n ga l g o r i t h ma n dg i v et h e r e s u l to f e x p e r i m e n t s u r f a c em e s hs i m p l i f i c a t i o np l a ya ni m p o r t a n tr o l ei nt h ef i e l d so f t h eq u a n t i t yo f t r a n s m i s s i o n s ， s t o r a g e o f 3 d o b j e c t sa n d m u l t i m o d e l d i s p l a y w e p r e s e n t n e w m e t h o d o f f a c ec l u s t e r , c a r r y o u t t h e o c t r e et od i v i d et h es p a c e ，p u tt r i a n g l em e s hi n t od i f f e r e n ts p a c e ，t h e nc l u s t e rt h et r i a n g l em e s hi n t h es a m es p a c e s oi tc a l la c c e l e r a t et h es p e e do f t h ew h o l ec l u s t e r a r e rs p a c ed i v i s i o n , e x t r a c t s f e a t u r e si ne v e r yr e g i o na n dt r i a n g u l a t e st h e mb yc o n s t r a i n e dd e l a u n a yt r i a n g u l a t i o n g e n e r a t i o no f r e a l i s t i ci m a g e so f g r a s ss c e n e si sa l w a y sa c h a l l e n g i n gp r o b l e m t h es t r u c t u r e s o f g r a s sa l ei ng e n e r a lv e r yc o m p l e x ，c a r r y i n go nv a r i o u sc a t e g o r yf e a t u r e s t om e e tt h er e q u i r e m e n t i nb o t l ls t o r a g ea n dc o m p u t a t i o n , v a r i o u sc o n s t r u c t i o nt o o l sa n dr e n d e r i n gt e c h n i q u e sa r ep r o v i d e dt o d e a lw i t hd i f f e r e n tv e g e t a t i o no b j e c t s i nt h i sp a p e r , w eu s es k e l e t o n sp o i n tt og e n e r a t eg r a s sb l a d e s i no r d e rt og e ta n i m a t i o ne f f e c t , w ea d d p a r t i c l et oe v e r yb l a d eo f g r a s s ，t h e nw e n s cr e a lt i m e c o l l u s i o nd e t e c t i o nb e 押e 髓s t o n eo b j e c ta n de v e r yp a r t i c l eo f b l a d et op r e s e n ta n i m a t e dg r a s s k e yw o r d s ：r e n d e r i n go fr e a l i s t i ci m a g e s , b i d i r e c t i o n a lr a yt r a c i n g , m e s hs i m p l i f i c a t i o n o c t r e e a n i m a t e dg r a s s 1 l 首都师范大学硕士学位论文 真实感图形算法弓实时绘制技术研究 第一章绪论 1 1 真实感图形绘制研究的重要意义 绘制技术是计算机图形学的一个重要分支，它研究的是如何将几何定义的模型变成可 视的图像。真实感图形绘制技术是图形学绘制技术发展的结果，它的目标是根据几何场景 的造型、材质和光源分锥，将其转变成跟真实场景在视觉效果上非常相似的图像，使观察 者有身临其境的感觉。在近三十年的时间罩，随着硬件技术和计算机图形学的高速发展， 真实感图形绘制技术取得了举世瞩目的成就，并且已广泛应用于c a d c a m 、计算机动画、 虚拟现实、科学计算可视化等众多领域，为社会的发展与进步做出了重大贡献。 几十年来，c a d c a m 技术的飞速发展，对许多行业的设计和生产过程产生了巨大影 响，使其自动化程度达到了前所未有的高度。在机械设计方面，传统的产品设计通常需制 作实物模型来检查设计效果，尤其是那些对外形美感要求较高的产品，一般要先按图纸制 作样品，再根据样品反映的问题进行多次修改，耗费大量人力、物力和时问。若采用真实 感图形显示技术，则可方便地在屏幕上显示产品在各种视角下的逼真图形，并且可直接在 计算机上对设计参数进行交互修改和绘制，直到满意为止。即可大大减少反复生产样品的 时问，缩短设计周期，又节约了生产样品的资金和人力：在建筑方面，建筑师往往要花费 很大的精力绘制效果图，如果采用真实感图形绘制技术，不但可以把这方面的工作交给计 算机处理，还可以结合虚拟现实技术进行建筑物体的虚拟漫游，这样，建筑师和用户在建 筑物还处于设计阶段，就可以非常直观地了解建成后的外观和内部空日j 的靠置及采光效果 等，做到胸有成竹。 计算机动画是真实感图形绘制技术的又一重大应用领域。在电影和电视广告中，要达 到某些特定的效果，往往需要进行许多次的试验和拍摄。那些危险场面、破坏场面和需要 动物配合的场面不但令电影工作者们非常为难，而且提高了电影的制作费用，还可能对人 员造成伤害。另外，有些事物和景象更是现实世界无法找到的，比如科幻片或者灾难片， 无法实景拍摄。通过计算机绘制出高度真实感的虚拟场景，这些困难都可以解决。可以说， 真实感图形绘制技术给影视工作者和艺术家提供了一个尽情发挥想象力的舞台。 虚拟现实是当前的一个热门研究课题，它在飞行训练、战斗模拟、计算机游戏等许多 领域具有十分广阔的应用 ； 景。真实感图形绘制技术是基于图形的虚拟现实的核心技术之 一，直接关系到人机交互速度和图像输出质量。 首都师范大学硕士学位论文 真实感图形算法与实时绘制技术研究 科学计算可视化是当i ； 的另一热门课题，它己在医学、地球科学、天文物理、化学、 机械工程等许多方面取得了巨大成就，将大批工程技术人员和医务人员从大量繁琐的数据 中解放出来。真实感图形是科学计算可视化的输出手段之一，绘制质量将直接关系到工程 技术人员对原始数据的理解和医务人员对病人病情和病因的判断，具有突出的现实意义。 真实感图形绘制技术的应用领域非常广阔，它的影响萨迅速地向工业生产和社会生活 的各个领域渗透。可以预料，在未来社会罩它必将发挥更为重要的作用。 1 2 常用真实感图形的绘制算法 真实感图形绘制是计算机图形学中的一个重要课题。早在1 9 6 7 年，计算机绘制真实感 图形就被提出，只是由于当时计算机运算速度慢，图形显示设备功能差，造价高，使其发 展和应用受到了一定程度的限制。近三十年来，随着计算机硬件技术的飞速发展，真实感 图形绘制技术取得了举世瞩目的巨大成就，光照模型、绘制方程、消隐算法、光线跟踪算 法、辐射度算法和体绘制算法相继被提出和完善，真实感图形绘制技术也随之f 1 益成熟。 下面我们对这些技术作一个简单的介绍。 1 2 1 光照模型 现实世界中，物体所表现的颜色都是光能作用的结果。客观世界中的物体都不同程度 地具有发射光线、吸收光线、反射光线和透射光线的能力。光线照射到物体表面时，一部 分被吸收并转化为热能，其余部分光被反射或透射。j 下是部分反射或透射的光线被眼睛接 收后，我们才感觉到物体的存在及其所特有的形状和色彩。因此，要绘制高度真实感图形， 就必须定义场景中的光源。为了便于计算，我们必须定量地描述光的多少或强弱，亮度和 强度就是用来定量描述光的两个基本概念。物体表面光的亮度是指单位投影面积在单位立 体角内发出的光的能量，它是物体表面上的小面元所具有的性质。对点光源常用强度来代 替亮度。强度是指点光源在单位立体角内发出的光能。同样大小的被照射面，离光源越远， 接收到的光能就越少。光的传播服从反射定律和折射定律，光源与物体所表现颜色的关系 可通过光照模型来模拟。物体所表现的颜色与光源有密切的关系。光照模型的作用就是计 算物体可见表面上每个点的颜色与光源的关系，因此它是决定图形真实感的一项重要内 容。物体表面发出的光是极其复杂的，它既与环境中光源的数目、形状、位置、光谱组成 和光强分布有关，也与物体本身的反射特性和物体表面的朝向有关，甚至还与人眼对光线 的生理和心理视觉因素有关。把这一切都通过计算机精确地计算出来是不现实的，我们只 能用尽可能精确的数学模型光照模型来模拟光和物体的相互作用，从而近似地计算物 体可见表面每一点的亮度和颜色。最基本的光照模型是p h o n g 模型【9 m 引，它使光源和视点 首都师范大学硕i ：g e 位论文真实感图形算法与实时绘制技术研究 的位置可以任意选定。 p h o n g 模型表达式如下： ，= 乞e + + 巧( | + ) ( r + k ) + ，j 墨+ ( + 日) ”( r + k ) ( 1 一1 ) 其中，l 邑为环境光参数 为入射光强 髟为物体表面的漫反射系数 足。为物体表面的镜面反射系数 为物体表面的法向 从物体表面指向光源的向量 r 光源到物体表面的距离 视线与l 的平分向量 p h o n g 模型假设反射光线集中在反射方向( 反射角等于入射角的方向) 附近，并随着与 反射方向央角的增大，反射光急剧减弱。用p h o n g 模型计算所得的物体表面好像塑料，镜 面反射光是光源的颜色，不能反映物体表面的材料特性，而且镜面反射在入射角很大时有 失真。这个模型模拟的反射效果不理想，用它生成的图形缺乏质感。后来b l i n n ，c o o k ， t o r r a n c e 等人相继对p h o n g 模型进行了一些修改，使图形的真实感有明显的提高。1 9 8 2 年， c o o k 和t o r r a n c e 提出了一个基于物理光学的表面反射模型c o o k t o r r a n c e 模型i 。诎s 2 1 ，使 得模型中反射光的位置和分布与实际情况非常接近，因而用它绘制的图形具有很好的质 感。 c o o k t o r r a n c e 模型的表达式如下： i = l k 厂+ ( 髟f o + ( + 1 0 + k + d + f + g ( n + 矿) ) g 、 ( 卜2 ) 其中，l 瓦，为环境光参数，e ，髟为漫反射与镜面反射的比例，髟+ 墨= l ，确物体表 面的分布函数，是菲涅耳函数，表示入射角和材料折射率的不同引起的镜面反射率不同 g 为几何衰减因子，由微平面相互遮挡。 c o o k 模型运用了光学中的菲涅尔方程，此方程在入射光为非偏振光时是非常精确的。 利用上述光照模型，可以计算出场景中各物体每一点的颜色。该颜色只与直接光源、物体 的材料及该点的法向量有关，与它周围的物体还没有建立联系，这样的光照模型被称为局 部光照( 1 0 c a li l l u m i n a t i o n ) 模型。但现实世界罩的大多数物体都具有明显的反光特性( 因此我 们的眼睛才能感觉到它们的存在) ，有些物体还具有透明特性，一个物体的反射光和透射光 也会对其它物体产生明显的影响。光线跟踪算法和辐射度算法较好地解决了这方面的问 首都师范大学硕 学位论文真实感图形算法与实时绘制技术研究 题，它们被称为全局光照( 西o b a li l l u m i n a t i o n ) 模型。其中光线跟踪算法解决了物体之间的镜 面反射和透射的影响，能产生镜像、透明和阴影等效果，但对漫反射处理不足，辐射度算 法正好解决了这一不足，它从能量的角度出发，很好地模拟了物体之间的漫反射。 1 2 2 绘制方程 1 9 8 6 年k a j i y a 给出的绘制方程( r e n d e r i n g e q u a t i o n ) 【捌i 8 6 统一了以自口所有光照模型，该 方程为： l ( x ，j ) = g ( 工，一) 【占( k 工) + f p ( x ，工，z ) j ( ，膏。) d r 。】( 1 - 3 ) ， 这罩i ( x ，x ) 为点x 对点工的光亮度贡献，g ( x , x ) 为点工自身发光向x 辐射的光亮度， 以工，一，工。) 为工处关于入射方向，一膏和反射方向工一工“的双向反射率，g ( x ，算) 为遮挡因 子，若x * u x 相互可见，g ( x ，j ) 为1 ，否则为0 。 上式表明，场景中的任意一点工对另一点工的光亮度贡献，等于工处自身向x 发射的 光亮度和场景中所有其它物体表面发射的光亮度经由石处反射到达硇q 光亮度之和。 k a j i y a 用这一方程作为计算机图形绘制中各种光照模型的理论基础，而不是用它来模拟所 有的光照效果，因为这个绘制方程没有考虑介质对光线的吸收、散射以及光强与波长的关 系等。绘制方程描述了全局光照模型中的递归关系，它可以简单地用线性积分算子r 来表 示： i = 萨+ g r ( 1 )( 卜4 ) 其中 r ( ，) tj o ( x , x ，j ) ，( j ，x ) d z 。 ， 曰为线性积分算子，( 1 - 4 ) 可以进一步改写为 ( 1 一g r ) i = 9 6 从而得到下面的展开式 s i l l s 9 ： i = ( 1 一g r ) - 1 9 苫 = g e + g ( r g ) c + g ( r g ) 2 占+ g ( j 蹭) 3 占+ = g c + g r e + g r 2 9 + g 尺s + = r g c ( 1 5 ) 展开式( 卜5 ) 有明显的物理意义。它表明场景中任意一点算向另一点工发射的光亮度，是由 于来自光源的能量经过不断反射的结果。式中右边的第一项是工自身发光向埴接照射的 结果；第二项代表的是光源作用于j ，在工处经过一次反射到达工的光亮度；而第三项表 示光源的能量经过其它曲面一次反射到工，再经过j 反射到达工的光亮度，因而是二次反 射的结果。其它各项依此类推都有相似的意义。由于绘制方程的一般性，该方程的求解显 然是非常困难的。k a j i y a 利用m o n t e - c a r l o 方法直接求解式( 1 5 ) ，提出一种非常有效，但是 4 首都师范大学硕上学位论文 真实感翻形算法与实时绘制技术研究 计算量很大的全局光照求解技术。 1 2 3 材质与纹理 从光照模型公式可以看出，物体的漫反射系数、镜面反射系数和透明系数等物理量与 物体所表现的颜色直接相关。这些物理量是真实感图形绘制中常用的材质参数，通常在建 模的时候就定义好，并存储在相应的数据结构中。材质参数是影响质感的重要参数，随意 给定的参数很难做到自然和真实。实际计算时应根据实际材料的测量结果进行设定，若没 有现成的测量结果，则应根据图形效果对参数反复修讵，以达到较好的效果。但是若一个 基本物体只指定一种简单的材质，当然不能模拟自然界中精美的花纹和图案，图形的逼真 程度同样会受到很大的限制。纹理映射技术成功地解决了这一问题，通过定义纹理与物体 之间的映射关系，可以合成真实感图形表面的花纹、图案和细微结构【d ”9 6 1 。纹理映射大 致可分为两类：一类用于改变物体表面的图案和颜色；一类用来改变物体表面的法向量以 产生凹凸不平的效果 c a b 穗t l 。另外，也有人将通过扰动函数来改变反射系数和透射系数的技 术归类为纹理映射【b i 砷酊，并分别称作反射纹理和透射纹理。表面颜色纹理是图形学中最常 用的纹理之一，它通常用一个二维数组存放一幅数字化图像，用插值法来构造各点的纹理 值。在进行图像纹理映射时，映射区域一般是一个三维空甸上的平面或曲面，确定纹理图 像和映射区域之自j 的对应关系是纹理映射的一个基本问题 r “k - 9 6 1 s m l t a t l 。对于平面来说，可 将其旋转至与某个坐标平面重合，这样就成了一个二维平面，于是容易与图像域建立对应 关系。对于空间曲面，一般用其二维参数域与纹理域对应。纹理定义好之后，可以在图形 的计算过程中进行纹理映射，通常表面颜色纹理的映射可分为如下几个步骤来进行： 颜色纹理映射算法 ( 1 ) 确定纹理图像和映射区域之闻的对应关系，求出映射区域中每个采样点的三维坐标。 ( 2 ) 求出采样点三维坐标所对应的平面坐标或参数坐标( “，v ，) ( 3 ) 通过( 甜，v r ) 求图像域内的坐标( “，u ) 。 ( 4 ) 用插值法求( 虬，u ) 点的颜色值。 将上面所获得的颜色值，结合物体的各种反射和透射系数作为漫反射系数代入光照模 型计算公式，即可得到相应的纹理效果。纹理映射还可用柬模拟某些特殊的材质，增强物 体表面的质感，从而使图像更加逼真。为了描述粗糙物体表面凹凸不平的细节，使所绘制 的场景有更高的真实感效果，凹凸纹理映射( b u m p m a p p i n g ) 技术被引进到真实感图形的绘 制中。凹凸纹理映射通常是通过对所绘制的曲面上法向量方向的扰动实现的。对曲面上采 样点法向量方向进行扰动的手段很多，我们下面介绍的参数曲面凸凹纹理映射是比较高效 首都师范大学顽： ：学位论文 真实感图形算法与实时绘制技术研究 的一种。 假设p ( 珥订为参数曲面上的一点，那么p 处的单位法向量为 栉= 只只1 只只l ( 1 6 ) 式中 只= 瓦a 瓦# y 瓦o , ，r ；= ( 考考考) r ( - 一，) 我们对p 点曲面在法向量方向通过凹凸函数( b u f n pf u n c t i o n ) d ( u , v ) 做- - 个小移位，这个 函数是已知的，并且移位足够小( | 政珥i 1 ) ，那么： p = p + d ( u ，v 加 ( 卜8 ) 这个小移位在绘制时并没有真的画出来，它只是影响该点处的法向量方向，使得曲面 绘制出来具有凹凸不平的效果。移位p 处的法向量由下式给出： 厅= 只 ( 卜9 ) 这样，由式( 卜8 ) 我们可以得到如下的偏微分方程： 巧：只+ 掣开+ d ( u , v ) 牟：只+ 譬! 一+ d ( 嘞v ) 行。 ( 1 一l o ) 如果d 足够小，( 1 - 1 0 ) 两式中的最右边一项可以忽略，并r n n = o 这样，可以得 到： 玎：n + 掣作+ 掣一只( 1 - 1 1 ) o u洲 实际实现的时候，掣和掣可以预先计算好存储在数组中，这一点与一般的纹理映射类似。 卵o u i 2 4 消隐 消隐算法包括隐藏线的消除和隐藏面的消除。其中隐藏线消除算法主要用在绘制线框 图，对于普通的真实感图形绘制来说，c a t m u l l 提出的深度缓存算法( z b u f f e r 算法) 是最常用 的隐藏面消除策略 c a t m 7 4 1 z b u f f e r 消隐算法虽然生成图像的效果较差，但它的数据结构简 单，运算速度快，硬件实现比较方便，特别适合速度要求较高场合。其算法思想大致如下： z b u f f e r 消隐算法 z b u f f e r 0 帧缓冲区置成背景色c b u f f ( x ，y ) = c o l o r o f b a c k g r o u n d ； z 缓冲区置成最大之值z b u f f ( x ，y ) = m a x d e p t h ； f o r ( 场景中所有的面片) 将当前面片投影到投影平面： f o r ( 该面片所覆盖的每个象素( x ，y ” 首都师范大学硕l ：学位论文 真实感图形算法与实时绘制技术研究 通过插值法计算面片在该象素点的深度值z ( x ，y ) ： i f ( z ( x ，y ) z b u 坂x ，y ) ) z b u m x ，y ) = z ( x ，”； c b u 坝x ，y ) = 当前面片( x ，y ) 点处s h a d i n g 值； ) ) 显示c b u f i ) z - b u f f e r 算法占用内存空白j 较大。当系统内存紧张时，可将显示窗e 1 分为若干块，对每块 单独进行z - b u f f e r 消隐，这样可以节省所需内存，但增加了一些额外的时间开销。 1 2 5 光线跟踪算法 光线跟踪( r a y t r a d n g ) 的思想是由a a p 刚首先提出的【 p p c 删。后来，g o l d s t e i n 和n a g e l 对a p p e l 的光线跟踪思想作了一些改进，并首次用光线跟踪算法产生了阴影效果刚7 1 使计 算机绘制图形的真实感向前迈进了一大步。但由于当时计算机运算速度相对较慢，光线跟 踪算法的时问丌销极大，一般的计算机系统难以承受；另外，当时的图形显示设备性能有 限，没有显示高度真实感图形的硬件基础，使光线跟踪的发展受到了一定程度的限制。直 到1 9 7 9 年，d s k a y 用光线跟踪算法产生了反射和折射效梨h y 7 9 1 ，迎来了光线跟踪算法的 又一次飞跃。这个算法对镜面反射和透明性的模拟非常成功，使物体的高光点、镜像和透 明效果非常自然。它是真正意义上的高度真实感图形显示算法，现在仍被广泛采用。 光线跟踪基本思想可用算法形式描述如下【7 州1 9 0 铀9 5 】： 光线跟踪基本算法 f o r ( 需要计算的每个象素c ) 确定通过视点v 和象素e 的光线r ： r a y - t r a c i n g ( r ，i ，1 ) ； 置e 的亮度为i ： ) r a y - t r a c i n 烈r ，i ，a ) * r 为当前跟踪光线，l 为当前跟踪光线的亮度，a 为i 对总亮度的贡献系数+ 首都| | i | j 范人学顾： 学位论文 真实感图形算法与实时绘制技术研究 i f ( a e )为最小贡献系数 i = 0 ： e 1 s e r 与景物求交，返回可见点只： 计算只点的局部照明亮度l ； i f ( 只所在的表面为光滑镜面) 确定p l 的镜面反射光线r ，： r a y t r a c i n g ( r | 1s 。k 。a 1 ： i f ( 只所在的表面为透明面) f 确定量的规则透射光线置： r a y t r a c i n g ( r , 1 t k l a ) ； ，= 爿( l4 - k ，1 ，+ k ，) ： ) 光线跟踪算法使计算机产生图形的真实感大幅度提高，但卓越的图形绘制效果与昂贵 的计算开销形成了鲜明的对比。为了使这一算法真正实用化，减少运算量势所必行，因此， 许多人开始研究光线跟踪的加速方法光线跟踪中最费时的运算是线面求交，有关资料表 明，如果不采取加速措旌，线面求交约占整个光线跟踪时间的9 5 以上【啪啪】。因此，减少 运算量的关键在于提高线面求交的速度或减少线面求交的次数。 层次包围盒方法是减少线面求交次数的重要方法 k a y 8 6 l 。它的基本思想是，在复杂形体 外包一个容易求交的包围盒，例如长方体或球面等。在光线与该复杂物体求交之酶，先判 其是否与包围盒相交，若与包围盒不相交；说明它与包围盒中的复杂形体也不相交，从而 节约了时间。只有当光线与包围盒有交时，才有必要与复杂形体进行求交运算。若原复杂 首都师范人学硕士学位论文 真实感图形算法与实时绘制技术研究 形体由多个部分组成，还可以为每个部分定义一个包围盒，从而形成一棵包围盒树。线面 求交时先从树根结点开始判断包围盒，若光线与根结点的包围盒不相交，则与原物体不相 交，否贝f j 再判断光线与每棵子树的包围盒是否相交，这样可以按层次访问包围盒，免除了 许多不必要的求交计算。只有当访问到树的叶子节点时，才需进行必要的求交计算。减少 求交计算的另一种重要方法是空间剖分法【“d 7 螂8 7 1 【s i m i 嘲。它的基本原理是，将物体所 在的空间剖分为若干个小体素，为每个体素建一张表以保存在该体素中或部分在该体素中 的物体。若一个物体在几个体素中，则每个体素的表中都要记录该物体。光线射出后，先 与其遇到的第一个体素中的所有物体求交，若有交且交点在该体素中，则此体素中的最近 交点就是系统中所有物体的最近交点，这样就没有必要与其它体素中的物体求交。若在第 一个体素中无交，则再判下一个体素，直至找到交点或穿出剖分空闻为止。由于只有射线 穿过的体素中的物体才可能参与求交，从而大大地减少了求交次数。空问割分法特别适合 于离散法造型系统中的形体或由多个简单形体构成的复杂形体。这样每个体素中的物体求 交速度都很快，而且避免了绝大多数不必要的求交计算。 选点计算加速法是另一种类型的加速方法。其理论基础是，物体表面的绝大部分颜色 的过渡都是很均匀的，只是在边界部分才产生颜色突变。由此可知，在颜色变化不大的地 方没有必要逐点进行计算，只需按照某种规则选择一些点进行真诈的光线跟踪计算，然后 对未计算的点进行线性插值即可。由于线性插值只包含简单的四则运算，比用光线跟踪算 法计算亮度要快得多，因此能起到加速作用。根据文献【埘神i 】中的结论，选点计算法可将 计算速度提高2 9 倍。 随着计算速度的提高，对图形质量的追求又更进了一步。后来又有人提出用双向式光 线跟踪法模拟镜面对周围物体的影响，本文第二章将对此进行深入的说明；使用分布式光 线跟踪法来产生模糊的镜像、模糊的透明和半夥。a 铲9 2 m 轴“删。这些算法进一步提高了图形 的逼真度，但这些算法时间歼销较普通的光线跟踪算法又大许多，在速度要求较高的场合 一般不宜采用。 1 2 6 辐射度算法 辐射度( r a d i o s i t y ) 算法源于五十年代提出的一种热辐射工程计算方法，原方法是用于 计算场景中所有面相互之间的热辐射作用。八十年代中期，g o r a l 等和n i s h i t a 等提出将这种 方法引入到计算机图形学中【g o m 8 4 】【n 曲8 5 l 。经过十多年的发展，辐射度算法成为真实感图形 的一种重要生成工具，并且由于这种算法具有与视点无关的特点，在v r 领域有着广泛的应 用前景。相对于其它真实感图形的绘制算法，辐射度算法的主要特点在于： 首都师范大学硕士学位论文真实感图形算法与实时绘制技术研究 ( 1 ) 经典的辐射度算法只处理纯漫反射封闭场景。 ( 2 ) 场景的辐射度计算与视点无关。 ( 3 ) 其它的绘制算法大都基于实践经验，而辐射度算法从一开始就建立在求解能量平衡方 程组的基础上，因而从光能分布计算上讲，辐射度算法比其它真实感图形的绘制算法更为 准确。 在辐射度技术刚被引入到计算机图形学中时，因为解析求解形状因子进而求解能量平 衡方程组的计算量非常大，工程上的应用受到了很大的限制。1 9 8 5 年，m i c h a e lf c o h e n 等 人提出用半立方体方法( h e m i c u b e ) 离散地求取形状因子的近似解。c o h e n 等人又在1 9 8 8 年 提出逐步求精绘制技术【叫雠耵。这两种技术的运用大大加快了能量分布的运算，使辐射度 技术在工程上的应用成为可能。此后，辐射度算法的研究主要集中在以下两个方面。 场景的划分： 场景划分的质量直接关系到辐射度运算的时问和空问复杂度、内存的要求、计算精度 以及最后结果的图形质量。 非纯漫反射场景的处理： 因为经典的辐射度算法只处理纯漫反射场景，而实际开常生活中的场景一般说来都包 含有非纯漫反射物体。解决这个问题的两趟法( t w o - p a s sm e t h o d ) 是先计算场景的漫反射和非 漫反射光能分布，然后在绘制时采用光线跟踪技术。如果对结果要求非常高，还包括利用 光线投射获得聚焦和失焦的特殊效果，这也就算所谓的多趟方法( m u l t i p a s sm e t h o d ) 。 1 2 7 体绘制算法 三维数据场体绘制算法本是科学计算可视化的图像输出手段，它广泛应用于现代科技 的信息表示中。如利用c t 和核磁共振( m r i ) 产生三维数据场的医学成象技术；利用爆炸产 生的声波生成三维数据场，合成用于地震探测的三维地质结构图：还有流体力学中表示飞 行器空气动力特征的三维网格数据场等等。 体绘制技术通常包括如下步骤： ( 1 ) 对输入的三维数据的每个采样值赋以颜色( c 0 1 0 r ) 和非透明度( o p a c i t y ) 。 ( 2 ) 将采样点投影到成象平面。 ( 3 ) 对投影后的采样点进行合成。 这种可视化技术利用光线在不同颜色的半透明介质中传输的物理模型，是最基本的体 绘制技术。最近，不少研究人员把体绘制技术应用到高度复杂场景的真实感图形绘制中 c h i b 9 7 n e y t 9 6 n c y r 9 引，用三维数据场来表示复杂的自然景物如树木草地等。运用三维数据场的 1 0 首都师范大学颈学位论文 真实感图形算法 j 实时绘制技术研究 优点在于，它不但大大减少描述场景的数据量，而且有效地缓解了绘制时的混淆现象。绘 制速度也相应有所提高。 1 2 8 算法比较 结合基本光照模型和z - b u f f e r 面消隐技术的绘制方法是最简单快捷的图形绘制手段，被 广泛应用于c a d c a m 和其它人机交互频繁的领域，尤其在建模阶段，许多v r 系统也采 用这种绘制方法。它的优越性在于处理简单，通常有硬件支持，绘制速度快，可以达到实 时交互。它的缺陷在于没有考虑场景中物体之问的相互影响，因此无法产生具有高度真实 感的图像。下面给出各种算法的比较情况。 光线跟踪算法 光线跟踪算法非常适合处理镜面反射和规则透射，可以计算出准确的高光和聚焦失焦 现象，它考虑了物体之间的相互作用，可以产生效果逼真的结果图。但是由于它是基于点 采样计算的，对于非点光源和平行光源的场景，例如包含线光源或面光源的场景，光线跟 踪计算速度将大受影响。再者，光线跟踪算法处理漫反射也非常不理想，而在现实生活中， 漫反射通常是光照作用的主要组成部分，所以光线跟踪产生的结果一般来说仍然不够真 实。 辐射度算法 辐射度算法很好地解决了场景的漫反射问题，颜色渗透( c o l o r b r e e d i n g ) 现象得到很好的 模拟。对于纯漫反射场景，运用辐射度技术可以产生非常真实的绘制效果。而且由于绘制 时与视点无关，因此一旦能量分布计算结束后，就可以快速绘制出任何视点的光照效果图， 这个优越性使得辐射度技术在vr 漫游中有广泛的应用i ； 景。但是这种技术也有它的不 足，那就是形状因子( f o r mf a c t o r ) 计算时间长，还有，经典的辐射度技术无法处理理想镜面 反射和规则透射，因此对绘制的场景有很大的限制。 结合光线跟踪和辐射度算法的两趟绘制方法和多趟绘制方法比较好地结合了两种绘 制方法的优点，绘制所得的效果图也相应具有更高得真实感。当然，计算复杂度也相应增 加。 体绘制技术 体绘制技术最近几年才被应用于真实感图形的生成，一般都是跟光线跟踪相结合。因 为数据场可以用来描述高度复杂的自然场景，因此在自然景物的绘制方面有非常好的应用 i j i 景。它的主要问题足数据量仍然很大，绘制速度离实时的要求还有相当的距离。 首都师范大学硕i 二学位论文 真实感图形算法与实时绘制技术研究 1 3 本文研究的内容 在日i 人的研究成果上，本文从以下几个方面进行探索研究： ( 1 ) 双向光线跟踪算法的应用实现 本部分在传统光线跟踪的研究基础上对双向光线跟踪算法做了一定的研究，给出了完 整的算法，实现了光线在非漫反射一漫反射场景中的传递，得到了较好的实验效果。 ( 2 ) l o d 模型的简化方法研究 层次细节技术是在不影响画面视觉效果的条件下，通过逐次简化景物的表面细节来减 少场景的几何复杂性从而提高绘制算法的效率。层次细节技术有很多种，其中在2 0 0 2 年m 啦j 提出了面聚类网格简化技术，本文在详细研究了该算法的基础上对其提出了改进，提出了 基于空间八叉剖分的面聚类网格简化算法。 ( 3 ) 真实感草地的动态模拟 草地的真实感实时绘制一直是真实感图形学中的难点，这罩面涉及到很多方面的问 题，包括叶子造型、地形的构造、物体与叶子碰撞的物理模型、叶子的动态效果等等。本 文就这些方面进行研究论述，我们把重点放在叶子动态效果上 首都师范大学硕士学位论文 真实感图形算法与实时绘制技术研究 第二章双向光线跟踪算法的应用实现 2 1 引言 光线跟踪【w 。瑚l 是最早用来解决反射、折射的涉及非漫反射面参与的光能传递的算法， 它基于假设光线是一根没有大小、长度的射线，从屏幕平面投射到场景中，与可见面相交； 它完全遵守反射折射定律。所以光线跟踪成功地解决了非漫反射面非漫反射面场景中的 光能传递。光线跟踪是逆向求解算法，属于递归算法，其核心为每次求交后调用自身再次 求交，直到反射折射深度达到最大值。 光线跟踪算法只逆向跟踪从视点出发经由镜面和透射面的反射和透射的光线，它只能 模拟周围场景在镜面和透射面上产生的整体光照效果而无法模拟漫射表面上的整体光照 明效果，因而，它对场景光照明的表达是不完全的。比如，一块黑板上可能接受来自- - 4 , 镜子的太阳的反射光，尽管黑板为一理想漫反射体，其表面上不能产生镜面高光直接投射到 l | 7 i i 图2 1 双向光线l m 踪原理 观察者的眼睛中，但在黑板上我们仍能观察到明亮的光斑。这就是一个典型的镜面光能一 漫射光能的例子，我们注意到使用传统的光线跟踪算法就难以模拟出这种光能的传播 1 w 0 2 1 。这是因为浸反射面的表面粗糙，几乎每一点上的法线都有不同程度的偏离。因为是 从屏幕上出发向场景采样，所以光线跟踪也在某程度上用一根光线的大小抹杀了很多不能 用有限采样表示的信息( 如用3 2 0 x 2 4 0 表示一个十万面的球，则很多极点的元面被忽略， 因为屏幕上的光线只能和一个元面有交) 。光线跟踪无法较精确地采样漫反射面上的光照 信息，那就更无法表现漫反射面的光能传递了。 2 2 原理 首都师范大学硕士学位论文 真实感圈形算法与实时绘制技术研究 为了解决上述问题，在分布式的基础上，h e c k b e r t 和h a n r a h a n 提出了双向光线跟踪的 思想。因为光线应该是从光源出发射向物体的，但光线跟踪则从屏幕出发射向物体再回溯 到光源。这样的好处是避免不需要的光线求解，简化算法，减少运算量。但这样不利于光 能传递的求解。双向光线跟踪的思想是在逆向光线跟踪的同时进行j 下向的光线跟踪。即同 时从光源和观察者出发，对光线进行j 下向和逆向跟踪。这罩的逆向跟踪实际上就是传统的 光线跟踪，而从光源出发的正向光线跟踪则用束计算来自环境的镜面反射光和规则透射光 对漫反射表面光亮度的贡献。显然，与逆向光线跟踪相反，j 下向光线跟踪是一个与视点和 视线方向无关的过程。双向光线跟踪过程如图2 1 所示。 在图中，我们假设要求出a 点在场景中的颜色和亮度值。按传统的光线跟踪算法，我 们会计算从光源直接发送过来的光亮度，。啊，传统光线跟踪光亮度贡献l ，还要用正向光 线跟踪算法计算光源经镜面反射后对a 处的光亮度贡献j ，这样我们得到的视点a 的光亮 度为ti = i j + i i + k s l s 。 2 3 相关研究 由上述可知，双向光线跟踪技术的实现难点在于计算光能经镜面反射或规则投射后对 漫反射表面产生的自j 接光亮度贡献1 h e c k b e r t 和h a n r a h a n 采用光束跟踪技术求解多边形 场景在光源镜面反射的照射下引起的间接漫反射分量。a r v o “ v o s 6 i 于1 9 8 6 年采用“照明图” 方法成功地计算了上式中的间接漫射分量，所谓“照明图”，即存贮景物表面上的一些 网格点处的自j 接漫射分量，并以二维纹理的方法影射到该景物表面上。算法首先由光源朝 各镜面或透射表面网格点发射照明光线，然后对这些光线进行跟踪。容易知道“照明图” 存在走样问题。之后，c h a u o p a d h y a y 等采用迭代法和三维网格来进行光能传播【c 嘲7 1 辐 射度方法1 如0 9 4 能解决理想漫反射表面之问的能量传递的，随后的推广辐射度方法则能处理 包含镜面，透射镜面以及各种纹理表面的复杂环境。但辐射度方法的时自j 复杂度较高。 朱一宁 z a d 8 1 等的方法是一个简化算法，它仅适合于多边形场景。该算法不直接从光源 出发对场景进行正向光线跟踪，从而避免了前两种方法需从光源出发跟踪大量光线以及由 此引起的图形走样现象。 2 4 算法及实验结果 2 4 1 算法 对传统光线跟踪算法进行扩展，形成了本文给出的双向光线跟踪算法，算法从传统光 线跟踪中被跟踪光线与景物表面的交点p ( x , y ，z ) 出发，求周围光滑景物表面上一点p ，使 1 4 首都师范大学硕士学位论文真实感图形算法与实时绘制技术研究 之能将光源发出的光经镜面反射至p 点。取光源在p 处产生的镜面反射光作为景物交点p 处的问接点光源，并计算其入射光亮度，：。假设当前光源的位置为只0 。，y 。，z ，) ，其光强为 j 。则 i ；一t d c o s o + 七，j ( 2 - 1 ) 其中0 为入射方向e p 与p 处的平面法向量之间的夹