算法,下面介绍几种常用算法 27.31画家算法 画家算法的原理是:先把屏幕置成背景色,再把物体的各个面按其离视点的远近进行排序,离视点 远者在表头,离视点近者在表尾,排序结果存在一张深度优先级表中。然后按照从表头到表尾的顺序 逐个绘制各个面。由于后显示的图形取代先显示的画面,而后显示的图形所代表的面离视点更近,所 以由远及近的绘制各面,就相当于消除隐藏面。这与油画作家作画的过程类似,先画远景,再画中景 最后画近景。由于这个原因,该算法习惯上称为画家算法或列表优先算法 下面给出了一种建立深度优先级表方法。先可根据每个多边形顶点z坐标的极小值Zmin的大小把多 边形作一初步的排序。设Zmin最小的多边形为P,它暂时成为优先级最低的一个多边形。把多边形序 列中其它多边形记为Q。现在先来确定P和其它多边形Q的关系。Zmin(P)<Zmin(Q)若Zmax(P)<Zmin(Q), 则P肯定不能遮挡Q。如果对某一多边形Q有Zmax(P)>Zmin(Q),则必须作进一步的检查。这种检查分 以下五项(如图 abcde所示): b.P和Q在oxy平面上投影的包围盒在x方向上不相交 c.P和Q在oxy平面上投影的包围盒在y方向上不相交 dP和Q在oxy平面上的投影不相交 e.P的各项点均在Q的远离视点的一侧 f.Q的各顶点均在P的靠近视点的一侧 y 图2.7.10P不遮挡Q的各种情况(ab,c,d,e)及互相遮挡f 上面的五项只要有一项成立,P就不遮挡Q。如果所有测试失败,就必须对两个多边形在XY平面上 的投影作求交运算。计算时不必具体求出重叠部分,在交点处进行深度比较,只要能判断出前后顺序 即可。若遇到多边形相交或循环重叠的情况(如图f),还必须在相交处分割多边形,然后进行判断。 画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面, 而且深度优先级表中面的顺序可能出错。在两个面相交,三个以上的面重叠的情形,用任何排序方法 都不能排出正确的序。这时只能把有关的面进行分割后再排序 2.73.22缓冲区( Z-Buffer)算法 画家算法中,深度排序计算量大,而且排序后,还需再检查相邻的面,以确保在深度优先级表中前 者在前,后者在后。若遇到多边形相交,或多边形循环重叠的情形,还必须分割多边形。为了避免这 些复杂的运算,人们发明了Z缓冲区(Z- Buffer算法。在这个算法里,不仅需要有帧缓存来存放每个 象素的颜色值,还需要一个深度缓存来存放每个象素的深度值算法，下面介绍几种常用算法。 2.7.3.1 画家算法 画家算法的原理是：先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序，离视点 远者在表头，离视点近者在表尾，排序结果存在一张深度优先级表中。然后按照从表头到表尾的顺序 逐个绘制各个面。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所 以由远及近的绘制各面，就相当于消除隐藏面。这与油画作家作画的过程类似，先画远景，再画中景， 最后画近景。由于这个原因，该算法习惯上称为画家算法或列表优先算法。 下面给出了一种建立深度优先级表方法。先可根据每个多边形顶点 z 坐标的极小值 Zmin 的大小把多 边形作一初步的排序。设 Zmin 最小的多边形为 P，它暂时成为优先级最低的一个多边形。把多边形序 列中其它多边形记为 Q。现在先来确定 P 和其它多边形 Q 的关系。Zmin(P)<Zmin(Q)若 Zmax(P)<Zmin(Q)， 则 P 肯定不能遮挡 Q。如果对某一多边形 Q 有 Zmax(P)>Zmin(Q)，则必须作进一步的检查。这种检查分 以下五项（如图 abcde 所示）： b. P 和 Q 在 oxy 平面上投影的包围盒在 x 方向上不相交 c. P 和 Q 在 oxy 平面上投影的包围盒在 y 方向上不相交 d. P 和 Q 在 oxy 平面上的投影不相交 e. P 的各顶点均在 Q 的远离视点的一侧 f. Q 的各顶点均在 P 的靠近视点的一侧 图 2.7.10 P 不遮挡 Q 的各种情况(ab,c,d,e) 及互相遮挡 f 上面的五项只要有一项成立，P 就不遮挡 Q。如果所有测试失败，就必须对两个多边形在 XY 平面上 的投影作求交运算。计算时不必具体求出重叠部分，在交点处进行深度比较，只要能判断出前后顺序 即可。若遇到多边形相交或循环重叠的情况（如图 f），还必须在相交处分割多边形，然后进行判断。 画家算法原理简单。其关键是如何对场景中的物体按深度排序。它的缺点是只能处理互不相交的面， 而且深度优先级表中面的顺序可能出错。在两个面相交，三个以上的面重叠的情形，用任何排序方法 都不能排出正确的序。这时只能把有关的面进行分割后再排序。 2.7.3.2 Z 缓冲区(Z-Buffer)算法 画家算法中，深度排序计算量大，而且排序后，还需再检查相邻的面，以确保在深度优先级表中前 者在前，后者在后。若遇到多边形相交，或多边形循环重叠的情形，还必须分割多边形。为了避免这 些复杂的运算，人们发明了 Z 缓冲区(Z-Buffer)算法。在这个算法里，不仅需要有帧缓存来存放每个 象素的颜色值，还需要一个深度缓存来存放每个象素的深度值