面向分布式虚拟环境的并行图形绘制系统研究 2007年3月

本课题组完成三项成果 一、新型高性能混合式自适应并行图形绘制系统 二、基于Direct3D的并行图形绘制技术 三、基于网格的可视化系统GVis

新型高性能混合式自适应并行图形绘制系统的成果创新点 混合式自适应并行图形绘制体系结构 Scene-Framework场景组织框架 基于节点迁移的负载平衡策略 并行遮挡剔除技术研究 适用于并行绘制的几何编码技术

基于Direct3D的并行图形绘制技术的成果创新点 支持D3D9应用程序级透明的并行图形绘制的体系结构由一个资源分配节点和多个并行执行的资源绘制节点组成； 资源分配节点完成绘制资源截取功能，其流程分三层，包括绘制命令截取层、绘制命令解析层和绘制资源并行化层； 资源绘制节点完成绘制资源重构功能，其流程分三层，包括绘制资源存储层、绘制命令解码层、绘制命令重构层； 支持多流模式的绘制任务划分；

基于网格的可视化系统GVis的成果创新点 提出基于网格可视化系统的三层体系结构模型，包括运行时环境层，可视化框架层和网格门户层。各个层次之间功能相对独立，耦合性小，具有良好的扩展性； 完全基于Java实现的交互式可视化网格系统，具有良好的跨平台性和易访问性； 支持大规模体数据实时的交互式可视化处理和大范围内可用的远程多任务处理等功能。

软件清单 项目 软件名称 说明 高性能并行图形绘制系统 ParallelSG 包括运行于动态绘制组上的ParallelSG_Server（又包含主节点的Master版本和从节点的Slave版本）和运行于控制节点上的ParallelSG_Controller 。 基于Direct3D的并行绘制系统 D3DPR 包括资源分配、资源绘制两个部分 基于网格的可视化技术 GVis GVis运行时环境层GVRE，GVis可视化框架层GVVF和GVis网格门户层GVisPortal，

论文清单 Zonghui Wang, Xiaohong Jiang, Jiaoying Shi，HLA/RTI Performance Testing，20051006，国际学术会议论文集，EI 仇应俊, 石教英, 赵友兵, 陈为，面向网格的交互式可视化平台GVis研究与实现，计算机研究与发展，20051201，国内一级刊物论文 石教英, 赵友兵, 仇应俊，面向网格的可视化系统研究，计算机研究与发展，41(12)，20051201，EI 毛祖秋, 李超, 林海, 石教英, 林叶青，基于OpenSG的多屏幕立体绘制—用于模型的集群立体显示系统，计算机研究与发展，42，20051201，国内一级刊物论文 Zonghui Wang, Jiaoying Shi, Xiaohong Jiang，A Scalable HLA-based Distributed Simulation Framework for VR Application，16th International Conference on Artificial Reality and Telexistence 2006，20060101，SCI Yaping Zhang, Yang Zhao, Jiaoying Shi, Dan Xu，Digitization of culture heritage based on tour into the picture，TECHNOLOGIES FOR E-LEARNING AND DIGITAL ENTERTAINMENT 2006，20060401， SCI

论文清单(续1) ZONGHUI WANG, XIAOHONG JIANG , JIAOYING SHI，Efficient communication approach in HLA-based Distributed simulation for VR application，Journal of Computational Information Systems ，20060401，SCI Aihong Qin，Hua Xiong ,Jiaoying Shi, Zhen Liu，Piecewise Compression of Large Mesh，IS&T/SPIE’s 16th Annual Symposium Electronic Imaging Science and Technology 2006，20060601，SCI QIN Ai-hong, XIONG Hua, PENG Hao-yu, LIU Zhen, SHI Jiao-ying，Cluster Parallel rendering based on encoded mesh ，Jounal of Zhejiang Univesity，7，20060701，SCI Haoyu Peng, Hua Xiong, Jiaoying Shi，Parallel-SG：Research of Parallel Graphics Rendering System on Cluster，Proceedings of the 2006 ACM International Conference on VRCIA，20060714，EI Hua Xiong，Haoyu Peng，Aihong QinJiaoying Shi，Parallel Occlusion Culling on GPUs Cluster，Proceedings of the 2006 ACM International Conference on VRCIA，20060714，EI

