一种基于分块组织的多层次兵棋地图快速绘制方法

本发明涉及一种基于分块组织的多层次兵棋地图快速绘制方法，步骤为：创建六角网格模板块，计算六角网格模板块中所有顶点位置并存储；根据所需绘制的六角网格的分辨率，计算在X、Y方向上所需的拼接块数量；逐个绘制每个拼接块；本发明通过发掘六角网格在几何结构及材质属性上的可重用性特征，减少冗余计算，提高计算速度，使绘制大规模六角网格的速度达到实时。

技术领域

[0001] 本发明属于计算机仿真技术和计算机图形技术领域，尤其涉及兵棋地图的基于分 块组织的多层次结构的快速绘制。

背景技术

[0002] 兵棋地图数字化处理是计算机兵棋系统实现中的重要环节。它对整个或者局部地 形区域进行六角网格化，按照一定规则将地形信息转换为六角网格单元面或边的属性，以 供兵棋棋子使用。在实际应用中，为准确反应地形信息，六角网格往往拥有大量的六边形单 元，且拥有多种材质属性(颜色、线宽等）。大量不同材质的边、面绘制计算往往成为制约可 视系统显示效率的瓶颈，而目前关于这方面的研究却非常有限。

[0003] 传统的六角网格绘制方法是先计算所有六角格单元的中心点，然后为每个中心点 计算对应的六个顶点，最后绘制连接六个顶点的线段。这种绘制方式简单但包含大量冗余 操作。如中心点的计算和相邻六角网格单元边的重复计算等。设六角网格单元个数为N，传 统方法需要计算6N个顶点和绘制12N条边。

[0004] 为此，杨伦等人(杨伦，彭春光，黄健，黄柯棣.兵棋推演中地形量化算法研究与实 现.计算机仿真.2008,25⑼：96-99.)提出一种基于图元的六角网格加速绘制方法。它根据 六角网格中的结构规律，提取包含4条边的图元，绘制时平移重复绘制图元。该方法能避免 大量的冗余操作，其需要计算的顶点数为2N，绘制的总边数为3N。

[0005] 六角网格也是计算机图形学中重要的几何组织结构。但目前的研究多集中在基于 六角网格系统的直、曲线生成(刘勇奎，石教英.六角网格上的图形显示.计算机辅助设计与 图形学学报.2004，16⑶：331-336)、窗口裁剪(付文超.基于类直角坐标的六角网格系统下 图形绘制及裁剪算法改进.暨南大学硕士学位论文，2011.)等基本几何算法的研究上。对六 角网格本身的高效绘制较少研究。

[0006] 六角网格绘制操作的效率对兵棋系统的可视化效率有很大影响。在高分辨率下， 六角网格单元的数量巨大，且六角单元的面和边对应多种材质以表达复杂的地形信息。已 有技术方法，受空间表达能力或计算能力的限制，不便于对这种大规模的复杂情况进行高 效处理，计算效率不高。

发明内容

[0007] 本发明的目的在于提供一种基于分块组织的多层次兵棋地图快速绘制方法，它通 过发掘六角网格在几何结构及材质属性上的可重用性特征，减少冗余计算，提高计算速度， 使绘制大规模六角网格的速度达到实时。

[0008] 本发明是基于分块组织的多层次兵棋地图快速绘制方法，其步骤包括：

[0009] (1)创建模板块，计算模板块中所有顶点位置并存储；

[0010] (2)整个兵棋地图六角网格以块拼接的方式进行绘制。所需的拼接块依据模板块 经平移、缩放变换得到。在本步骤中，根据所需绘制的兵棋地图六角网格在平面直角坐标系 中沿X轴和沿Y轴方向上的单元数，确定在相邻平铺拼接方式下，X和Y方向上所需的拼接块 数量；

[0011] (3)逐个绘制每个拼接块，即计算当前拼接块的平移、缩放变换参数，根据模板块 顶点位置变换得到本拼接块的所有顶点位置;根据不同面、边材质属性，将本拼接块内的单 元分组，为每一分组生成正常显示和层次细节(LOD)显示的顶点索引数组;若正常显示，则 根据正常情况顶点索引数组，将相同材质的面、边集中绘制;若需要LOD显示，则计算LOD等 级，根据LOD顶点索引数组，将相同材质的面、边集中绘制。

[0012] 所述步骤⑴具体实现如下：

[0013] (11)创建在X，Y轴方向上的六角单元个数(六角网格分辨率)均为k的六角网格，作 为模板块，k为2的整数倍，该模板块中的每个单元均为正六边形，边长为1，模板块的最小轴 向包围盒的左下顶点坐标为(〇,〇)，依次计算每个单元的六个顶点坐标，计算顺序设置为从 左到右，从下到上处理每个单元;在每个单元内部，则是自左下顶点开始按照逆时针顺序计 算所有6个顶点；

[0014] (12)为确保在任意相机缩放比例下，相邻拼接块的衔接处皆可无误差的无缝连 接，以短整型数存储模板块的顶点坐标，为提高精度，在计算时需要扩大正六边形的边长， 即乘以一个扩大倍数λ，λε [0,短整型的最大值];

[0015] (13)计算完成后，模板块的所有顶点坐标按顺序保存在长度为k*k*6*2的短整型 数组中，将该顶点位置数组绑定OpenGL的VB0,存储在显卡的顶点缓冲区中。

[0016] 所述步骤(2)具体实现如下:计算绘制整个兵棋地图六角网格在X、Y方向上所需的 拼接块数量。方法是:设所需绘制的六角网格在Χ、Υ方向上的分辨率分别为W和Η，令拼接块 在Χ、Υ方向上平铺相邻排列，则拼接块在Χ、Υ方向上的数量分别为

和拼接块中超出 所需绘制范围的单元一律设置为透明材质，绘制时不显示。

[0017] 所述步骤⑶具体实现如下：

[0018] (31)设置当前拼接块相对于模板块的平移，缩放参数，使用OpenGL坐标变换矩阵， 得到当前拼接块的顶点位置坐标；

[0019] (32)根据不同六角网格单元的面、边材质属性，将本拼接块内的六角单元分组，为 每一面材质属性分组生成用于正常显示的面顶点索引数组，其中存储具有该材质的六角单 元的八个顶点索引，每个六角单元由两个梯形组合绘制，共8个顶点，为每一边材质属性分 组生成用于正常显示的边顶点索引数组，其中存储具有该材质的六角单元边的两个顶点索 引；

[0020] (33)为每一面材质属性分组生成用于LOD显示的面顶点索引数组，将每一面材质 的所有LOD面顶点索引数据放在一个大的顶点索引数组中；当需要调用不同级别LOD数据 时，取不同的数组大小即可；为每一边材质属性分组生成用于LOD显示的边顶点索引数组， 存储方式与LOD面顶点数组相同，即也将每一边材质的所有LOD边顶点索引数据放在一个大 的顶点索引数组中；

[0021] (34)若正常绘制，贝Ij用glDrawElements 〇函数逐个绘制每种面材质的面顶点索引 数组;再逐个绘制每种边材质的边顶点索引数组，若需要使用低细节层次绘制，则仅绘制当 前L㈤级别的单元，S卩用glDrawEIements 〇函数逐个绘制每种面材质的LOD面顶点索引数 组;再逐个绘制每种边材质的LOD边顶点索引数组。

[0022] 本发明的有益效果如下：

[0023] 与现有的兵棋地图绘制方法相比，本发明更好的利用了六角网格在结构和属性上 的可重用性特征，更多地去除了冗余计算，绘制速度更快。冗余计算的节省来自于三方面： 一是仅需计算并存储模板块，绘制时使用OpenGL的变换矩阵快速获得顶点坐标，节省了大 量顶点坐标的计算。二是将具有相同材质属性的六角格单元面与边进行集中化组织，以顶 点数组的方式绘制，节省大量由于逐个绘制面、边导致的绘制函数调用开销。三是按照LOD 层次组织的顺序组织数组存储，减少存储冗余。本发明已应用于某兵棋系统，绘制包含100 万（1000*1000)单元的六角网格，帧速率不低于40fps，很好地解决了原系统由大量六角网 格绘制负担带来的显示迟滞问题。

