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

第第4章章 多细节层次模型和绘制多细节层次模型和绘制计算机科学系计算机科学系2009，51第4章 多细节层次模型生成和绘制第4章 多细节层次模型和绘制计算机科学系1第4章 多细主要内容主要内容4.1简介简介 4.2基本概念基本概念4.3 网格简化算法网格简化算法4.4 多分辨率模型生成算法多分辨率模型生成算法4.5 实时连续实时连续LOD模型绘制模型绘制4.6 地形实时绘制地形实时绘制2第4章 多细节层次模型生成和绘制主要内容4.1简介 2第4章 多细节层次模型生成和绘制4.1 简介简介n细节层次细节层次LOD（Level of Detail）1976年年Clark提出提出指对同一场景或场景中的物体，使用具有不同细指对同一场景或场景中的物体，使用具有不同细节的描述方法得到一组模型，供绘制时选择使用节的描述方法得到一组模型，供绘制时选择使用目的是减少模型的多边形个数，提高绘制速度目的是减少模型的多边形个数，提高绘制速度广泛应用于复杂场景快速绘制、飞行模拟器、广泛应用于复杂场景快速绘制、飞行模拟器、3D动画、虚拟现实等系统动画、虚拟现实等系统3第4章 多细节层次模型生成和绘制4.1 简介细节层次LOD（Level of Detail4.1 简介简介nLOD方法的基本思想方法的基本思想不同的物体或物体的不同部分采用不同的细节不同的物体或物体的不同部分采用不同的细节绘制时，如果物体离视点比较远，或者物体比较绘制时，如果物体离视点比较远，或者物体比较小，可以用较粗的小，可以用较粗的LOD模型绘制，反之用较细模型绘制，反之用较细的模型绘制的模型绘制同样，对运动快的物体用较粗的同样，对运动快的物体用较粗的LOD模型绘制，模型绘制，反之用较细的模型绘制反之用较细的模型绘制4第4章 多细节层次模型生成和绘制4.1 简介LOD方法的基本思想4第4章 多细节层次模型4.2 基本概念基本概念n误差度量误差度量如何生成不同细节的模型如何生成不同细节的模型n局部误差局部误差距离误差计算距离误差计算曲率误差计算曲率误差计算5第4章 多细节层次模型生成和绘制4.2 基本概念误差度量5第4章 多细节层次模型生成和绘4.2 基本概念基本概念n全局误差全局误差计算法计算法具有较好的近似效果，但计算量大具有较好的近似效果，但计算量大一般用法一般用法简化过程中，删除的顶点具有尽量小的全局误差简化过程中，删除的顶点具有尽量小的全局误差精化过程中，增加的顶点具有尽量大的全局误差精化过程中，增加的顶点具有尽量大的全局误差6第4章 多细节层次模型生成和绘制4.2 基本概念全局误差6第4章 多细节层次模型生成和绘4.2 基本概念基本概念n简化操作简化操作指在网格模型简化过程中使用到的基本操作指在网格模型简化过程中使用到的基本操作包括包括顶点删除：把三角形中不重要的顶点删去顶点删除：把三角形中不重要的顶点删去三角形删除：若三角形的面积小于某个值，移去三角形删除：若三角形的面积小于某个值，移去顶点删除顶点删除三角形删除三角形删除7第4章 多细节层次模型生成和绘制4.2 基本概念简化操作顶点删除三角形删除7第4章 多细4.2 基本概念基本概念n简化操作简化操作包括（续）包括（续）边折叠：把边折叠成一个新点，并把与边相连的点连边折叠：把边折叠成一个新点，并把与边相连的点连到新点到新点三角形折叠：把三角形折叠成一个新点，并把与三角三角形折叠：把三角形折叠成一个新点，并把与三角形相连的点连到新点形相连的点连到新点边折叠边折叠三角形折叠三角形折叠8第4章 多细节层次模型生成和绘制4.2 基本概念简化操作边折叠三角形折叠8第4章 多细节4.3 网格简化算法网格简化算法n几何元素删除型算法几何元素删除型算法几何元素直接删除型几何元素直接删除型通过评价顶点或三角形的重要性，如果不重要则直接通过评价顶点或三角形的重要性，如果不重要则直接删除，并对得到的空洞进行三角化删除，并对得到的空洞进行三角化近平面合并型近平面合并型把近似位于同一平面上的相邻三角形合并把近似位于同一平面上的相邻三角形合并边折叠型边折叠型搜索平面区域和特征边，然后使用边折叠操作简化模搜索平面区域和特征边，然后使用边折叠操作简化模型型代表研究者代表研究者Hoppe（微软研究院）（微软研究院）9第4章 多细节层次模型生成和绘制4.3 网格简化算法几何元素删除型算法9第4章 多细4.3 网格简化算法网格简化算法n基于顶点聚类的模型简化算法基于顶点聚类的模型简化算法赋予各顶点权值，特征变化较大的点权值大赋予各顶点权值，特征变化较大的点权值大根据物体复杂程度，相对大小等因素，把物体所根据物体复杂程度，相对大小等因素，把物体所占空间划分为多个立方体单元占空间划分为多个立方体单元计算出立方体里各顶点的代表点计算出立方体里各顶点的代表点把位于立方体单元内的点用代表点代替，把产生把位于立方体单元内的点用代表点代替，把产生的退化多边形移去的退化多边形移去10第4章 多细节层次模型生成和绘制4.3 网格简化算法基于顶点聚类的模型简化算法10第44.3 网格简化算法网格简化算法n基于折叠操作的模型简化算法基于折叠操作的模型简化算法基于边的折叠基于边的折叠步骤步骤计算原始模型中每个顶点的误差矩阵计算原始模型中每个顶点的误差矩阵Q选有效的可进行折叠的定点对选有效的可进行折叠的定点对为每个顶点对（为每个顶点对（v1，v2）计算最优的用于代替）计算最优的用于代替V1，v2的新点的新点v0把所有顶点按折叠顺序放在堆中（把所有顶点按折叠顺序放在堆中（V0T（Q1+Q2），），v0为折叠代价），最小代价放在顶部为折叠代价），最小代价放在顶部重复地把顶点对（重复地把顶点对（v1，v2）从堆中输出，进行折叠，）从堆中输出，进行折叠，并修改受影响的顶点对的代价并修改受影响的顶点对的代价11第4章 多细节层次模型生成和绘制4.3 网格简化算法基于折叠操作的模型简化算法11第44.4 多分辨率模型生成算法多分辨率模型生成算法n简介简介多分辨率模型是一种支持对同一场景中不同物体多分辨率模型是一种支持对同一场景中不同物体或同一物体的不同部分，使用具有不同的细节的或同一物体的不同部分，使用具有不同的细节的描述方法的数据结构描述方法的数据结构控制场景复杂度、加速图形绘制、提高交互性的控制场景复杂度、加速图形绘制、提高交互性的一个非常有效的方法一个非常有效的方法主要方法主要方法基于小波的多分辨率分析基于小波的多分辨率分析基于网格简化或者网格细分的多分辨率模型基于网格简化或者网格细分的多分辨率模型12第4章 多细节层次模型生成和绘制4.4 多分辨率模型生成算法简介12第4章 多细节层4.4 多分辨率模型生成算法多分辨率模型生成算法nMRM模型模型适用于任意网格简化或精化操作适用于任意网格简化或精化操作具有高效的数据结构，能快速遍历所有数据具有高效的数据结构，能快速遍历所有数据不规则三角形网格，适用多种物体的多分辨率模不规则三角形网格，适用多种物体的多分辨率模型型13第4章 多细节层次模型生成和绘制4.4 多分辨率模型生成算法MRM模型13第4章 多4.5 实时连续实时连续LOD模型绘制模型绘制nLOD绘制技术绘制技术分成与视点相关和无关两类分成与视点相关和无关两类视点无关：根据不同的误差标准预先生成不同精视点无关：根据不同的误差标准预先生成不同精度的模型，绘制时根据视点的位置选择相应的模度的模型，绘制时根据视点的位置选择相应的模型绘制型绘制视点相关：根据视点动态生成简化模型视点相关：根据视点动态生成简化模型比较比较前者需要较多存储空间，模型切换时会产生跳变前者需要较多存储空间，模型切换时会产生跳变计算量较大，模型能连续平滑过渡计算量较大，模型能连续平滑过渡14第4章 多细节层次模型生成和绘制4.5 实时连续LOD模型绘制LOD绘制技术14第4章4.5 实时连续实时连续LOD模型绘制模型绘制n与视点无关的与视点无关的LOD预处理：存储局部变化的模型，一般采用基于三预处理：存储局部变化的模型，一般采用基于三角形折叠的算法角形折叠的算法绘制时：依据视点的距离，选择局部细节变化大绘制时：依据视点的距离，选择局部细节变化大的模型的模型特点：绘制速度快，但需要较多的存储空间特点：绘制速度快，但需要较多的存储空间15第4章 多细节层次模型生成和绘制4.5 实时连续LOD模型绘制与视点无关的LOD15第4.5 实时连续实时连续LOD模型绘制模型绘制n与视点相关的与视点相关的LOD预处理：计算出每个顶点的误差值（几何误差和预处理：计算出每个顶点的误差值（几何误差和屏幕误差的综合），根据视点、视见体等生成简屏幕误差的综合），根据视点、视见体等生成简化模型化模型辅助加速绘制辅助加速绘制视见体裁剪视见体裁剪背面剔除背面剔除帧间连贯性帧间连贯性特点：不需要额外的外存，但计算细节的时间耗特点：不需要额外的外存，但计算细节的时间耗费较多费较多16第4章 多细节层次模型生成和绘制4.5 实时连续LOD模型绘制与视点相关的LOD16第4.6 地形实时绘制地形实时绘制n背景背景GIS地理信息系统地理信息系统、虚拟现实虚拟现实和和军事仿真军事仿真等领域等领域地形数据宠大，实时绘制和内存管理能力有限地形数据宠大，实时绘制和内存管理能力有限1990s后期地形多分辨率绘制技术研究大量盛行，后期地形多分辨率绘制技术研究大量盛行，出现至少十种以上的典型算法出现至少十种以上的典型算法多分辨率技术主要包括多分辨率技术主要包括LOD数据组织方式、误差计算、性能优化1997年后基于规则三角形网成为主流的多分辨率年后基于规则三角形网成为主流的多分辨率建模绘制技术建模绘制技术17第4章 多细节层次模型生成和绘制4.6 地形实时绘制背景17第4章 多细节层次模型生4.6 地形实时绘制地形实时绘制n地形的表示地形的表示 不规则网格方法不规则网格方法 TIN(Triangulated Irregular Network)多边形少，地形表示精度低；数据结构复杂；检索面多边形少，地形表示精度低；数据结构复杂；检索面 速度慢，不易于地形的碰撞检测和变形处理。速度慢，不易于地形的碰撞检测和变形处理。规则网格方法规则网格方法(Uniform Grid Method)多边形冗余大，易实时构造多细节模型多边形冗余大，易实时构造多细节模型LOD；视点附；视点附近区域精度高。近区域精度高。18第4章 多细节层次模型生成和绘制4.6 地形实时绘制地形的表示 18第4章 多细节层4.6 地形实时绘制地形实时绘制n规则网格方法规则网格方法LOD细节层次模型细节层次模型 模型的动态抽取模型的动态抽取 误差评定方案误差评定方案19第4章 多细节层次模型生成和绘制4.6 地形实时绘制规则网格方法19第4章 多细节层4.6 地形实时绘制地形实时绘制nLOD细节层次模型细节层次模型 四叉树四叉树二叉树二叉树20第4章 多细节层次模型生成和绘制4.6 地形实时绘制LOD细节层次模型 20第4章 4.6 地形实时绘制地形实时绘制nLOD细节层次模型（续）细节层次模型（续）问题：裂缝和问题：裂缝和T形交叉点形交叉点四叉树四叉树 21第4章 多细节层次模型生成和绘制4.6 地形实时绘制LOD细节层次模型（续）21第4章4.6 地形实时绘制地形实时绘制n二叉树模型二叉树模型ROAM算法最早提出算法最早提出二叉树结构和自顶向下构建三角网格，帧间连贯性处理二叉树结构和自顶向下构建三角网格，帧间连贯性处理性能突出性能突出等腰直角三角形引入斜边的中点后一分为二，递归分解等腰直角三角形引入斜边的中点后一分为二，递归分解后形成三角形二叉树。子三角形替代父三角形时实现细后形成三角形二叉树。子三角形替代父三角形时实现细化，反之实现粗化。化，反之实现粗化。22第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型22第4章 多细节层次4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）顶点间的依赖关系顶点间的依赖关系DAG 父三角形斜边中点与子三角形直角顶点间的关系父三角形斜边中点与子三角形直角顶点间的关系23第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）23第4章 多细4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）误差计算误差计算依赖视点位置依赖视点位置与地形的崎岖程度有关与地形的崎岖程度有关投影方式有关投影方式有关保证地形不出现裂缝保证地形不出现裂缝嵌套误差判据球24第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）24第4章 多细4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）视锥裁剪技术视锥裁剪技术 包包围围球球的的视视锥锥剔剔除除方方法法：三三角角形形与与视视锥锥外外接接球球距距离离和和半半径径关关系判断系判断 三角形外接球：三角形外接球：视锥外的快速判断：视锥外的快速判断：25第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）25第4章 多细4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性活跃帧（活跃帧（live frameslive frames）依据前一帧所显示的三角形而得到当前帧应显示的三依据前一帧所显示的三角形而得到当前帧应显示的三角形网格，减少计算角形网格，减少计算ROAM算法采用按误差值大小排序确定合并与分裂的算法采用按误差值大小排序确定合并与分裂的三角形队列，维护队列增加了时间开销，在一定程度三角形队列，维护队列增加了时间开销，在一定程度上影响了绘制效率上影响了绘制效率 活跃帧：视点在当前位置时，三角形状态将不发生变活跃帧：视点在当前位置时，三角形状态将不发生变化的帧数化的帧数 影响因素：视点位置和方向（是否在视锥内）影响因素：视点位置和方向（是否在视锥内）26第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）26第4章 多细4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性活跃帧计算活跃帧计算视点：视点：视锥：视锥：活跃帧：活跃帧：27第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）视点：27第4章 4.6 地形实时绘制地形实时绘制n二叉树模型（续）二叉树模型（续）帧间连贯性帧间连贯性队列队列 分裂队列分裂队列Qs 合并队列合并队列Qm 直绘队列直绘队列QrN是延迟处理次数的阈值是延迟处理次数的阈值 ：大小影响大小影响Qr中个数，影响中个数，影响LOD生成时间生成时间 与地形起伏程度有关与地形起伏程度有关 28第4章 多细节层次模型生成和绘制4.6 地形实时绘制二叉树模型（续）28第4章 多细4.6 地形实时绘制地形实时绘制n动态地形动态地形局部区域高度数据发生变化局部区域高度数据发生变化误差重新计算（静态地形在预处理阶段生成）误差重新计算（静态地形在预处理阶段生成）数据精度提高数据精度提高扩展精度方法（全局和局部）扩展精度方法（全局和局部）局部扩展时需要考虑不同精度数据的混合绘制局部扩展时需要考虑不同精度数据的混合绘制变化区域内的顶点误差判据球半径小变化区域内的顶点误差判据球半径小区域被破坏区域被破坏形变区域形变区域精度高精度高原始区域原始区域精度低精度低29第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形形变区域精度高原始区域精度4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）边界点性质边界点性质左边界上引入顶点后，地形网格模型的右半块中不会左边界上引入顶点后，地形网格模型的右半块中不会引入顶点引入顶点30第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）30第4章 多细节4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）局部扩展局部扩展定理定理 设单元格设单元格C 的精度被扩大为原来的的精度被扩大为原来的2k倍，为了保证不倍，为了保证不出现裂缝，不论出现裂缝，不论k为多大的正整数，只需要扩大过渡区内为多大的正整数，只需要扩大过渡区内单元格的分辨率。单元格的分辨率。扩展后扩展后过渡过渡区区31第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）扩展后过渡区31第44.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域完整性区域完整性问题问题利用视点和嵌套误差判据球生成地形三角网精度会破利用视点和嵌套误差判据球生成地形三角网精度会破坏区域的完整性坏区域的完整性陷入地陷入地形内形内32第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）陷入地形内32第4章4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域完整性区域完整性解决方法解决方法主要方法：主要方法：（1）最大值法：）最大值法：Iwoa大学大学He将区域内所有顶点误差设置为将区域内所有顶点误差设置为最大值最大值 区域内部没有区域内部没有LOD，三角形过多，三角形过多（2）斜边长度代替空间误差）斜边长度代替空间误差 国防大学王林旭提出，不能有效保证区域的完整性国防大学王林旭提出，不能有效保证区域的完整性33第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）33第4章 多细节4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域完整性区域完整性区域的三角形划分区域的三角形划分 基本划分：由单元三角形及单元子三角形组成的集合基本划分：由单元三角形及单元子三角形组成的集合 最优划分：三角形合并后数目最少的划分最优划分：三角形合并后数目最少的划分 特特 点：基本划分是区域内部的最精细表示，而最优划分点：基本划分是区域内部的最精细表示，而最优划分是最粗糙表示是最粗糙表示 生成最优划分算法：生成最优划分算法：主要是任务是三角形与区域相交测试主要是任务是三角形与区域相交测试34第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）34第4章 多细节4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域的区域的LOD 为了生成区域的最优划分，也需要强迫较多三角为了生成区域的最优划分，也需要强迫较多三角形分裂（虽然比基本划分减少了三角形数目）。形分裂（虽然比基本划分减少了三角形数目）。根据人的视觉原理，远离区域时，区域就越来越根据人的视觉原理，远离区域时，区域就越来越小，边界也越来越模糊。因此，可以建立区域边界小，边界也越来越模糊。因此，可以建立区域边界的的LOD，减少因确定边界带来较多的分裂操作，减少因确定边界带来较多的分裂操作考虑的因素：视点距离和视线方向考虑的因素：视点距离和视线方向35第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）考虑的因素：视点距离4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域的区域的LOD 实现思路实现思路 视角阈值化，动态调整顶点视角阈值化，动态调整顶点的误差数据。的误差数据。含义：含义：当视点接近区域时，当视点接近区域时，Ri 扩大，扩大，保证视点在嵌套球内；当视点远保证视点在嵌套球内；当视点远离区域时，离区域时，Ri的扩大程度降低，的扩大程度降低，视点落在嵌套球内的可能性就越视点落在嵌套球内的可能性就越来越小，从而产生区域的细节层来越小，从而产生区域的细节层次次36第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）36第4章 多细节4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）实例实例车辙和脚印车辙和脚印37第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）37第4章 多细节4.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域保持区域保持 采用区域的层次细节算法，保证了视点在近距离能观察到采用区域的层次细节算法，保证了视点在近距离能观察到区域完整形状，而在远距离处看到区域轮廓，三角形个数减少。区域完整形状，而在远距离处看到区域轮廓，三角形个数减少。没有保持没有保持保持保持LOD38第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）没有保持保持LOD34.6 地形实时绘制地形实时绘制n动态地形（续）动态地形（续）区域保持实例区域保持实例房屋、树木房屋、树木近距离近距离 中等距离中等距离 远距离远距离没有区域没有区域保持保持 区域保持区域保持房屋和树木陷入地面内房屋和树木陷入地面内39第4章 多细节层次模型生成和绘制4.6 地形实时绘制动态地形（续）近距离 4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制重点和难点是海量地形数据的组织重点和难点是海量地形数据的组织分块绘制分块绘制根据视点位置，加载局部块地形数据，每块地形进行单独根据视点位置，加载局部块地形数据，每块地形进行单独绘制绘制地形分块地形分块每块大小为（每块大小为（2k1）（2k1），不足部分按边界值），不足部分按边界值进行延伸进行延伸整幅地形大小不再必须为整幅地形大小不再必须为（2n1）（2n1）（nk）40第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制整幅地形大小不4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制地形调度与裁剪地形调度与裁剪按视点位置初步确定需要加载和卸载的子块按视点位置初步确定需要加载和卸载的子块按视锥精确计算可见块按视锥精确计算可见块绘制绘制每块单独绘制每块单独绘制数据结构只有一个三角形、数据结构只有一个三角形、二叉树和二叉树和DAG41第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制41第4章 4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制块间裂缝块间裂缝（边界点在相邻块上的活跃状态不同）（边界点在相邻块上的活跃状态不同）子块间子块间子块单元格间子块单元格间主要方法主要方法不规则法不规则法边界处用不规则法生成三角形边界处用不规则法生成三角形规则法规则法根据公共边顶点状态强制分裂根据公共边顶点状态强制分裂不规则法破坏了规则网格特性；不规则法破坏了规则网格特性；规则法没考虑边界顶点状态变规则法没考虑边界顶点状态变化后对其它边界的影响化后对其它边界的影响42第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制不规则法破坏了4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制无缝连接运算无缝连接运算(处理裂缝处理裂缝)两相邻块两相邻块A和块和块B，无缝连接，无缝连接U(A,B)公共边界上顶点状态一致公共边界上顶点状态一致其它边界受影响，但影响范围的有限其它边界受影响，但影响范围的有限 相邻子块相邻子块 运算结果运算结果43第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制 相邻子块4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制定理定理 对子块对子块A，B，C，D，排列如下图，则无缝，排列如下图，则无缝连接操作连接操作(A,B,C,D)(ABBC+CDDA)n。其中块的横纵向点数。其中块的横纵向点数 N=2n+1k1 k2 k3 44第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制k1 4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制窗口扫描定理窗口扫描定理 对空间上相邻的块组对空间上相邻的块组Aij(i0,m;j=0,n)，用，用2 2窗口对块组按行（列）进行扫描处理，窗口对块组按行（列）进行扫描处理，进行一遍处理后，相邻块间不存在裂缝。进行一遍处理后，相邻块间不存在裂缝。45第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制45第4章 4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制单元格间裂缝处理单元格间裂缝处理块内单元格块内单元格块间单元格块间单元格将单元格看作块，利用窗将单元格看作块，利用窗口扫描定理扫描单元格口扫描定理扫描单元格子块间的子块间的边界线边界线子块间的子块间的边界线边界线块间块间单元格单元格块内块内单元格单元格46第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制将单元格看作块4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制实验实验-验证算法有效性验证算法有效性地形大小地形大小：81938193子块大小子块大小：257257 详细论述见：计算详细论述见：计算机辅助设计与图形学机辅助设计与图形学学报学报2006，10“地形分块绘制中的地形分块绘制中的边界裂缝处理算法边界裂缝处理算法”47第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制地形大小：详细4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制实验实验性能性能裂缝处理时间裂缝处理时间增加的三角形数增加的三角形数裂缝处理时间不到裂缝处理时间不到1ms1ms，对整体，对整体的实时性影响很小；的实时性影响很小；加入活跃点造成的边界提升的深加入活跃点造成的边界提升的深度很小，裂缝处理后增加的三角度很小，裂缝处理后增加的三角形数目在形数目在2020100100个左右个左右48第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制裂缝处理时间不4.6 地形实时绘制地形实时绘制n大规模地形的实时绘制大规模地形的实时绘制实例实例49第4章 多细节层次模型生成和绘制4.6 地形实时绘制大规模地形的实时绘制49第4章 4.6 地形实时绘制地形实时绘制n发展动向发展动向基于硬件（基于硬件（GPU）的加速技术）的加速技术Vertex 和和 Fragment Shading基于基于LOD的合成地形环境的合成地形环境建模建模绘制绘制50第4章 多细节层次模型生成和绘制4.6 地形实时绘制发展动向50第4章 多细节层次模