摘要
BSP树算法是在三维景物空间中实现消隐的一种常见算法.BSP树消隐算法中的遍历算法通常是采用递归来实现,在实时虚拟环境具体实现时会导致很大的系统开销.本文在分析BSP树消隐算法中的BSP树的构造和遍历方法的基础上,以一种基于顺序存储结构的非递归算法来代替通常的递归算法,有效的提高了BSP树的遍历速度,提高了三维景物空间的消隐的生成速度,降低了场景中的景物表面多边形的存储空间,有利于实时虚拟环境中三维景物的快速生成.
The Binary Space Partitioning tree algorithm is an usual culling algorithm in three-dimensional scene.Studying the current Binary Space Partitioning tree culling algorithm,we find that the recursion is used to realize the traversal of Binary Space Partitioning tree culling algorithm,which will lead to prodigious systematic spending in concrete realizing of real-time virtual environment. Based on analyzing the construction and traversal of Binary Space Partitioning tree,a non-recursion algorithm founded on the ordinal store structure is used to replace the usual recursion algorithm,which effectively enhances the traversal speed of Binary Space Partitioning tree and the creating culling speed of the three-dimensional scene,reduces the memory spaces of scene surface polygon,and is propitious to fast create the three-dimensional scene in real-time virtual environment.
出处
《安徽师范大学学报（自然科学版）》
CAS
2015年第5期427-431,共5页
Journal of Anhui Normal University(Natural Science)
关键词
BSP树算法
中序遍历
消隐
满二叉树
Binary Space Partitioning tree algorithm
inorder traversing
culling
full Binary tree
