一种基于莫顿码及镜像编码的平衡八叉树模型

来源：计算力学学报杂志2024年第3期北京时间：

作者：袁瑶,徐骏,顾剑锋

单位：上海交通大学 材料改性与数值模拟研究所, 上海 200240,上海交通大学 材料改性与数值模拟研究所, 上海 200240,上海交通大学 材料改性与数值模拟研究所, 上海 200240,上海交通大学 材料基因组联合研究中心, 上海 200240

摘要：在接触分析和动画模拟等网格规模庞大、需要实时更新的应用场景下,普遍采用莫顿码实现包围盒层次树结构的快速重构。但现有的层次树由于结构平衡性差,普遍存在搜索效率不稳定的问题,为此本文在莫顿码法的基础上提出了一种兼顾构建与搜索效率的平衡八叉树模型BOT树(Balanced Octree)。设计了镜像编码来保证树的上层节点均有8个分支,且同层树节点所含三角面数之差不超过1。实际算例表明,BOT树与现有模型OIOT树在CUDA并行框架下对比,构建加速比最高可达1.29×,且网格规模越大,BOT树构建效率的优势越明显。同时,与OIOT树相比BOT树的筛除率更高,在凸体接触和边缘接触算例中加速比分别达到1.13×和1.06×。

关键词：层次包围盒树,平衡八叉树,cuda并行框架,莫顿码,

基金资助：国家重点研发计划(2018YFA0702900)资助项目.