包含高度复杂绘制元素的三维场景高性能绘制优化方法

摘要

本发明涉及一种包含高度复杂绘制元素的三维场景高性能绘制优化方法。该方法包括：遍历三维场景绘制系统中所有绘制单元，收集每个绘制单元与绘制相关的状态，并枚举得到由若干状态所构成的状态集合；将所有状态集合中元素的状态参数设置用两个值分别表示，根据每个绘制单元的绘制状态参数设置得到状态编码；将由所有状态参数构成的状态编码作为二进制格雷码，将绘制单元按照格雷码排序，格雷码编码的值相同的绘制单元组成链表结构；依次收集格雷码对应的绘制单元，建立绘制单元的队列；设置所有绘制单元的相同的状态参数；按照绘制单元队列的顺序进行三维场景的绘制。本发明能够对绘制系统中的多种绘制单元的绘制顺序进行调节，提高绘制效率。

说明书

技术领域

本发明属于信息技术、计算机图形与虚拟现实技术领域，具体涉及一种面向包含高度复杂绘制元素的三维场景的高性能绘制优化方法。

背景技术

一个复杂的虚拟现实环境，往往由各种绘制场景元素构成，例如既包含地形，树木，草地，道路，建筑物，窗户(透明)，云，汽车交通工具(金属材料)，水面(深水，浅水)，喷泉，人物(骨骼，蒙皮动画)，飞行器等各种三维物体，又包含火焰，天空大气，雨，雪，雾，炫光，阴影，反射，散射等自然现象。单独针对上述其中一种三维物体或者现象而设计的绘制单元在进行绘制时，其效率可能是高效的。一个绘制单元是指由一定的绘制数据和绘制算法组成，并具有一些确定的绘制状态、参数以及材质纹理参数等，每个绘制算法执行一遍绘制管线的流程。

使用OpenGL图形标准进行任何三维场景的绘制，其绘制单元的执行过程都要遵循绘制(渲染)流水线。一个绘制单元的执行过程就是首先利用OpenGL提供的API接口对GPU的绘制状态进行设置，或者向GPU发送一些特殊的绘制参数(例如GLSL的shader中的各项参数)，或者设置某些材质和纹理参数等，然后向绘制流水线提交几何(顶点)数据，最后由GPU执行绘制指令的过程。这样通过OpenGL的接口，用户为GPU设置了相应的绘制参数和状态，并最终使GPU按照用户需要的方式绘制出正确的渲染结果。发送绘制数据的代码具有和状态设置的代码相同的生命周期，但是由于状态的设置是为了给实现绘制效果提供绘制参数，指定绘制功能，而传送绘制是为了给GPU提供绘制的场景数据对象。在进行场景绘制时，对不同的场景常常具有相同的绘制状态但却需要设定不同的顶点数据源，而具有相同顶点数据的场景却可能需要形成不同的绘制效果。

在包含高度复杂绘制元素的三维场景的绘制过程中，当多个绘制单元一起被绘制时，由于各自绘制的方式不同，在执行绘制的操作流程上可能产生冲突，如一个绘制单元需要开启某种绘制状态，而另外一种绘制需要关闭该绘制状态。当该冲突反复出现时，反复执行这些互相冲突的操作会耗费一定的CPU和GPU时间。不同的绘制单元会设置截然相反的绘制状态，例如在执行绘制透明物体的绘制单元时，利用深度缓冲进行深度测试的状态是启用的， 深度缓冲的状态是禁止写入的；而在进行不透明物体绘制的时候，深度测试的状态仍然是启用，但同时深度缓冲的状态应该设置为允许写入。

高度复杂绘制元素的三维场景在绘制时涉及多种三维物体和多种自然现象的及其对应的多个绘制单元。每个绘制单元的实现都遵循向GPU所管理的显存发送数据，设置GPU运行状态、参数以及材质和纹理等这一流程。而每一次操作都需要耗费CPU和GPU一定的时间，尤其是会消耗CPU的时间，因为每一次操作都会调用一次3D图形绘制的底层接口。但如果相邻两个绘制过程具有相同的操作，就能够省去一次重复的操作，提高绘制效率。

以下面的一个图形系统中各个元素的绘制过程为例：

1.设置绘制状态、参数以及材质1，绘制模型A，

