（计算机应用技术专业论文）虚拟现实中的三维模型简化技术.pdf

摘要 虚拟现实技术作为一种强大的人机交互技术，一直是信息领域研究开发和应用 的热点方向之一。而对于虚拟现实技术的发展，三维图形的实时生成是一项非常 关键的技术，因为大规模三维虚拟场景的实时交互必然要涉及到复杂几何模型的 交互显示。出于对虚拟场景真实感的需求，模型的复杂度往往非常的高，甚至超 出了目前高性能计算机系统的实时绘制能力。另一方面，随着近几十年计算机技 术的飞速发展，软硬件技术都有了很大幅度的提高，在这种趋势下，为了提高软 件的可移植性，图形数据模型都采用浮点数来表示，相关的处理算法也不再苛求 整数运算。这样，在处理大规模三维数据模型的时候，就会对计算机硬件有非常 高的要求。 因此，如何提高大规模复杂场景的绘制速度，从而实现复杂数据的实时交互显 示，已成为当前计算机图形学中的热点问题。 为了要获得理想的视觉效果和计算机处理速度，可以使用一定的技术对场景中 的模型进行管理。细节层次( l e v e lo f d e t a i l s ，l o d ) 技术是目前最常用的技术之 一，即将三维物体用多种不同的精度表示，并且根据观察点位置变化而选择不同 精度的模型予以成像。可见，对于三维复杂模型的简化算法就成为影响整个虚拟 现实系统的关键因素之一，也就是要在不影响图形精度的前提下尽可能的简化模 型，删除模型中的顶点和面，使其能够在不失真的情况下高速实时显示。 论文主要对基于虚拟现实系统的三维模型简化方法进行了深入的研究。首先对 虚拟现实系统、三维图形建模以及l o d 技术做了简要的介绍：针对目前常用的三 维图形文件的文件格式，为了便于处理，定义了一种专用的三维文件格式，给出 了处理方法；在对l o d 技术介绍的基础上，针对其中的边折叠算法进行了重点分 析，给出了实现方法及测试分析结果；最后针对现有算法计算量大、效率低的缺 点，提出了一种基于设备坐标系的完全不包含浮点运算的模型简化算法。通过对 该算法进行的测试分析表明，该算法可以应用于超大规模三维模型的初步简化以 及部分对精度要求不高的实时交互系统。 关键词：虚拟现实细节层次技术网格简化 边折叠设备坐标系 2 虚拟现实中的三维模型简化技术 a b s t r a c t v i r t u a lr e a l i t y ，a st h em o s tp o w e r f u lt e c h n o l o g yo fh u m a n c o m p u t e ri n t e r a c t i o n , h a sa l w a y sb e e no n eo ft h es p o t l i g h to fi n f o r m a t i o nf i e l dr e s e a r c ha n da p p l i c a t i o n h o w e v e r ，t ot h ed e v e l o p m e n to fv i r t u a lr e a l i t y ，r e a l t i m er e n d e r i n g3 dg r a p h i c si sa k e yi t e m ，b e c a u s el a r g e s c a l e3 dr e a l - t i m ei n t e r a c t i o no fv i r t u a ls c e n ei sr e l a t e dt o i n t e r a c t i v ed i s p l a yo fc o m p l i c a t e dg e o m e t r ym o d e l o u to ft h en e e do fr e a l i t yf e e l i n go f v i r t u a ls c e n e ，t h em o d e li sm o r ec o m p l i c a t e dt h a nt h ea b i l i t yo f r e a l t i m ed r a w i n go f t h e c u r r e n th i g h q u a l i t yc o m p u t e rs y s t e m o nt h eo t h e rh a n d 、撕t 1 1t h er a p i dd e v e l o p m e n to f c o m p u t e rt e c h n o l o g yi ns e v e r a ld e c a d e s ，t h es o f t w a r ea n dh a r d w a r et e c h n o l o g yh a s b e e ni n c r e a s e di nl a r g es c a l e f o rr a i s i n gt h es o f t w a r ep o r t a b i l i t yi nt h i sn _ e n d t h e g r a p h i cd a t am o d e l sa r ei n d i c a t e db yf l o a t i n gp o i n tn u m b e r s ，t h er e l a t e dp r o c e s s i n g c a l c u l a t i o nn ol o n g e rd e m a n d si n t e g e rc o m p u t a t i o n , a l lk i n d so ft h e s i m p l i f i e d c a l c u l a t i o no f l o di sb a s e do nf l o a tc o m p u t a t i o n s o ，w h e nd e a l i n gw i t hl a r g e s c a l e3 d d a t am o d e lw eh a v ea h i g l l 一q u a l i t yr e q u i r e m e n tt ot h ec o m p u t e r h a r d w a r e t h e r e f o r e ，h o wt oi m p r o v et h ed r a w i n gs p e e do fl a r g e - s c a l ec o m p l i c a t e ds c e n ea n d t h e nr e a l i z i n gc o m p l i c a t e dd a t ar e a l t i m ei n t e r a c t i v ed i s p l a y ，h a sb e c o m et h ep r e s e n t s p o t l i g h ti nc o m p u t e rg r a p h i c s w ec a nu s cc e r t a i nt e c h n o l o g yt ob ei nc h a r g eo ft h em o d e lo ft h es c e n et og a i n i d e a lv i s u a le f f e c ta n dc o m p u t e rp r o c e s s i n g t h el o di sc o m m o n l yu s e da tp r e s e n t t h a ti st os a y ，t h e3 do b j e c t sa r ed i s p l a y e di nv a r i o u sp r e c i s i o na n dc h o o s ev a r i o u s p r e c i s i o nm o d e lt of o r mi m a g ea c c o r d i n gt ot h ep o s i t i o nv a r i a t i o no ft h ev i e w p o i n t i t c a nb es e e nt h a tt h es i m p l i f i c a t i o no f3 dc o m p l e xm o d e li so n eo ft h ek e yf a c t o r s a f f e c t i n ge n t i r ev i r t u a lr e a l i t ys y s t e m i ta l s om e a n st h a tw en e e ds i m p l i f yt h em o d e la s p o s s i b l ea sw ec a na n dd e l e t et h ev e r t e xa n d t h ef a c eo ft h em o d e lw i t h o u ta f f e c t i n gt h e g r a p h i ca c c u r a c ya n dm a k ei tr e a l - t i m ed i s p l a yi nh i g hs p e e da n dw i t h o u td i s t o r t i o n t h er e s e a r c ho ft h et h e s i si sa b o u tt h es i m p l i f i e dc a l c u l a t i o no f3 dm o d e lb a s e do n v i r t u a lr e a l i t ys y s t e m a tf i r s tm a d eao v e r a l li n t r o d u c t i o no fv i r t u a lr e a l i t ys y s t e m ， t h e ni n t r o d u c e dt h em o s tc u r r e n t l y u s e d3 dg r a p h i c sf i l e i no r d e rt om a k ee a s i e r p r o c e s s i n g ，t h ec h a p t e ra l s od e f i n e das p e c i a l3 df i l ef o r m a ta n ds u p p l yam e t h o df o r p r o c e s s a f t e r w a r d sd e s c r i b e dl o dt e c h n o l o g yi nd e t a i l sa n dg a v em o r ee m p h a s i so n e d g ec o l l a p s ea l g o r i t h m ，t h e np r o g r a m m i n ga n dg a v eat e s ta n a l y s i so ft h ep r o g r a m l a s t l yp u tf o r w a r dam o d e ls i m p l i f i e dc a l c u l a t i o nb a s e do nd e v i c ec o o r d i n a t es y s t e m a n dw i t h o u tf l o a tc o m p u t a t i o n ，t h e ng a v eat e s ta n a l y s i so f t h i sc a l c u l a t i o n k e y w o r d s ：v i r t u a lr e a l i t y l o dm e s hs i m p l i f i c a t i o ne d g ec o l l a p s e d e v i c ec o o r d i n a t es y s t e m 声明 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人 在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的 说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：右屡旌日期己0 0 7 , 譬，d本人签名：倒纽拉 日期! ! ! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论 本人签名 导师签名 年解密后适用本授权书。 日期上d 矿z o 日期妇z ：生：囟 第一章绪论 1 1 1 虚拟现实的概念 第一章绪论 1 1 虚拟现实系统简介 虚拟现实技术( v i r t u a lr e a l i t y , 简称v r ) 1 2 l ，是在2 0 世纪6 0 年代发展起来的 一门涉及到众多学科的高新技术。它集成计算机技术、传感与测量技术、仿真技 术、微电子技术于一体。近几年间，随着计算机软硬件水平的迅猛发展，新型交 互设备的不断涌现和完善、p c 机图形加速卡的性能大幅度的提高，使虚拟现实技 术的应用领域也不断的扩展。 从功能上讲，它是指用计算机图形学构造出酷似真实世界的一种仿真模拟，而 且这个合成的虚拟世界并不是静态的，它可以对用户的输入( 如手势、动作命令 等) 做出实时的响应。这里的实时响应，是指计算机能够探测到用户的输入并同 时对虚拟世界做出对应的修改。 因此，虚拟现实是一种高端的人机接口，它包括通过视觉、听觉、触觉、嗅觉 和味觉等多种感觉通道的实时模拟和实时交互。 1 1 2 v i i 建模 虚拟现实系统中的一个重要因素是虚拟世界的建模口j ，首先要建立从i o 设备 到仿真场景的映射，例如，一个传感手套可能控制着虚拟世界中的一只虚拟手， 一个h m d 跟踪器可以设置仿真视图。v r 接口映射需要编写关于用户特征和i o 通信的标准程序，这些任务通常是通过商业工具包解决的。 完成了i o 设备的映射之后，就要开发虚拟世界的对象数据库，这就意味着要 对虚拟对象的形状、外观、运动学约束、智能行为和物理特性进行建模。最后， 为了保持与仿真的实时交互，还需要在模型管理步骤中对这些模型进行优化。 对虚拟世界的建模过程一般分为以下几步：首先是通过几何建模，描述虚拟对 象的形状以及外观；然后通过运动建模确定三维对象在世界坐标系中的位置，以 及它们在虚拟世界中的运动；第三步是物理建模，综合体现对象的物理特性，包 括重量、惯性、表面硬度等：最后对于较大规模的仿真环境，还要对部分用户不 可能控制到的对象进行行为建模。 由此可见，对三维物体的几何建模是虚拟现实技术的基础。 虚拟现实中的三维模型简化技术 1 2 三维图形建模技术 三维图形建模技术主要是研究三维物体信息在机内的生成和表示，描述三维物 体信息的模型包括有几何模型、光照模型和颜色模型。 几何模型是用来描述物体在三维空间中的形状的，一般来说，几何造型是通过 对点、线、面、体等几何元素，经过平移、旋转等几何变换和并、交、差等集合 运算，产生满足设计目的的物体模型。 几何造型所涉及的基本问题，就是如何建立计算机能够处理的几何模型，以及 处理的方法。 1 2 1 传统的几何造型技术 在计算机图形学中，传统的构造几何模型的方法分为三大类l l 】：分解表示、构 造表示和边界表示。 分解表示的原理是：将形体按某种规则分解为小的更易于描述的部分，每一小 部分又可分为更小的部分，持续分解过程直至每一小部分都能够直接描述为止。 常用的分解表示方法有：空间位置枚举表示法、八叉树表示法和单元分解表示法。 构造表示是按照生成过程来定义形体的方法，通常有扫描表示、构造实体几何 表示和特征表示三种。 边界表示( b o u n d a r yr e p r e s e n t a t i o n ，简称b r 印或者b r ) 是通过描述实体的 边界来表示一个实体的方法，它是几何造型中最成熟、无二义的表示法，也是在 几何造型中得到广泛应用的一种形体表示方法。它的基本思想是通过对形体边界 的描述来定义一个形体，即是用面、环、边和点来定义形体的位置和形状。 为了描述一个形体的边界，b - - r e p 法必须详细记录构成形体的所有几何信息 和拓扑信息，以便直接存取构成形体的各个面、面的边界边以及各个顶点的定义 参数，使利于以面、边、点为基础的各种几何运算和操作。 1 2 2 虚拟现实系统中常用的造型方法 每一种造型方法都有它自己的适用范围，目前没有哪一种造型方法可以较好的 适用于所有情况。而对于虚拟现实系统中的建模问题，主要是要求能够比较真实 的重建三维世界，所以它通常有以下的要求：表示图形的覆盖域大；容易做几何 变换；便于计算物体的整体性质：能够快速绘制图形。目前最常用的方法是多边 形网格表示法。 多边形网格表示法是一种对曲面的近似表示方法，它是用一系列彼此相连的平 第一章绪论 面多边形来近似的表示物体弯曲的表面，属于一种边界表示。 多边形网格是由顶点和边构成的集合。集合中的多边形彼此相连，每条边属于 两个多边形，连接两个顶点，一个闭合的边序列构成一个多边形。 根据不同的应用需要，多边形网格表示法也分为很多种，比较常用的有：直接 表示、顶点表指针表示和边表指针表示。 、直接表示法： 直接表示法是对多边形网格中的每一个多边形建立一个顶点坐标序列。 p = ( ( 而，m ，毛) ，( 屯，y 2 ，z 2 ) ，( 矗，乙) ) 公式( 1 - 1 ) 这些顶点按照沿多边形一周的顺序被存储，相邻两个顶点以及头尾顶点之间都 包含一条边。 这种表示方式对于网格来说，公共顶点重复存储，浪费了大量空间；而且公共 顶点和公共边都没有显式的表示出来，不利于图形的操作。 二、顶点表指针表示法： 顶点表指针表示法是使用顶点表指针来定义多边形。多边形网格中的所有顶点 在顶点序列中被存储一次。 矿= ( ( 而，y j ，毛) ，( x 2 ，y 2 ，z 2 ) ，( 矗，乙” 公式( 1 - 2 ) 再用一个指向这个顶点序列的索引表来定义多边形。如图1 1 ： v 1 v = ( ( x l ，y l ，zj ) ，( x2 ，y 2 ，z2 ) ， ( 工3 ，y 3 ，z3 ) ，( 石4 ，y 4 ，z4 ) ) p l = ( 1 , 2 ，4 ) v 3 p 2 = ( 4 ，2 ，3 ) 图1 1 顶点指针表示法 三、边表指针表示法： 边表指针表示法中，多边形网格的所有顶点存储于一个顶点序列；所有的边存 储于一个边序列。在边序列中，每条边只出现一次，包含该边的两个顶点及该边 所属的两个多边形。 在这种表示法中，多边形是由一个边表指针定义的，只向边序列中的对应元素。 如图1 2 ： 虚拟现实中的三维模型简化技术 v 1 v 2 以 v = ( ( x l ，咒，z 1 ) ，( 工2 ，y 2 ，z 2 ) ， ，( b ，乃，z 3 ) ，( 矗，几，z 4 ) ) 毛= ( ，k ，鼻，) v 3 只= ( 巨，巨，e ) 图i 2 边表指针表示法 1 3l o d 技术榻i 述 在开发虚拟现实系统的时候，往往场景中会用到大量的三维模型，这些模型可 能是从不同的渠道获取，其中很多都是非常复杂的。如果内存不能够满足这些模 型的大存储容量需求，就不得不牺牲时间拉进行存储交换。这样，整个系统的实 时交互性能就会下降。 为了要获得理想的视觉效果和计算机处理速度，使用一定的技术对场景中的模 型进行管理就显得非常重要。常用的技术有：单元分割法、l o d 技术、脱线预计 算以及内存管理技术。通过这些技术来对模型进行管理，可以提高系统运行的实 时性。 在复杂模型的动态显示过程中，当观察点距离某一物体很近的时候，该物体的 模型将在屏幕上占据较多的像素点；而当观察点距离该物体很远的时候，它的模 型在屏幕上只占据很少的像素点。在这种情况下，用大量的多边形面片去精确的 表示该物体是不必要的。为了更好地实现三维复杂模型的实时动态显示，将三维 物体用多种不同的精度表示( 例如用精确模型和简化模型两种) ，并且根据观察点 位置变化而选择不同精度的模型予以成像，就成为非常有效的手段。这种方法通 常称为细节层次( l e v e lo f d e t a i l s ，l o d ) 技术【8 】o 1 4 课题的提出 在开发一个大型虚拟现实系统的时候，要想让虚拟场景能够逼真，就需要大量 的物体模型，这些模型全部依靠编写程序来生成是不现实的，通常都是将来自其 他渠道的模型素材添加到场景中。这些素材可能是由3 d ss t u d i om a x 之类的软件 绘制出来的，也可能是由三维扫描仪扫描得到的，他们本身往往并不是针对我们 第一章绪论 5 的三维场景专门设计的，而是一些精度很高，很复杂的模型文件。 如果直接将这些模型文件读入，并且在三位场景中成像，可能会浪费大量的系 统资源，甚至使整个虚拟现实系统的实时交互成为不可能。 为了解决这一问题，使用l o d 技术来对准备添加到场景中的模型进行简化是 一种常用的有效方法。 本论文所讨论的基本算法是l o d 技术中的“边折叠算法”。该算法能够产生 很好的简化结果，具有高效通用的特点，是目前广泛使用的简化算法之一。但是 在使用此类算法进行模型简化的时候，为了要保证模型不失真，在简化前要先建 立很复杂的数据结构，而且每删除掉一条边都要进行大量的计算。简化处理所需 的时间会随着模型复杂度的提高而大幅度增长。 理论上讲，这一步是必不可少的。要想真实的重现一个三维物体，表面比较复 杂的区域，多边形面片的密度就要大些；而表面比较光滑的区域，多边形面片的 密度可以小一些。所以，在进行模型简化的过程中，判断某条边是否可以删除一 定要进行复杂的计算。 但是在实际应用当中，由于我们使用的三维物体模型来自不同的渠道，其中可 能包含了大量的冗余信息： 第一，目前许多常用的三维绘图软件都是使用曲面模型来绘制和描述物体的， 将绘制好的模型导出成多边形网格模型的时候往往会有大量的冗余信息。 第二，某些物体不是为了虚拟现实系统的应用而设计的，模型本身精度极高， 而我们的虚拟场景要在屏幕上显示，分辨率却相差甚远。将模型放到的虚拟场景 中，大部分三角形的面积是小于一个像素的。这种情况，我们要删除三角形或者 删除边，可以不必去考虑区域的复杂度，直接删除。因为一条边的边长本身小于 一个像素，那么将这条边压缩为一个像素点，不会对生成三维图像的精度有任何 影响。 因此，对于这些三维模型，在进行l o d 技术简化之前，可以根据显示分辨率先 作一个预处理，将冗余信息剔除掉。例如可以先将模型中边长小于一个像素的边 删除掉，将相关的顶点合并。这样，在进行便折叠简化的时候，物体复杂度已经 大幅度降低，处理时间就可以减少。 6 虚拟现实中的三维模型简化技术 第二章外部三维模型的输入 在构造虚拟场景的过程中，对于规则物体可以通过编写程序代码来直接生 成；对于简单得不规则物体模型，可以将模型的数据直接写在程序中；而对于大 多数复杂的不规则物体，则需要从外部文件中读取。因此一般的虚拟现实系统中 都是通过读取外部文件来绘制物体模型的。 2 1 常用的3 d 文件格式 2 1 1 常用3 d 文件格式简介 随着计算机软硬件和3 d 图形技术的发展，形成了非常多的3 d 文件格式嗍， 其中比较常见的有以下几种： 1 、3 d s 文件格式： 3 d s 文件是由3 ds t u d i o m a x 开发出来的三维图形文件。3 ds t u d i o 是a u t o d e s k 公司开发的一套用于在微机上制作三维动画的应用程序，它的功能非常强大，许 多精美的电视广告都使用它制作的。 由于3 d s 是一种非常普遍的数据格式，以3 d s 格式保存的三维图形文件非常 丰富。各种三维图形素材光盘以及内容丰富的网上图形站点，都有非常丰富的3 d s 模型库。在微机上直接利用3 ds t u d i o 软件制作3 d s 格式的三维图形文件也非常容 易。 2 、o b j 文件格式： w a v e f r o n to b j 文件定义了三维物体的几何特性和其他的一些特性，由于文件 结构非常简单，因此适合在应用程序中读取或进行3 d 文件格式转换。w a v e f r o n t 的模型文件可以是a s c i i 格式( o b j ) ，也可以是二进制格式( m o d ) ，它不仅可 以定义多边形模型，也可以定义自由曲面模型。 3 、a s e 文件格式： a s e 文件是指3 ds t u d i o m a x a s c i i e x p o r t 输出文件，它是以文本的形式保存 了3 d 模型的所有信息。这种文件的好处是易于读取，也非常容易修改，只需一般 的文本编辑软件，如写字板，记事本等即可。但是这种文本文件一般非常大，读 入的时间比较长，对它支持的软件较少，即便是3 ds t u d i om a x 软件本身也不能 直接输入a s e 格式的文件。如果需要使用a s e 格式的文件，必须通过三方工具软 件进行转换。 第二章外部三维模型的输入 4 、m d 2 m d 3 文件格式： q u a k e 2 和q u a k e 3 模型格式由著名游戏公司i d 公司自主设计，广泛应用于i d 公司开发的各种三维游戏中，其文件扩展名分别为m d 2 和m d 3 。由于这两种模 型的文件格式相对比较简单，在其他的一些三维图形程序中也逐步得到了广泛应 用。 5 、m s 3 d 文件格式： m i l k s h a p e 3 d 是一个多边形建模工具，最初是为h a l f - l i f e 软件设计，在后来的 发展过程中，逐渐加入了其他格式的三维模型的输入输出功能。m i l k s h a p e 3 d 目前 支持来自2 7 种游戏程序共约3 7 种不同格式文件的输入与输出功能。 6 、w r l 文件格式： 用于在i n t e m e = t 上传输三维图形，如a u t o c a d ( d x f ) 格式。 7 、p l y 文件格式： 是a n i m a t o rp r o 创建的一种图形文件格式，其中包含用来描述多边形的一系列 点的信息。 在这些三维数据文件中，w r l 和p l y 文件格式比较简单，适合用来绘制三维 复杂物体的网格模型。 本论文中所使用的三维模型都使用p l y 文件来存贮的，处理过程中的演示和 测试则是基于w r l 格式。 2 1 2p l y 文件格式的介绍 p l y 文件是最简单的描述了多边形的一系列点的信息的外部三维数据文件格 式，因此最适宜用于网格模型的绘制。p l y 文件所描述的三维数据信息包括顶点 数据信息( 主要指顶点的几何坐标) ；还包括多边形的面信息( 一般是三角形的一 些信息) 。典型的p l y 文件结构如图2 1 ： 文件头 顶点表 多边形表 图2 i p l y 文件结构 头部是一系列以回车结尾的文本行，用来描述文件的剩余部分。头部包含一个 虚拟现实中的三维模型简化技术 对每个元素类型的描述，包括元素名( 如“顶点”) ，这个元素在工程里有多少， 以及一个与这个元素关联的不同属性的列表。头部还说明这个文件是二进制的或 者是a s c i i 的。头部后面的是每种元素类型的元素列表，按照在头部中描述的顺 序出现。 下面是一个立方体的完整a s c i i 描述。相同的二进制版本头部的唯一不同是用 词“b i n a r y _ l i t t l e _ e n d i a n ”或者“b i n a r y _ b i g _ e n d i a n ”来替换词“a s c i i ”。大括号中的 注释不是文件的一部分，它们是这个例子的注解。文件中的注释一般在“c o n m a e n t ” 开始的关键词定义行里。 p l y f o r m a ta s c i i1 0 ( 文件格式和版本 c o m m e n tm a d eb ya n o n y m o u s 注释行) c o m m e n tt h i sf i l ei sac u b e e l e m e n tv e r t e x8 定义“v e r t e x ”( 顶点) 元素，在文件中有8 个l p r o p e r t yf l o a g 2x 顶点包含浮点坐标“x ”) p r o p e r t yf l o a g 2y 顶点包含浮点坐标“y ”) p r o p e r t yf l o a t 3 2z 顶点包含浮点坐标“z ”) e l e m e n tf a c e6 在文件里有6 个“f a c e ”( 面片) p r o p e r t yl i s tu i n t 8i n t 3 2v e r t e x _ i n d e x v e r t e x _ i n d i c e s ”( 顶点素引) 一列整数l e n d h e a d e r 文件头部结束) 00 0 顶点列表的开始 oo1 01 l 01o lo o l0l l 1 l 11o 40l23 面片列表开始 47654 40 451 4156 2 42 673 437 4 0 这个例子说明头部的基本组成。头部的每个部分都是以一个关键词开头以回车 结尾的a s c i i 串。即使是头部的开始标记“p l y ”和结尾标记“e n d h e a d e r ”也是 第二章外部三维模型的输入 9 以这种形式。 一般元素以下面的格式描述： e l e m e n t p r o p e r t y p r o p e r t y 数据类型 p r o p e r t y 属性罗列在“e l e m e n t ”( 元素) 行后面定义，既包含属性的数据类型也包含属 性在每个元素中出现的次序。一个属性可以有三种数据类型：标量，字符串和列 表。属性可能具有的标量数据类型如表2 1 所示： 名称类型 字节数 j n t 8 字符 1 u i n t 8 无符号字符 1 i n t l 6 短整型 2 u i n t l 6 无符号短整型 2 i n t 3 2整型 4 u i n t 3 2无符号整型 4 f l o a t 3 2 单精度浮点数 4 f l o a t 6 4 双精度浮点数 8 表2 1p l y 文件元素的数据类型 使用列表数据类型的属性定义有一种特殊的格式： p r o p e r t yl i s t 这种格式的一类例子是上面的立方体文件中的： p r o p e r t yl i s tu i n t 8 i n t 3 2v e r t e x _ i n d e x 这表示属性“v e r t e xi n d e x ”首先包含一个非负字符表示在属性里包含多少个 索引，接下来是一个列表包含若干整数，其个数等于前面指定的索引个数。在这 个列表里的每个整数都是一个顶点的索引。 以下再列出一个复杂点的例子，也是一个立方体定义： p l y f o r m a ta s c i i1 o c o m m e n ta u t h o r ：a n o n y m o u s c o m m e n to b j e c t ：a n o t h e rc u b e e l e m e n tv e r t e x8 上l 一壅垫翌壅! 竺三丝堡型堕些垫查 p r o p e r t yf l o a t 3 2x p r o p e r t yf l o a t 3 2y p r o p e r t yf l o a t 3 2z p r o p e r t yr e du i n t 8 顶点颜色的r 分量 p r o p e r t yg r e e nu i n t 8 顶点颜色的g 分量1 p r o p e r t yb l u eu i n t 8 顶点颜色的b 分量l e l e m e n tf a c e7 p r o p e r t yl i s tu i n t 8i n t 3 2v e r t e x _ i n d e x e l e m e n te d g e5 模型里面有5 条边， p r o p e r t yi n t 3 2v e r t e x l p r o p e r t yj n t 3 2v e r t e x 2 p r o p e r t yu i n t 8r e d p r o p e r t yu i n t 8g r e e n p r o p e r t yu i m 8b l u e e n dh e a d e r 边的第一个顶点的索引， 第二个项点的索引 边颜色的r 分量， 00 0 2 5 500 ( 顶点列表开始 00 12 5 500 0l l2 5 500 0 10 2 5 500 l0 0002 5 5 1010 0 2 5 5 1 1 10 0 2 5 5 1 l0 002 5 5 30l2 面片列表开始，三角形l 30 23 47 6 54 f 四边形 40 45 1 4156 2 4 2673 437 40 0 l2 5 5 2 5 52 5 5 f 边列表开始， 12 2 5 52 5 52 5 5 23 2 5 52 5 5 2 5 5 30 2 5 52 5 5 2 5 5 20 000 第二章外部三维模型的输入 这个文件为每个顶点指定一个颜色值，有红、绿、蓝三色分量表示。为了说明 变长v e r t e xi n d e x ( 顶点索引) 的能力，物体的头两个面片是两个三角形而不是一 个四边形。这意味着物体的面片数是7 。这个物体还包括一个边列表。每条边包括 两个指向说明边的顶点的指针。每条边也有一种颜色。上面定义的五条边指定了 颜色，使文件里的两个三角形高亮。前四条边白色，它们包围两个三角形。最后 一条边是黑的，他是分割三角形的边。 上面的例子显示了顶点、面片和边三种元素的用法。p l y 格式同样允许用户 定义它们自己的元素。定义新元素的格式于顶点、面片和边相同。由于本论文主 要是对外来的p l y 模型文件做处理，所以这部分内容不做研究。 2 1 3w r l 文件格式与v r m l 语言简介 有关w r l 各式的资源非常多，w r l 格式现在成为网上虚拟现实的一种标准 的文件格式，它是使用v r m l 语言描述的文本文件，各式非常简单。 v r m l 语言是一种与互联网结合，用来描述三维交互世界的程序语言，可应用 于创建虚拟现实的对象、景象和展示模型等。通过浏览器，互联网的用户可以欣 赏到由v r m l 创建的三维虚拟现实，而不再只是二维的平面图形或图像。 只要在计算机上安装了支持v r m l 的浏览器( 如c o s m op l a y e r 等) ，就可以直 接显示w r l 各式的模型文件。另外，由于w r l 的文件格式是一般文本文件，所 以基本上使用任何的纯文本编辑器都可以进行编辑。由p a r a l l e i g r a p h i c s 公司开发 的名为v r m l p a d 的v r m l 编辑器，是一个使用起来比较方便的编辑器，具有强大 的程序编写辅助功能。 由于v r m l 属于一种编程语言，它具有比较强大的三维建模功能和相对比较 复杂的语法，所以w i l l 文件的格式不可能简单的进行统一描述。在本论文中， w r l 文件是用来输出并进行演示，而非读取数据，所以不必去详细研究v r m l 语 法，只要给出一种统一的格式作为模板即可。 以下就是在在本论文中使用的w r l 文件格式： # v r m lv 2 0u t t 8 v r m l 文件头，必须位于第一行 s h a p e a p p e a r a n c ea p p e a r a n c e f 定义一个造型节点 m a t e r i a lm a t e r i a l ，定义物体的材质 d i f f u s e c o l o r0 50 30 0 a m b i e n t i n t e n s i t yo 4 0 s p e c u l a r c o l o r0 70 70 7 s h i n i i l e s s0 2 虚拟现实中的三维模型简化技术 ) ) g e o m e t r yl n d e x e d f a c e s e t 用面造型的方式定义物体几何形状 e o o r dc o o r d i n a t e p o i n t 顶点序列 这里是各顶点的坐标值，每个项点对应三个坐标值 】 ) c o o r d l n d e x 多边形序列 每个多边形用其各顶点的索引序列表示，以1 作为面的结束标志 】 ) ) 上例是使用v r m l 语言中的“几何面造型”方法来描述三维物体的几何模型。 采用这种方法是为了和我们的数据来源p l y 文件格式相对应。其中顶点序列是所 有顶点的三维坐标值，可以直接从数据源中获取；多边形序列中的每个多边形， 是通过该多边形的各个顶点的索引值来表示的，以1 作为该多边形的结束标志。 前面还定义了一个m a t e r i a l 节点，指定物体的材质为黄金，这与数据源无关，只是 为了最终结果显示出来能比较清楚直观。 2 l 4p l y 文件与v r m l 文件的转换 本文中用来测试算法的的三维模型均选用p l y 文件。要测试一种模型简化算 法，除了要测试其运行的效率之外，还应该将处理前后的显示效果作一个对比， 看其是否失真。由于p l y 格式并非目前计算机操作系统能够识别的文件格式，所 以无法直接在操作系统下显示出来。要想得到原始p l y 文件的显示效果，一般需 要借助第三方工具。 由于w r l 格式的文件是采用v r m l 语言描述的文本文件，其数据格式与p l y 文件格式有相似性，而w r l 格式的文件可以直接在操作系统的的浏览器中显示。 所以，可以编写一个简单的小程序，将p l y 文件转换为w r l 格式后，在浏览器 中显示预览。 另外，本论文研究的是网格模型的简化，并未涉及到颜色与光照问题，所以为 了方便格式转换，可以将p l y 中原有的颜色等无关信息全部剔出掉，只保留顶点 第二章外部三维模型的输入 集与面集。输出到w r l 文件中后，另外定义一个统一的材质模型来进行显示。 此程序非常简单，在论文中不作详细说明，程序清单可参见附录a 。 2 2p l y 文件的读取 本论文中对模型的建立和简化运算都是使用j a v a 语言来实现的，因为j a v a 语 言具有纯面向对象的特性。但是直接用j a v a 语言从p l y 文件或者w r l 文件中读 取数据都很不方便。因为j a v a 语言在处理文本格式描述的数据文件上有很多不足 之处，而p l y 文件和w r l 文件中的数据都使用文本格式描述的；另外，许多p l y 文件都非常的大，直接用j a v a 3 d 来显示该模型往往会导致内存溢出。 因此，本文在读取外部文件时，自定义了一种二进制数据文件格式d a ：r 格式，先用c 语言编写一个专用的格式转换程序，将p l y 文件转换为这种格式。 然后用j a v a 语言从d a t 格式文件中读取图形信息，建立相关数据结构，进行模型 简化。最后将处理完的结果输出为w r l 格式，利用m 浏览器来观察结果。 2 2 1d a t 文件格式的定义 d a t 格式是针对本论文自定义的一种专用的二进制数据文件格式，如图2 2 ： i n t ： h a t ： f l o a t ： f l o a t ： i n t ： 1 n l ： 顶点数 三角形数 顶点x 坐标顶点y 坐标顶点z 坐标 顶点x 坐标顶点y 坐标顶点z 坐标 三角形顶点三角形顶点三角形顶点 三角形项点三角形顶点三角形顶点 图2 2 d a t 文件结构 文件中每4 个字节为一个单元，第一个单元是一个3 2 位整数v ，表示三维物 体模型中的顶点个数：第二个单元是一个3 2 位整数f ，表示三维物体模型中的三 角形个数；从第三个单元开始，往后3 v 个单元用来存储模型中的顶点，每个单元 都是3 2 位浮点数，存储顶点的一个坐标值，每三个单元存储一个顶点；再往后一 虚拟现实中的三维模型简化技术 直到文件结束，共3 f 个单元用来存储三角形，每个单元都是3 2 位整数，存储三 角形中一个顶点在顶点表中的序号，每三个单元存储一个三角形。 文件的大小应为：( ( v + f ) x3 + 2 ) x 4 v 字节，可根据头八个字节的数值与文件长 度来进行正确性验证。 2 2 2 从p l y 到d a t 的转换 直接用j a v a 语言从p l y 文件中读取数据非常复杂，且会影响整个算法的效率。 因此，本论文在读取数据之前先用c 语言编写一个专用的格式转换程序，将p l y 文件转换为前面定得d a t 格式，然后再用j a v a 语言从d a t 文件中读取数据。 由于p l y 文件是采用文本格式描述的数据文件，信息和数据之间使用空格作 为分隔符，因此可用c 语言的f s e a n f 函数进行读取。 具体处理过程如下： 第一步，从文件头开始按顺序查找字符串”v e r t e x ”，则下一个字符串就是顶点 数v ，以3 2 位整数的格式读入下一个字符串： 第二步，统计一下头部信息当中包含了多少个”p r o p e r t y ”