虚拟视景系统中碰撞检测算法的理论研究
|
摘要
虚拟现实(Virtual Reality-VR)简单的说是一种可以创建和体验虚拟世界的计算机系统。作为一门先进的人机交流技术,虚拟现实技术已被广泛的应用在视景仿真、军事模拟、虚拟制造、虚拟设计、虚拟装配、科学可视化等领域。本文主要在理论上对虚拟场景中使用的碰撞检测算法进行有限探讨,并以本人实际参与工作的飞机模拟机视景系统为例,论述碰撞检测算法在虚拟场景中的应用。模拟机视景系统主要为飞行员提供飞行训练时的座舱外景象,由于飞行员飞行时视觉信息占总信息的70%,因此视景系统内容的丰富度、逼真度和清晰度都会影响模拟机的质量和飞行训练的效果。而碰撞检测作为视景系统的重要组成部分,在视景系统中占有重要的地位,精确的碰撞检测对提高视景系统的真实性、增强视景系统的沉浸感有着至关重要的作用。
碰撞检测方法很多,本文主要针对即空间剖分技术和包围盒技术这两种主要方法进行了深入的研究。这两种技术的计算方法有所不同,但目的都是尽可能地减少参与相交测试的物体对或基本几何元素的数目,从而大大提高碰撞检测的效率。空间剖分技术是根据场景中物体的密集程度,按照一定的算法将空间划分成若干子空间,每个检测时刻都只针对该时刻子空间里的物体进行检测。包围盒技术是用体积稍大且几何特性简单的包围盒来近似地代替复杂的几何对象进行测试。在这两种方法中,空间剖分算法的选择是否合理以及包围盒形状的简化是否恰当是碰撞检测是否有效的关键。
通过对空间剖分与包围盒两项技术进行研究和分析,本文结合飞行模拟机视景系统建模的特点,通过对已有几种包围盒技术优缺点的分析,提出了一种简化包围盒模型。该方法主要通过对模型进行投影交叉测试和交叉点高度判断,将三维碰撞检测问题分解为二维问题和一维问题,从而降低了问题的复杂度。因客观条件所限,本文只对碰撞检测的算法进行理论研究,力图用最简单实用的算法建模解决复杂的碰撞问题,作为在实践中的理论指导。
In flight simulator, visual system presents a scene for pilots in the flight training process. Of all the information during a flight, 70 percent is given by vision, so, the enrichment, reality and accuracy of visual system will influence the quality of flight simulator and the effect of flight training. Collision detection, as an important part to form a visual system, has a very high station, a precise collision detection will make the visual system much more real and immersed. In the recent years, with the springing up of Virtual Reality and Distributed Interactive Simulation, the research of collision detection is becoming pop gradually, and is being paid more and more emphases.
There are many methods for collision detection, but this paper has only done some deep research on two important methods, space-division technology and bounding-box technology. Although the two technologies have different ways to calculate, they both aim to enhance the efficiency of collision detection by reducing the objects participating in the collision detection and the number of basic geometrical elements. Space-division technology divides the whole space into several sub-spaces according to certain algorithm and the denseness of objects in the scene. After dividing, the computer will test only the objects in one sub-space at one time. Bounding-box technology will use a bounding-box instead of the object itself to take part in the test, the box will be slightly bigger but much simpler than the corresponding object. In the two methods, whether the choice of algorithm for space-division is reasonable and whether the reduction of the bounding-box’s shape is proper will influence the efficiency of collision detection.
Through research, analyses and experiments on the two technologies, on the consideration of the characteristics of the models in the visual system of flight simulator, and analyzing the merits and demerits of several traditional bounding-boxes, the paper proposed a simplified bounding-box. And the new method tests the collision detection by the projection’s overlapping test and the intersection’s altitude test, in this way, it divides the three-dimensional problem into a two-dimensional problem and a one-dimensional problem, so, it reduces the complexity of the problem.
碰撞检测方法很多,本文主要针对即空间剖分技术和包围盒技术这两种主要方法进行了深入的研究。这两种技术的计算方法有所不同,但目的都是尽可能地减少参与相交测试的物体对或基本几何元素的数目,从而大大提高碰撞检测的效率。空间剖分技术是根据场景中物体的密集程度,按照一定的算法将空间划分成若干子空间,每个检测时刻都只针对该时刻子空间里的物体进行检测。包围盒技术是用体积稍大且几何特性简单的包围盒来近似地代替复杂的几何对象进行测试。在这两种方法中,空间剖分算法的选择是否合理以及包围盒形状的简化是否恰当是碰撞检测是否有效的关键。
通过对空间剖分与包围盒两项技术进行研究和分析,本文结合飞行模拟机视景系统建模的特点,通过对已有几种包围盒技术优缺点的分析,提出了一种简化包围盒模型。该方法主要通过对模型进行投影交叉测试和交叉点高度判断,将三维碰撞检测问题分解为二维问题和一维问题,从而降低了问题的复杂度。因客观条件所限,本文只对碰撞检测的算法进行理论研究,力图用最简单实用的算法建模解决复杂的碰撞问题,作为在实践中的理论指导。
In flight simulator, visual system presents a scene for pilots in the flight training process. Of all the information during a flight, 70 percent is given by vision, so, the enrichment, reality and accuracy of visual system will influence the quality of flight simulator and the effect of flight training. Collision detection, as an important part to form a visual system, has a very high station, a precise collision detection will make the visual system much more real and immersed. In the recent years, with the springing up of Virtual Reality and Distributed Interactive Simulation, the research of collision detection is becoming pop gradually, and is being paid more and more emphases.
There are many methods for collision detection, but this paper has only done some deep research on two important methods, space-division technology and bounding-box technology. Although the two technologies have different ways to calculate, they both aim to enhance the efficiency of collision detection by reducing the objects participating in the collision detection and the number of basic geometrical elements. Space-division technology divides the whole space into several sub-spaces according to certain algorithm and the denseness of objects in the scene. After dividing, the computer will test only the objects in one sub-space at one time. Bounding-box technology will use a bounding-box instead of the object itself to take part in the test, the box will be slightly bigger but much simpler than the corresponding object. In the two methods, whether the choice of algorithm for space-division is reasonable and whether the reduction of the bounding-box’s shape is proper will influence the efficiency of collision detection.
Through research, analyses and experiments on the two technologies, on the consideration of the characteristics of the models in the visual system of flight simulator, and analyzing the merits and demerits of several traditional bounding-boxes, the paper proposed a simplified bounding-box. And the new method tests the collision detection by the projection’s overlapping test and the intersection’s altitude test, in this way, it divides the three-dimensional problem into a two-dimensional problem and a one-dimensional problem, so, it reduces the complexity of the problem.
引文
[1] 张茂军.虚拟现实系统[M].北京:科学出版社,2001.1-5
[2] 傅治平.自由互动的虚拟现实[J].北京邮电大学学报(社会科学版),2005, 7(1):5-11
[3] 万钢.基于 VEGA 的虚拟现实应用研究[D]:[硕士学位论文].西安,西北工业大学,2005
[4] 马利民.虚拟现实技术及其应用展望[J].计算机时代,2005(2):1-2
[5] 陈定方,理勋祥,李文峰,尹念东.基于分布式虚拟现实技术的汽车驾驶模拟器的研究[J].系统仿真学报,2005,17(2):347-350
[6] 林宗坚,刘先林.精确时空立体景观虚拟现实的构建与应用方法研究[J].测绘科学,2005,30(2):17-19
[7] 杨波,虚拟现实技术—MultiGen、Vega 应用研究[D]:[硕士学位论文].成都:电子科技大学,2002
[8] 王裕俭.基于Multigen Creator和Vega的虚拟现实探讨[J].测绘信息与工程,2003,28(4):14-16
[9] 石教英.虚拟现实基础及使用算法[M].北京:科学出版社,2002
[10] Donald Hearn 等,计算机图形学[M](第二版).北京:电子工业出版社,2002
[11] 吴家铸,党岗等.视景仿真技术及应用[M].西安:西安电子科技大学出版社,2001
[12] 邓军 , 杨学良 . 飞行模拟器视景系统模型 [J]. 计算机工程与应用,2000,9:163-165
[13] 谢广辉,魏少宁.飞行模拟器视景系统发展现状和趋势[J].航天医学与医学工程,2003,16(3):223-226
[14] 陈建东.全飞行模拟机视景系统显示技术的发展[J].中国民航飞行学院学报,2000(2):31-32
[15] 王润杰,李松维,范贤德.飞行模拟器视景中纹理压缩技术的研究与实现[J].系统仿真学报,2003,15(1):90-93
[16] 杨克俭,刘舒燕,陈定方.分布交互三维视景行为-特征建模方法研究[J].计算机辅助设计与图形学学报,2000,12(11):846-850
[17] 魏迎梅.虚拟环境中碰撞检测问题的研究[D]:[硕士学位论文].长沙:国防科学技术大学,2000
[18] 刘惠义,邱云,张春红.虚拟视景交互漫游系统的实时碰撞检测方法研究[J].河海大学学报(自然科学版),2005,33(3):339-342
[19] 李芙玲,张瑾. 碰撞检测技术研究 [J].华北科技学院学报,2004,1 (2):71-73
[20] 潘振宽,崔树娟,张继萍,李建波.基于层次包围盒的碰撞检测方法[J].青岛大学学报(自然科学版),2005,18(1):71-76
[21] 陈学文,丑武胜,刘静华,王田苗.基于包围盒的碰撞检测算法研究[J].计算机工程与应用,2005,5:46-50
[22] 马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006(4).
[2] 傅治平.自由互动的虚拟现实[J].北京邮电大学学报(社会科学版),2005, 7(1):5-11
[3] 万钢.基于 VEGA 的虚拟现实应用研究[D]:[硕士学位论文].西安,西北工业大学,2005
[4] 马利民.虚拟现实技术及其应用展望[J].计算机时代,2005(2):1-2
[5] 陈定方,理勋祥,李文峰,尹念东.基于分布式虚拟现实技术的汽车驾驶模拟器的研究[J].系统仿真学报,2005,17(2):347-350
[6] 林宗坚,刘先林.精确时空立体景观虚拟现实的构建与应用方法研究[J].测绘科学,2005,30(2):17-19
[7] 杨波,虚拟现实技术—MultiGen、Vega 应用研究[D]:[硕士学位论文].成都:电子科技大学,2002
[8] 王裕俭.基于Multigen Creator和Vega的虚拟现实探讨[J].测绘信息与工程,2003,28(4):14-16
[9] 石教英.虚拟现实基础及使用算法[M].北京:科学出版社,2002
[10] Donald Hearn 等,计算机图形学[M](第二版).北京:电子工业出版社,2002
[11] 吴家铸,党岗等.视景仿真技术及应用[M].西安:西安电子科技大学出版社,2001
[12] 邓军 , 杨学良 . 飞行模拟器视景系统模型 [J]. 计算机工程与应用,2000,9:163-165
[13] 谢广辉,魏少宁.飞行模拟器视景系统发展现状和趋势[J].航天医学与医学工程,2003,16(3):223-226
[14] 陈建东.全飞行模拟机视景系统显示技术的发展[J].中国民航飞行学院学报,2000(2):31-32
[15] 王润杰,李松维,范贤德.飞行模拟器视景中纹理压缩技术的研究与实现[J].系统仿真学报,2003,15(1):90-93
[16] 杨克俭,刘舒燕,陈定方.分布交互三维视景行为-特征建模方法研究[J].计算机辅助设计与图形学学报,2000,12(11):846-850
[17] 魏迎梅.虚拟环境中碰撞检测问题的研究[D]:[硕士学位论文].长沙:国防科学技术大学,2000
[18] 刘惠义,邱云,张春红.虚拟视景交互漫游系统的实时碰撞检测方法研究[J].河海大学学报(自然科学版),2005,33(3):339-342
[19] 李芙玲,张瑾. 碰撞检测技术研究 [J].华北科技学院学报,2004,1 (2):71-73
[20] 潘振宽,崔树娟,张继萍,李建波.基于层次包围盒的碰撞检测方法[J].青岛大学学报(自然科学版),2005,18(1):71-76
[21] 陈学文,丑武胜,刘静华,王田苗.基于包围盒的碰撞检测算法研究[J].计算机工程与应用,2005,5:46-50
[22] 马登武,叶文,李瑛.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006(4).