2.设置绘制状态、参数以及材质2，绘制模型B，

3.设置绘制状态、参数以及材质1，绘制模型C。

上述过程包含了三个绘制单元，模型A和C的绘制状态、参数以及材质等信息是相同的，但是模型A和C的绘制并不是在一起的，而是被模型B的绘制打断了，造成绘制状态、参数以及材质1被设置了两次。如果调整其绘制顺序如下：

1.设置绘制状态、参数以及材质2，绘制模型B，

2.设置绘制状态、参数以及材质1，绘制模型A，C。

则按照上述顺序进行绘制的效率要获得提升。因此合理安排场景中绘制单元的绘制顺序对提高绘制效率具有重要的作用。但是在实际绘制系统中，各个绘制单元的操作多种多样，该如何安排绘制单元的执行顺序才能获得最优的性能是整个绘制系统设计的关键。

假设一个绘制单元由包含状态设置指令在内的一系列各种操作构成，假设第i个操作的执行代价为f_i，那么绘制单元k的绘制过程花费的代价F_k为：

$F_k={\Sigma }_{i=0}^n{f}_i---\left(1\right)$

假设在绘制整个场景的绘制系统之中的一遍绘制过程中相邻的两个绘制单元K₁和K₂具有完全相同的一些操作，而这些相同的操作可以为两个绘制单元所共用(如设置绘制状态、参数等)，则执行这两个绘制单元时可以只执行一遍这些相同的操作而无需重复执行，从而节省出一定的时间代价，假设这些因重复而可被省略的操作的执行代价为F_k1k2，那么对于按照顺序依次绘制的N个绘制单元的绘制流程来说，执行所有操作花费的代价总值W为：

$W={\Sigma }_{i=0}^N{F}_{ki}-{\Sigma }_{i=0}^{N-1}{F}_{kiki+1}---\left(2\right)$

由式(2)可以看出对于N个绘制单元的绘制流程来说，如何安排它们的绘制顺序使得最大从而W最小是获得最佳绘制效率的关键。

该问题是旅行商的NP难问题，而解决这一问题的目的就是为了减少绘制系统执行绘制流程的时间，因此不能以花费额外的高昂时间开销为代价进行排序以获得较好的渲染排序结果。Ogre系统(Open Source 3D Graphics Engine,http://www.ogre3d.org/)和Irrlicht引擎(http://irrlicht.sourceforge.net/)采用了以材质信息中的某个参数作为排序的依据，实际上大部分情况下该参数是材质具有的第一个纹理的名称。这种以绘制单元中的某个数据作为参考的较优排序结构的贪心的算法能够迅速得把具有相似的材质的场景放到绘制队列中相邻的位置。其算法复杂度与排序算法的复杂度相同。添加渲染排序模块就是为了提高绘制效率，但同时渲染排序模块本身执行各个绘制单元的管理操作也会增加CPU的时间，所以渲染排序模块本身执行操作一定要高效。

发明内容

本发明的核心思想就是通过添加一个绘制(渲染)排序模块(方法)对一个高度复杂的绘制系统中的多种绘制单元的绘制顺序进行调整，将绘制状态、绘制参数以及材质等相同的绘制单元放置在一起绘制，这样相同的一些绘制操作仅执行一遍即可。同时将状态、参数以及材质等参数值变化较小的绘制单元排序作为相邻的绘制单元，从而减少相邻两个绘制单元之间进行状态切换操作的代价F_k1k2，可以减少冗余的状态参数以及材质等的设置操作，从而提高绘制效率。

本发明采用的技术方案如下：

一种面向包含高度复杂绘制元素的三维场景的高性能绘制优化方法，包括以下步骤：

1)遍历三维场景绘制系统中所有绘制单元，收集每个绘制单元与绘制相关的状态，并枚举得到由若干状态所构成的状态集合；所述状态包括绘制状态、绘制参数以及材质纹理等信息，统一以状态参数来表示；

2)将所有状态集合中元素的状态参数设置用两个值分别表示(例如某个状态参数的启用设置其参数值为1，该状态的禁用则为0；又例如某个参数值的设置可以表示为1，而与该参数无关则可以表示为0；如果无法用二值表示的状态、参数以及材质等不在本发明考虑范围之内)，根据每个绘制单元的绘制状态参数设置得到状态编码，每一个状态参数对应一个二进制位；

