欢迎光临《计算力学学报》官方网站!
 
一种基于莫顿码及镜像编码的平衡八叉树模型
A Balanced Octree Based on Morton Code and Mirror Code
投稿时间:2022-11-01  修订日期:2023-01-05
DOI:
中文关键词:  层次包围盒树  平衡八叉树  cuda并行框架  莫顿码
英文关键词:BVH  balancing octree  cuda  Morton code
基金项目:
作者单位邮编
袁 瑶 上海交通大学材料改性与数值模拟研究所 200240
徐 骏 上海交通大学材料改性与数值模拟研究所 200240
摘要点击次数: 27
全文下载次数: 0
中文摘要:
      在接触分析、动画模拟等网格规模庞大、需要实时更新的应用场景下,普遍采用莫顿码实现包围盒层次树结构的快速重构。但现有算法的层次树由于结构平衡性差,普遍存在搜索效率不稳定的问题,为此本文在莫顿码法的基础上提出了一种兼顾构建与搜索效率的平衡八叉树模型(Balanced Octree,BOT树)。该模型设计了镜像编码来保证树的上层节点均有8个分支,且同层树节点所含三角面数之差不超过1。实际算例表明,BOT树与现有模型OIOT树在CUDA并行框架下对比,构建加速比最高可达1.29×,且网格规模越大,BOT树构建效率的优势越明显。同时,与OIOT树相比BOT树具有更高的筛除率,在凸体接触和边缘接触算例中的加速比分别达到1.13×和1.06×。
英文摘要:
      In contact analysis and animation simulation, there are mass frequent re-mesh operations. A series of algorithms based on Morton code method have been established to carry out fast construction of BVH trees. Unfortunately, the search efficiency of BVH trees constructed by these algorithms is unstable due to their unbalance. Therefore, an alternative algorithm of the balanced octree (BOT tree) based on Morton code, targeting both fast construction and stable search efficiency, is proposed in this paper. A mirror code method is designed to ensure that each upper node of BOT tree contains 8 branches and the amount difference of triangle units belonging to those nodes on the same tree level is no larger than one. Experiments showed that, the parallel construction of BOT tree achieved 1.29× speedup over that of the existed OIOT tree under the CUDA framework. And the construction efficiency of BOT tree increased with larger mesh size. Meanwhile, BOT tree has higher filter rate. In parallel contact searching sample, it achieved 1.13× and 1.06× speedup over OIOT tree in convex-contact and edge-contact cases, respectively.
  查看/发表评论  下载PDF阅读器
您是第10645761位访问者
版权所有:《计算力学学报》编辑部
本系统由 北京勤云科技发展有限公司设计