[科普中国]-画家算法

画家算法也叫作优先填充，它是三维计算机图形学中处理可见性问题的一种解决方法。当将三维场景投影到二维平面的时候，需要确定哪些多边形是可见的，哪些是不可见的。

简介

“画家算法”表示头脑简单的画家首先绘制距离较远的场景，然后用绘制距离较近的场景覆盖较远的部分。画家算法首先将场景中的多边形根据深度进行排序，然后按照顺序进行描绘。这种方法通常会将不可见的部分覆盖，这样就可以解决可见性问题。

画家算法无法处理相互重叠的多边形在有些场合下，画家算法可能无法解决可见性问题。在这个例子中，多边形 A、B、C 互相重叠，我们无法确定哪一个多边形在上面，哪一个在下面，我们也无法确定两个多边形什么时候在三维空间中交叉。在这种情况下必须用一些方法对这些多边形进行切分、排序。1972年提出的Newell算法就是切分类似多边形的一种方法，在计算几何领域人们已经提出了许许多多的解决方法。

一些基本的画家算法实现方法也可能效率很低，因为这将使得系统将可见多边形集合中的每个点都进行渲染，而没有考虑这些多边形在最终场景中可能被其它部分遮挡。这也就是说，对于细致的场景来说，画家算法可能会过度地消耗计算机资源。1

逆向画家算法这种算法首先绘制距离观察者较近的物体，已经进行绘制的部分不再进行其它的绘制过程。在计算机图形系统中，这种方法由于无需根据光照、纹理等参数计算被较近物体遮挡的远处物体的颜色，所以效率非常高。但是，这种方法也有许多与普通画家算法同样的问题。

深度缓冲技术画家算法的这些缺陷导致了深度缓冲技术的发展，深度缓冲技术可以看作是画家算法的一个发展，它根据逐个像素的信息解决深度冲突的问题，并且抛弃了对于深度渲染顺序的依赖。即使在这样的系统中，有时也使用画家算法的变体。由于深度缓冲实现通常是基于硬件中的固定精度深度缓冲寄存器，因此舍入误差就会带来一些显示问题，即在多边形连接的地方会出现重叠或者间隙。为了避免这种问题，一些图形处理引擎使用了“过度渲染”的方法，即根据画家算法的顺序绘制两个多边形中受影响的边界。这也就是说有些像素如同在画家算法中那样实际上绘制了两次，但是由于图像中只有很少的一部分才做这样的处理，因此对于性能的影响很小。2

本词条内容贡献者为:

杨晓红 - 副教授 - 西南大学