3)将由所有状态参数构成的状态编码作为二进制格雷码，将对应的绘制单元按照格雷码排序，格雷码编码的值相同的绘制单元组成链表结构；

4)依次收集格雷码对应的绘制单元，建立绘制单元的队列，该队列由链表形式表示和存储；

5)设置所有绘制单元的相同的状态参数，即不在状态集合中出现的状态参数；

6)按照绘制单元队列的顺序进行三维场景的绘制。

进一步地，步骤6)在执行每个绘制单元时，首先进行绘制状态的更新；绘制结果为生成一帧图像，标记为第j帧；如果绘制系统中绘制单元的数目以及每个绘制单元的绘制状态参数设置不发生改变，则继续绘制第j+1帧，如此循环执行，直至绘制系统运行被终止。

进一步地，步骤6)中，如果绘制单元的数目发生变化，则做如下处理：

a>如果向绘制系统添加了一个绘制单元k_N+1，则首先检查并判定是否引入新的状态，即该绘制单元的所有绘制状态参数是否包含在状态集合中：

a1>如果未引入新的状态位，则说明之前的n个状态位完全覆盖了新绘制单元所涉及的状态，绘制队列不需要做任何变更；

a2>否则需要引入新的状态位，则添加第n+1位二进制位作为新的状态位，并且能够断定：该k_N+1绘制单元的第n+1个状态位的值与其它N个绘制单元的第n+1位的值不同；

b>如果去除了一个绘制单元k，则检查判断是否需要从状态集合I中删除某些状态，检查方法为对其余N-1个绘制单元的n个状态所对应的状态位的值进行逐一比较。

进一步地，步骤6)中，如果某一个绘制单元k的状态参数i_q所对应的状态发生改变，则修改其格雷码，其对应状态位的值由0→1或者由1→0；具体方法是：首先检查N个绘制单元的该状态位的值是否都相同，即都是1或者0；如果相同，则该状态i_q从状态集合I中删除；并作如下步骤的操作：把所有N个绘制单元的格雷码中i_q所对应的位的值设置为0，并将该位左边所有数位统一右移一位，格雷码的位数减1变为n-1。

本发明的有益效果如下：

本发明提出一种基于格雷码形式的绘制单元优化排序方法，N个绘制单元的排序复杂度为O(N)，排序之后获得的益处首先是把具有相同的绘制状态、参数以及材质等的绘制单元组成一组一起绘制，其状态参数的值只需要设置一次即可对该绘制单元组生效；其次相邻两个状态参数的值存在差异的绘制单元的绘制状态参数的差异理想状况下为1个(当N＝2ⁿ-1时，n为格雷码的位数，且每个绘制单元的状态编码恰好彼此不同时)，即每个绘制单元每次仅仅执行一个状态参数的设置操作(因为除了该状态参数外，其它状态参数等都与上一个绘制单元相同，无需重新设置)。这样本发明的优化排序算法可以大大节约每个绘制单元设置状态参数的时间开销。三维场景的实时绘制的一帧对应的是一遍执行完绘制任务所对应的所有按顺序排列的绘制单元，下一帧将重复执行这些按顺序排列的绘制单元，即三维场景的绘制系统循环执行绘制单元的任务。由于格雷码是一种循环格式的编码，因此本方法的另外一个优势就是，从一帧结束时的绘制状态至下一帧开始时的绘制状态，其差异通常为1个，即绘制状 态仅仅需要通过执行一个状态参数设置操作即可。这样又进一步减少了绘制系统的时间代价。

附图说明

图1是本发明方法的整体流程图。

图2是根据格雷码组织所有绘制单元(以四位格雷码为例)的示意图。

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面通过具体实施例和附图，对本发明做进一步说明。

本发明的面向包含高度复杂绘制元素的三维场景高性能绘制优化方法，其整体流程如图1所示，具体包括以下步骤：

1.三维场景绘制系统启动；

2.遍历所有N个绘制单元K＝{k₁,k₂,…k_N}，收集每个绘制单元的状态，所述状态包括绘制状态、绘制参数以及材质纹理等信息，统称为状态参数，并枚举得到n个状态所构成的状态集合I＝{i₁,i₂,i₃,…i_n}，说明除了这n个状态参数之外，余下的绘制状态、绘制参数、材质纹理，所有N个绘制单元皆保持一致；

