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

多分辨率外型及其在虚拟现实中的运用

概要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) 272 13.43 6.76

terrain(8192) 1872 29.85 11.86

bunny(69473) 2306 1777.18 332.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: 对每个三角形TMRM,假设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: 对每个三角形FTS[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) LoD1LoD2LoD3LoD4 LoD5 1 13,280 26,836 90 90 85 75 65 2 13,930 20,306 70 70 65 60 0 3 13,429 14,464 60 50 45 0 0 4 10,636 6,930 25 20 6 0 0 ------------------LoD1:180tri LoD2:120triLoD3:60tri LoD4:25triLoD5:10tri Table：传统BSP树和MRBSP树的比较

BSP类型Model 三角形数目构造时间 绘制时间运转时间 Molecular 7344 336,343 280 336,623 Fish 6280 90,100 120 90,220 传统Cow 5804 57,082 130 57,212 BSP树 Angel 2232 7,350 40 7390 Sphere 1680 1,012 30 1,042 Head 5 7,711 50 7,760 MRBSP树Molecular 31658 995,311 741 741 Fish 27039 1198,714 290 290 Cow 25085 497,660 290 290 Angel 9555 107,405 120 120 Sphere 7225 681,831 80 80 Head 5779 ,437 180 180 Table:运用MRBSP树多个LoD模型的绘制时间

模型 参数 层次(b)层次(c)层次(d)层次(e)层次(f)Molecular三角形数目 7344 3938 1822 800 364 model绘制时间(ms) 741 540 330 150 120 Fish 三角形数目 6280 3126 1488 624 266 绘制时间(ms) 290 240 230 150 70 Cow 三角形数目 5792 3224 1586 682 292