BSP树消隐算法的改进研究  

A Study and Realization of Binary Space Partitioning Tree Culling Algorithm

作　　者：赵祥好[1] 

机构地区：[1]安徽省委党校信息中心,安徽合肥230022

出　　处：《安徽师范大学学报（自然科学版）》2015年第5期427-431,共5页Journal of Anhui Normal University(Natural Science)

摘　　要：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.

关 键 词：BSP树算法 中序遍历 消隐 满二叉树 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]