(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211111028.3 (22)申请日 2022.09.13 (71)申请人 桂林电子科技大 学 地址 541004 广西壮 族自治区桂林市七 星 区金鸡路1号 (72)发明人 赵雅彬　张文辉　史翔天　林镇源　 陈少坤　车向明　丁逸飞　 (74)专利代理 机构 桂林市持衡专利商标事务所 有限公司 45107 专利代理师 陈跃琳 (51)Int.Cl. G06F 30/28(2020.01) G06T 15/00(2011.01) G06T 9/40(2006.01) G06T 17/00(2006.01)G06T 1/20(2006.01) G06F 111/08(2020.01) G06F 113/08(2020.01) (54)发明名称 一种基于GPU八叉树加速和SPH算法的流体 模拟方法 (57)摘要 本发明公开一种基于GPU八叉树加速和SPH 算法的流体模拟方法， 为了降低CPU的负荷， 并将 八叉树的遍历放在GPU中进行， 改良了传统的八 叉树算法， 使用线性表来存储八叉树的节点， 将 指针替换成线性表中的下标， 使其在传入GPU时 依然可用， 无需指针重定位， 并提出一个O(1)空 间复杂度的迭代方法来做到对八叉树的遍历， 既 利用了GPU强大的并行计算能力， 又发挥了八叉 树在近邻搜索算法中的性能优势， 经GPU和线性 八叉树加速后， 整体帧率受水体粒子数目的限制 大幅减小， CPU负荷有较大程度的下降。 权利要求书2页 说明书6页 附图1页 CN 115438600 A 2022.12.06 CN 115438600 A 1.一种基于GPU八叉树加速和S PH算法的流体模拟方法， 其特 征是， 包括步骤如下： 步骤S1、 初始化DirectX渲染管线； 步骤S2、 使用CPU在预设范围内随机生成水体粒子的坐标； 步骤S3、 在CPU中根据水体粒子的坐标建立线性八叉树； 步骤S4、 在CPU中将水体粒子的坐标和线性八叉树 一并传至GPU； 步骤S5、 在GPU中以深度优先的顺序遍历线性八叉树来检测查询水体粒子的近邻水体 粒子； 步骤S6、 将水体粒子的坐标从GPU返回CPU； 步骤S7、 在CPU中运用渲染方案对水体粒子进行着色。 2.根据权利要求1所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征 是， 步骤S2中， 随机生成的水体粒子的坐标的位于预设范围内为[ ‑10,10]的立方体内。 3.根据权利要求1所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征 是， 步骤S3的具体过程如下： 步骤S3.1、 基于所有水体粒子的坐标计算出所有水体粒子所形成的包围盒的中心坐 标， 以及该包围盒的长 宽高； 步骤S3.2、 新建一个空的线性八叉树； 定义线性八叉树的每个节点均指向一块立方体 的三维空间， 且每个子节点是对父节点进行三维空间细分所得到； 其中对父节点进行三维 空间细分即以父节点所指向的三 维空间的中心 坐标为三 维坐标原 点， 以X轴、 Y轴和Z轴为分 割线， 将父节点的三维空间均匀分割为8 个大小相等的子三 维空间， 这些子三 维空间即为子 节点所指向的三维空间； 采用线性表来存储线性八叉树的节点， 其中节点的序号为当前节 点在线性表中的下标， 并且每个节点中存放父节 点的序号和所有子节点的序号来 实现返回 根节点和对子树的遍历； 步骤S3.3、 向空的八叉树中插入根节点， 根节点的中心坐标和长宽高即为包围盒的中 心坐标和长 宽高， 并标注根节点 为不含水体粒子的节点； 步骤S3.4、 循环遍历每一个水体粒子， 获取当前 水体粒子的坐标， 并执 行如下操作； 步骤S3.4.1、 从根节点 开始遍历线性八叉树： 若当前节点为线性八叉树的非叶节点， 则根据当前水体粒子的坐标和当前节点的中心 坐标的位置关系决定当前 水体粒子应放入当前节点的哪一个子节点， 并继续执 行S3.4.1； 若当前节点 为线性八叉树的叶节点， 则跳转至步骤S3.4.2； 步骤S3.4.2、 判断当前节点中是否含有水体粒子： 如果当前节点中不含水体粒子， 则将当前 水体粒子的放入当前叶子节点； 如果当前节点中含有水体粒子， 则把当前节点中的原有水体粒子拿出来， 并将当前节 点进行三维空间细分； 细分完成后， 根据当前节点中原有水体粒子和叶节点中心的位置关 系决定原有水体粒子应放入当前节点的哪一个子节点， 同时根据当前水体粒子的坐标和当 前节点的中心坐标的位置关系决定 当前水体粒子应放入当前节点的哪一个子节点； 若此时 原有水体粒子和当前水体粒子仍处于同一子节点中， 则将该子节点视为当前节点， 并重复 执行步骤S3.4.2； 若此时原有水体粒子和当前水体粒子不处于同一子节点中， 则继续执行 3.4。 4.根据权利要求1所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征权　利　要　求　书 1/2 页 2 CN 115438600 A 2是， 步骤S4中， 在GPU中， 水体粒子的坐标采用DirectX11框架中的SRV缓冲区作为输入， 采用 DirectX1 1框架中UA V缓冲区作为输出； 线性八叉树采用SRV缓冲区进行存 储。 5.根据权利要求1所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征 是， 步骤5的具体过程如下： 步骤S5.1、 新建两个临时变量分别存 储当前访问的节点和上一个访问的节点； 步骤S5.2、 访问根节点； 步骤S5.3、 如果当前访问的节点是上一个访问的节点的子节点或上一个访问的节点为 空， 则表示当前访问的节点尚未访问过， 跳转到步骤S 5.4； 如果当前访问的节 点是上一个访 问的节点的父节点， 则表示上一个访问的节点及其子树都已访问， 跳转到步骤S5.6； 步骤S5.4、 如果当前访问的节点是叶节点， 则表明当前访问的节点中存放的是水体粒 子信息， 跳转到步骤S 5.5； 如果当前访问的节点是非叶节 点， 则表明当前访问的节 点中存放 的是树干信息， 则跳转到步骤S5.6； 步骤S5.5、 判断当前访问的节点中的水体粒子的坐标是否位于查询水体粒子的作用域 内： 若是， 则判断当前访问的节点中的水体粒子为查询水体粒子的紧邻水体粒子， 根据SPH 公式和紧邻水体粒子来计算查询水体粒子的坐标， 计算结束后访问当前访问的节点的父节 点， 并跳转到步骤S5.3； 若当前访问的节点中的水体粒子的坐标不在查询水体粒子的作用 域内， 则跳转到步骤S5.3； 步骤S5.6、 如果当前访问的节点下有未访问的子节点， 则访问该未访问的子节点； 如果 当前访问的节点下没有未访问的子节点， 且当前访问的节点的父节点不为空， 则访问当前 访问的节 点的父节 点， 并跳转到步骤S 5.3； 如果当前访问的节 点下没有 未访问的子节 点， 且 当前访问的节点的父节点 为空， 则线性八叉树遍历完成， 跳转到步骤S6 。 6.根据权利要求5所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征 是， 步骤S5.1中， 当采用临时变量CurrentNode储存当前访问的节点， 临时变量LastNode储 存上一个访问的节点时， 可以使用两个节点间的父子关系来表示当前线性八叉树遍历的不 同阶段： 若临时变量LastNode所存储的上一个访问的节点是临时变量CurrentNode所存储的当 前访问的节点的父节 点， 则代表当前阶段为遍历临 时变量LastNode所存储的上一个访问的 节点的子节点阶段； 若临时变量LastNode所存储的上一个访问的节点是临时变量CurrentNode所存储的当 前访问的节点的子节 点， 则代表已经访问完临时变量LastNode所存储的上一个访问的所有 子节点， 应该访问Cur rentNode所存储的当前访问的节点的下一个子节点； 当LastNode所存储的上一个访问的节点是CurrentNode所存储的当前访问的节点的最 后一个子节 点， 则代表Current Node所存储的当前访问的节 点的所有子节 点已遍历完， 应遍 历CurrentNode所存储的当前访问的节点的父节点的其 他子节点； 当CurrentNode所存储的当前访问的节点为根节点 的父节点， 且LastNode所存储的上 一个访问的节点 为根节点时， 线性八叉树深度优先遍历结束。 7.根据权利要求1所述的一种基于GPU八叉树加速和SPH算法的流体模拟方法， 其特征 是， 步骤7中， 在CPU中运用屏幕空间流体渲染方案对水体粒子进行着色。权　利　要　求　书 2/2 页 3 CN 115438600 A 3