画家算法

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

<!--more-->

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

MacDown Screenshot

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

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

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

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

深度缓冲

定义

在计算机图形学中,深度缓冲是在三维图形中处理图像深度坐标的过程,这个过程通常在硬件中完成,它也可以在软件中完成,它是可见性问题的一个解决方法。可见性问题是确定渲染场景中哪部分可见、哪部分不可见的问题。画家算法是另外一种常用的方法,尽管效率较低,但是也可以处理透明场景元素。深度缓冲也称为Z缓冲。

当三维图形卡渲染物体的时候,每一个所生成的像素的深度(即z坐标)就保存在一个缓冲区中。这个缓冲区叫作z缓冲区或者深度缓冲区,这个缓冲区通常组织成一个保存每个屏幕像素深度的x-y二维数组。如果场景中的另外一个物体也在同一个像素生成渲染结果,那么图形处理卡就会比较二者的深度,并且保留距离观察者较近的物体。然后这个所保留的物体点深度保存到深度缓冲区中。最后,图形卡就可以根据深度缓冲区正确地生成通常的深度感知效果:较近的物体遮挡较远的物体。这个过程叫作z消隐。

深度缓冲的分辨率对于场景质量有很大的影响:当两个物体非常接近的时候,16位的深度缓冲区可能会导致“z缓冲区fighting”的人为噪声;使用24位或者32位的深度缓冲区就会表现得较好;由于精度太低,所以很少使用8位的深度缓冲区。

Z消隐

在渲染过程中,z消隐是根据深度信息对像素的早期剔除。当渲染隐藏表面所需要的计算量很大的时候,这种方法可以提升处理性能。z消隐是深度缓冲的一个直接结果,在这种方法中每个待定像素的深度都要与相同位置的现存像素的深度进行比较。

使用深度缓冲区,一旦像素的深度已经确定,那么就可以对这个像素进行裁剪,这样如果该像素不可见的话就可以完全跳过照明与纹理处理的过程,并且需要消耗许多时间的像素浓淡工具通常也会跳过对于裁剪掉的像素的处理。这样z消隐就成为了在填充速度、光照、纹理或者像素浓淡处理是主要瓶颈的场合的一种很好的优化工具。

尽管深度缓冲可以处理未经排序的几何体,但是按照深度不断增加的方式(与画家算法排序方式相反)对多边形进行排序,每个像素就可以只渲染一次。对于填充速度有限但是有大量重复绘制场合,这种方法就可以提高处理性能。

数学基础

待渲染的照相机空间中的深度经常定义为近距near到远距far之间的z值,在透视变换之后,得到新的z'值: MacDown Screenshot 其中z是照相机空间的值,它有时候也表示为w或者w'。

结果z'是在 -1到1之间归一化之后的值,其中近距near 平面位于 -1处,远距far平面位于1处。在这个范围之外的相应点在视图体之外,不需要进行渲染。

为了实现深度缓冲,在整个屏幕空间上的对当前多边形顶点之间进行插值来计算z'的值,通常这些中间数值在深度缓冲区中用定点数格式保存。距离近距near平面越近,z'值越密;距离越远,z'值越稀。这样距离照相机越近精度越高。near平面距离照相机越近,则远距离位置的精度越低。near平面距离照相机太近是在远距离物体产生人为误差的一个常见因素。

w缓冲

为了实现w缓冲,通常照相机空间中的z值或者w值都保存成浮点数格式,但是这些数值无法根据顶点在整个屏幕上进行线性插值——通常对它的倒数进行插值,然后再取倒数。这样得到的结果w值与z'不同,它们在near平面与far平面之间均匀分布。

根据应用的不同z缓冲与w缓冲生成的图像质量也有所不同。

Javascript

当在JavaScript中使用canvas标签的时候,可以将下面的程序作为深度缓冲的公式。

1
2
3
4
5
6
//F=far, N=near, Z=final return
f=0;
n=0;
z=0;
z=((f+n)/(f-n))+((1/z)*((-2*f*n)/(f-n)));
// Optimized: z=(f+n-2*f*n/z)/(f-n)