基于游戏引擎和GPU并行处理的分形图生成与渲染方法

摘要

基于游戏引擎和GPU并行处理的分形图生成与渲染方法，本发明涉及图像游戏引擎中GPU并行处理技术领域，其旨在解决现有技术存在图像数据信息划分不合理，并行处理与同步操作等命令结构设置局限以导致渲染性能和效率低下，无法满足实时渲染的性能需求等技术问题；并且，本发明提出新的技术问题，具体是，在游戏引擎中，对于同时通过并行使用两个以上分形算法获得高效、高质量的图像渲染如何实现。构建基于分形特征的软件渲染生成算法；利用GPU并行处理技术实时处理分形图几何特征，利用控制流指令并行算法优化渲染生成管线，实现对分形图模型的快速生成与渲染，达到在用户PC机中快速、准确的显示效果。

说明书

技术领域

本发明涉及图像游戏引擎中GPU并行处理技术领域，具体涉及在游戏引擎中一种基于GPU并行处理的分形图生成算法和实时渲染技术的开发与优化。

背景技术

自然界中诸多自然图形都以非常复杂且不规则的方式存在和变化，随着计算机虚拟化、视觉化、快速化的计算进程加快，处理图形数据规模越来越大，渲染性能与质量的需求急速上升，并已成为游戏引擎技术中的瓶颈。今天，游戏场景日趋复杂化和规模巨大化，产生的海量数据已进入并行处理的计算时代，单纯依靠增加图形处理器数量来提高渲染性能与质量不是一个好的方法，提高图形实时渲染性能与质量的优化方法值得研究。游戏引擎中基于GPU并行处理技术来解决图形的快速生成与渲染是一种可行方案，本发明融合了GPU并行处理、分形算法、实时渲染技术，实现在游戏引擎中高效生成分形图及其快速渲染。

本发明主要完成分形图绘制、表面纹理组合以及渲染等工作，核心内容是对场景图中的分形结构和渲染节点信息按多边形网格进行任务划分、通信、组合和映射。其中，对场景图数据信息的划分必须做到信息量大且网格精细。传统场景图数据信息的划分方式有其局限性，不能够很好满足图形实时渲染的性能需求。

基于GPU并行处理的内存对象通信是通过局部/全局、结构化/非结构化、静态/动态、同步/异步通信方式，获取游戏场景中各种任务网格的渲染信息，结合线程束同步指令、控制流同步指令等并行算法进行信息传送与控制。采用基于GPU异构并行计算技术对图像对象信息并行处理，提高分形图生成与渲染的运算能力，实现游戏引擎中分形图的快速生成与渲染。实时渲染GPU并行处理是将数据并行、数据融合、指令并行、线程并行、同步指令、控制流同步指令、并行归约、线程束同步等技术相互协作，利用GPU内核编程在游戏引擎建立计算效率高、精准性好的数据控制流水线并行计算模式和渲染生成架构。

随着当今实时计算图形处理技术快速发展，传统单一化引擎设计模式已无法满足各大型游戏中增加场景特效、虚拟仿真等高性能计算需求。游戏引擎中开发二维分形图生成与渲染环境具有效果直观、构架简单、成本低廉等优点，可作为面向3D实时渲染GPU并行处理的游戏引擎开发实验平台，进行实时渲染、并行计算、分形图生成等方面的研究，可利用并行算法验证和实现多种多样的分形图生成与渲染控制、性能优化。基于此方法，可以满足游戏引擎开发向多元化发展的需求。另外，GPU并行处理的实现方法具有很好的扩展性，对提高开发人员的创新意识，促进图形学处理技术的快速发展等都很有意义。

值得注意地，在游戏引擎中，树木等植被的图像渲染，现有技术通常选用调用简单几何图形库通过重复贴图进行边界拟合，再进行着色操作，但渲染效果和处理效率很是令人失望，并且占用大量系统资源；主要原因是，植被形态学本质特征决定了贴图拟合无法实现较好的效果；进而，较好的解决方案就是分形图渲染；有少数使用单一分形算法进行植被渲染，然而同样存在效率低下，命令结构受限制的问题；需要特别提出地是，根据渲染对象，简单组合分形算法与单一分形算法效能相比并没有提高，其中处于工作的仅有一种分形算法，其余均处于同步等待。本发明利用节点思想，通过在图像分割域中设置图形节点和在不同处理任务中设置任务节点，从而实现了多个分形算法同时通过图形处理器并行处理利用。

发明内容

针对上述现有技术，本发明目的在于提供基于游戏引擎和GPU并行处理的分形图生成与渲染方法，其旨在解决现有技术存在图像数据信息划分不合理，并行处理与同步操作等命令结构设置局限以导致渲染性能和效率低下，无法满足实时渲染的性能需求等技术问题；并且，本发明提出新的技术问题，具体是，在游戏引擎中，对于同时通过并行使用两个以上分形算法获得高效、高质量的图像渲染如何实现。

为达到上述目的，本发明采用的技术方案如下：

基于游戏引擎和GPU并行处理的分形图生成与渲染方法，包括在主机端，读取运行环境，创建图像缓存，再调用语言程序创建图像对象；在主机端，编译关于图像对象的内核程序，并在设置内核参数后，将内核程序发送至设备端；在设备端，在内核初始化后，根据内核程序，同步线程束并执行控制流指令操作，其中控制流指令操作：依次包括场景图多边形网格计算并进行图形节点设置，任务划分，图形对象数据流通讯并进行任务节点设置，递归算法分形图生成、IFS算法分形图生成与L系统算法分形图生成，纹理映射和渲染计算；在设备端，根据渲染计算的结果，判断动态负载是否均衡，如果动态负载不均衡，依次进行场景图更新操作、拷贝至图像缓存与内核执行并行归约操作，并根据内核执行并行归约操作的结果，再次进行判断动态负载是否均衡，从而进行循环操作；在设备端，当动态负载均衡时，并行渲染计算的结果，再释放图像对象至主机端。本发明还能够整合更多经典分形算法以实现更极致的图像渲染效果。

上述方案中，优选地，所述的主机包括中央处理器，所述的设备包括图形处理器。

上述方案中，所述的场景图多边形网格计算，包括执行数据分解功能的域分解，将复杂分形数据分解近似相等的小数据块图形并设置图形节点；所述的任务划分，包括按照可并行计算的图形节点划分，进行不同层次的功能分解，再将若干个相互独立分形数据的图形节点进行并行渲染计算以及进行渲染顶点的快速计算。

上述方案中，所述的图形对象数据流通讯，包括在任务划分后，形成的固定任务之间设置任务节点，并根据数据流并发执行任务节点，主要利用任务独立节点间的数据通信同步与线程并行的内核函数异步执行功能完成，也完成同步任务的并行执行和数据流的并发控制。

上述方案中，所述的递归算法分形图生成，包括通过三分集形成原理计算三分集的递归算法和模拟树分形形态，设定分形元和改变分形元的偏转角度，在显示区域内生成koch曲线，实时绘制分形图，并进行分形图动态细分曲面着色计算；其中，递归算法分形图还设置二维分形图场景图节点。

上述方案中，所述的二维分形图场景图节点，包括通过优化的L系统生成算法和优化的IFS分形算法获得的二维分形图场景图节点，实现控制二维分形图绘制和实时渲染的计算过程。

上述方案中，优选地，所述的IFS算法分形图生成，通过Sierpinski迭代和仿射变换系数，完成分形图的自相似特点生成，完成分形图实时绘制与渲染，获取游戏引擎中粒子系统的分形图生成渲染管线。

上述方案中，优选地，所述的L系统算法分形图生成，包括单规则L系统分形图生成和多规则L系统生成分形图生成。