附图说明null实施方式

[0028] 如图4所示，本发明包括三个阶段:第一阶段是创建模板块;第二阶段是确定拼接 块分辨率;第三阶段是显示拼接块。

[0029] 第一阶段的步骤如下：

[0030] 1)创建在X，Y轴方向上的六角单元个数(六角网格分辨率)均为k (k为2的整数倍） 的六角网格，作为模板块。该模板块中的每个单元均为正六边形，边长为1。模板块的最小轴 向包围盒的左下顶点坐标为(〇,〇)。依次计算每个单元的六个顶点坐标。计算顺序可设置为 从左到右，从下到上处理每个单元。在每个单元内部，则是自左下顶点开始按照逆时针顺序 计算所有6个顶点。

[0031] 若以浮点数存储模板块的顶点坐标，当拼接块依据模板块计算自身顶点坐标时， 不同块对于同一边界顶点的坐标计算会有不同，不便于块之间的无缝连接。因此，为了确保 在任意相机缩放比例下，相邻拼接块的衔接处皆可无误差的无缝连接，以短整型存储模板 块的顶点坐标。为了提高精度，在计算时需要扩大正六边形的边长，即乘以一个扩大倍数λ， Ae [0,短整型的最大值]。

[0032] 2)计算完成后，模板块的所有顶点坐标按顺序被保存在长度为k*k*6*2的短整型 数组中。将该顶点位置数组绑定OpenGL的VB0,存储在显卡的顶点缓冲区中。在后续的拼接 绘制中，所有拼接块的顶点信息均根据该数组变换获得。该数组在整个运行过程中保持不 变，且仅初始化一次。

