Journal of Software:2002.13(9):1840-1845

An Improved Intervisibility Testing Algorithm
LIANG Xiao-hui,ZHAO Qin-ping
Chart / table
Similar Articles
Article :Browse 2685   Download 2960
Received:February 25, 2002    Revised:June 11, 2002
> 中文摘要: 对虚拟环境中点到点的通视性检查算法进行了研究.在深入分析了一个目前具有代表性的投影覆盖检测(sieve overlap,简称SO)算法的基础上,对该算法进行了改进,使其更适合大规模分布式虚拟环境及各种仿真的需要.SO算法利用桶表和单线索三叉树进行地形多边形的管理及各种检索工作.基于感兴趣区的思想,大幅度缩减了桶表的检索范围,使点到点的通视性检查具有更高的真实性和实时性,能够更为有效地为大规模分布式虚拟环境中的动态实体提供各种环境信息.对SO算法及其改进算法SO*在虚拟环境中应用的时间空间效率进行了分析.
Abstract:The intervisibility testing algorithm in the virtual environment that based on the LOS (line of sight) is researched on. After analyzing, the SO (sieve overlap) algorithm, which is more universal and efficient than other point to point intervisibility testing algorithm, is improved to fit more for the requirements of large-scale virtual environment and simulation. SO algorithm uses Bucket List and Singly Threaded Ternary Tree to manage and search the terrain polygon. The searching scale of Bucket List is reduced based on the AOI(area of interestiong).This makes the point to point intervisibility testing algorithm more real and efficient and gives the environmental infomation to the dynamic entity in the large scale virtual environment more efficiently.The space and time efficiency of the algorithm SO*and the SO is also compared.
文章编号:     中图分类号:    文献标志码:
基金项目:国家高技术研究发展计划资助项目(2001AA115130) 国家高技术研究发展计划资助项目(2001AA115130)
Foundation items:
Reference text:


LIANG Xiao-hui,ZHAO Qin-ping.An Improved Intervisibility Testing Algorithm.Journal of Software,2002,13(9):1840-1845