上述方案中，所述的纹理映射，包括固定在简单纹理坐标上的立方映射；进一步包括随着镜头移动而更新环境映射，即根据周围环境颜色变化计算物体表面颜色的映射；进一步包括由网格三角形顶点确定的，增加细节纹理计算的法线映射；进一步包括一种投纹理映射，将物体表面的所有三角形的纹理坐标，通过一系列图形变换，把物体坐标转换到投影空间坐标；还包括一种阴影映射，以光源点作为摄像头位置进行渲染场景，结合观察点作为摄像头位置进行正常渲染，在像素着色器中输出的深度来判断是否需要在像素上增加光照颜色。GPU顶点着色器完成这些映射与环境渲染插值计算，最后完成不在顶点像素最终位置的像素着色器纹理采样及环境渲染的深度预测。

上述方案中，所述的渲染计算，包括在OpenCL语言程序中，按照稀疏表和线段树结构加速优化场景图的数据结构，同步执行两个以上的内核函数，同时保持数据传输的异步执行，使分形图图像缓存快速加入渲染任务队列；渲染后的图像缓存在设备端完成原子操作和并行归约混合操作；执行OpenCL与运行环境中的DirectXAPI互操作；从DirectX上下文创建OpenCL上下文，使用DirectX共享图像缓存中的图像对象，同时传输纹理数据至图像对象；最后OpenCL共享DirectX渲染图像缓存。实现控制流同步指令并行操作的内核。

与现有技术相比，本发明有益效果：

(1)显著突出地并实质进步地，通过在图像分割域中设置图形节点和在不同处理任务中设置任务节点，进一步实现了多个分形算法同时通过图形处理器并行处理利用，从而获得了通过简单组合分形算法所不能够实现的高速、高质量图像渲染。

(2)本发明专利是在游戏引擎中一种基于GPU并行处理的分形图生成和渲染方法，能够快速生成并实时渲染各种复杂分形图场景元素，以更加直观、快速的方式对分形图生成算法进行控制，对图形节点信息实时渲染计算，通过利用并行算法让计算机处理器运转更节省时间。重点是在游戏引擎中引入分形图生成与渲染优化方案，实现了更加自然、真实、快速的渲染生成效果。在2D/3D引擎中模拟各种复杂且非规则分形图的生成与渲染，能更方便获取大量有价值的引擎处理方法和场景元素数据，为分形图生成控制及快速渲染的研究提供支持。

(3)本发明专利基于GPU并行处理分形图生成与渲染方法。分形图渲染通过场景图数据结构优化加速，实现光照映射和快速渲染各种复杂的场景图形元素。具体通过分形图L系统算法将光照实时映射到处理器计算单元中，经过一系列同步指令并行融合和流数据并行控制决策，实现在PC客户端对整个分形图渲染的着色信息实时控制、快速显示，实现了在游戏引擎中分形图实时生成与渲染，同时优化了分形图实时渲染性能，提高了游戏场景元素绘制的高效性与多样性。通过GPU并行处理方式在游戏引擎中实现分形图快速生成与渲染，简单讲是将图形几何信息包括点、线、多边形、分形图并行处理，快速实现计算的过程，GPU与CPU共同协作，充分发挥异构并行计算的优点，提高了图形渲染的时间效率与管理水平，真正的实现引擎快速可视化。

附图说明

附图1基于OpenCL并行归约和线程束同步的控制流同步指令优化算法流程图。

附图2可编程实时图形流水线中着色处理流程图。

附图3基于OpenCL并行归约和线程束同步的控制流同步指令优化算法的GPU内核函数实现流程图。

附图4生成二维水草的流程图。

附图5Sierpinski垫片生成流程图。

附图6Sierpinski垫片生成效果(IFS)图。

附图7L系统算法流程图。

附图8单规则L系统分形效果图。

附图9正弦波替代直线生成二维分形图。

附图10正切函数取代两点间直线的二维分形图。

附图11圆形取代直线的水草图。

附图12植物形态分形图模拟效果图。

附图13圆形取代直线的二维图。

附图14同一规则下角度随机生成(0～20°)分形图。

附图15角度不变规则随机生成分形图。

附图16规则角度(直线)均随机生成的分形图。

具体实施方式

本说明书中公开的所有特征，或公开的所有方法或过程中的步骤，除了互相排斥的特征和/或步骤以外，均可以以任何方式组合。