论文清单(续2) Yongxia Zhou, Jiaoying Shi, Jiarong Yu，Free and shape-controlled flows of smoke，Proceedings of the 2006 ACM International Conference on VRCIA，20060714，EI Hua XiongZhen LiuAihong Qin ，Haoyu PengJiaoying Shi，Predictive Occlusion Culling for Interactive Rendering of Large Complex Virtual Scene，VSMM 2006，20060714，EI 刘 真，石教英，彭浩宇，秦爱红，A Survey of Cluster-Based Parallel Rendering System，系统仿真学报，18(suppl)，20060801，EI 周永霞,石教英,郁佳荣，Physical based smoke animation，计算机辅助设计与图形学报，18(9)，20060901，国内一级刊物论文 彭浩宇，金哲凡，秦爱红，熊华，石教英，A Nesting Parallel Pipeline for Parallel Graphics Rendering System Based-on，18(10)，20061001，国内一级刊物论文 Zhen Liu, Jiaoying Shi, Hua Xiong, Aihong Qin，Multi-Stream Based Rendering Resource Interception and Reconstruction in D3DPR for High-Resolution Display，16th International Conference on Artifical Reality and Telexistence, ICAT2006，20061001，EI

专利清单 专利名称 发明人 专利号 数字图像处理中基于HVS的自然图像抠图方法 林生佑，石教英 ZL 03 1 17071.4 数字图像处理中以任意图像为背景的快速抠图方法 ZL 03 1 16447.1 计算机集群并行绘制系统中基于时空变换的负载平衡设计方法 金哲凡，石教英 ZL 03 1 16216.9 基于相对深度计算的画中游方法 曹智清，石教英 ZL 2004 1 0052974.0

一、新型高性能混合式自适应并行图形绘制系统

分布式虚拟环境图形绘制的特点 普遍采用多屏拼接显示或CAVE系统 要求与分布式仿真应用无缝集成 场景规模大和高交互性，对绘制速度要求提高 任务划分固定－－按屏幕空间划分 负载不平衡 要求与分布式仿真应用无缝集成 场景规模大和高交互性，对绘制速度要求提高

成果创新点 混合式自适应并行图形绘制体系结构 Scene-Framework场景组织框架 基于节点迁移的负载平衡策略 并行遮挡剔除技术研究 适用于并行绘制的几何编码技术

混合式自适应并行绘制体系结构 提出基于动态绘制组的混合式自适应并行绘制体系结构 特点： 基本绘制单元---动态绘制组 Sort-first和sort-lastd的混合式并行绘制体系结构 动态绘制组内工作流程的自适应切换 复式嵌套并行绘制流水线

混合式自适应并行绘制体系结构 ---动态绘制组 Dynamic Rendering Team (DRT) 由一个主节点和若干绘制从节点构成 绘制的功能单元 主 从 …… DRT

Tile Projector Display 混合式自适应并行绘制体系结构 支持sort-first和sort-last的混合式并行绘制体系结构 这两种工作流程能根据负载分布均匀度进行自适应切换 Sort-first DRT Projector Screen 1 Screen 2 Controller Screen 3 Screen 4 Sort-first or sort-last Tile Projector Display

混合式自适应并行绘制体系结构 ---DRT内的第二层优化并行流水线 传统串行工作方式 i-1帧 i帧 i+1帧 GR C D (a)串行流水线 绘制时间为t1，图像生成时间t2，投影显示时间t3，一般情况下，t1≈t2>> t3。 串行流水线的绘制时间Ts = t1+t2+t3。

