（本科）5章 图形裁剪、消隐和光栅化(II)ppt课件.ppt

《（本科）5章 图形裁剪、消隐和光栅化(II)ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）5章 图形裁剪、消隐和光栅化(II)ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程主讲人：5章 图形裁剪、消隐和光栅化(II)2022/5/13第第5章章 图形裁剪、消隐和光栅化图形裁剪、消隐和光栅化5.1 图形的窗口裁剪图形的窗口裁剪 线段裁剪算法线段裁剪算法 多边形裁剪算法多边形裁剪算法5.2 图形光栅化图形光栅化 线段光栅化线段光栅化DDA算法算法 线段光栅化线段光栅化Bresenham算法算法 多边形光栅化多边形光栅化5.3 图形消隐图形消隐 凸多面体消隐凸多面体消隐 画家算法画家算法 Z缓存算法缓存算法 光线投射算法光线投射算法2022/5/135.2 图形光栅化图形光栅化5.2.4 圆的光栅化：圆的光栅化：Bresenham算法（简介）算法（简介） 园具有园

2、具有1/8对称性，只需要计算圆周右上对称性，只需要计算圆周右上1/8弧这一段。弧这一段。 设园心处于坐标原点，园的半径为设园心处于坐标原点，园的半径为R，弧左侧一端坐标为，弧左侧一端坐标为(0,R)，右侧一端坐标为，右侧一端坐标为(0.707R, 0.707R)。2022/5/135.2 图形光栅化图形光栅化与线段情况的推导类似，与线段情况的推导类似，Bresenham算法的公式为算法的公式为初值初值 循环循环 R23e,Ry, 0 x111R707. 0,.,1i 6x4eeyyelse10)yx(4ee1yy0eifii1ii1iiii1ii1ii2022/5/135.2 图形光栅化图形光

3、栅化5.2.5 多边形光栅化：扫描线填充算法多边形光栅化：扫描线填充算法 算法的目的是得到多边形内部光栅点（像素点），是对多边算法的目的是得到多边形内部光栅点（像素点），是对多边形进行离散化的算法。形进行离散化的算法。2022/5/135.2 图形光栅化图形光栅化基本思路基本思路 用一条水平线与多边形求交点，得到的多个交点再组合成线用一条水平线与多边形求交点，得到的多个交点再组合成线段，这些线段上的点就是多边形内部点。由于得到的线段是水段，这些线段上的点就是多边形内部点。由于得到的线段是水平线段，很容易计算线段上的光栅点。如果用来计算的水平线平线段，很容易计算线段上的光栅点。如果用来计算的水平

4、线足够多，这个方法就能得到多边形所覆盖的全部光栅点。足够多，这个方法就能得到多边形所覆盖的全部光栅点。2022/5/135.2 图形光栅化图形光栅化（1）准备工作）准备工作建立两个表，建立两个表，ET表和表和AEL表。表。- ET表保存所有边的信息，每个边占一行。表保存所有边的信息，每个边占一行。- ET表的数据项包括：线段下端点的表的数据项包括：线段下端点的y坐标，上端点的坐标，上端点的y坐标，坐标，下端点下端点x坐标，线段的斜率的倒数坐标，线段的斜率的倒数1/k。- ET表按线段下端点的表按线段下端点的y坐标进行排序，坐标进行排序，y坐标最小的排在前。坐标最小的排在前。- AEL表存储与当

5、前计算的扫描线相关联的边，每个边占一行。表存储与当前计算的扫描线相关联的边，每个边占一行。- AEL表数据项包括：上端点表数据项包括：上端点y，与当前扫描线交点，与当前扫描线交点x，斜率倒，斜率倒数数1/k。2022/5/135.2 图形光栅化图形光栅化（2）计算步骤）计算步骤 将全部边存储到将全部边存储到ET表，清空表，清空AEL表。表。 计算多边形整体的最小计算多边形整体的最小y坐标坐标ymin和最大和最大y坐标坐标ymax。- 循环所有的扫描线，对第循环所有的扫描线，对第i条扫描线进行下面步骤。条扫描线进行下面步骤。- 检查检查AEL表，清除表，清除ymaxy的边。的边。- 对对AEL表

6、中的边，计算表中的边，计算x = x +1/k。- 检查检查ET表，将下端点表，将下端点y=扫描线扫描线y的边加到的边加到AEL表。表。- AEL按按x增加排序。增加排序。- 取出交点，进行合并。取出交点，进行合并。- 合并后的交点，按顺序组合为线段，这些线段在多边形内。合并后的交点，按顺序组合为线段，这些线段在多边形内。 2022/5/135.2 图形光栅化图形光栅化ET下端点下端点y 上端点上端点y 下端点下端点x 1/k 0 4 0 1/2 0 2 0 1 1 2 3 -1 1 4 3 -1/3AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k（空）（空）ymin = 0，ym

7、ax=42022/5/135.2 图形光栅化图形光栅化以下进行扫描线循环，以下进行扫描线循环，y=yminymax，每次循环加，每次循环加1。 - 对第对第i条扫描线条扫描线 - 检查检查AEL表，清除表，清除ymaxy的边。的边。AEL表存储着与扫描线相表存储着与扫描线相关的边，如果扫描线变动，有些边可能不再关联，需要清除。关的边，如果扫描线变动，有些边可能不再关联，需要清除。y = 0AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k（空）（空）2022/5/135.2 图形光栅化图形光栅化- 对对AEL表中的边，计算表中的边，计算x = x +1/k。现在。现在AEL表的边，一

8、定是表的边，一定是前条扫描线时就已经存在于表中的边，前条扫描线时就已经存在于表中的边，x是与前条扫描线的交点，是与前条扫描线的交点，进入新扫描线后，交点需要进行更新。由于进入新扫描线后，交点需要进行更新。由于y增加值为增加值为1，x只需只需增加斜率的倒数。增加斜率的倒数。y = 0AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k（空）（空）2022/5/135.2 图形光栅化图形光栅化- 检查检查ET表，将下端点表，将下端点y=扫描线扫描线y的边加到的边加到AEL表。表。ET表原本表原本没有与扫描线相关联的边，现在可能有了关联，而且与扫描线没有与扫描线相关联的边，现在可能有了关联，

9、而且与扫描线的交点一定是该边下端点的的交点一定是该边下端点的x。所以就将该边下端点的。所以就将该边下端点的x存储到存储到AEL表中的表中的x位置。两个表中，上端点位置。两个表中，上端点y与斜率倒数与斜率倒数1/k相同。相同。y = 0AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 0 1/2 2 0 12022/5/135.2 图形光栅化图形光栅化- AEL按按x增加排序。此时，增加排序。此时，AEL表中，所有的边都与扫描线有表中，所有的边都与扫描线有交点。交点。y = 0交点交点 (0,0) (0,0)2022/5/135.2 图形光栅化图形光栅化- 取出交点，进行合并。取

10、出交点，进行合并。 因为多边形顶点为两个边因为多边形顶点为两个边共用，在计算扫描线与边的共用，在计算扫描线与边的交点时，会被重复计算。所交点时，会被重复计算。所以要将一些重合交点进行合并，规则为以要将一些重合交点进行合并，规则为 如果重复点所属的两个边在扫描线的两侧，合并为一个。如果重复点所属的两个边在扫描线的两侧，合并为一个。 如果重复点所属的两个边在扫描线的同侧，不合并。如果重复点所属的两个边在扫描线的同侧，不合并。 将水平边看做是处于扫描线下侧的边。将水平边看做是处于扫描线下侧的边。 以上合并规则保证了最终形成的交点数量必为偶数。以上合并规则保证了最终形成的交点数量必为偶数。2022/5

11、/135.2 图形光栅化图形光栅化y = 0交点交点 (0,0) (0,0) 不合并不合并- 合并后的交点，按顺序组合为线段，合并后的交点，按顺序组合为线段，这些线段在多边形内。这些线段在多边形内。线段线段 (0,0) (0,0)包含光栅点为包含光栅点为 (0,0)2022/5/135.2 图形光栅化图形光栅化y = 1AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 0 1/2 2 0 1 - 检查检查AEL表，清除表，清除ymaxy的边。的边。AEL表存储着与扫描线相表存储着与扫描线相关的边，如果扫描线变动，有些边可能不再关联，需要清除。关的边，如果扫描线变动，有些边可能不

12、再关联，需要清除。2022/5/135.2 图形光栅化图形光栅化y = 1- 对对AEL表中的边，计算表中的边，计算x = x +1/k。AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 1/2 1/2 2 1 12022/5/135.2 图形光栅化图形光栅化- 检查检查ET表，将下端点表，将下端点y=扫描线扫描线y的边加到的边加到AEL表。表。y = 1AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 1/2 1/2 2 1 1 2 3 -1 4 3 -1/32022/5/135.2 图形光栅化图形光栅化- AEL按按x增加排序。增加排序。 取出交点取出交点(

13、1/2,1) (1,1) (3,1) (3,1) 不合并，得到两条线段。不合并，得到两条线段。2022/5/135.2 图形光栅化图形光栅化y = 2AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 1/2 1/2 2 1 1 2 3 -1 4 3 -1/3 - 检查检查AEL表，清除表，清除ymaxy的边。的边。2022/5/135.2 图形光栅化图形光栅化- 对对AEL表中的边，计算表中的边，计算x = x +1/k。y=2AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 1 1/2 2 2 1 2 2 -1 4 8/3 -1/3- 检查检查ET表，将下端点

14、表，将下端点y=扫描线扫描线y的边加到的边加到AEL表。表。2022/5/135.2 图形光栅化图形光栅化- 取出交点，进行合并。取出交点，进行合并。 (1,2) (2,2) (2,2) (8/3,2)不需要合并，得到两条线段。不需要合并，得到两条线段。2022/5/135.2 图形光栅化图形光栅化y = 3 - 检查检查AEL表，清除表，清除ymaxy的边。的边。AEL上端点上端点y 当前扫描线交点当前扫描线交点x 1/k 4 1 1/2 4 8/3 -1/32022/5/135.2 图形光栅化图形光栅化- 对对AEL表中的边，计算表中的边，计算x = x +1/k。y=3AEL上端点上端点

15、y 当前扫描线交点当前扫描线交点x 1/k 4 3/2 1/2 4 7/3 -1/3- 检查检查ET表，将下端点表，将下端点y=扫描线扫描线y的边加到的边加到AEL表。表。2022/5/135.2 图形光栅化图形光栅化- 取出交点，进行合并。取出交点，进行合并。 (3/2,4) (7/3,3)不需要合并，得到一条线段。不需要合并，得到一条线段。y=4（略）（略）2022/5/135.2 图形光栅化图形光栅化例：如图所示的多边形，按扫描线算法进行计算例：如图所示的多边形，按扫描线算法进行计算2022/5/135.2 图形光栅化图形光栅化建立建立ET表，将全部边存进去，并按下端点表，将全部边存进去

16、，并按下端点y排序排序下端点下端点y，上端点，上端点y，下端点，下端点x，斜率，斜率1/k。 1 2 2 6 1 5 2 -1/4 2 6 8 -1/2 4 6 5 1/2 4 5 5 -42022/5/135.2 图形光栅化图形光栅化建立建立AEL表，表形式如下，此时还没有数据表，表形式如下，此时还没有数据上端点上端点y 交点交点x 斜率斜率1/k。2022/5/135.2 图形光栅化图形光栅化取扫描线取扫描线y=1，按步骤进行检查，按步骤进行检查- 检查检查AEL表，清除所有满足表，清除所有满足“上端点上端点yy”的边，现在没有。的边，现在没有。- 对对AEL表中的边，计算表中的边，计算x

17、 = x +1/k。现在没有。现在没有。- 检查检查ET表，将下端点表，将下端点y=1的边加到的边加到AEL表。此时在表。此时在ET表中找表中找到两个边。加入到两个边。加入AEL后，后，AEL表如下：表如下：上端点上端点y 交点交点x 斜率斜率1/k。 2 2 6 5 2 -1/42022/5/135.2 图形光栅化图形光栅化- AEL按按x增加排序并取出交点为增加排序并取出交点为(2,1) (2,1)。- 交点合并。因这两个交点所属两个边在扫描线同侧，不需要交点合并。因这两个交点所属两个边在扫描线同侧，不需要合并。合并。- 组合为线段组合为线段(2,1)(2,1)。所覆盖的光栅为。所覆盖的光

18、栅为(2,1)。2022/5/135.2 图形光栅化图形光栅化取扫描线取扫描线y=2- 检查检查AEL表，清除所有满足表，清除所有满足“上端点上端点yy”的边，现在没有。的边，现在没有。- 更新交点，计算更新交点，计算x = x +1/k。- 检查检查ET表，将下端点表，将下端点y=2的边加到的边加到AEL表。表。 上端点上端点y 交点交点x 斜率斜率1/k。 2 8 6 5 1.75 -1/4 6 8 -1/2- AEL按按x增加排序并取出交点为增加排序并取出交点为(1.75,2) (8,2) (8,2)- 交点合并。为交点合并。为(1.75,2) (8,2)。- 组合为线段组合为线段(1.

19、75,2) (8,2)。所覆盖的光栅为。所覆盖的光栅为(2,2)(3,2) . (8,2)。2022/5/135.2 图形光栅化图形光栅化取扫描线取扫描线y=3- 检查检查AEL表，清除所有满足表，清除所有满足“上端点上端点yy”的边，表中的第一的边，表中的第一行被清除。行被清除。- 更新交点，计算更新交点，计算x = x +1/k。- 检查检查ET表，将下端点表，将下端点y=3的边加入，没有的边加入，没有上端点上端点y 交点交点x 斜率斜率1/k。 5 1.5 -1/4 6 7.5 -1/2- AEL按按x增加排序并取出交点为增加排序并取出交点为(1.5,3) (7.5,3)- 没有需要合并

20、的交点。没有需要合并的交点。- 组合为线段组合为线段(1.5,3) (7.5,3)。所覆盖的光栅为。所覆盖的光栅为(2,3)(3,3) . (7,3)。2022/5/135.2 图形光栅化图形光栅化取扫描线取扫描线y=4（y=5,6做练习）做练习）- 检查检查AEL表，清除所有满足表，清除所有满足“上端点上端点yy”的边，现在没有。的边，现在没有。- 更新交点，计算更新交点，计算x = x +1/k。- 检查检查ET表，将下端点表，将下端点y=4的边加入的边加入上端点上端点y 交点交点x 斜率斜率1/k。 5 1.25 -1/4 6 7 -1/2 6 5 1/2 5 5 -4- AEL按按x增

21、加排序并取出交点为增加排序并取出交点为(1.25,4) (5,4) (5,4) (7,4)- 不需要合并。不需要合并。 组合为线段组合为线段(1.25,4) (5,4)和和 (5,4) (7,4)。2022/5/135.2 图形光栅化图形光栅化5.2.6 多边形光栅化：种子填充算法（简介）多边形光栅化：种子填充算法（简介） 如果已知区域内的一个光栅点，将它称为种子，那么与它相如果已知区域内的一个光栅点，将它称为种子，那么与它相邻的，上下左右四个方向的四个光栅点或者在区域内，或者在邻的，上下左右四个方向的四个光栅点或者在区域内，或者在边界上。对那些不是边界点的相邻点，逐个取出，作为新种子，边界上

22、。对那些不是边界点的相邻点，逐个取出，作为新种子，同样还可以找到它的四个相邻点。如此循环下去，就能够从最同样还可以找到它的四个相邻点。如此循环下去，就能够从最初的作为种子的点开始，逐渐扩散到整个区域。初的作为种子的点开始，逐渐扩散到整个区域。2022/5/135.3 图形消隐图形消隐 物体的三维特性使得物体表面各部分分散在不同的方向，相物体的三维特性使得物体表面各部分分散在不同的方向，相对于我们的位置，总存在正面和反面，我们看到的只能是正面。对于我们的位置，总存在正面和反面，我们看到的只能是正面。另外，不同的物体由于位置关系，还可能相互遮挡，即使是物另外，不同的物体由于位置关系，还可能相互遮挡

23、，即使是物体的正面，也会不能完全看到。体的正面，也会不能完全看到。 消隐就是对图形进行计算，确认其前后遮挡关系，去除被遮消隐就是对图形进行计算，确认其前后遮挡关系，去除被遮挡的多边形或多边形的一部分。此类方法是基于几何计算的，挡的多边形或多边形的一部分。此类方法是基于几何计算的，称为物体空间算法。称为物体空间算法。 另一类方法是在多边形光栅化之后，绘制时绘制时对同位置另一类方法是在多边形光栅化之后，绘制时绘制时对同位置的像素进行比较，比较该像素与视点的距离，只绘制距离最近的像素进行比较，比较该像素与视点的距离，只绘制距离最近的像素。此类算法称为物体空间算法。的像素。此类算法称为物体空间算法。2

24、022/5/135.3 图形消隐图形消隐5.3.1 凸多面体消隐凸多面体消隐 多面体可以分为凸的或非凸的，凸多面体任意两个相邻面的多面体可以分为凸的或非凸的，凸多面体任意两个相邻面的内夹角都小于内夹角都小于180度。将凸多面体的任意一个面展开成平面，多度。将凸多面体的任意一个面展开成平面，多面体整体上位于该平面的同一侧，不会跨过这个平面。这就意面体整体上位于该平面的同一侧，不会跨过这个平面。这就意味着，如果某一个面的可见的，那么这个面必然整体都可见，味着，如果某一个面的可见的，那么这个面必然整体都可见，不会仅是部分可见。不会仅是部分可见。2022/5/135.3 图形消隐图形消隐 设设N为一个

25、表面多边形的法线，为一个表面多边形的法线，V为面中心指向摄像机的向量，为面中心指向摄像机的向量，N和和V均为单位向量。均为单位向量。N、V夹角由下式计算夹角由下式计算VNcos2022/5/135.3 图形消隐图形消隐如果如果 ，根据余弦的性质，有，根据余弦的性质，有 ，即此时面，即此时面是是“朝向朝向”摄像机的，为朝前面即可见面。摄像机的，为朝前面即可见面。如果如果 ，面，面“背向背向”摄像机，为朝后面，不可见。摄像机，为朝后面，不可见。对凸多面体上的各个面元，都可以根据对凸多面体上的各个面元，都可以根据 的符号来判断其的符号来判断其可见性。可见性。本算法称为凸多面体的本算法称为凸多面体的R

26、oberts消隐算法。算法的意义是，可以消隐算法。算法的意义是，可以很方便地判断出朝后面（即背面）。无论是凸的还是非凸的多很方便地判断出朝后面（即背面）。无论是凸的还是非凸的多面体，背向摄像机的面都是不可见的。面体，背向摄像机的面都是不可见的。对任意多面体，可以先将朝后面去除，再计算朝前面的互相遮对任意多面体，可以先将朝后面去除，再计算朝前面的互相遮挡关系。这样消隐计算的范围就小了很多。挡关系。这样消隐计算的范围就小了很多。0cos 220cos VN2022/5/135.3 图形消隐图形消隐5.3.2 画家消隐算法画家消隐算法 画家在绘画时，往往是采用由远到近的次序。先画较远的景画家在绘画时

27、，往往是采用由远到近的次序。先画较远的景物，再画较近的景物。这样较近的景物自然就遮住了较远的景物，再画较近的景物。这样较近的景物自然就遮住了较远的景物。画家消隐算法基本思路是先按距离对所有面元进行排序，物。画家消隐算法基本思路是先按距离对所有面元进行排序，绘制输出时按先远近的顺序进行绘制，模仿了画家的方法，因绘制输出时按先远近的顺序进行绘制，模仿了画家的方法，因此称为画家消隐算法。此称为画家消隐算法。2022/5/135.3 图形消隐图形消隐 将物体模型看做是多个多边形组成的，将多边形进行排序，将物体模型看做是多个多边形组成的，将多边形进行排序，再按由远到近的顺序逐个多边形进行绘制，自然就能形

28、成正确再按由远到近的顺序逐个多边形进行绘制，自然就能形成正确的遮挡关系。的遮挡关系。 问题问题 一是排序问题。多边形是一个面，其上包含很多个点，按哪一是排序问题。多边形是一个面，其上包含很多个点，按哪个点计算到摄像机视点（个点计算到摄像机视点（z=0）的距离对顺序是有影响的，这里）的距离对顺序是有影响的，这里假设按多边形中心点进行计算。假设按多边形中心点进行计算。 二是两个或多个多边形可能会出现交叉情况，计算时还是要二是两个或多个多边形可能会出现交叉情况，计算时还是要测试顺序相邻的多边形之间的交叉关系，判断交叉的具体情况，测试顺序相邻的多边形之间的交叉关系，判断交叉的具体情况，重新确认前后关系

29、。必要时还要对多边形进行分割，重新排序。重新确认前后关系。必要时还要对多边形进行分割，重新排序。2022/5/135.3 图形消隐图形消隐排序问题的一些情况，假设排序问题的一些情况，假设z轴为视线方向。轴为视线方向。2022/5/135.3 图形消隐图形消隐画家消隐算法步骤为画家消隐算法步骤为（1）将场景中所有多边形存入一个线性表，记为）将场景中所有多边形存入一个线性表，记为L；（2）根据每个多边形的远近（）根据每个多边形的远近（z坐标值大小）对它们进行预排坐标值大小）对它们进行预排序，较远的排在前，较近的排在后。序，较远的排在前，较近的排在后。2022/5/135.3 图形消隐图形消隐画家消

30、隐算法步骤为画家消隐算法步骤为（1）将场景中所有多边形存入一个线性表，记为）将场景中所有多边形存入一个线性表，记为L；（2）根据每个多边形的远近（）根据每个多边形的远近（z坐标值大小）对它们进行预排坐标值大小）对它们进行预排序，较远的排在前，较近的排在后。序，较远的排在前，较近的排在后。2022/5/135.3 图形消隐图形消隐（3）设当前应该绘制的多边形为）设当前应该绘制的多边形为Pi； 找出排在找出排在Pi之后的所有与之后的所有与Pi在在z轴上投影区有重叠的多边形，轴上投影区有重叠的多边形，这些多边形放入这些多边形放入Q；2022/5/135.3 图形消隐图形消隐（4）逐一比较）逐一比较P

31、i与与Q中的中的Qi的前后关系的前后关系 如果如果Pi与所有的与所有的Qi后在后在x及及y方向不重合，则绘制方向不重合，则绘制Pi; 如果如果Pi与上所有顶点在与上所有顶点在Qi的朝向照相机一侧，则交换的朝向照相机一侧，则交换Pi和和Qi ，重新开始重新开始; 如果如果Pi与上所有顶点不全与上所有顶点不全在在在在Qi的同一侧，且的同一侧，且Qi与上与上所有顶点也不全在在所有顶点也不全在在Pi的同的同一侧，计算两者的交线，沿一侧，计算两者的交线，沿交线将交线将Pi分割为两个多边形，分割为两个多边形，重新开始。重新开始。2022/5/135.3 图形消隐图形消隐 画家算法不适合于存在多边形面交叉、

32、甚至是循环交叉的复画家算法不适合于存在多边形面交叉、甚至是循环交叉的复杂情况。如果场景中的物体互相没有相交情况，也没有物体自杂情况。如果场景中的物体互相没有相交情况，也没有物体自相交的情况，那么第（相交的情况，那么第（3）、（）、（4）步就不需要进行，画家算法）步就不需要进行，画家算法简单易行。简单易行。2022/5/135.3 图形消隐图形消隐5.4.3 Z缓存算法缓存算法 缓存就是内存中的一段存储空间。缓存就是内存中的一段存储空间。Z缓存算法需要建立两个缓存算法需要建立两个缓存区，颜色缓存和深度缓存，其大小都和屏幕（也可以是图缓存区，颜色缓存和深度缓存，其大小都和屏幕（也可以是图像）大小相

33、同。即屏幕上的每一个像素，在两个缓存中都有对像）大小相同。即屏幕上的每一个像素，在两个缓存中都有对应的存储单元，存储该像素的颜色和深度。应的存储单元，存储该像素的颜色和深度。2022/5/135.3 图形消隐图形消隐Z缓存算法基本思想缓存算法基本思想 光栅化完成后，每个像素具有窗口坐标光栅化完成后，每个像素具有窗口坐标(x,y)和深度和深度z。绘制时。绘制时若当前点比已经绘制的点远（若当前点比已经绘制的点远（z值更大），则放弃不绘制；若近值更大），则放弃不绘制；若近（z值更小）则绘制并将深度值存入值更小）则绘制并将深度值存入Z缓存。缓存。 Z缓存算法也称深度缓存算法，属于图像空间消隐算法。算缓

34、存算法也称深度缓存算法，属于图像空间消隐算法。算法的最大优点在于步骤简单，它可以自然地处理隐藏面，画面法的最大优点在于步骤简单，它可以自然地处理隐藏面，画面可任意复杂。由于计算过程简单，且显卡已经支持足够的缓存，可任意复杂。由于计算过程简单，且显卡已经支持足够的缓存，Z缓存算法是能够用硬件实现的算法。缓存算法是能够用硬件实现的算法。2022/5/135.3 图形消隐图形消隐Z缓存算法步骤：缓存算法步骤：（1）初始时，深度缓存所有单元均置为最大）初始时，深度缓存所有单元均置为最大z值，帧缓存各单值，帧缓存各单元均置为背景色。元均置为背景色。（2）对场景中所有的面元进行循环，不计该面元是来自哪个物

35、）对场景中所有的面元进行循环，不计该面元是来自哪个物体，也不计该面元在空间哪个位置。原则上，面元的次序是无体，也不计该面元在空间哪个位置。原则上，面元的次序是无关的，实际上还有要按物体一个一个的绘制。关的，实际上还有要按物体一个一个的绘制。（3）对一个面元中所有的像素进行循环。）对一个面元中所有的像素进行循环。 取出一个像素点，其平面坐标为取出一个像素点，其平面坐标为(x,y)，深度值为，深度值为z，颜色值为，颜色值为cokor。若若zD(x,y)，则，则D(x,y)=z，I(x,y)=color，否则不做处理。，否则不做处理。2022/5/135.3 图形消隐图形消隐5.4.4 光线投射算法

36、（简介）光线投射算法（简介） 从屏幕上每一个像素点出发，沿着视线（摄像机投射线）方从屏幕上每一个像素点出发，沿着视线（摄像机投射线）方向发射出一条光线。对场景中所有物体，计算与光线的交点，向发射出一条光线。对场景中所有物体，计算与光线的交点，就是光线投射算法。就是光线投射算法。2022/5/135.3 图形消隐图形消隐求交点的方法：求交点的方法：for （每个物体）（每个物体） 光线与物体包围盒是否有交点光线与物体包围盒是否有交点 if 有交点有交点 for （每个面元）（每个面元） 检查像素点是否在面元包围盒内检查像素点是否在面元包围盒内 if（在面元包围盒内）（在面元包围盒内） 计算交点计

37、算交点P 存储到数组存储到数组T 2022/5/135.3 图形消隐图形消隐 过程结束后，全部交点存储在数组过程结束后，全部交点存储在数组T中，对中，对T按距离顺序进按距离顺序进行排序，最远的交点排在前面，相对较近的交点排在后面。行排序，最远的交点排在前面，相对较近的交点排在后面。 如果没有交点，则如果没有交点，则T = null，该像素的颜色为背景色。，该像素的颜色为背景色。 如果如果Tnull，考虑到场景中存在透明的物体，那么应该按透，考虑到场景中存在透明的物体，那么应该按透明度规则进行混合运算。过程如下明度规则进行混合运算。过程如下 像素颜色像素颜色=背景色背景色 for （每个交点（每

38、个交点Ti） 像素颜色像素颜色=Ti透明度透明度Ti颜色颜色 + (1- Ti透明度透明度) 像素颜色像素颜色 2022/5/135.3 图形消隐图形消隐 光线投射算法与光线投射算法与Z缓存算法很相似，可以说是次序上的不同，缓存算法很相似，可以说是次序上的不同，但光线投射算法有着较强的实用性。但光线投射算法有着较强的实用性。 在渲染中，实际上需要进行的图形计算始终以像素为最终目在渲染中，实际上需要进行的图形计算始终以像素为最终目标，所有的计算都是为某个像素进行的。模型上有无数个点，标，所有的计算都是为某个像素进行的。模型上有无数个点，最终与像素对应的那个点才是有计算意义的点。使用光线投射最终与

39、像素对应的那个点才是有计算意义的点。使用光线投射算法先得到需要计算的点，然后光照计算、纹理映射等工作都算法先得到需要计算的点，然后光照计算、纹理映射等工作都是对这个点进行，才是有秩序、有效率的计算流程。是对这个点进行，才是有秩序、有效率的计算流程。2022/5/13习题习题1 说明在多边形的逐边裁剪法的步骤和规则，并举例说明说明在多边形的逐边裁剪法的步骤和规则，并举例说明2 下图所示多边形，按逐边裁剪法进行裁剪，写出裁剪步骤下图所示多边形，按逐边裁剪法进行裁剪，写出裁剪步骤2022/5/13习题习题3 消隐算法分为哪两大类？各自的特点和适用性如何？你所了消隐算法分为哪两大类？各自的特点和适用性如何？你所了解的几种算法，分别属于哪类？解的几种算法，分别属于哪类？4 写出凸多面体消隐算法的具体步骤，为什么该算法只适合于写出凸多面体消隐算法的具体步骤，为什么该算法只适合于凸多面体？凸多面体？5 顶点为顶点为A(0,0,1),B(2,0,1),C(1,2,2),D(0,2,1)所构成的四面体，若所构成的四面体，若视线向着视线向着Z轴的正向，确定能够显示的面。轴的正向，确定能够显示的面。6 说明画家算法的处理步骤。说明画家算法的处理步骤。7 比较比较 Z-Buffer消隐算法及光线投射消隐算法的不同。消隐算法及光线投射消隐算法的不同。