3.所有状态集合中元素的状态参数设置由两个值分别表示：开启(启用)、关闭(禁用)，分别编码为1和0，其它状态参数设置只要其值能够用两个不同的值表示也可以(例如绘制多边形的模式分为线框模式和填充模式两种)；根据该条件计算每个绘制单元k的绘制状态参数设置，得到状态编码，每一个状态对应一个二进制位；

4.将该编码看做二进制格雷码，将对应的绘制单元按照格雷码排序，格雷码编码的值相同的绘制单元组成链表结构；如果两个绘制单元A和B对应完全一样的格雷码，则两个绘制单元的先后顺序无关紧要。该步骤的具体实现如下(如图2所示)：

4.1建立数组元素数目为N的数组；

4.2遍历每个绘制单元k，得到其格雷码G_k，并将格雷码转换为自然码A_k；可参照后文表1的四位格雷码与自然码的对照表；

4.3如果数组的第A_k个元素中的值为空，则将绘制单元k的指针放入数组的第A_k个元素中，作为该数组元素的值；

4.4如果数组的第A_k个元素中的值不为空，则根据该数组元素所指向的链表的末尾遍历，并将绘制单元k的指针放入该链表的末尾。

5.从数组的第一个元素开始，依次收集格雷码对应的绘制单元，建立最终高效率的绘制 单元的队列Q，该队列Q由链表形式表示和存储；

6.设置所有绘制单元的相同的状态参数的值(即不在状态集合I中出现的状态参数，对于所有绘制单元，这些状态参数均相同)；

7.然后绘制系统按照绘制单元队列Q的顺序依次执行进行绘制，在执行每个绘制单元的绘制算法时，首先进行绘制状态的更新(往往只有一个绘制状态的切换)；绘制结果为生成一帧图像，标记为第j帧；

8.如果绘制系统中绘制单元的数目以及每个绘制单元的绘制状态参数设置不发生改变，则将继续绘制第j+1帧(第j+1帧的开始状态与第j帧的结束状态相比，由于第j+1帧的第1个绘制单元与第j帧的第N个绘制单元的绘制状态参数的值相差位仅仅为1位(理想状态下)，即状态的差异仅仅只有一项，则仅仅需要更新一种状态就可以进行正确的绘制了)，循环执行步骤7；

9.如果绘制单元的数目发生变化：

9.1如果向绘制系统添加了一个绘制单元k_N+1，则首先检查并判定是否引入新的状态，即该绘制单元的所有绘制状态参数是否包含在状态集合I中(含n个集合元素所代表的状态参数)。

9.1.1如果未引入新的状态位，则说明之前的n个状态位完全覆盖了新绘制单元所涉及的状态参数，绘制队列Q不需要做任何变更；

9.1.2否则需要添加该状态参数作为元素到状态集合I中(集合元素数变更为n+1)，同时引入新的状态位，则添加第n+1位二进制位作为新的状态位，并且可以断定：该k_N+1绘制单元的第n+1个状态位的值与其它N个绘制单元的第n+1位的值不同。因为如果其它N个绘制单元的第n+1位如果存在不同的话，那原本就应该有n+1个状态位来表示这N个绘制单元，这样就产生矛盾。例如：如果该绘制单元k_N+1的第n+1状态位值为0，即禁用状态，则其它N个绘制单元的该位的值一定为1；

1)如果该绘制单元k_N+1的第n+1状态位值为0，则将该编码位放置于其格雷码编码的最高位，即0******(*代表原先其它编码位的值，*的个数为n个)，并将其它N个绘制单元的格雷编码位的最高位置为1；同时只需要将绘制单元k_N+1插入绘制队列Q的头部，即作为第一个单元进行绘制。因为根据格雷码原理，其它N个绘制单元的编码都大于当前这个绘制单元k_N+1的编码，同时这N个绘制单元的绘制先后顺序维持不变；

2)如果该绘制单元k_N+1的第n+1状态位值为1，则将该编码放置于格雷编码的最高位，即1*****(*代表其它编码位的值，*的个数为n个)，并将其它N个绘制单元的格雷编码位的最高位置为0。同时将绘制单元k_N+1插入绘制队列Q的尾部，即作为最后一个单元进行绘制。因为根据格雷码原理，其它N个绘制单元的编码都小于当前这个绘制单元k_N+1的编码，同时这N个绘制单元的绘制先后顺序维持不变；

