VR04多细节层次模型生成和绘制.课件.ppt

1、计算机科学系计算机科学系2009，5第2页第4章 多细节层次模型生成和绘制4.1简介简介 4.2基本概念基本概念4.3 网格简化算法网格简化算法4.4 多分辨率模型生成算法多分辨率模型生成算法4.5 实时连续实时连续LOD模型绘制模型绘制4.6 地形实时绘制地形实时绘制第3页第4章 多细节层次模型生成和绘制n细节层次细节层次LOD（Level of Detail） 1976年年Clark提出提出 指对同一场景或场景中的物体，使用具有不同细指对同一场景或场景中的物体，使用具有不同细节的描述方法得到一组模型，供绘制时选择使用节的描述方法得到一组模型，供绘制时选择使用 目的是减少模型的多边形个数，提

2、高绘制速度目的是减少模型的多边形个数，提高绘制速度 广泛应用于复杂场景快速绘制、飞行模拟器、广泛应用于复杂场景快速绘制、飞行模拟器、3D动画、虚拟现实等系统动画、虚拟现实等系统第4页第4章 多细节层次模型生成和绘制nLOD方法的基本思想方法的基本思想 不同的物体或物体的不同部分采用不同的细节不同的物体或物体的不同部分采用不同的细节 绘制时，如果物体离视点比较远，或者物体比绘制时，如果物体离视点比较远，或者物体比较小，可以用较粗的较小，可以用较粗的LOD模型绘制，反之用较模型绘制，反之用较细的模型绘制细的模型绘制 同样，对运动快的物体用较粗的同样，对运动快的物体用较粗的LOD模型绘制模型绘制，反

