Sorting-Cube:有效的多边形深度排序算法

摘要

三维空间的多边形相对于视点或者光源的深度排序是图形绘制的重要算法。本文提出了一个有效、简单的多边形深度排序方法:Sorting-Cube方法。对于任意给定的视点,建立以它为中心。各个方面都分别平行于坐标平面的正立方体,即排序立方体:Sorting Cube。通过扫描多边形在正立方体上的投影以及有向图的搜索就能获得相对于该点的一个多边形从前到后的深度序列。不同于传统的方法,本文给出了多边形的透视投影以及任意两多边形深度比较的理论推导过程,算法实现的数据结构。理论和实践证明了算法的有效性,尤其适应于动态环境的深度排序。