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