多分辨率造型及其在虚拟现实中应用

多分辨率造型及其在虚拟现实中的应用,概要,1.背景介绍1.1什么是多分辨率模型1.2为什么多分辨率模型有用1.3多细节层次模型/多分辨率模型1.4多分辨率模型的应用2.多分辨率造型简述3.我们VR小组的一些研究4.结论,1背景介绍,1.1什么是多分辨率模型(1)两种含义:*网格的一种紧凑表示，从这种表示可以得到任意分辨率的模型*一组不同细节层次(levelofdetail,简称LoD)的模型(2)特点*紧凑表示/网格压缩*LoD模型间的连续过渡,例子(3166,1769,839个三角形),1.2为什么多分辨率模型有用?,(1)多边形的表示*多边形是计算机图形学中最普遍的元素*特定的硬件能快速绘制多边形*多边形可以近似地表示任何模型(2)问题*表示复杂模型需要大量多边形*高端图形系统每秒能绘制1M多边形*交互应用一般需要30fps的帧速率*图形硬件很难跟上模型复杂度的增长,1.2为什么多分辨模型有用?,(3)多分辨率模型*减少模型复杂度和硬件性能之间的矛盾*支持实时绘制和交互*增加增强式计算问题的效率辐射度计算光线跟踪碰撞检测复杂可视化仿真,1.3多细节层次模型/多分辨率模型,(1)LoD(a)使用不同的LoD来表示原始模型(b)选择标准:*距离*运动*在视窗中的位置*投影在屏幕上的大小(2)LoD模型和多分辨率模型间的差别*离散/连续*一组模型/紧凑表示,1.4多分辨率模型的应用,(1)CG,CAD和VR/VE(2)GIS(geographicsinformationsystem)(3)通用仿真(飞行模拟)(4)交互式ViSC(5)分布式VR/协同设计,2.多分率造型简述2.1多分辨率造型方法,*基于小波的方法M.Eck-etal.95*基于网格简化的方法(1)多分辨率小波造型方法两步:(a)构造基网格(b)细分基网格构造新网格,多分辨率造型方法,(2)基于网格简化的方法构造连续LoD模型，相邻两个细节层次模型间的差别就是一次简化操作.典型的例子:*累进网格(PM)H.Hoppe96*粘合多分辨率模型(GMM)A.Ciampalini98*多分辨率模型(MRM)Pan99,多分辨率造型方法,(3)PM(a)基本思想(b)PM的用途*有效地生成LoD*支持累进传输*网格压缩(4)GMM(a)基本思想(b)限制:不能处理由单独分离的物体组成的场景,2.2网格简化技术*近平面合并*重新划分*顶点/边/面删除*顶点聚类*边/三角形折叠.,3我们VR小组的一些研究结果,3.1改进的网格简化和PM生成方法(1)基本思想*使用三角形折叠操作*采用二次误差矩阵(2)特点*大大简化原始模型*支持PM的构造,Fig.边折叠,Fig.三角形折叠,(3)算法框架,Step1:计算每个三角形的误差矩阵.Step2:对每个三角形，根据误差矩阵计算折叠生成顶点的位置并计算由此带来的误差.Step3:根据折叠误差按升序排列所有的三角形为一队列.Step4:取出三角形队列中的第一个三角形执行折叠操作，更新相应的信息.Step5:如果三角形队列为空或误差要求已经达到，则转Step6，否则转Step4.Step6:结束,(4)构造基于三角形折叠的PM(5)实验结果Table1我们算法和Garland算法运行时间的对比-原模型(tri.)简化模型(tri.)Garland算法(s)我们的算法(s)-surface(5000)27213.436.76terrain(8192)187229.8511.86bunny(69473)23061777.18332.10-,FigLoD模型(2892,1079,493,220个三角形),FigLoD模型(16629,6464,3079,634个三角形),FigLoD模型(3760,1842,734个三角形),3.2多分辨率BSP(MSRBSP)树和多分辨率造型系统,(1)基本思想和特点*集成BSP树和LoD来支持实时绘制*在预处理过程中为整个LoD模型生成一个MRBSP树*当LoD模型被替换时，不需要重建MRBSP树.*保持了传统BSP树的优点*根据视点生成动态的LoD模型*MRBSP支持LoD模型间的平滑过渡,(2)相关工作Wileyetal.1997提出了一种把LoD模型结合到修改了的BSP树中的方法.局限:(a)使用静态LoD模型(b)跳跃式增长(3)多分辨率模型表示(MRM)*MRM可以被当作GMM模型的树.*MRM用边折叠算法生成,(4)MRM生成算法:,Step1:输入原网格M,初始化顶点，边，三角形和MRM的数据结构;Step2:对每条边计算其折叠后的误差，并根据生成一个边队列;Step3:取出边队列中的第一条边e，折叠e并把新生成的顶点和三角形插入MRM，同时修改MRM中相关三角形的出生误差和死亡误差;Step4:根据更新的误差重新排列边队列，如果边队列非空则转Step3;Step5:输出MRM.,(5)MRBSP树的表示,在3D几何空间(x,y,z)中,MRBSP树可以表示为包含几何空间(x,y,z)和分辨率参数t的4D空间中的元组.假设传统BSP树有形式bspfi,那么我们的MRBSP可以描述如下:mrbspf(t)=1(t)bspf1+2(t)bspf2+m-1(t)bspfm-1+m(t)bspfm(1)Wheret=1,2,m,and:j(t)=1ift=j(2),(6)MRBSP树的细分,*为了加速MRBSP树的构造和绘制过程，我们根据模型误差把MRM分成几个子MRM，并为每个子MRM构造子MRBSP树.*MRM中的每个面都有生命期birth_time,death_time，并且MRM中所有面的生命期的总和就是LoD模型的分辨率0，Emax.,Fig.MRBSP的细分,(7)MRBSP树的构造算法,Step1:把0，Emax按指数规律分成m个子集Ei,并且初始化三角形集合TSi=.Step2:对每个三角形TMRM,如果life(T)Ei,则TSi=TSiT.Step3:对每个三角形集合TSi,i1.m,循环地做Step48来构造和TSi相关的MRBSP子树MRBSPi;Step4:如果TSi,则令TS=TSi.Step5:如果TS,则从TS中选择一个分割平面P.,.,Step6:对每个三角形FTSi,根据平面P判断F,如果F在P上,则把F插入当前的根节点;如果F整个地位于平面P的一侧,则把F插入它所在的一侧的子集.Step7:如果F跨越平面P,则它应当被分为两个或更多的部分，并把每部分插入到该部分所在的一侧对应的子集.Step8:通过为两个子集列表做Step5-8来递归地构造MRBSPi的MRBSP树.当MRBSPi构造完成,转到Step3做下一个三角形集合.Step9:输出MRBSP树集合.,(8)实验结果,Table:多个MRBSP树子分的统计结果子分层次构造时间(ms)MRBSP节点绘制时间(ms)LoD1LoD2LoD3LoD4LoD5113,28026,8369090857565213,93020,306707065600313,42914,46460504500410,6366,9302520600-LoD1:180triLoD2:120triLoD3:60triLoD4:25triLoD5:10tri,Table：传统BSP树和MRBSP树的比较,BSP类型Model三角形数目构造时间绘制时间运行时间Molecular7344336,343280336,623Fish628090,10012090,220传统Cow580457,08213057,212BSP树Angel22327,350407390Sphere16801,012301,042Head13557,711507,760MRBSP树Molecular31658995,311741741Fish270391198,714290290Cow25085497,660290290Angel9555107,405120120Sphere7225681,8318080Head5779137,437180180,Table:使用MRBSP树多个LoD模型的绘制时间,模型参数层次(b)层次(c)层次(d)层次(e)层次(f)Molecular三角形数目734439381822800364model绘制时间(ms)741540330150120Fish三角形数目628031261488624266绘制时间(ms)29024023015070Cow三角形数目579232241586682292绘制时间(ms)29025022015075Angel三角形数目2232122658424694绘制时间(ms)1201101107030Sphere三角形数目168084042219284绘制时间(ms)8068502720Head三角形数目135587541217371绘制时间(ms)1801601207020,Fig.我们的多分辨率造型系统的用户界面,Fig:用我们的多分辨率造型系统生成的LoD模型,Fig:用我们的多分辨率造型系统生成的LoD模型,Fig:我们的多分辨率造型系统的连续LoD模型,Fig:场景中