3、之用较细的模型绘制，反之用较细的模型绘制第5页第4章 多细节层次模型生成和绘制n误差度量误差度量 如何生成不同细节的模型如何生成不同细节的模型n局部误差局部误差 距离误差计算距离误差计算 曲率误差计算曲率误差计算)()(zEzD22222222)/()/(2)/(yZyxZxZ第6页第4章 多细节层次模型生成和绘制n全局误差全局误差 计算法计算法 具有较好的近似效果，但计算量大具有较好的近似效果，但计算量大 一般用法一般用法简化过程中，删除的顶点具有尽量小的全局误差简化过程中，删除的顶点具有尽量小的全局误差精化过程中，增加的顶点具有尽量大的全局误差精化过程中，增加的顶点具有尽量大的全局误差yx

4、yxZyxZ,),( ),(第7页第4章 多细节层次模型生成和绘制n简化操作简化操作 指在网格模型简化过程中使用到的基本操作指在网格模型简化过程中使用到的基本操作 包括包括 顶点删除：把三角形中不重要的顶点删去顶点删除：把三角形中不重要的顶点删去 三角形删除：若三角形的面积小于某个值，移去三角形删除：若三角形的面积小于某个值，移去顶点删除顶点删除三角形删除三角形删除第8页第4章 多细节层次模型生成和绘制n简化操作简化操作 包括（续）包括（续） 边折叠：把边折叠成一个新点，并把与边相连的点连边折叠：把边折叠成一个新点，并把与边相连的点连到新点到新点 三角形折叠：把三角形折叠成一个新点，并把与三角

5、三角形折叠：把三角形折叠成一个新点，并把与三角形相连的点连到新点形相连的点连到新点边折叠边折叠三角形折叠三角形折叠第9页第4章 多细节层次模型生成和绘制n几何元素删除型算法几何元素删除型算法 几何元素直接删除型几何元素直接删除型 通过评价顶点或三角形的重要性，如果不重要则直接通过评价顶点或三角形的重要性，如果不重要则直接删除，并对得到的空洞进行三角化删除，并对得到的空洞进行三角化 近平面合并型近平面合并型 把近似位于同一平面上的相邻三角形合并把近似位于同一平面上的相邻三角形合并 边折叠型边折叠型 搜索平面区域和特征边，然后使用边折叠操作简化模搜索平面区域和特征边，然后使用边折叠操作简化模型型

6、代表研究者代表研究者Hoppe（微软研究院）（微软研究院）第10页第4章 多细节层次模型生成和绘制n基于顶点聚类的模型简化算法基于顶点聚类的模型简化算法 赋予各顶点权值，特征变化较大的点权值大赋予各顶点权值，特征变化较大的点权值大 根据物体复杂程度，相对大小等因素，把物体所根据物体复杂程度，相对大小等因素，把物体所占空间划分为多个立方体单元占空间划分为多个立方体单元 计算出立方体里各顶点的代表点计算出立方体里各顶点的代表点 把位于立方体单元内的点用代表点代替，把产生把位于立方体单元内的点用代表点代替，把产生的退化多边形移去的退化多边形移去第11页第4章 多细节层次模型生成和绘制n基于折叠操作的

7、模型简化算法基于折叠操作的模型简化算法 基于边的折叠基于边的折叠 步骤步骤 计算原始模型中每个顶点的误差矩阵计算原始模型中每个顶点的误差矩阵Q 选有效的可进行折叠的定点对选有效的可进行折叠的定点对 为每个顶点对（为每个顶点对（v1，v2）计算最优的用于代替）计算最优的用于代替V1，v2的新点的新点v0 把所有顶点按折叠顺序放在堆中（把所有顶点按折叠顺序放在堆中（V0T（Q1+Q2），），v0为折叠代价），最小代价放在顶部为折叠代价），最小代价放在顶部 重复地把顶点对（重复地把顶点对（v1，v2）从堆中输出，进行折叠，）从堆中输出，进行折叠，并修改受影响的顶点对的代价并修改受影响的顶点对的代价第

8、12页第4章 多细节层次模型生成和绘制n简介简介 多分辨率模型是一种支持对同一场景中不同物体多分辨率模型是一种支持对同一场景中不同物体或同一物体的不同部分，使用具有不同的细节的或同一物体的不同部分，使用具有不同的细节的描述方法的数据结构描述方法的数据结构 控制场景复杂度、加速图形绘制、提高交互性的控制场景复杂度、加速图形绘制、提高交互性的一个非常有效的方法一个非常有效的方法 主要方法主要方法 基于小波的多分辨率分析基于小波的多分辨率分析 基于网格简化或者网格细分的多分辨率模型基于网格简化或者网格细分的多分辨率模型第13页第4章 多细节层次模型生成和绘制nMRM模型模型 适用于任意网格简化或精化

9、操作适用于任意网格简化或精化操作 具有高效的数据结构，能快速遍历所有数据具有高效的数据结构，能快速遍历所有数据 不规则三角形网格，适用多种物体的多分辨率模不规则三角形网格，适用多种物体的多分辨率模型型第14页第4章 多细节层次模型生成和绘制nLOD绘制技术绘制技术 分成与视点相关和无关两类分成与视点相关和无关两类 视点无关：根据不同的误差标准预先生成不同精视点无关：根据不同的误差标准预先生成不同精度的模型，绘制时根据视点的位置选择相应的模度的模型，绘制时根据视点的位置选择相应的模型绘制型绘制 视点相关：根据视点动态生成简化模型视点相关：根据视点动态生成简化模型 比较比较 前者需要较多存储空间，

10、模型切换时会产生跳变前者需要较多存储空间，模型切换时会产生跳变 计算量较大，模型能连续平滑过渡计算量较大，模型能连续平滑过渡第15页第4章 多细节层次模型生成和绘制n与视点无关的与视点无关的LOD 预处理：存储局部变化的模型，一般采用基于三预处理：存储局部变化的模型，一般采用基于三角形折叠的算法角形折叠的算法 绘制时：依据视点的距离，选择局部细节变化大绘制时：依据视点的距离，选择局部细节变化大的模型的模型 特点：绘制速度快，但需要较多的存储空间特点：绘制速度快，但需要较多的存储空间第16页第4章 多细节层次模型生成和绘制n与视点相关的与视点相关的LOD 预处理：计算出每个顶点的误差值（几何误差

11、和预处理：计算出每个顶点的误差值（几何误差和屏幕误差的综合），根据视点、视见体等生成简屏幕误差的综合），根据视点、视见体等生成简化模型化模型 辅助加速绘制辅助加速绘制 视见体裁剪视见体裁剪 背面剔除背面剔除 帧间连贯性帧间连贯性 特点：不需要额外的外存，但计算细节的时间耗特点：不需要额外的外存，但计算细节的时间耗费较多费较多第17页第4章 多细节层次模型生成和绘制n背景背景 GIS地理信息系统地理信息系统 、虚拟现实虚拟现实和和军事仿真军事仿真等领域等领域 地形数据宠大，实时绘制和内存管理能力有限地形数据宠大，实时绘制和内存管理能力有限 1990s后期地形多分辨率绘制技术研究大量盛行，后期地形

12、多分辨率绘制技术研究大量盛行，出现至少十种以上的典型算法出现至少十种以上的典型算法 多分辨率技术主要包括多分辨率技术主要包括 LOD数据组织方式、误差计算、性能优化 1997年后基于规则三角形网成为主流的多分辨率年后基于规则三角形网成为主流的多分辨率建模绘制技术建模绘制技术第18页第4章 多细节层次模型生成和绘制n地形的表示地形的表示 不规则网格方法不规则网格方法 TIN (Triangulated Irregular Network) 多边形少，地形表示精度多边形少，地形表示精度低；低；数据结构复杂；检索面数据结构复杂；检索面 速度慢，不易于地形的碰撞检测和变形处理。速度慢，不易于地形的碰撞

13、检测和变形处理。 规则网格方法规则网格方法(Uniform Grid Method) 多边形冗余大，易实时构造多细节模型多边形冗余大，易实时构造多细节模型LOD；视点附；视点附近区域精度高。近区域精度高。第19页第4章 多细节层次模型生成和绘制n规则网格方法规则网格方法 LOD细节层次模型细节层次模型 模型的动态抽取模型的动态抽取 误差评定方案误差评定方案第20页第4章 多细节层次模型生成和绘制nLOD细节层次模型细节层次模型 四叉树四叉树 二叉树二叉树第21页第4章 多细节层次模型生成和绘制nLOD细节层次模型（续）细节层次模型（续） 问题：裂缝和问题：裂缝和T形交叉点形交叉点 四叉树四叉树

14、 第22页第4章 多细节层次模型生成和绘制n二叉树模型二叉树模型 ROAM算法最早提出算法最早提出 二叉树结构和自顶向下构建三角网格，帧间连贯性处理二叉树结构和自顶向下构建三角网格，帧间连贯性处理性能突出性能突出 等腰直角三角形引入斜边的中点后一分为二，递归分解等腰直角三角形引入斜边的中点后一分为二，递归分解后形成三角形二叉树。子三角形替代父三角形时实现细后形成三角形二叉树。子三角形替代父三角形时实现细化，反之实现粗化。化，反之实现粗化。 （a）L=0 （b）L=1 （c）L=2 （d）L=3 （e）L=4 （f）L=5 （g）L=6 （h）L=7 v0 v1 v2 v3 v4 T0 T1 T

15、00 T01 v5 v7 v8 v6 第23页第4章 多细节层次模型生成和绘制n二叉树模型（续）二叉树模型（续） 顶点间的依赖关系顶点间的依赖关系DAG 父三角形斜边中点与子三角形直角顶点间的关系父三角形斜边中点与子三角形直角顶点间的关系 . v0 v1 v2 v3 v4 v5 v6 v7 v8 （a）L=0 （b）L=1 （c）L=2 （d）L=3 （e）L=4 （f）L=5 （g）L=6 （h）L=7 v0 v1 v2 v3 v4 T0 T1 T00 T01 v5 v7 v8 v6 第24页第4章 多细节层次模型生成和绘制n二叉树模型（续）二叉树模型（续） 误差计算误差计算 依赖视点位置依

16、赖视点位置 与地形的崎岖程度有关与地形的崎岖程度有关 投影方式有关投影方式有关保证地形不出现裂缝保证地形不出现裂缝嵌套误差判据球第25页第4章 多细节层次模型生成和绘制n二叉树模型（续）二叉树模型（续） 视锥裁剪技术视锥裁剪技术 包围球的视锥剔除方法：三角形与视锥外接球距离和半径关包围球的视锥剔除方法：三角形与视锥外接球距离和半径关系判断系判断 三角形外接球：三角形外接球： 视锥外的快速判断：视锥外的快速判断：)(max)(TcTcTChildTcTcCrRdRRT)(第26页第4章 多细节层次模型生成和绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性活跃帧（活跃帧（live fra

17、meslive frames） 依据前一帧所显示的三角形而得到当前帧应显示的三依据前一帧所显示的三角形而得到当前帧应显示的三角形网格，减少计算角形网格，减少计算 ROAM算法采用按误差值大小排序确定合并与分裂的算法采用按误差值大小排序确定合并与分裂的三角形队列，维护队列增加了时间开销，在一定程度三角形队列，维护队列增加了时间开销，在一定程度上影响了绘制效率上影响了绘制效率 活跃帧：视点在当前位置时，三角形状态将不发生变活跃帧：视点在当前位置时，三角形状态将不发生变化的帧数化的帧数 影响因素：视点位置和方向（是否在视锥内）影响因素：视点位置和方向（是否在视锥内）第27页第4章 多细节层次模型生成

18、和绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性活跃帧计算活跃帧计算),min(,cos21222111011nnLvRdnvRdnvRdsfniivdRRLmvCf),min(CfsffLLL Ov OE Rm Rv 运动方向 视点：视点：视锥：视锥：活跃帧：活跃帧：第28页第4章 多细节层次模型生成和绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性队列队列 分裂队列分裂队列Qs 合并队列合并队列Qm 直绘队列直绘队列QrN是延迟处理次数的阈值是延迟处理次数的阈值 ： 大小影响大小影响Qr中个数，影响中个数，影响LOD生成时间生成时间 与地形起伏程度有关与地形起伏程度有

19、关 NLNLnnNLnnQrQmQsfff,2112第29页第4章 多细节层次模型生成和绘制n动态地形动态地形 局部区域高度数据发生变化局部区域高度数据发生变化 误差重新计算（静态地形在预处理阶段生成）误差重新计算（静态地形在预处理阶段生成） 数据精度提高数据精度提高 扩展精度方法（全局和局部）扩展精度方法（全局和局部） 局部扩展时需要考虑不同精度数据的混合绘制局部扩展时需要考虑不同精度数据的混合绘制 变化区域内的顶点误差判据球半径小变化区域内的顶点误差判据球半径小 区域被破坏区域被破坏形变区域形变区域精度高精度高原始区域原始区域精度低精度低第30页第4章 多细节层次模型生成和绘制n动态地形（

20、续）动态地形（续） 边界点性质边界点性质 左边界上引入顶点后，地形网格模型的右半块中不会左边界上引入顶点后，地形网格模型的右半块中不会引入顶点引入顶点第31页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 局部扩展局部扩展定理定理 设单元格设单元格C 的精度被扩大为原来的的精度被扩大为原来的2k倍，为了保证不倍，为了保证不出现裂缝，不论出现裂缝，不论k为多大的正整数，只需要扩大过渡区内为多大的正整数，只需要扩大过渡区内单元格的分辨率。单元格的分辨率。扩展后扩展后过渡过渡区区第32页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 区域完整性区域完整性问题问题 利用

21、视点和嵌套误差判据球生成地形三角网精度会破利用视点和嵌套误差判据球生成地形三角网精度会破坏区域的完整性坏区域的完整性陷入地陷入地形内形内第33页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 区域完整性区域完整性解决方法解决方法主要方法：主要方法：（1）最大值法：）最大值法：Iwoa大学大学He将区域内所有顶点误差设置为将区域内所有顶点误差设置为最大值最大值 区域内部没有区域内部没有LOD，三角形过多，三角形过多（2）斜边长度代替空间误差）斜边长度代替空间误差 国防大学王林旭提出，不能有效保证区域的完整性国防大学王林旭提出，不能有效保证区域的完整性第34页第4章 多细节层次模型

22、生成和绘制n动态地形（续）动态地形（续） 区域完整性区域完整性区域的三角形划分区域的三角形划分 基本划分：由单元三角形及单元子三角形组成的集合基本划分：由单元三角形及单元子三角形组成的集合 最优划分：三角形合并后数目最少的划分最优划分：三角形合并后数目最少的划分 特特 点：基本划分是区域内部的最精细表示，而最优划分点：基本划分是区域内部的最精细表示，而最优划分是最粗糙表示是最粗糙表示 生成最优划分算法：生成最优划分算法： 主要是任务是三角形与区域相交测试主要是任务是三角形与区域相交测试第35页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 区域的区域的LOD 为了生成区域的最优

23、划分，也需要强迫较多三角为了生成区域的最优划分，也需要强迫较多三角形分裂（虽然比基本划分减少了三角形数目）。形分裂（虽然比基本划分减少了三角形数目）。 根据人的视觉原理，远离区域时，区域就越来越根据人的视觉原理，远离区域时，区域就越来越小，边界也越来越模糊。因此，可以建立区域边界小，边界也越来越模糊。因此，可以建立区域边界的的LOD，减少因确定边界带来较多的分裂操作，减少因确定边界带来较多的分裂操作考虑的因素：视点距离和视线方向考虑的因素：视点距离和视线方向第36页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 区域的区域的LOD 实现思路实现思路 视角阈值化，动态调整顶视角阈

24、值化，动态调整顶点的误差数据。点的误差数据。 含义：含义： 当视点接近区域时，当视点接近区域时，Ri 扩大，扩大，保证视点在嵌套球内；当视点远保证视点在嵌套球内；当视点远离区域时，离区域时，Ri的扩大程度降低，的扩大程度降低，视点落在嵌套球内的可能性就越视点落在嵌套球内的可能性就越来越小，从而产生区域的细节层来越小，从而产生区域的细节层次次kRRDDkdDecdeniiilod/118013531354524501)()(cos第37页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 实例实例车辙和脚印车辙和脚印第38页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续

25、） 区域保持区域保持 采用区域的层次细节算法，保证了视点在近距离能观察到采用区域的层次细节算法，保证了视点在近距离能观察到区域完整形状，而在远距离处看到区域轮廓，三角形个数减区域完整形状，而在远距离处看到区域轮廓，三角形个数减少。少。没有保持没有保持保持保持LOD第39页第4章 多细节层次模型生成和绘制n动态地形（续）动态地形（续） 区域保持实例区域保持实例房屋、树木房屋、树木近距离近距离 中等距离中等距离 远距离远距离没有区域没有区域保持保持 区域保持区域保持房屋和树木陷入地面内房屋和树木陷入地面内第40页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 重点和难点

26、是海量地形数据的组织重点和难点是海量地形数据的组织 分块绘制分块绘制根据视点位置，加载局部块地形数据，每块地形进行单独根据视点位置，加载局部块地形数据，每块地形进行单独绘制绘制 地形分块地形分块 每块大小为（每块大小为（2k1）（2k1），不足部分按边界值），不足部分按边界值进行延伸进行延伸整幅地形大小不再必须为整幅地形大小不再必须为（2n1）（2n1）（nk）第41页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 地形调度与裁剪地形调度与裁剪 按视点位置初步确定需要加载和卸载的子块按视点位置初步确定需要加载和卸载的子块 按视锥精确计算可见块按视锥精确计算可见块 绘

27、制绘制 每块单独绘制每块单独绘制 数据结构只有一个三角形、数据结构只有一个三角形、二叉树和二叉树和DAG第42页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 块间裂缝块间裂缝（边界点在相邻块上的活跃状态不同）（边界点在相邻块上的活跃状态不同） 子块间子块间 子块单元格间子块单元格间 主要方法主要方法 不规则法不规则法边界处用不规则法生成三角形边界处用不规则法生成三角形 规则法规则法根据公共边顶点状态强制分裂根据公共边顶点状态强制分裂不规则法破坏了规则网格特性；不规则法破坏了规则网格特性；规则法没考虑边界顶点状态变规则法没考虑边界顶点状态变化后对其它边界的影响化后对

28、其它边界的影响第43页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 无缝连接运算无缝连接运算(处理裂缝处理裂缝) 两相邻块两相邻块A和块和块B，无缝连接，无缝连接U(A ,B) 公共边界上顶点状态一致公共边界上顶点状态一致 其它边界受影响，但影响范围的有限其它边界受影响，但影响范围的有限 相邻子块相邻子块 运算结果运算结果第44页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制定理定理 对子块对子块A，B，C，D，排列如下图，则无，排列如下图，则无缝连接操作缝连接操作(A,B,C,D)(ABBC+ CDDA)n。其中块的横纵向点数。其中块

29、的横纵向点数 N=2n+1k1 k2 k3 第45页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 窗口扫描定理窗口扫描定理 对空间上相邻的块组对空间上相邻的块组Aij(i0, m; j=0, n) ，用，用2 2窗口对块组按行（列）进行扫描处理，窗口对块组按行（列）进行扫描处理，进行一遍处理后，相邻块间不存在裂缝。进行一遍处理后，相邻块间不存在裂缝。 第46页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 单元格间裂缝处理单元格间裂缝处理块内单元格块内单元格块间单元格块间单元格将单元格看作块，利用窗将单元格看作块，利用窗口扫描定理扫描单

30、元格口扫描定理扫描单元格子块间的子块间的边界线边界线子块间的子块间的边界线边界线块间块间单元格单元格块内块内单元格单元格第47页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 实验实验-验证算法有效性验证算法有效性 (a) (b) (c) (左)裂缝处理前的光滑阴影图，图中的空白区域为裂缝(中)裂缝处理后的光滑阴影图(右)网格图. (a)视点位置号 1，位置(750.,550,2390) (b) 视点位置号 6，位置(2900，1300，5000) (c)视点位置号 17，位置(7300，500，1600) 地形大小地形大小：81938193子块大小子块大小：257

31、257 详细论述见：详细论述见：计算计算机辅助设计与图形学机辅助设计与图形学学报学报2006，10“地形分块绘制中的边地形分块绘制中的边界裂缝处理算法界裂缝处理算法”第48页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 实验实验性能性能 裂缝处理时间裂缝处理时间 增加的三角形数增加的三角形数裂缝处理时间不到裂缝处理时间不到1ms1ms，对整体，对整体的实时性影响很小；的实时性影响很小；加入活跃点造成的边界提升的加入活跃点造成的边界提升的深度很小，裂缝处理后增加的深度很小，裂缝处理后增加的三角形数目在三角形数目在2020100100个左右个左右第49页第4章 多细节层次模型生成和绘制n大规模地形的实时绘制大规模地形的实时绘制 实例实例第50页第4章 多细节层次模型生成和绘制n发展动向发展动向 基于硬件（基于硬件（GPU）的加速技术）的加速技术 Vertex 和和 Fragment Shading 基于基于LOD的合成地形环境的合成地形环境 建模建模 绘制绘制