（计算机应用技术专业论文）基于网格简化和表面光场的实时绘制技术研究.pdf

摘要 随着计算机动画、虚拟现实、科学计算可视化等技术的广泛应用，三维实时 绘制技术逐渐成为计算机图形学的研究热点。虽然图形绘制技术经过了近四十年 的发展，取得了长足的进步，但实时绘制出复杂场景的具有照片级真实感的结果 仍然是一个具有挑战意义的研究课题。本文从两个方面研究了计算机图形学的实 时绘制技术：网格简化技术和基于图象的绘制技术。 一方面随着绘制场景复杂性的增加，图形绘制引擎面对着超过引擎实时处理 能力的数据集合。为了进行实时绘制，需要一个有效的简化算法生成与原物体近 似的、可以实时绘制的新几何数据集。目前在各种应用中，场景、物体大多采用 多边形网格来表示其几何数据，因此本文通过研究多边形的网格简化算法来解决 大型数据的实时绘制问题。另一方面，人们对绘制结果的要求越来越高，传统的 基于物体几何和表面属性的绘制方式很难实时绘制出具有照片级真实感的场景， 这将会限制计算机动画和虚拟现实技术的进一步应用。本文在网格简化的基础上 采用基于图象的绘制算法进一步增强了场景的绘制质量，使绘制的结果具有了照 片级的真实感。 本论文首先给出了一个实时的网格简化算法，在预处理阶段通过对边的折叠 逐渐减少复杂物体三角面片的数量，达到错误率上限时停止简化，在简化的过程 中记录边折叠的逆操作一顶点分裂，进而将结果存储为二叉树表示形式。在使 用阶段，根据用户视点的位置、方向裁剪物体对应的二叉树，并适当进行的顶点 分裂操作，形成用户可接受的绘制结果。这种算法在简化速度和简化质量上做了 一个很好的折衷，既能很好的保持物体原有的形状、拓扑信息，又能以较高的速 度进行简化。 进一步可以通过我们提出的基于边分组的表面光场影射算法，使物体在普通 的p c 机上进行照片级真实感的实时绘制。算法从多幅已知摄像机参数和位置的 图象开始，通过计算物体几何信息投影到图象样本上的可见性，得到“三角形对” 样本的完全可见和部分可见列表，在此基础上利用“三角形对”的局部坐标系对 位置、视点信息分别进行重新采样，最终形成用一系列的二维采样矩阵表示的四 捅要 维表面光场，然后在预处理阶段就对这些基于“三角形对”的光场矩阵进行非均 匀分解，形成二维表面纹理和视点纹理，并按照三角形面积的大小对纹理进行排 序，其中的矩阵分解次数由用户指定的重建质量决定。最后在绘制阶段采用纹理 映射和分组技术进行任意视点和方向的实时显示，充分利用了图形硬件的加速功 能。 实验结果表明，以上两种技术能够在较大程度上提高绘制效率，并且能够达 到较高的绘制质量。在文章的结论部分，对于以上二者的发展以及进一步结合进 行了展望。 关键词：网格简化；边折叠；基于图象的绘制( i b r ) ；表面光场；纹理映射 主元分析( p c a ) i i i a b s t r a c t a b s t r a c t w i t ht h ew i d e s p r e a da d o p t i o no ft e c h n o l o g i e ss u c ha sc o m p u t e ra n i m a t i o na n d v i r t u a le n v i r o n m e n t s ，t h r e ed i m e n s i o n a lr e n d e r i n gi s b e c o m i n gm o r ea n dm o r e i m p o r t a n t w i t ht h ep r o g r e s so nc o m p u t e rg r a p h i c si nr e c e n tf b r t yy e a r s ，r e a l t i m e r e n d e r i n go fc o m p l e xo b j e c t sa n ds c e n er e m a i n sab i gp r o b l e m i nt h i st h e s i sw ea d o p t t w o t e c h n o l o g i e s ，w h i c ha r em e s hs i m p l i f i c a t i o na n di m a g e b a s e dr e n d e r i n g ，t os o l v e t h i sp r o b l e m m a n ya p p l i c a t i o n s i nc o m p u t e rg r a p h i c sa n dr e l a t e df i e l d sc a l lb e n e f i tf r o m a u t o m a t i cs i m p l i f i c a t i o no f c o m p l e xp o l y g o n a ls u r f a c em o d e l sd u et ot h ea p p l i c a t i o n s a r eo f t e nc o n f r o n t e dw i t ho v e r - s a m p l e dm o d e l sw h o s ec o m p l e x i t ya r eb e y o n dt h e l i m i t e da v a i l a b l eh a r d w a r ec a p a c i t y a ne f f e c t i v ea l g o r i t h mf o rr a p i d l yp r o d u c i n g h i g h q u a l i t ya p p r o x i m a t i o n so ft h eo r i g i n a lm o d e l si sav a l u a b l et o o lf o rm a n a g i n g d a t ac o m p l e x i t y h o w e v e r , t h eq u a l 耐o ft r a d i t i o n a lr e n d e r i n gs y s t e mi sn o tf e a t u r e d b yr e a lt i m e ，i nt h eo t h e rw o r d s ，t h er e n d e r i n gr e s u l ti st i m e c o n s u m i n g l a t e s t d e v e l o p m e n t si ni m a g e - b a s e dm o d e l i n ga n dr e n d e r i n gp r o v i d es i g n i f i c a n ta d v a n t a g e s o v e rt r a d i t i o n a l i m a g es y n t h e s i sp r o c e s s ，i n c l u d i n gi m p r o v e dr e a l i s m ，s i m p l e r e p r e s e n t a t i o na n da u t o m a t i cc o n t e n tc r e a t i o n i nt h i st h e s i s ，w ep r o p o s ear e a l - t i m em e s hs i m p l i f i c a t i o nm e t h o db a s e do ne d g e c o n t r a c t i o n t h et e c h n o l o g yu s e q u a d r i cm e t r i cm e a s u r et os e l e c tc o n t r a c t e de d g ea n d t h eo p e r a t i o ni ss t o r e df o rf u t u r eu s ei n p r e p r o c e s s i n gs t a g eo fr e n d e r i n g t h e p r e - p r o c e s s i n gi s t e r m i n a t e dw h e ne r r o rm e a s u r er e a c h e sat h r e s h o l da n dc a nb e r e p a i r e d t of o r mb i n a r yt r e e t h i st e c h n i q u ep r o v i d e sa l le f f e c t i v ec o m p r o m i s e b e t w e e nt h ef a s t e s ta l g o r i t h m s ，w h i c ho f t e np r o d u c ep o o rq u a l i t yr e s u l t s ，a n dt h e h i g h e s t q u a l i t ya l g o r i t h m s ，w h i c ha r eg e n e r a l l yv e r ys l o w i no r d e rt oe n h a n c et h er e a l i s mo fr e n d e r i n gr e s u l t ，w ea d o p ts u r f a c el i g h tf i e l d m a p p i n gt e c h n o l o g y i nt h i st h e s i sa ni m a g e b a s e dm e t h o d n o u n i f o r ml i g h tf i e l d m a p p i n gi sp r o p o s e d b yc o m b i n i n ge d g e b a s e ds u r f a c el i g h tf i e l dp a r t i t i o na n d t i n u n i f o r md e c o m p o s i t i o no f l i g h tf i e l dm a t r i x ，t h r o u g hw h i c ha r e a l t i m ep r o g r e s s i v e r e n d e r i n gc a nb ea c h i e v e d s t a r t i n gf r o mm u l t i p l ei m a g e sc a p t u r e df r o mv a n t a g e p o i n t s ，w ep a r t i t i o nt h e mo v e rb i t r i a n g l ea n da r r a n g et h e mi n t o2 dm a t r i x e st h a tw i l l b ef a c t o r e di n t ou n - u n i f o r mt e x t u r e st oa p p r o x i m a t et h el i g h tf i e l dd a t a a sar e s u l t ， w ep r e s e n ta ni m a g e - b a s e dr e n d e r i n gm e t h o d - - 一n o u n i f o r ml i g h tf i e l dm a p p i n gb y g r o u p i n gt h e s et e x t u r e si n t ot i l e sa n dr e n d e r i n gd i r e c t l yf r o mt h e s ec o m p a c td a t a a b s t r a c t t h r o u g hg r a p h i cc a r d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dc a np r o m o t er e n d e r i n gs p e e d g r e a t l ya n dw i t ht h ea s s i s to fg e o m e t r i ci n f o r m a t i o n ，t h es a m p l i n gd e n s i t yo f i m a g e b a s e dr e p r e s e n t a t i o n sc a nb eg r e a t l yr e d u c e d ，a n dt h er a d i a n c ed a t ac a n p o t e n t i a l l yb er e p r e s e n t e dm o r ec o m p a c t l y i nt h el a s tp a r t ，t h e j o i n to f t h e s et w o t e c h n o l o g i e si sp r o s p e c t e d k e yw o r d s ：m e s hs i m p l i f i c a t i o n ，e d g ec o n t r a c t ，i m a g e b a s e dr e n d e r i n g ( m r ) s u r f a c el i g h tf i e l d ，t e x t u r em a p p i n g ，p r i n c i p l ec o m p o n e n t a n a l y s i s ( p c a ) v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：幂i l 日期：竺：! 旦 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 翌盘， 导师签名： 至室立 日期：兰丝垒当 第一章绪论 第一章绪论 随着计算机动画【1 ，2 、虚拟现实技术以及科学计算可视化的广泛应用，对物 体、场景的实时绘制提出了更高的要求，一方面物体、场景越来越复杂，远远超 过了绘制引擎的实时绘制能力，另一方面要求生成的物体、场景更加真实、具有 良好的交互性，这就要求进一步研究复杂场景的真实感的、实时绘制技术。 计算机图形学利相关领域的许多应用都依赖于模型的多边形网格以进行模 拟和显示，这些模型一般具有固定数量的顶点、多边形，提供了单一层次的模型 细节，因此这种单一的几何模型不适合对物体在不同应用环境下的绘制。本论文 集中解决了复杂物体、过采样物体多边形网格的自动简化问题，通过简化算法使 模型可以使用较少的多边形网格近似表示原始模型，并且能够保持对原始模型外 观的高度近似，请参看图l - 1 。 ( a ) 原始模型( b ) 1 4 的原始模型( c ) 4 4 的原始模型 图l - 1 ：多边形模型和自动简化的结果 f i g u r e1 1p o l y g o n a lm o d e lw i t ha p p r o x i m a t i o n s 在本论文中将介绍一种改进的网格简化算法，它在预处理阶段通过对边的折 叠逐渐减少复杂物体兰角面片的数量，达到错误率上限时停止简化( 边折叠) ， 在简化的过程中记录边折叠的逆操作一顶点分裂，进而将结果存储为二叉树表 示形式。在使用阶段，根据用户视点的位置、方向裁剪物体对应的二又树，并适 当的进行顶点分裂操作，形成用户可接受的绘制结果。 从图1 1 中可以看出，虽然通过网格简化可以减少模型的绘制时间，同时在 一定程度上保持了物体的外观，但是其绘制结果并不具有强烈的真实感，这对于 北京工业大掌工学硕士学位论文 像电影制作等领域的应用是不合适的。为了进一步增强绘制效果，本文进步采 用基于图象的绘制技术【3 4 ，5 ，6 ，7 ，耕，结合网格简化算法，实时的绘制出具有真实感 的图象。 基于图象的绘制技术( i m a g e b a s e dr e n d e r i n g ，i b r ) 通过对场景的采样，生 成场景的近似全光函数【3 8 】，以重采样的方式对场景进行真实感的绘制。图l - 2 是基于图象绘制的一个例子，左面的图象是实际拍摄的照片，右面的图象是一个 不同角度的实时绘制结果。它采用了本文提出的基于边分组的表面光场( s u r f a c e l i g h tf i e l d ，s l f ) 映射技术进行绘制，在普通的p c 机上可以达到2 0 3 0 f p s 的绘 制速度，详细描述请参照第4 章。 ( a ) 原始照片( b ) 3 次近似实时绘制的结果 图1 - 2 ：光场的绘制结果 f i g u r e1 2 t w or e s u l t so fs u r f a c eli g h tf i e l dr e n d e r i n g 本章的内容是按照以下方式组织的：首先介绍了网格简化和基于图象绘制技 术( i m a g e b a s e dr e n d e r i n g ，i b r ) 的研究背景、方法以及意义，并简要地阐述本 文提出的网格简化算法和表面光场映射技术，最后将介绍论文的内容排列与组织 结构等有关内容。 1 1 实时绘制技术的研究背景 第一章绪论 近年来，随着虚拟现实、多媒体技术一特别是网络多媒体( 如网络游戏) 的 发展与推广，计算机图形学的实时绘制技术受到了人们的广泛关注。传统的真实 感图形绘制算法追求的是图形的真实感和高质量，而对每一帧画面的绘制速度并 没有严格的限制。而虚拟现实、网络多媒体系统要求的实时绘制技术本质上是一 种限时计算技术，即要求算法必须在给定的时间内，完成对场景的绘制，同时尽 可能的保持场景的真实感【9 1 。 计算机图形的绘制过程主要通过软件和硬件来实现，而在绘制技术高速发展 的今天更多的是利用硬件来加速实现绘制过程。一般采用帧缓存的填充速率、_ ：_ 二 角形绘制速率、以及图形内存带宽来衡量图形引擎硬件的绘制能力。对于一个特 定的系统，这些参数都是固定的，但是计算机需要显示的场景的复杂度是变化的， 为了维持恒定的绘制速度如3 0 f p s ，就需要根据应用系统的需要自适应的调整 场景的复杂程度。适应这种需求，需要一种可以对模型进行自动的简化处理的技 术，而网格简化技术 1 0 - 1 4 1 正是这样的一种技术。它一种传统的计算机图形学实时 绘制技术，通过这种技术可以将通过不同方式采样得到的场景几何信息实时的简 化、绘制，同时能够最大限度的保持物体原有的形状和拓扑。 三维激光扫描仪、医学图象系统、计算机视觉系统都可以产生实际物体复杂 的三维模型。计算机辅助设计系统、散乱点的曲面重建、等势面的抽取算法同样 也可以产生实际或者虚拟物体的复杂模型。在这些系统本身都可以通过一定的技 术将获得到的原始数据转化成多边形网格表示方式，多边形网格表示方式是目前 最常用的种几何表示方式” 。这些系统都对原始物体进行了精细的采样以最 大限度的保持原物体的形状，因此这些模型的多边形表示方式巾常常包含着几百 万个多边形网格。但是由于计算机绘制能力的限制，对这些复杂的模型，在普通 的机器上根本不能实时绘制，同时这些模型需要被多种应用系统使用，而不同的 应用系统对模型精细度的要求也是不一样的。 为了适应这种实时绘制、多分辨率模型的需求，需要对物体表面的刚格进行 自动的简化。网格简化的应用包括从需要简单三维模型的分布式虚拟现实到需要 精细模型的电影特效制作，在这些应用系统中存在着绘制模型精细程度和汁算机 处理能力之间的矛盾，精细的模型可以产生更加逼真的效果，但需要太多的处理 时间，这在某些实时系统中是不可接受的。为了在一个可接受的时间内绘制出结 北京工业大学工学硼士宇位论文 果，必须使用物体的一个简化模型来代替原有的精细模型。同时保存。个物体精 细的几何模型仅仅是为了在以后对任何应用都有足够的数据可供使用，而对于某 些应用而言仅仅需要原始数据的一个粗略的近似就足够了。因此网格简化是个 对模型按照不同的应用进行裁剪的工具，使应用系统既能够使刖足够精细的模型 又不造成绘制效率上的浪费。 但是网格简化是面向计算机处理的( 为了适应计算机的处理能力) ，而绘制 最终需要的是一个直观、具有强烈真实感的画面，这就需要进一步研究图形学的 真实感绘制问题，这也是从2 0 世纪6 0 年代的矢量图形学开始，人们一直在关心 的话题。追求具有照片级真实感( p h o t o r e a l i s t i c ) 的绘制效果是图形学发展过程 中一条始终不变的主线。图形学的研究人员和电子工程师不断地开发出更强大的 显示设备，提出了更有效的几何表示和光照模型来解决这个问题。到2 0 世纪9 0 年代，真实感图形学成了传统图形学的一个主要部分m j 。 然而真实感绘制在传统图形学中还是一件很困难的事。在计算机图形学领域 中，传统的真实感绘制方法通过模拟光的传输、反射、折射规律生成照片级真实 感的图象。这类算法首先创建真实感的模型，这本身是一件很困难的事，设计师 必须非常细致地一点一点地建立几何模型，分析模型的表面几何特性以及反射、 折射特性，然后通过模拟物理规律以及一些启发式的规则如辐射度方法 ( r a d i o s i t y ) 和全局光照方法( g l o b a li l l u m i n a t i o n ) 生成图象，这些算法的计算 复杂度很高。总之，传统的真实感绘制方法存在的缺点是：建模很困难，绘制很 慢。这类算法在过去的3 0 年中直在发展，使能够绘制的场景越来越复杂、越 来越真实，绘制速度也逐渐在提高。但是这类算法需要获得模型的表面几何特性 以及反射、折射特性，这需要很繁琐、细致的工作。在另一方面，计算机视觉以 图象和摄像机参数为输入，输出场景几何的描述、结构以及光的特性。由于计算 机视觉的输出可以用在图形学的输入中，这两个领域的研究可以结合在一起。 计算机图形学研究的是如何运用模型生成真实感的图象，而计算机视觉则通 过分析图象来创建物体的模型( 包括物体的几何和表面模型以及物体的运动变 化) 。可见，计算机视觉和计算机图形学是一个可以互补的组合，i b r 技术也是 从这样的基本思想出发的，即对输入图象，用计算机视觉技术来获取模型表示， 用计算机图形学来生成新的图象。i b r 技术就是结合计算机视觉技术来简化和加 第一苹鳍诧 快真实感的图形绘制，通过二维或者三维图象获取设备获得可以描述场景的图 象，利用计算机视觉技术对图象进行处理，形成可存储、检索的样本，然后i b r 绘制算法【5 ，1 8 , 1 9 通过对样本数据库的检索并结合定的几何数据日j 以绘制出具 有照片级真实感的图象。 从上面的论述中可以看出，传统的计算机图形学绘制方法是一种物理模拟的 过程，而i b r 技术是一种信号重采样、重建的过程。在这类算法中，最关键的 问题是模型的表示，即怎样的模型才是恰当的，其中最主要因素是这个模型到底 有多少几何信息、多少采样数据。几个重要的i b r 算法或系统都是围绕着模型 的不同表示展开的【4 ，5 ，6 ，7 ，2 “。最具体的模型只需要很少的几何信息，但需要很大 的采样数据；相反的最简洁的模型有完备的几何信息，它只需要很少的采样图象， 但这样的模型仅仅利用计算机视觉技术来获取是很困难的，同时这种模型表示的 绘制系统很难实时的绘制出照片真实感的结果。于是，一个i b r 系统要在几何 信息的多少、几何信息的获取难度、以及绘制的速度和真实感之闻做出恰当的取 舍【2 2 】。 综上所述，网格简化和i b r 技术是图形学实时绘制的两种加速技术，它们 分别从物体、场景的几何以及图象两个角度来加速系统的绘制流程。本文研究的 目的就是将两种技术进行初步的结合，也就是研究在一定几何表示的前提下( 通 过网格简化的过程获得) ，对原始图象进行处理，形成样本数据有效的、简洁的 表示方式，并实时的绘制出具有照片真实感的结果。 1 2 研究现状综述 多分辨率模型的思想起源于2 0 多年前，最初用在飞行模拟中，用来简化大 犁地形表面的实时绘制( 主要用在高地的简化以及曲面的简化卜) 。使用般的 多边形网格来表示多分率模型只有近1 0 年的历史，最初网格简化算法用来生成 离散的、静态的l o d 模型 2 3 , 2 4 1 ，近年来更多的算法用来解决动态、自适应的网 格简化2 5 1 问题。与网格简化相关的工作还包括网格压缩和网格平滑【2 6 1 ，在这 置个相近的领域中，采用网格简化生成物体的多分辨模型并采用有效的方式表示 是基础。 静态l o d 的基本思想是：对场景中的物体或者物体的不同部分，采用不同 北京工业大学工学硕士学位论文 的细节描述方法，在绘制的时候，如果一个物体离视点比较远，或者这个物体比 较小，就可以用粗糙的l o d 模型绘制。反之，如果一个物体离视点比较近，或 者物体比较大，就必须采用较精细的l o d 模型来绘制。同样的情况也可以用在 有运动物体的场景中，对场景中运动的物体采用粗糙的l o d ，静止的物体采用 较精细的l o d 。但这种静态l o d 方式缺乏灵活性，并且需要大量的存储空间来 存储同一个物体不同分辨率的模型，在模型转换的时候也容易产生失真。于是人 们提出了各种实时、动态的网格简化算法来解决这些问题，其中有四种主要的算 法，表l l 是对他们之间性能、适用范围的比较( 具体的论述请参考第2 2 节) 。 表i - 1 各种网格简化算法的比较 t a b l ei - it h ec o m p a r i s o no f f o u rm e s hs i m p l i f i c a t i o na l g o r i t h m 算法顶点聚类项点删除二次误差累进网格 项目 类型采样点删除边折叠边折叠 误差范围 局部局部全局全局 拓扑保持保持不保持保持 模型类型任意网格流形面流形面任意网格 误差是否有界无无无无 计算复杂度逐渐升高，简化质量逐渐升高 而基于图象的绘制技术可以追溯到1 9 9 1 年a d e l s o n1 3 j 提出的关于七维全光 函数的论述：从物体发出的光线可以被参数化成为一个7 d 全光函数。 f ( x ，y ，z ，p ， ，f ) 斗( r ，g ，6 ) ( 1 1 ) 重建、计算这样的一个七维函数是非常困难的，为了简化计算，人们通过各 种方法对全光函数进行降维处理，1 9 9 5 年m c m i l l a n l 4 ，”】通过限制时间和光源( 往 静态环境、光照不变的情况下) 提出了5 d 全光函数，1 9 9 6 年l e v o y 5 1 和g o r t l e r l 6 】 提出了4 d 光场绘制算法，他们将物体限制在一个包围盒中，通过两个平行平面 对物体发出的光线进行参数化，得到四维光场函数，1 9 9 9 年s h u m 【7 1 提m 了3 d 第一章绪论 光场表示方式，通过这些处理使光场在表示、压缩方面有了较大的改进，但光场 的数据量还是比较大，而且绘制算法没有得到相应的改进。 另一方面，计算机图形学也在逐渐采用图象来表示物体的细节，如纹理影射、 凸凹纹理、几何纹理等技术。这些信息被存储在样本库中，在绘制的时候，通过 反向查找样本库来重建目标图象。这个过程和i b r 技术非常类似，但问题是， 这种传统方法需要非常细致的几何信息，对样本图象的要求反而非常少，通过复 杂的模拟计算来获得真实感的效果。 i b r 技术同传统的图形绘制技术的结合是一个正在兴起的研究热点，许多问 题还处于研究的起步阶段，本文在这方面做出了一个尝试，通过试验证明这种方 面具有一定的实用价值，特别适用于透明、半透明或者绒毛类等表面特性复杂的 物体的绘制，对于一般的物体同样也能以非常高的真实感进行绘制。 1 3 论文创新 本文研究的目的是：将网格简化和基于图象的绘制两种技术进行初步的结 合，通过网格简化技术，实时绘制出整个场景，对其中静态的物体、场景研究在 一定几何表示的前提下( 通过网格简化的过程获得) ，对原始图象进行处理，形 成样本数据有效的、简洁的表示方式，并实时绘制出具有照片真实感的结果。 在这个目的下，本文提出了以下的创新： 提出了一种新的网格简化框架，通过预处理使原始网格的最简化形式呈 现出二叉树结构，并且以递进网格形式存储，在绘制阶段结合b s p 可见 性判别策略可以实时的处理大规模网格数据。 提出了生成光场采样矩阵的非均匀采样算法，通过d e l a u n a y 三角剖分算 法可以使半遮挡数据根据重建质量的要求n a n 最终的样本数据库中， 为数据分解提供更有效的支持。 提出了以“三角形对”为基础的表面光场分组算法，这种分组方式一方 面保证了重建光场的连续性，另一方面降低了运算的复杂度。 提出了光场矩阵的非均匀分解算法，通过这种算法使光场数据能够更加 紧致的表示场景信息，从而需要更少的数据来表示场景样本。 利用分组算法改进了表面光场绘制效率，通过对分解后的样本数据进行 北京工业大学工学硕士学位论文 分组排序，利用双通道的纹理影射算法，提高了绘制效率。 1 4 本文的内容安排与组织结构 本文主要研究实时绘制算法，主要内容包括网格简化算法、表面光场的绘制 技术两个部分。在网格简化方面，本文提出了一种新的网格简化框架，通过预处 理使原始网格的最简化形式呈现出二叉树结构，并且以递进网格形式存储，在绘 制阶段结合b s p 可见性判别策略可以实时处理大规模网格数据。在表面光场的绘 制方面，本文提出了基于边分组的光场矩阵非均匀分解算法，通过对分解数据的 分组排序，在绘制阶段可以充分利用数据的相关性，减少索引时间，加快绘制效 率。 文文分为以下几个部分：第一章主要介绍了实时绘制算法的研究背景、研究 意义，并简要的介绍了国内外的研究现状，同时对本文的创新做了一个总结。第 二章详细的介绍网格简化和表面光场绘制技术的研究现状，对各种算法作出了一 个比较，同时详细介绍了物体表面模型的两类表示方式。第三章给出了我们在网 格简化方面所提出的一个框架，着重介绍了边折叠算法的一般步骡，同时介绍了 本文使用的二次误差简化标准，并从理论上作出了分析，最后介绍了二叉树结构 的生成、存储。第四章提出表面光场的实时绘制算法，从多幅已知摄像机参数和 位置的图象开始，通过计算物体几何信息投影到图象样本上的可见性，得到“三 角形对”样本的完全可见和部分可见列表，并利用几何信息对样本进行采样，在 此基础上利用“三角形对”的局部坐标系对光场视点信息重新采样，最终形成一 系列的二维采样矩阵，然后在预处理阶段就对这些基于边分组的光场矩阵进行非 均匀分解，形成二维表面纹理和视点纹理，并按照三角形面积的大小对纹理进行 排序。在绘制阶段采用纹理映射和分组技术进行实时绘制，充分利用了图形硬件 进行加速。第五章给出了实验结果，并做出了详细的分析，同时对本文的应用背 景作了详细的探讨。最后，在第六章总结本文所阐述的内容，并展望了本方向未 来的工作。 第二章相关工作 第二章相关工作 这一章论述了本文的工作基础，首先介绍了物体表面模型的两种表示方式 多边形网格表示和光场表示，接着介绍了网格之间的相似度度量的标准，这是网 格简化算法的基础，然后给出了三角形网格简化算法的发展、典型算法描述，最 后给出了光场绘制技术的发展、算法描述。 在本章中我们采用了以下的记法：本章所说的向量都是指列向量，并且以小 写的黑体字表示，矩阵以大写的黑体字表示。因此u v 。u v 表示向量1 1 和v 的 内积，而a 2 i i v5 表示两个向量的外积。 2 1 物体表面模型的表示 从第一章的介绍中可以看出，三维世界中的物体既可以采用三维几何1 4 ，2 7 来表示，然后利用传统的绘制方式进行显示；也可以使用图象来表示【5 ，6 ，2 8 1 ，在 这类基于图象的绘制算法中，既可以通过计算机视觉的方式自动生成物体的三维 几何信息，然后进行绘制，也可以通过光场采样算法【5 ，6 ，3 0 , ”】，直接使用图象 样本生成原物体在新视点的图象。 2 1 1 几何模型 物体的三维几何表示方式很多【l l ，1 2 3 2 , ”】，目前在虚拟现实和些交互系统中 常用的还是多边形网格模型。从广义上讲，物体的多边形表面模型是三维欧氏空 间r 中的一组平面多边形的集合。 采用三角形网格表示物体的表面是非常有效的：三角形网格非常灵活，并且 应用范围非常广。大多数商用建模、绘制系统中都支持多边形表示方式，因此多 边形模型可以较容易的获得，并且可以被广泛使用。同时，计算机硬件绘制加速 绘制技术已被广泛的使用，其绘制的基本单元就是多边形 3 4 。目前来讲，没有其 它的模型表示方式能够获得如此广泛的应用。由于多边形都可以三角化为一组三 北京工业大学工学硕士学位论文 角形，我们假定物体的模型全部由三角形面片组成( 对于某些设备获得的网格可 能含有孤立的点或者线段，我们可以在进行网格简化之前对模型几何进行预处理 除去多余的顶点或者边) 。 在这种假设下，为了下文叙述上的方便，我们对物体的三角形网格定义如下： m = ( v ，f ) 是一个由顶点列表和三角形列表组成的二元组，其中顶点列表 v = ( v ，v ：，v 。) 和三角形列表f = ( ，f 2 ，l ) 都是有序的序列。每一个顶点 v ，= 阮，y j ，毛r 是一个在三维欧氏空间r 中的列向量，每个三角形f ，= ( ，z ) 由 三个表示三角形顶点( v ，v 。，v ，) 的有序列表组成。对于m 中任意一个顶点v ，可 能有1 个或多个三角形使用了v ；，把这些三角形定义为与顶点v ：相关的三角形 l ，简称为相关三角形口5 1 ( o f 珂，0 k m ) 。对m 中任顶点v ，与v i 相关 的所有三角形r 按逆时针方向排列，则构成有序三角形环( 或者半环) ，简记为 t l 陬1 羽。 2 1 2 光场表示 上面介绍了物体表面的一种表示方式，而在近几年出现了另外一种物体表面 三维信息的表示方式，它不需要显式的构建物体的几何信息，通过对物体的密集 采样形成光场函数，用来表示物体的三维信息。这种方法就是基于图象的绘制方 式。 基于图象的绘制技术( i b r ) 就是直接利用输入图象来合成在新视点位置、 方向的绘制图象，由于它可以直接采用现实环境中的图象进行合成，i b r 技术可 以产生很好的真实感效果，在某些算法中可以采用少量的模型作为绘制时进一步 的支持。经典的i b r 算法可根据其对几何的依赖程度分成三类：不需要几何的 算法，需要一定几何的算法以及需要明确几何的算法【3 6 1 。不需要几何的代表性 算法有：l i g h tf i e l dr e n d e r i n g 【5 1 ，l u m i g r a p h 【6 1 ，c o n c e n t r i cm o s a i c s 7 1 ，i m a g e m o s a i c k i n g1 3 7 。需要一定几何的代表性算法有：v i e wi n t e r p o l a t i o np s i ，v i e w m o r p h i n g 3 9 , 4 0 ，表面光场( s u r f a c e l i g h tf i e l d ) 【4 1 ，8 1 。需要明确的几何的代表性 算法有：3 dw a r p i n g 【1 7 l4 2 ，l d i ( l a y e r e dd e p t hi m a g e s ) 1 4 3 ，v i e w d e p e n d e n tt e x t u r e 1 0 第二章相关工作 m a p sm 2 1 i 。不需要几何支持的i b r 算法通常被称为纯粹的i b r 算法，这类算法一 般采样要求比较高，数据量比较大，但绘制的速度快，真实感强。需要明确几何 支持的i b r 算法一般只需要很少的输入图象作为样本，采样要求很低，但它需要 依靠计算机视觉技术来恢复出场景的几何，绘制的真实感一般比不需要几何支持 的i b r 算法差。在实际中很多算法是介于这两个极端之间的。总之，大部分i b r 算法都是在应用需求、绘制的真实感、绘制速度、表示的简洁性、采样数据量和 恢复几何的代价之间做出折衷。 图2 - 1 对几种最常用的i b r 算法进行了一个总结，其中纵坐标是几何数据的 利用量，而横坐标是对图象样本的利用量。从图中可咀看出v i e w d e p e n d e n t t e x t u r em a p p i n g ( v d t m ) 2 1 1 算法和表面光场算法( s l f ) 4 1 1 是位于这两个极端 之间的，它们既使用了一定量的几何信息，又采用了较多的图象样本信息，最终 图象的绘制质量具有较好的真实感同时也保持了较快的绘制速度。 g e o m e t r i c d a t a 图2 1 ：i b r 技术的分类 f i g u r e2 - 1t h ec a t a l o g so fi b r 北京3 2 业大学工学蚀士学位论又 a d e l s o n 1 和b e r g e n 在1 9 9 1 年提出了全光函数的概念，他们认为早期计算机 视觉的主要任务是获得一个紧致的、有效的全光函数的局部变化的描述。全光函 数的概念为i b r 技术提供了很好的理论基础，i b r 技术的重要算法也都围绕着如 何有效的简化全光函数，如何获得简化后的全光函数来展开。在 1 】中a d e l s o n 和 b e r g e n 提出的全光函数是个7 维函数： f ( x ，y ，z ，0 ，庐，五，f ) 寸( r ，g ，6 ) ( 2 - 1 ) 它定义了通过空间任意点( x ，y ，z ) ，任意方向( p ，妒) ，任意波长的 ，任何时间f 的 光线的颜色值( 亮度值) 。 为了简化计算在一般的i b r 系统中，兄和，都取常数值。对剩下五个参数的 不同形式的简化就产生了不同的i b r 系统，p l e n o p t i cm o d e l i n g ( 5 d ) 4 ”1 ，l i g h t f i e l d 5 1 和l u m i g r a p h 6 1 ( 4 d ) ( 见图2 2 ) ，c o n c e n t r i cm o s a i c s ( 3 d ) 【7 】，l a y e r e dd e p t h i m a g e s 【4 3 】和v i e wd e p e n d e n tm o d e l s 口o ，2 1 】( 2 5 d ) ，c y l i n d r i c a l s p h e r i c a lp a n o r a m a ( 2 d ) 【”1 。 这些方法都是通过对输入的图象作不同的参数化处理，形成样本数据库，在 绘制的时候通过对数据库的查找算法产生新视点的合成图象。由于对五和r 都取 常数值，这些系统都是针对静态场景、光照不变的情况下进行的。在 4 4 1 0 0 ，w o n g 等提出了光照可变的i b r 技术。为了表示统一，可以把场景的光照加入全光函 数，这样就得到了一个完备的物体表面的反光特性的完备描述( 见公式2 2 ) 。 r = r ( r i ；r ，) ( 2 - 2 ) 其中： r f = r i 吒，屹f ，占，庐f ， 川tj ( 2 _ 3 ) r ，= r ，妒o ，矿”，p ，0 ，妒， ，t ，j ( 2 _ 4 ) r 表示入射到物体的全光函数，耳表示物体反射的全光函数。r 定量地描 述了入射到点( ，匕) ，方向为( 只，谚) 的光线与从点( ，巧) 反射，沿着 ( 只，谚) 方向的光线的关系。 由于本文主要采用4 d 的全光函数，下面着重介绍一下4 d 全光函数的绘制 算法。1 9 9 6 年l e v o y 5 】和g o r t l e r l 6 1 提出了4 d 光场绘制算法，他们将物体限制在 第二章相关工作 个包围盒中，进步假定光线在空间中传播时保持不变，通过两个平行平面对 物体发出的光线进行参数化，5 d 的全光函数可以参数化为4 d 的全光函数，如 图( 2 2 ) 所示。 在图2 2 中获得的每一i 晤图象中每一像素点作为一条和平面u v 以及s t 相 交的光线的亮度值，其样本值作为数据库中对应于两个交点( “，v ) 以及( br ) 确定 的函数值，用公式来表示就是： 在生成新图象的时候，对于待生成图象中的每一点，计算图象中由视点确定 的光线和两个平面的交点，并将交点的参数值作为数据库的索引依据，通过插值 形成图象中最终的像素值。l j | g h tf i l e d 和l u m i g r a p h 的差别就在丁对几何的利用 上，l i g h tf i e l d 算法在插值的时候，仅仅利用了网格周围的点的数据：而 l u m i g r a p h 算法采用几何校正技术，插值时用三维空间上相邻的两个点作为近邻 点，即使他们在参数空间上相隔较远。 图2 - 2 ：l i g h tf i e l d 参数化方式 f i g u r e2 - 2 t h ep a r a m e t e r i z a t i o no fl i g h tf i e l d 这里会引起