在计算机图形学领域中,光线追踪技术最早由Turner Whitted提出,是一种广泛用于真实感图像合成的技术。Whitted指出,在光线追踪算法中,95%的时间花费在了光线与物体的求交计算之上,因此研究减少光线追踪中求交测试的算法与数据结构的重要性不言而喻。二叉空间分割(BSP)树是一种用于给光线追踪系统加速的空间分割技术,其基本思想是用若干限制条件的情况下,将待渲染的三维空间用一超平面递归地划分为更小两个的子空间,从而达到快速筛选出空间的某一位置图元的目的。kd树是一种虚拟平面和空间坐标轴平行的特殊的BSP树。在实际应用场景,kd树被广泛应用于各类光线追踪算法中进行空间划分。因为采用非轴对称超平面的BSP树分割法被普遍认为具有遍历效率低、不稳定等缺点。本文的研究显示,通过优化BSP树的构建算法,其加速性能不亚于甚至能超过kd树。本文的主要研究内容如下:1.为了结合kd树与BSP树各自的优势,本文提出了一种新型的BSP树数据结构。在该树中,接近根部的节点使用kd树节点类似的轴对齐分割面进行分割,而对靠近底部的节点使用BSP树任意分割面进行分割。渲染测试表明,该种组合型BSP树的性能优于一般传统的BSP树。2.在构造组合型BSP树时,由于直接使用kd树的SAH算法做节点代价估计会导致BSP树节点远远多于kd树节点,因此需要使用适合该种组合BSP树的SAH算法。本文所提及的SAH改进算法通过将BSP树节点的遍历代价表示成该节点内三角形图元数的线性组合来解决该问题。实验表明,使用该种SAH构建的组合树性能更为优秀。