混合式自适应并行绘制体系结构 ---DRT内的第二层优化并行流水线 我们的并行工作方式 i-1帧 GRi-1 Ci-2 Di-3 GRi Ci-1 Di-2 GRi+1 Ci Di-1 GRi+2 Ci+1 Di i帧 i+1帧 i+2帧 I/O Network CPU/GPU Parallel （b）优化并行流水线 绘制时间为t1，图像生成时间t2，投影显示时间t3，一般情况下，t1≈t2>> t3。 优化并行流水线的绘制时间Tp = max(t1 , t2 , t3) 。

混合式自适应并行绘制体系结构 ---测试结果 测试场景：“Power Plant”模型 1185个小模型，总三角面片数13M 方案 投影墙设置 (DRT数) 主节点数 从节点数 动态绘制组内部平均绘制服务器数 一 1×1 1 31 32 二 2×2 4 28 8 三 3×3 9 23 四 5×3 15 17 2

混合式自适应并行绘制体系结构 ---测试结果 DRT内采用串行流水线

Scene-Framework场景组织框架 具有场景图(scene graph)的外在组织形式，但与传统场景图总是基于某种数据结构定义之上不同，Scene-Framework本身不定义特定的数据结构； 提供抽象基类（TreeNode）作为构建场景图的单元，此基类定义了并行绘制相关接口,向上层并行绘制系统提供统一的并行功能接口； 不同数据类型的场景继承此基类，构建支持特定数据类型的子场景图； 支持不同数据结构的子场景图统一挂在Scene- Framework框架下协同工作。

Scene-Framework场景组织框架 TreeNode … ... Tree （Root） （leaf） 用TreeNode类构造的子场景图 Scene Tree Scene Render …… 抽象基类 Scene-Framework TreeNode TreeNodeStatic TreeNodeTerrain TreeNodeDynamic TreeNode的继承类示意

Scene-Framework场景组织框架 综合应用实例 原始数据结构 数据量 静态场景Power Plant 点与面片的序列 13M三角面片 地形场景Puget 带LOD选择的四叉树 1909.3MB几何数据和49.15MB纹理数据 动态场景 3DS模型 100架飞机、100架坦克，共约27万面片，11M纹理 能支持异构数据结构的场景 能与分布仿真应用无缝集成

基于节点迁移的负载平衡策略 实现 优势 DRT之间：通过绘制从节点在DRT之间的迁移、从而调整各DRT的计算能力来维护各DRT间的负载平衡 解决了多屏拼接显示系统的限制 算法开销小 有效降低冗余处理的风险

负载平衡策略---负载平衡测试结果

遮挡剔除技术研究 遮挡剔除是加速绘制大规模复杂场景的重要加速技术之一 。 提出两类遮挡剔除并行化策略： 提出基于可见性预测的遮挡剔除算法 可见性预测是遮挡剔除算法研究的一个难点。 提出并行遮挡剔除算法 并行遮挡剔除算法是遮挡剔除算法中研究不足的问题。

基于预测的遮挡剔除 基本思路 建立场景的空间层次结构； 由上到下、从前到后遍历该空间层次结构； 利用硬件遮挡查询功能判断节点可见性； 利用空间和时间连贯性建立节点可见性预测机制，以减少硬件遮挡查询的次数。

基于预测的遮挡剔除算法 关键技术 可见性预测机制通过可见性预测器实现，可见性预测器包含：可见性状态、可见帧计数器和遮挡帧计数器。 在进行节点的硬件遮挡查询前，先通过可见性预测器预测其可见性，若可见性预测器不能断定可见性状态，才执行其硬件遮挡查询。

基于预测的遮挡剔除 实验结果 测试场景：8百万和1千3百万三角面片的大规模复杂虚拟场景。 保守遮挡剔除和近似遮挡剔除可以分别减少25%和50%的硬件遮挡查询次数。 在大多数绘制帧中，遮挡剔除效率达到了70%到99%。

