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

作     者：袁瑶 徐骏 顾剑锋 YUAN Yao;XU Jun;GU Jian-feng

作者机构：上海交通大学材料改性与数值模拟研究所上海200240 上海交通大学材料基因组联合研究中心上海200240 

出 版 物：《计算力学学报》 (Chinese Journal of Computational Mechanics)

年 卷 期：2024年第41卷第3期

页      面：467-473页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：层次包围盒树 平衡八叉树 cuda并行框架 莫顿码 

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