李 朝 奎，杨 偶，吴 柏 燕，殷 智 慧，李 拥

大范围3DCM场景实时并行绘制的任务划分及策略

李 朝 奎，杨 偶，吴 柏 燕，殷 智 慧，李 拥

（湖南科技大学地球空间信息科学研究中心，湖南 湘潭 411201;地理空间信息湖南省工程实验室，湖南 湘潭 411201）

针对三维城市模型（3DCM）场景并行绘制的几何图元分布特性，利用动态负载平衡算法实现3DCM场景绘制任务划分和分配。给出了负载平衡性能的一种度量权，提出一种递归划分算法：即把按顺序执行的任务集，根据其子任务间潜在的并行性，划分成若干个可并发执行的任务子集，并把每个子集分配给处理机，使各处理机之间的数据通信量尽可能同步，同时兼顾各处理机之间的负载平衡，从而实现了一种新的负载平衡算法。

3DCM场景;并行绘制;任务划分;动态负载平衡

0 引言

随着计算机图形技术的实用化以及近年来三维扫描和建模技术的快速发展，三维模型的数据量急剧增大，单纯依赖于图形加速卡的单机绘制技术并不能满足大范围3DCM场景的实时绘制要求。一般3DCM场景非常复杂，而任何硬件在单位时间内处理场景的能力总是有限的［1－3］。目前大范围3DCM场景的数据量大大超过了计算机的内存容量，使得绘制系统无法将整个场景一次性调入，因此，处理大规模3DCM场景数据的一般方法是对场景数据进行空间划分，将整个场景分割成多个便于管理的数据块，并按照空间层次的形式进行组织［1］。大规模3DCM场景绘制任务的划分与调度是将一个大规模的3DCM场景绘制任务集进行分解，并把每个分解的可并发执行的任务子集映射到不同的处理机上进行并行运算，以提高3DCM场景绘制的速度［4，5］。……