遮挡剔除并行化策略 对基于预测的可见性遮挡剔除算法，我们提出了两类遮挡剔除并行化策略： 数据并行化策略。 功能并行化策略。

遮挡剔除并行化策略 数据并行化策略：将要进行的硬件遮挡查询分布到集群机的不同节点执行。 根据分布遮挡查询的顺序不同，数据并行化策略又可以分为sort-first方式和sort-last方式。

遮挡剔除并行化策略 功能并行化策略：用不同的集群机节点组成遮挡剔除流水线。 功能并行化策略可以分为静态遮挡剔除流水线和动态遮挡剔除流水线两类。

遮挡剔除并行化策略 实验场景：8百万和1千3百万三角面片的大规模复杂虚拟场景。 绘制速率分别达到了25帧和15帧，在15台PC集群机上比单机遮挡剔除速度提高了2倍和4倍。

适用于并行绘制的几何模型压缩技术 背景 目标 网络带宽有限； 频繁的大模型数据传送； -主节点机和从节点机之间的数据传输； -磁盘到内存的数据读取； -内存到显存的数据传送。 传统压缩算法不适合并行机基于视线的sorting和可见性预测。 目标 为cluster并行绘制系统配置更合适的几何模型压缩算法，在有限带宽下提高模型数据的传输速度,支持压缩域sorting。

适用于并行绘制的几何模型压缩技术 传统in-the-core压缩算法只能把一个模型压缩为整体传输,存在的局限性有: 只适用于小模型； 不能分片随机存取； 不支持压缩域基于视点的sorting； 不支持压缩域可见性预测和剔除。

适用于并行绘制的几何模型压缩技术 传统Out-of-core压缩算法把一个大模型分为多个patches分别压缩,存在的局限性有: 边界数据随所在的patch一起压缩多次(需要压缩的次数等于公用此点的patches数目。)； 解压缩时,重复的边界数据使得模型中的顶点增多； 压缩存在量化误差。解压缩后，具有不同误差的相同边界点不能保证完全重合,patches间产生裂缝； Patch的法向连贯性差,不利于基于视点的sorting。

适用于并行绘制的几何模型压缩技术 PRMC：Parallel rendering based mesh compression 算法思想: 对大模型分割为具有法向连贯性和平坦度均匀的patches，每个patch的数据分为边界和内部数据两种类型。内部数据采用已有的算法压缩,边界数据进行分段压缩。绝大部分边界的几何信息只压缩一次，但可以被多个patches共享。 算法组成： （1） 基于法向连贯性的分割算法 （2） 分段边界压缩算法

适用于并行绘制的几何模型压缩技术 基于法向连贯性的分割算法 step1：Out of Core采用坐标轴分割超出内存容量的模型； 其中法向控制函数 step3：采用MeTiS分割上步结果，获得均匀的分割效果。 MeTiS明尼苏达大学电脑科学系开发的应用程序库.适合分割大型无结构图，速度快，分割结果中，patches中的元素数量基本相同，最多和最少的元素数量之差在10%范围内。 http://glaros.dtc.umn.edu/gkhome/views/metis

适用于并行绘制的几何模型压缩技术 分割结果 特点 patches中三角形数量基本相同（变化范围小于 10%),同时每个patch法向锥的上限受到控制。

适用于并行绘制的几何模型压缩技术 分段边界压缩 Step1:找出边界。 上图：模型中部分曲面片，红色线段为相邻patch公用的边，这些边的集合称为patch边界。 下图：边界结果图，其中直线段表示上图中能显示出的边界，曲线段表示左图中没有显示出的其余边界。

适用于并行绘制的几何模型压缩技术 分段边界压缩 Step2:边界分为子段。 右图:把边界分成子段：若patchi和patchj相邻,Lij是patchi和patchj共用的一条边,则Lij的集合称为patchi和patchj的一个子段，然后对子段中的边按连接关系排序。图中每个子段用一种颜色表示。

