计算机工程 ›› 2008, Vol. 34 ›› Issue (5): 231-233,.doi: 10.3969/j.issn.1000-3428.2008.05.081

• 工程应用技术与实现 • 上一篇    下一篇

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

王功明1,2,郭新宇1,赵春江1,王纪华1   

  1. (1. 国家农业信息化工程技术研究中心,北京 100097;2. 中国科学院计算技术研究所,北京 100080)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-03-05 发布日期:2008-03-05

Virtual Walkthrough Collision Detection Based on Object-oriented Octree

WANG Gong-ming1,2, GUO Xin-yu1, ZHAO Chun-jiang1, WANG Ji-hua1   

  1. (1. National Engineering Research Center for Information Technology in Agriculture, Beijing 100097; 2. Institute of Computing Technology, Chinese Aademy of Sciences, Beijing 100080)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-03-05 Published:2008-03-05

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

关键词: 面向对象, 八叉树, 碰撞检测, 包围球, 凸多面体剖分, 粒子系统

Abstract: 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.

Key words: object-oriented, octree, collision detection, encircle sphere, dividing a convex polyhedron to tetrahedrons, particle system

中图分类号: