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

A balanced octree based on morton code and mirror code

在接触分析和动画模拟等网格规模庞大、需要实时更新的应用场景下,普遍采用莫顿码实现包围盒层次树结构的快速重构。但现有的层次树由于结构平衡性差,普遍存在搜索效率不稳定的问题,为此本文在莫顿码法的基础上提出了一种兼顾构建与搜索效率的平衡八叉树模型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.