适用于并行绘制的几何模型压缩技术 分段边界压缩 Step3:选择子段的参照点。 右图:子段的两个端点称为鞍点，选择其中一个作为此子段后续点几何压缩时的参照点， 参照点不进行压缩。图中参照点用菱形表示。

适用于并行绘制的几何模型压缩技术 分段边界压缩 Step4:压缩子段 右图. 每个子段从参照点开始,顺序对子段中的其余点进行几何属性的预测编码。其中,虚线段表示已经压缩的子段；红色字符串表示子段的编码； 复合圆表示编码后的一个子段表达,它作为一个可以独立存取的压缩子段。

适用于并行绘制的几何模型压缩技术 系统实现原理

适用于并行绘制的几何模型压缩技术 绘制性能 图. 对比一般模型，集群机采用PRMC模型后，sorting 和transmission速度提高的比率

适用于并行绘制的几何模型压缩技术 特点 把每个压缩的patch和边界子段当作一个数据单元来处理； 支持压缩域sorting； 压缩比约为1:4—1:16； Sorting 速度和数据传输速度均有提高； 更适用于需要多次传送数据的立即模式集群机。

二、基于Direct3D9并行图形绘制技术

引言 现有并行图形绘制系统都是基于OpenGL Direct3D的迅猛发展 提出支持Direct3D9的并行图形绘制系统D3DPR

D3DPR的研究目标 基于图形集群硬件平台 支持Direct3D9应用程序透明并行化 驱动高分辨率大屏幕的多屏拼接显示

成果创新点 支持D3D9应用程序级透明的并行图形绘制的体系结构由一个资源分配节点和多个并行执行的资源绘制节点组成； 资源分配节点完成绘制资源截取功能，其流程分三层，包括绘制命令截取层、绘制命令解析层和绘制资源并行化层； 资源绘制节点完成绘制资源重构功能，其流程分三层，包括绘制资源存储层、绘制命令解码层、绘制命令重构层； 支持多流模式的绘制任务划分；

Direct3D9图形绘制流水线

Direct3D9图形库的特征 基于多流模式场景数据的组织模式 1.顶点缓冲器 2.索引缓冲器 3.流：顶点缓冲器和索引缓冲器中具有相同 数据类型的的顺序数据 4.多流：顶点缓冲器的位置、法矢量、颜色 等各个属性信息分别保存在不同的顶点缓 冲器中 绘制资源：顶点缓冲器的顶点流，索引缓冲器的索引流，纹理内存的纹理流和命令流

D3DPR的系统结构 绘制资源节点完成绘制资源的截取 绘制资源节点完成绘制资源重构和绘制命令执行功能

资源分配节点 绘制命令截取：绘制命令的过滤与转换 绘制命令解析：绘制命令编码 绘制资源并行化：绘制资源的打包和发送

资源绘制节点 绘制资源存储：绘制资源的解包和存储策略 绘制命令解码：绘制命令的编码 绘制命令重构：命令的逆转换

基于多流模式的绘制任务划分 由于Direct3D9采用多流模式组织场景数据，因此D3DPR在绘制命令执行过程中通过计算基于多流模式场景数据的包围盒进行绘制任务划分

绘制任务重新划分的策略 策略一：保持表示顶点流的顶点缓冲器不变，遍历索引流的数据，判断每个三角形是否属于改绘制节点，如果属于在索引缓冲器中保留该索引序列，否则就删除。这是一个索引流进行再划分的过程。 策略二：在删除索引缓冲器数据的过程中，同时对顶点缓冲器和索引缓冲器的数据进行重排。

D3DPR部分实验结果

D3DPR部分实验结果

D3DPR部分实验结果

三、基于网格的交互式可视化系统GVis

成果创新点 提出基于网格可视化系统的三层体系结构模型，包括运行时环境层，可视化框架层和网格门户层。各个层次之间功能相对独立，耦合性小，具有良好的扩展性； 完全基于Java实现的交互式可视化网格系统，具有良好的跨平台性和易访问性； 支持大规模体数据实时的交互式可视化处理和大范围内可用的远程多任务处理等功能。