下面结合附图对本发明做进一步说明：

本发明专利是在游戏引擎中设计一种基于GPU并行处理的分形图生成和渲染方法，以OpenSceneGraph图形引擎和Cocos2d-x、Unity3d游戏引擎系统为开发平台，搭建GPU并行处理的分形图生成与渲染架构，实现分形模型对象的信息任务划分、数据流通信、图像缓存存储、组合与映射。基于OpenCL异构并行计算平台，对生成分形图的L系统算法进行改进与优化，使用VC++2013调用DirectX图形库进行实验，实验证明了本改进算法的可行性。另外，在游戏引擎中构建异构并行计算平台较简单且易调整，对于多种复杂且不规则分形图的生成与渲染较易快速实现，也便于进行多种不同环境的实验。

所述分形图生成与渲染方法，以二维分形图生成算法为基础，基于GPU并行处理模式，构建参数可控的计算架构，融合并行技术、分形图算法和DirectX技术，完成图形引擎平台开发与优化。分形图渲染，重点包含平行光、反射光、漫反射、点光源等，在GPU并行处理环境下执行具有较高性能。

所述分形图生成与渲染方法，还包括L系统算法生成规则，研究影响L系统生成分形图的几大要素，通过实验研究这几大因素对L系统算法生成分形图有哪些影响，针对不同类型的L系统算法进行改进工作。

图1基于OpenCL并行规约和隐式同步的线程束同步控制流指令优化算法流程图。控制流指令并行算法即通过原子操作与并行规约混合操作，以及融合隐式同步的线程束同步下多kernel函数执行和数据流异步传输，实现分形图在GPU异构并行环境下快速生成与渲染。

图2可编程实时图形流水线中着色处理流程图。流水线用到顶点处理器和片元(像素)处理器，可编程顶点处理器执行顶点着色程序，可编程片元处理器执行像素着色程序。顶点处理阶段和像素(片元)处理阶段之间有一个光栅处理器即一个复杂状态机，确定哪些像素位于几何图元边界上。渲染算法执行单个几何图元的输入，并采用高度一致的方式访问其他存储器资源，即同时访问连续存储器的位置如所有相邻三角形图元或相邻像素点。

图3基于OpenCL并行归约和线程束同步的控制流同步指令优化算法的GPU内核函数实现流程图。采用细粒度并行的控制流水线指令并行计算模型，全局光照模型并行计算正好与OpenCL并行任务网格模型相映射，每个工作项对应控制流指令优化算法中的每个渲染任务网格并独立计算，划分的图形网格数量对应索引空间来指定生成的工作项数目。通过多线程执行Direct3D缓存图像对象实现指令并行。内核程序进行指令多发射操作与分支预测，同时，执行并行归约预判全局内存和共享内存的访存计算量，图形缓存对象执行控制流指令并行，执行内核函数的渲染计算。并行操作内核函数时，判定最大化流水线并行执行和数据并行执行的概率。

图4生成二维水草的流程图。根据L系统算法生成二维分形图，可看成一个人在马路上行走。当一个人在十字路口的时候，出现方向选择，向左或向右前进，每一时刻行走的状态，用字母F表示向前行进，用“+”、“-”表述向左、向右拐弯。L系统算法绘制规则如下：

F：以人的面向为方向，前进一步，画出线段；

+：向左旋转90°；

-：向右旋转90°；

