基于面向对象八叉树的虚拟漫游碰撞检测

借助面向对象概念，根据层数和叶结点链表个数上限来构建存储场景物体信息的高效八叉树。每个叶结点指向记录对应空间区域内物体信息的链表，每个空间物体信息链表按照其对象大小降序排列。在逐步求精阶段用降序包围球遍历链表进行检测，然后根据凸多面体剖分算法，使用主从MPI模式并行处理以实现精确碰撞检测。该方法利用物体空间位置关系进行碰撞检测，毋需存储大量空间物体三角面片。在基于粒子系统的土壤可视化漫游中的运行结果表明，该方法精度高、实时性好，具有一定的研究和应用价值。

Virtual Walkthrough Collision Detection Based on Object-oriented Octree

By virtue of object-oriented concept, the efficient octree that stores object’s information in scene is constructed based on number of layers and amount of leaf node link tables. Every leaf node pointed link table that records object’s information is sorted by its size in corresponding special area. The descent order encircle sphere algorithm is used to detect in seeking exactness phase. Then the principal and subordinate Message Passing Interface(MPI) pattern are parallel applied to realize accurate collision detection according to dividing a convex polyhedron to tetrahedrons algorithm. Compared with the traditional octree algorithm, this method does collision detection by using object’s spatial position relation instead of storing lots of spatial object’s triangle faces. It is applied in the soil visual walkthrough based on particle system. The result of this application proves that it has high precision and good real-time performance. It is researchful and can be applied to some extent.