可视化网格的目标和研究内容 研究目标 研究内容 使用网格技术构建网格系统，聚集和整合大规模网络环境中的计算、存储和绘制资源，为大规模数据集的可视化应用提供强有力的支撑平台，并广泛的向用户提供交互式的可视化服务 研究内容 资源的聚集和管理 并行/远程可视化应用 可视化服务和用户访问 多用户的协同可视化

可视化网格的相关工作有哪些 基于已有的并行系统通过网格对外提供服务 可视化网格中间件 面向海量数据传输的可视化网格 建立在已有的可视化系统之上，针对同构平台 可扩展性和跨平台性不够 可视化网格中间件 扩展现有网格中间件，加入可视化功能 与科学计算的集成 较少的用户交互功能 面向海量数据传输的可视化网格 涉及可视化部分较少

相关工作与本文工作的比较 相关工作的特点总结 本文工作的突出特点 不具备一个完整可视化网格系统应有的功能 大多数基于已有系统，扩展性和跨平台性不够 较少考虑到用户交互性特点和要求 本文工作的突出特点 完整的可视化网格系统，由网格支撑、可视化应用框架和网格门户三部分组成 完全基于Java设计和实现，具有良好的跨平台性和易用性 充分考虑到用户交互性特点，对现有的网格技术进行适当的选取和必要的扩充，从而支持用户和可视化应用的交互，并满足用户交互的实时性、稳定性和可靠性需求

GVis系统3层体系结构 GVis运行时环境GVRE 资源管理、信息管理、数据管理、任务管理 GVis可视化框架GVVF 可视化、并行可视化、远程可视化 GVis网格门户GVisPortal 用户访问系统的功能界面

GVis运行时环境GVRE GVRE的功能目标 GVRE的功能模块 屏蔽网格资源的异构性、自治性和动态性特征，为可视化应用提供透明、高效、稳定执行的网格环境 GVRE的功能模块 信息管理 资源管理（资源管理网格服务） 任务管理（任务代理网格服务） 数据管理

GVis可视化框架GVVF GVVF的功能目标 GVVF的功能模块 实现网格环境中大规模数据集的实时交互可视化 底层消息通信 任务分割 绘制 合成 交互显示

GVVF任务分割模块 负责协调整个可视化任务的执行，提供基于图像空间和基于对象空间两种并行方式 采用二分加权分割算法，根据绘制节点的性能将可视化任务均匀的分配给各个绘制节点，从而达到一定的负载平衡。

GVVF绘制与合成模块 利用面向对象的思想，通过继承和实现以下接口和类就可以支持新的可视化和合成算法，具有良好的可扩展性

GVVF交互显示模块 提供用户和可视化任务的实时交互 获取可视化的最终结果并显示 获取用户的交互输入

GVis网格门户GVisPortal 网格门户 GVis网格门户GVisPortal 网格用户和网格系统之间的界面 基于Web实现的网格门户 容易访问 交互功能有限 交互效率不高 GVis网格门户GVisPortal 基于Java应用程序实现的桌面型门户 用户交互功能丰富、交互效率高

GVis网格门户GVisPortal

GVis系统测试 大数据集的可视化测试 最大数据集3.75GB, 30个绘制节点、2~3fps 1.5GB（12个绘制结点） 3~5fps

GVis系统测试 多任务测试 Teddybear（1M），图像空间并行 Bonsai（64M），对象空间并行 平均帧速率15～20帧

总结 新型高性能混合式自适应并行图形绘制系统特别适合分布式虚拟环境的应用； D3DPR支持D3D9应用程序透明化并行绘制； 基于网格的可视化系统GVis结构灵活，易于扩充，下一步计划增加基于网格的分布仿真模块和基于网格的并行绘制模块。