基于k-d树快速精确排序的四面体可视化

投影四面体法是四面体体数据可视化的一种重要方法.为了保证绘制结果准确,每一帧都需要对所有四面体按照遮挡关系进行排序,然而四面体之间强烈的依赖性不仅导致排序效率很低,而且很难并行实现.提出了一种基于k-d树空间划分的快速精确的四面体排序策略,在每个叶节点内逐层并行提取互不遮挡的四面体,层与层之间自然有序,且各叶节点的操作彼此独立进行.最后将结果按照叶节点之间的空间遮挡顺序组织在一起.通过两个级别的并行,在保证精确排序的同时极大地提高了效率,且数据结构易于图形处理单元gpu实现.实验结果表明,基于k-d树快速精确排序策略的gpu实现极大地缩短了排序时间.