[:将当前信息压栈；

]：将“[”时刻的信息出栈。

以简单的生成一幅二维分形水草图为例。设定初始字符“F”；生成规则只需一条即：

F→F[+F]F[F][-F+F]，旋转角度设为10°。

图5sierpinski垫片生成流程图。IFS算法生成二维分形图，通过sierpinski迭代和仿射变换系数实现分形的自相似。

图6sierpinski垫片生成效果(IFS)图。IFS算法生成二维分形图的主要思想是获取自仿射系数，通过概率选择生成所需要的分形图。IFS码的参数很多，任意对某个参数进行改动，都会使分形图发生变化。因此，IFS码极为重要，决定了二维分形图的基本形状。

图7L系统算法流程图。实际应用中的图形仿真，不会都形如图6那样，没有交叉点或间断点。从L系统原理着手，通过多加入几个行走方向，行走角度不固定为90°即适当改变行走角度，适时加入“[”和“]”等手段即可实现。

图8单规则L系统分形效果图。例如，生成规则：F→F[-F][+F][--F]F[++F]F

步骤1：F

步骤2：F[-F][+F][--F]F[++F]F

步骤3：F[-F[-F][+F][--F]F[++F]F][+F[-F][+F][--F]F[-F][+F][--F[-F][+F][--F]F[++F]F]F

[++F]F[++F]F[-F][+F][--F]F[++F]F][--F]F[++F]F

步骤4：……

以上几个步骤可以看出，字符串生成速度非常快。对最终生成的字符串，按照每个字符的几何解释作图，可得需要的二维分形图。

图9正弦函数取代直线生成二维分形图。在(x₁,y₁)和(x₂,y₂)两点间画n个正弦波，设两点欧氏距离为d,，周期为T＝d/n。曲线可由若干直线段去逼近，直线段数越多，逼近误差越小。画正弦曲线时取足够多点，这些点坐标通过y＝Asinx得出，连接这些点形成正弦曲线。取得点越多越接近正弦曲线，但是点数太多会降低时间效率，因此需要合理选择点数。图9，以F→F[+F]F[F][-F+F]为例，观察生成的图形用来模拟海藻类植物效果更佳，在虚拟植物形态模拟或者园林规划中可以用这种方法进行设计，使植物形态更逼真。

图10正切函数取代直线生成二维分形图。与正弦函数类似，将正弦改成正切函数即可，由于正切函数y＝tanx定义域是{x|x≠kπ+π/2,k∈Z}而非R，特别注意：正切图形是间断的而非连续的。针对商品防伪，可采用正切函数取代直线，如此改进的L系统算法可以实现对图形的模糊化处理。

图11圆形取代直线的水草图。调用Direct3D图形库，用折线逼近法绘制圆。由图可见，用圆形替换两点间的直线来模拟藻类植物的自然特征是不尽理想的。但L系统算法可以模拟很多奇特的二维分形图如万花筒、三角垫片、花纹等等，只要对L系统算法的生成规则进行一定改进即可生成。

图12植物形态分形图。两点间闭合曲线和直线组成，默认渲染为黑色(可调)。

图13圆形取代直线的二维图。用圆取代两点间直线，在两点间画n个圆形，调用OpenGL图形库，用折线逼近法画圆。

图14同一规则下角度随机生成的效果图(0～20°)。

图15角度不变规则随机生成效果图。

图16规则和角度均随机生成的分形图。

本发明专利通过GPU并行处理控制流指令进行图形处理性能优化，对分形图L系统算法进行改进。基于GPU并行渲染流水线，将分形图绘制添加了光照计算和环境映射变化，利用控制流指令并行算法优化渲染生成管线，实现对分形图的快速生成与渲染，获得了在用户PC中快速、准确的显示效果。获取复杂且不规则的分形图几何特征，通过顶点像素计算和光照坐标变换，实时渲染L系统算法生成分形图、IFS算法融合递归算法生成分形图；结合OpenCL异构并行计算技术，实时优化控制流指令并行算法，实时处理分形图几何特征的加速渲染。其中，包括对场景图任务网格的划分、OpenCL与Direct3D之间图像缓冲对象数据流的通讯、组合同一处理器执行任务；每个任务映射到具体处理器、使不同GPU图形处理器并发地执行每个映射任务；根据映射任务需要，选择负载平衡和任务调度算法进行映射权衡及线程并行动态规划。在游戏引擎中设计基于GPU并行处理的分形图生成与渲染方法，将获取复杂场景元素实时显示在PC用户端，最终在游戏引擎中实现分形图生成与渲染的并行优化与控制。

技术的进步只是选用标准的参考，但是出于改劣发明,或者成本考量,仅仅从实用性的技术方案选择。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何属于本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。