随着计算机图形学的发展,三维虚拟场景以其更强的真实感和沉寖感,更好的交互性被越来越多的人认可,具有交互功能的大规模三维场景绘制在很多领域都有着广泛的应用,如3D游戏、军事演习、航空模拟、地理信息系统、机械制造等。随着这些行业的高速发展,特别是3D游戏的风靡,对图形加速绘制技术的研究也迎来了新的热潮,其中可见性判断及剔除方法是主要的研究方向之一。典型的室外城市场景中,建筑物密度大,遮挡性强,对于此类场景最好的加速绘制方法就是遮挡剔除算法。由于遮挡剔除算法需要依赖于空间划分,建立层次结构,因此本文首先研究了kd-tree的相关算法,结合室外城市场景的自身特点,对原有的构建算法做出了适当的改进和简化,实现了一种适合城市场景的轻便的kd-tree构建算法。对于分割面的选择,算法抛弃了全局最优策略,而使用一种局部的贪心算法,每次只计算固定数量的候选面的成本,以最低成本的面作为分割面。实验证明算法能够以较低的成本构建出较为平衡的树结构。图形硬件的发展日新月异,随着场景规模和复杂度的急速上升,利用图形硬件加速绘制是必然的发展趋势。利用GPU的遮挡查询功能,本文研究和实现了一种改进的基于GPU的遮挡剔除算法。使用kd-tree空间划分技术将场景空间进行分割,构建出空间层次结构。本文充分利用空间连续性和时间连续性,对原始的剔除算法进行改进,有效减少了遮挡查询的等待延迟时间和多余的可见性测试。在此基础上,本文研究和实现了在层次结构中推导可见性信息的方法;利用kd-tree分割形成的子空间相对规则的特点,实现了一种在利用共享面判断可见性的方法。按照成本的高低,顺序使用了几种可见性测试,减少了成本相对较高的硬件查询次数。利用批处理技术避免了查询时频繁的渲染状态改变。对GPU遮挡查询建立概率计算模型,通过计算物体的直接渲染成本、硬件遮挡查询成本以及物体保持可见性的概率,对渲染物体与否做出决策,进一步减少硬件查询次数。最后,本文简要介绍了群体动画演示系统的整体架构,对场景管理器进行了设计,融入了本文研究的kd-tree构建算法和基于GPU的遮挡剔除算法。通过实验验证,本文研究的遮挡剔除算法能够有效加速复杂场景的绘制。