| 袁瑶,徐骏,顾剑锋.一种基于莫顿码及镜像编码的平衡八叉树模型[J].计算力学学报,2024,41(3):467~473 |
|
| 
码上扫一扫！ |
| 一种基于莫顿码及镜像编码的平衡八叉树模型 |
| A balanced octree based on morton code and mirror code |
| 投稿时间：2022-11-10 修订日期：2023-01-05 |
| DOI：10.7511/jslx20221101002 |
| 中文关键词: 层次包围盒树 平衡八叉树 cuda并行框架 莫顿码 |
| 英文关键词:BVH balanced octree cuda Morton code |
| 基金项目:国家重点研发计划(2018YFA0702900)资助项目. |
|
| 摘要点击次数: 239 |
| 全文下载次数: 165 |
| 中文摘要: |
| 在接触分析和动画模拟等网格规模庞大、需要实时更新的应用场景下,普遍采用莫顿码实现包围盒层次树结构的快速重构。但现有的层次树由于结构平衡性差,普遍存在搜索效率不稳定的问题,为此本文在莫顿码法的基础上提出了一种兼顾构建与搜索效率的平衡八叉树模型BOT树(Balanced Octree)。设计了镜像编码来保证树的上层节点均有8个分支,且同层树节点所含三角面数之差不超过1。实际算例表明,BOT树与现有模型OIOT树在CUDA并行框架下对比,构建加速比最高可达1.29×,且网格规模越大,BOT树构建效率的优势越明显。同时,与OIOT树相比BOT树的筛除率更高,在凸体接触和边缘接触算例中加速比分别达到1.13×和1.06×。 |
| 英文摘要: |
| In contact analysis and animation simulation,there are massive and 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,search efficiency of BVH trees constructed by these algorithms is unstable due to their unbalance.Therefore,an alternative algorithm of the balanced octree (BOT) 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 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 achieved 1.29×speedup over that of the existing OIOT under the CUDA framework.In addition,construction efficiency of BOT increase with larger mesh size.Meanwhile,a BOT tree has a higher filter rate.In parallel contact searching,it has achieved 1.13×and 1.06×speedup over OIOT in convex-contact and edge-contact cases,respectively. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
|