[0033] 图1展示了一个k = 4的模板块及其对应的顶点数组。图1中，标记在每个单元中心 的数字为该单元的顺序号。单元〇和单元1的顶点以VQ至Vll标记。按照如上所述的计算方法， 单元〇六个顶点的坐标分别为:VQ

,Vl

,V2 (2λ,

I，V3

[0034] 在第二阶段，根据所需绘制的六角网格的分辨率，确定所需的拼接块在X、Y方向上 的块数。确定方法是:设所需绘制的六角网格在Χ、Υ方向上的分辨率分别为W和Η，令拼接块

在Χ、Υ方向上平铺相邻排列，则拼接块在Χ、Υ方向上的数量分别为 和 图2展示了一 ό 个拼接示例，其中1=14，!1 = 7汰=4。为显示清晰，相邻块以不同颜色来区别显示。所需绘制 的六角网格边界单元以斜线填充。则Χ、Υ方向上的块数分别为4和2。超出所需绘制范围的单 元一律设置为透明材质，绘制时不显示，如在图2中X方向上大于14、Υ方向上大于7的单元。

[0035] 第三阶段的步骤如下：

[0036] 1)根据需要绘制的六角单元的半径、起始单元的中心点坐标和当前拼接块的位置 索引，设置当前拼接块相对于模板块的平移、缩放参数，使用OpenGL坐标变换矩阵，得到当 前拼接块的顶点坐标。

[0037] 2)对每个需要绘制的拼接块，根据单元的材质属性将网格单元分组，即具有相同 材质属性的单元归为一组。在兵棋绘制中，六角单元的面和边会具有不同的属性，对应不同 的含义。因此需要对面、边材质分别进行分组处理。在本步骤中，为每组生成一个用于正常 显示的顶点索引数组，以便在后续步骤中使用glDrawElementsO调用进行绘制。每种面材 质对应的顶点索引数组中存储所有具有该材质的六角单元的八个顶点索引（每个六角单元 由两个梯形组合绘制，共8个顶点）。每种边材质对应的顶点索引数组中存储所有具有该材 质的六角单元边的两个顶点索引。这里，拼接块中的顶点索引使用与模板块相同的顶点索 引设置规则，见图1。

[0038] 3)对每个需要绘制的拼接块，为每种材质分组生成对应的LOD顶点索引数组，以支 持层次细节绘制。即当画面缩小到足够比例时，使用对应层次的LOD顶点索引数组以减少所 需绘制的顶点。

