公开(公告)号：CN107689078A

公开(公告)日：2018-02-13

申请号：CN201710717268.0

申请日：2017-08-21

Applicant: 哈尔滨工程大学

Inventor： 叶秀芬 ,  江帆 ,  梅新奎 ,  刘文智 ,  王天 ,  赵新华 ,  崔建文 ,  贾同超 ,  宫垠 ,  孙晶

IPC: G06T17/00 ,  G06T19/00

CPC classification number: G06T17/005 ,  G06T19/003

Abstract: 本发明公开了一种基于链表排序平衡二叉树的层次包围盒树构建方法，属于虚拟现实中软体碰撞检测技术领域。本发明将所要建立包围盒树的物体按照合理精度划分成基本几何图元，并生成对应的AABB层次包围盒，创建链表存储二叉树，对所建立二叉树进行遍历，在链表中每个二叉树对象增加一个属性值存储着该二叉树到参照地点的长度，根据链表中二叉树对象中该属性值对链表进行升序排列；遍历链表，将链表中的二叉树两两进行合并，合并结果存入该链表。本发明使用链表排序的平衡二叉树方法降低了树的高度，解决了二叉树合并过程中的重复排序问题，降低了遍历时的时间复杂度，节省了构造树的耗时，提升了碰撞检测过程的实时性及碰撞检测效率。