公开(公告)号：CN119004833A

公开(公告)日：2024-11-22

申请号：CN202411145031.6

申请日：2024-08-20

Applicant: 中国科学院软件研究所

Inventor： 任丽欣 ,  何小伟 ,  刘树森 ,  郭煜中 ,  吴恩华

IPC: G06F30/20 ,  G06F16/901 ,  G06F113/08

Abstract: 本发明公开了一种层间独立的平衡树并行构建方法，所述方法包括：采用层次无关的并行算法为最精细一层的每个节点构建N‑平衡最小生成树，其中最精细一层的节点至少包含一个种子节点；使用线程安全的哈希表将所有N‑平衡最小生成树合并到单个树中，以消除重复节点，所述重复节点表示在构建单个树结构过程中被重复创建的节点；为所有的中间节点建立父子关系，基于中间节点及父子关系构建出全部叶节点，完成平衡树构建；其中，所述中间节点表示包括至少一个子节点的节点，所述叶节点表示不包括任何子节点的节点。本发明消除树的构建和平衡细化过程对层次的依赖性，避免了构造重复的内部节点，使得算法与GPU实现完全兼容。

公开(公告)号：CN115994976A

公开(公告)日：2023-04-21

申请号：CN202211578074.4

申请日：2022-12-06

Applicant: 中国科学院软件研究所

Inventor： 吴恩华 ,  何小伟 ,  任丽欣 ,  刘树森

IPC: G06T17/00

Abstract: 本发明涉及一种基于GPU的AASDF的构建方法及系统，其方法包括：S1：根据AASDF的定义，确定AASDF和层次稀疏八叉树的约束条件；步骤S2：用Eikonal方程定义AASDF模型；S3：构建AASDF模型的最精细层的叶节点；S4：基于叶节点，自下而上的顺序逐层构建AASDF模型中间层的节点；S5：基于中间层的节点初始化基于均匀网格构建的AASDF模型顶层的节点，采用标准快速迭代算法迭代更新，直至顶层节点收敛，AASDF模型构建完成；S6：基于AASDF模型的层次结构构建全局邻域关系，然后采用移动最小二乘基于节点的邻域关系进行插值，实现对AASDF的访问；S7：对任意两个AASDF模型重复步骤S3～S5进行自下向上的布尔运算。本发明提供的方法使用层次稀疏八叉树结构，实现AASDF在GPU的并行构建以及布尔运算。