[0039] 在本发明中，六角网格层次细节绘制按照如下机制进行。当相机位于很远处时，每 个网格单元在屏幕上缩小到某种程度，如仅相当于一个像素时，可以用一个点来代替一个 单元/边。此时，N个六角网格单元的显示数据就可以简化为N个点，6N条边的显示数据可以 简化为6N个点。而当相机进一步拉远，如4个六角单元的大小仅相当于一个像素时，可以用 这4个单元中的一个单元的某个顶点来代替这4个六角单元。这样，N个六角网格单元的显示 数据就被简化为N/4个顶点，6N条边的显示数据被简化为6N/4个顶点。以此类推，可以生成 若干个层次的LOD数据，以确保不论显示缩放比例如何，传递给显卡的用于绘制的图元数都 不会超过〇 (η)，n为屏幕像素数量。

[0040] 由于高等级（即简化比例更大的)LOD所需的数据为低等级LOD数据的子集，因此可 以将所有LOD数据放在一个大的顶点索引数组中，并当需要调用不同级别LOD数据时，在 glDrawElements 〇中传递不同的数组大小即可。以这种方式组织LOD数据可有效消除存储 冗余，降低内存开销。

[0041] 下面，将结合图例进行说明。图3展示了一个4*4的六角网格。每个单元的编号标记 于单元的左上角，面材质(A或B)标于单元中心。LOD等级分为0、1、2三级。每一级别中需要绘 制的单元以阴影填充。为表述清晰，在此例中以单元索引代替顶点索引进行说明。Bu f f e r A 和BufferB数组分别为材质A和B对应的LOD面索引数组。LengthA和LengthB数组分别为材质 A和B对应的LOD面索引长度数组。当LOD等级为2时，仅单元15需要显示，其材质为B，于是 LengthA[2] =0，LengthB[2] =l，BufferB[0] =15。当 LOD 等级为 1 时，显示单元 15、13、7、5， 面材质分别为B、B、B、A。于是 LengthA[l] =1，LengthB[l] =3，BufferA[0] =5，BufferB[l] =13，BufferB[2] =7 (单元15已被记录，不再重复记录）。当LOD等级为0时，所有单元均要被 显示，对应LengthA [0] = 9，LengthB [0] = 7。对于Buf f er数组所有记录过的单元索引均不重 复记录。于是，BufferA [1]至BufferA [8]分别记录 12、11、10、9、4、2、1、0; BifferB [3]至 BufferB[6]分别记录14、8、6、3。至此，完成按照面材质设置的LOD面索引数组。绘制时，若 LOD等级为2，LengthA [2] = 0，即材质A没有单元需要绘制;LengthB [2] = 1，即取Buff erB的1 个元素绘制，也就是绘制单元15。若LOD等级为I，LengthA[l] = 1，即取BufferA的1个元素绘 制，于是绘制单元5 ;LengthB [1] =3,即取BufferB的3个元素绘制，于是绘制单元15,13,7。 类似地可处理LOD等级0。

[0042] 4)计算需要使用的LOD级别。若不使用LOD绘制，即正常绘制，则绘制当前拼接块内 的全部六角单元。方法是用glDrawElements 〇函数逐个绘制每种面材质的面顶点索引数 组;再逐个绘制每种边材质的边顶点索引数组。若需要使用低细节层次绘制，则仅绘制当前 L㈤级别的单元。方法是用glDrawElements 〇函数逐个绘制每种面材质的LOD面顶点索引 数组;再逐个绘制每种边材质的LOD边顶点索引数组。

[0043] 下面是本发明的一些实验数据。在配置有3.4GHz CPU，12GB内存的台式机上对本 发明的性能进行了测试。选择前述的经典六角网格绘制方法作为对比算法。该算法逐一计 算六角网格的每个顶点坐标、绘制每条边、每个面。不根据材质重新组织顶点，绘制每条边、 每个面均单独调用OpenGL绘制函数。并且未使用LOD技术。以其作为基准测试方法，与其他 类似工作的性能对比可由此对比结果推知得到。下表给出了当屏幕分辨率为1680*1050时， 满屏绘制1000*1000个六角网格单元，两种方法的帧速率对比，如表1所示。显然，本发明明 显优于经典方法，绘制速度提高了 一个数量级。

[0044] 表1

[0045]

[0047]提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本 发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修 改，均应涵盖在本发明的范围之内。