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

摘要

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

权利要求

1.一种基于分块组织的多层次兵棋地图快速绘制方法，其特征在于步骤包括：

(1)创建模板块，计算模板块中所有顶点位置并存储；所述模板块为：创建在X，Y轴方向上的六角单元个数均为k的六角网格作为模板块，k为2的整数倍，模板块中的每个单元均为正六边形；

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

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

2.根据权利要求1所述的基于分块组织的多层次兵棋地图快速绘制方法，其特征在于所述步骤(1)具体实现如下：(11)创建在X，Y轴方向上的六角单元个数均为k的六角网格，作为模板块，k为2的整数倍，该模板块中的每个单元均为正六边形，模板块的最小轴向包围盒的左下顶点坐标为(0,

0)，依次计算每个单元的六个顶点坐标，计算顺序设置为从左到右，从下到上处理每个单元；在每个单元内部，则是自左下顶点开始按照逆时针顺序计算所有6个顶点；

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

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

3.根据权利要求1所述的基于分块组织的多层次兵棋地图快速绘制方法，其特征在于：

所述步骤(2)具体实现如下：计算绘制整个兵棋地图六角网格在X、Y方向上所需的拼接块数量，方法是：设所需绘制的六角网格在X、Y方向上的分辨率分别为W和H，令拼接块在X、Y方向上平铺相邻排列，则拼接块在X、Y方向上的数量分别为 和 拼接块中超出所需绘制范围的单元一律设置为透明材质，绘制时不显示。

4.根据权利要求1所述的基于分块组织的多层次兵棋地图快速绘制方法，其特征在于所述步骤(3)具体实现如下：(31)设置当前拼接块相对于模板块的平移、缩放参数，使用OpenGL坐标变换矩阵，得到当前拼接块的顶点位置坐标；

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

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

(34)若正常绘制，则用glDrawElements()函数逐个绘制每种面材质的面顶点索引数组；再逐个绘制每种边材质的边顶点索引数组，若需要使用低细节层次绘制，则仅绘制当前LOD级别的单元，即用glDrawElements()函数逐个绘制每种面材质的LOD面顶点索引数组；

再逐个绘制每种边材质的LOD边顶点索引数组。

说明书

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

技术领域

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

背景技术

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

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

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

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

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

发明内容

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

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

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

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

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

[0012] 所述步骤(1)具体实现如下：

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

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

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

[0016] 所述步骤(2)具体实现如下：计算绘制整个兵棋地图六角网格在X、Y方向上所需的拼接块数量。方法是：设所需绘制的六角网格在X、Y方向上的分辨率分别为W和H，令拼接块在X、Y方向上平铺相邻排列，则拼接块在X、Y方向上的数量分别为 和 拼接块中超出所需绘制范围的单元一律设置为透明材质，绘制时不显示。

[0017] 所述步骤(3)具体实现如下：

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

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

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

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

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

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

附图说明

[0024] 图1是本发明的模板块示意图与对应的顶点位置数组；

[0025] 图2是本发明的拼接块示意图；

[0026] 图3是本发明的LOD顶点索引数组组织方式示意图；

[0027] 图4是本发明的流程图。

具体实施方式

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

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

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

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

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

[0033] 图1展示了一个k＝4的模板块及其对应的顶点数组。图1中，标记在每个单元中心的数字为该单元的顺序号。单元0和单元1的顶点以v0至v11标记。按照如上所述的计算方法，单元0六个顶点的坐标分别为：v0( 0),v1( 0)，v2(2λ, )，v3( )，v4( )，v5(0, )。

[0034] 在第二阶段，根据所需绘制的六角网格的分辨率，确定所需的拼接块在X、Y方向上的块数。确定方法是：设所需绘制的六角网格在X、Y方向上的分辨率分别为W和H，令拼接块在X、Y方向上平铺相邻排列，则拼接块在X、Y方向上的数量分别为 和 图2展示了一个拼接示例，其中W＝14，H＝7，k＝4。为显示清晰，相邻块以不同颜色来区别显示。所需绘制的六角网格边界单元以斜线填充。则X、Y方向上的块数分别为4和2。超出所需绘制范围的单元一律设置为透明材质，绘制时不显示，如在图2中X方向上大于14、Y方向上大于7的单元。

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

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

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

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

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

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

[0041] 下面，将结合图例进行说明。图3展示了一个4*4的六角网格。每个单元的编号标记于单元的左上角，面材质(A或B)标于单元中心。LOD等级分为0、1、2三级。每一级别中需要绘制的单元以阴影填充。为表述清晰，在此例中以单元索引代替顶点索引进行说明。BufferA和BufferB数组分别为材质A和B对应的LOD面索引数组。LengthA和LengthB数组分别为材质A和B对应的LOD面索引长度数组。当LOD等级为2时，仅单元15需要显示，其材质为B，于是LengthA[2]＝0，LengthB[2]＝1，BufferB[0]＝15。当LOD等级为1时，显示单元15、13、7、5，面材质分别为B、B、B、A。于是LengthA[1]＝1，LengthB[1]＝3，BufferA[0]＝5，BufferB[1]＝13，BufferB[2]＝7(单元15已被记录，不再重复记录)。当LOD等级为0时，所有单元均要被显示，对应LengthA[0]＝9，LengthB[0]＝7。对于Buffer数组所有记录过的单元索引均不重复记录。于是，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，即取BufferB的1个元素绘制，也就是绘制单元15。若LOD等级为1，LengthA[1]＝1，即取BufferA的1个元素绘制，于是绘制单元5；LengthB[1]＝3，即取BufferB的3个元素绘制，于是绘制单元15,13,7。类似地可处理LOD等级0。

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

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

[0044] 表1

[0045]

[0046]

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