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

多分辨率造型及其在虚拟现实中的应用石教英浙江大学CAD&CG国家重点实验室概要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的细分MRBSPTree([0，Emax])[0，E0][E0，E1]Sub-MRBSPTree0[En-2，En-1]Sub-MRBSPTree1Sub-MRBSPTreen-1(7)MRBSP树的构造算法Step1:把[0，Emax]按指数规律分成m个子集E[i],并且初始化三角形集合TS[i]=.Step2:对每个三角形TMRM,如果life(T)∩E[i],则TS[i]=TS[i]{T}.Step3:对每个三角形集合TS[i],i[1..m],循环地做Step4–8来构造和TS[i]相关的MRBSP子树MRBSP[i];Step4:如果TS[i],则令TS=TS[i].Step5:如果TS,则从TS中选择一个分割平面P..Step6:对每个三角形FTS[i],根据平面P判断F,如果F在P上,则把F插入当前的根节点;如果F整个地位于平面P的一侧,则把F插入它所在的一侧的子集.Step7:如果F跨越平面P,则它应当被分为两个或更多的部分，并把每部分插入到该部分所在的一侧对应的子集.Step8:通过为两个子集列表做Step5-8来递归地构造MRBSP[i]的MRBSP树.当MRBSP[i]构造完成,转到Step3做下一个三角形集合.Step9:输出MRBSP树集合.(8)实验结果Table:多个MRBSP树子分的统计结果子分层次构造时间(ms)MRBSP节点绘制时间(ms)LoD1LoD2LoD3LoD4LoD5113,28026,8369090857565213,93020,306707065600313,42914,46460504500410,6366,9302520600------------------LoD1:180triLoD2:120triLoD3:60triLoD4:25triLoD5:10triTable：传统BSP树和MRBSP树的比较BSP类型Model三角形数目构造时间绘制时间运行时间Molecular7344336,343280336,623Fish628090,10012090,220传统Cow580457,08213057,212BSP树Angel22327,350407390Sphere16801,012301,042Head13557,711507,760MRBSP树Molecular31658995,311741741Fish270391198,714290290Cow25085497,660290290Angel9555107,405120120Sphere7225681,8318080Head5779137,437180180Table:使用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)1801601207020Fig.我们的多分辨率造型系统的用户界面Fig:用我们的多分辨率造型系统生成的LoD模型Fig:用我们的多分辨率造型系统生成的LoD模型Fig:我们的多分辨率造型系统的连续LoD模型Fig:场景中有多个物体Fig:场景中有多个物体4.结论和将来的工作4.1我们VR小组的其它研究工作*基于几何和图象简化的实时绘制*全可逆累进网格(FRPM)*基于静态和动态LoD的混合绘制*LoD模型间的变形和插值*协同CAD中LoD和PM的应用4.2将来的工作FutureWorks*复合场景的动态绘制(几何物体，地形数据，体数据，视频，动画，图象).*并行动态简化*把LoD集成到限时绘制中*网格水印致谢•国家自然科学基金委员会•我们VR小组的成员周昆陶志良张明敏成迟薏肖丹杨孟舟