9.1.3返回步骤6；

9.2如果绘制系统中某一个绘制单元k被去除，则首先检查判断是否需要从状态集合I中删除某些状态参数，检查方法为对其余N-1个绘制单元的n个状态参数所对应的状态位的值进行逐一比较(需要进行n次)；

9.2.1如果存在某一个状态参数i_p及其对应的格雷码状态位，N-1个绘制单元的该状态位的值都相同(即都是1或者都是0，实际实施可以通过位运算计算出)，则该状态参数i_p可以从状态集合I中删除；并作如下步骤的操作：

1)把所有N-1个绘制单元的格雷码中i_p所对应的位设置为0，并将该位左边所有数位的值统一右移一位，格雷码的位数减一变为n-1；

2)将相应的绘制单元从队列Q中删除，可以通过链表结点删除实现，其它绘制单元的顺序无需做任何调整，这也是格雷码的非常大的优点；

9.2.2继续执行9.2.1，直至所有n个状态参数全部检查完毕；

9.2.3如果不存在需要删除的状态参数，则直接找到绘制单元k在Q队列中的位置，并将其从链表结构中删除。

9.2.4返回步骤6；

10.如果某一个绘制单元k的状态参数i_q所对应的状态发生改变，则修改其格雷码，其对应状态位的值由0→1或者由1→0；

10.1首先检查N个绘制单元的该状态位的值是否都相同(即都是1或者0，可以通过位运算计算出)；

10.2如果相同，则该状态i_q可以从状态集合I中删除；并作如下步骤的操作：把所有N个绘制单元的格雷码中i_q所对应的位设置为0，并将该位左边所有数位统一右移一位，格雷码的位数减一变为n-1；返回步骤6；

10.3无论是否相同，绘制单元的顺序都无需做任何调整，这也是格雷码的非常大的优点(因为格雷码确保相邻两个编码之间只有一个二进制位的变化，当前绘制单元状态编码G_k→G_k’的改变只发生在一个二进制数位上，则当前绘制单元修改 之后的编码G_k’或者等于G_k-1或者等于G_k+1)；

10.4如果不同则直接返回步骤7；

11.绘制系统结束。

下面进一步说明实施例的实现细节。

3D图形的标准编程API OpenGL采用一种状态机机制。可以设置它的各种状态(或模式)，然后让这些状态一直生效，直到再次修改它们的值。例如当前颜色就是一个状态变量(等价于上述内容中的状态参数)，可以把当前颜色设置为白色、红色或其他任何颜色，在此之后绘制的所有物体都将使用这种颜色，直到再次把当前颜色设置为其他颜色。当前颜色只是OpenGL所维护的许多状态变量之一。其他的状态变量还有很多，并且有着各自的用途，例如控制当前视图和投影变换、直线和多边形点画模式、多边形绘图模式、像素包装约定、光照的位置和特征以及被绘制物体的材料属性等。许多表示模式的状态变量可以用glEnable()和glDisable()函数进行启用和禁用。

如果使用可编程的着色器，根据所用的OpenGL版本的不同，着色器所能识别的状态的数量也有所不同。每个状态变量(或模式)或者参数都有一个默认值。在任何时候都可以向系统查询每个状态变量的当前值。一般情况下，可以使用下面这6个函数之一来完成这个任务：glGetBooleanv()、glGetDoublev()、glGetIntegerv()、glGetfloatv()、glGetPointerv()或glIsEnabled()。具体选择的函数取决于希望返回的结果的数据类型。有些状态变量还有更为特定的查询函数(例如glGetLight*()、glGetError()或glGetPolygonStipple()等)。另外，还可以使用glPushAttrib()、glPushClientAttrib()函数把状态变量的集合保存到一个属性栈中，对它们进行临时的修改，以后再用glPopAttrirb()或glPopClientAttrib()恢复这些值。如果需要对状态变量进行临时修改，就应该使用这些函数，而不是使用任何查询函数，因为前者的效率更高。

对OpenGL状态设置的代码每次被调用后，如果没有其它状态设置的代码运行，那么就其效果就可以一直生效，不用每一帧都重复调用。

表1.四位格雷码与自然码对照表

以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。