一种快速高质量k-d树构建算法

提出了一种适用于交互式动态场景光线跟踪的高质量k-d树构建算法.结合基本的k-d树遍历代价函数和场景一般具有较均匀分布的特征,推导出合理表示节点中连续分割面遍历代价的计算公式.在计算过程中将待划分节点包围盒划分成均匀子空间,采用直接求解函数解析解的方式进行节点分割面计算.为了保证各种光线跟踪应用中较高的渲染效率,提出了不同情况下合理的空间划分数量计算函数.实验结果表明,该算法适用于各种不同图元分布的场景k-d树构建,并可以应用于整个构建过程,效率有了很大的提升,同时构建结果保持了与最优划分相近的质量.