04-6 第四章 真实感图形显示_面消隐.pptx

第1页：面消隐

计算机图形学讲义 第4章 真实感图形显示——面消隐

第2页：任意多面体的面消隐

任意多面体的面消隐

思考想象：可否使用这样的方法：把所有多边形按照其离视点的最小距离从小到大排序，先画后面的多边形，再依次画前面的多边形？

第3页：

第4页：本章目标与算例条件

目标

设有一个红色四边形的四个顶点 ABCD 的坐标分别为 {{0,0,0},{0,6,0},{6,6,0},{6,0,0}}，另有一个黄色四边形的四个顶点 EFGH 的坐标分别为 {{4,0,4},{6,2,4},{2,6,−4},{0,4,−4}}，设黑色屏幕大小为 0≤x≤7，0≤y≤7，当视点在 z 轴的负无穷远处时，计算屏幕每个像素应该显示的颜色。

第5页：

第6页：

第7页：本章主要内容

主要内容

1. 深度缓存算法基本原理。
2. 基于种子填色算法的深度缓存算法。
   • 计算实例。
   • 程序实现。
3. 基于扫描线算法的深度缓存算法。
   • 计算实例。
   • 程序实现。

第8页：深度缓存算法的基本思想

1 深度缓存算法的基本思想

• 深度缓冲器算法属于图像空间消隐算法。
• 思路：将所有平面对应于投影面同一像素的点与视点的距离进行比较，然后取离视点最近的点的属性值作为该像素的属性值。
• 为了计算方便，把 Z 轴旋转到和视线方向相同。ZB 为各像素处的深度值，CB 为各像素处的颜色值。

第9页：深度缓存算法的步骤

算法的具体步骤

• 初始化 ZB 和 CB：ZB(i, j) = Zmax，CB(i, j) = 背景色。
• For（每个多边形）
  • For（多边形内的每一点）
    • 计算它在这些点处的深度值 z(i, j)。
    • If z(i, j) < ZB(i, j)：ZB(i, j) = z(i, j)；CB(i, j) = 多边形在当前位置的颜色。

第10页：算法实现的关键

算法实现的关键

这个算法的关键在以下两点：

• A. 要尽快判断出哪些点落在一个多边形内。
• B. 并尽快求出一个点的深度值。

对于 A，可以使用区域填充算法，比如种子填色算法或者扫描线算法。对于 B，可以利用平面多边形在相邻点的深度相关性来计算。

第11页：基于种子填色的深度缓存算法

2 基于种子填色算法的深度缓存算法

void seed_filling(x, y, fcolor, bcolor) int x, y, fcolor, bcolor; { int c; c = getpixel(x, y); if (c != fcolor && c != bcolor) { putpixel(x, y, fcolor); seed_filling(x+1, y, fcolor, bcolor); seed_filling(x-1, y, fcolor, bcolor); seed_filling(x, y+1, fcolor, bcolor); seed_filling(x, y-1, fcolor, bcolor); } }

第12页：种子填色算法（填充边界）

种子填色算法（填充边界）

void seed_filling(x, y, fcolor, bcolor) int x, y, fcolor, bcolor; { int c; c = getpixel(x, y); if (c == bcolor) putpixel(x, y, fcolor); else if (c != fcolor) { putpixel(x, y, fcolor); seed_filling(x+1, y, fcolor, bcolor); seed_filling(x-1, y, fcolor, bcolor); seed_filling(x, y+1, fcolor, bcolor); seed_filling(x, y-1, fcolor, bcolor); } }

第13页：深度值的计算

深度值的计算

设某个多边形所在平面方程为 ax + by + cz + d = 0，则有深度值 z 的表达式；相邻点之间可利用深度相关性由已知深度递推得到。

第14页：深度缓存计算实例

计算实例

设有一个红色四边形的四个顶点 ABCD 的坐标分别为 {{0,0,0},{0,6,0},{6,6,0},{6,0,0}}，另有一个黄色四边形的四个顶点 EFGH 的坐标分别为 {{4,0,4},{6,2,4},{2,6,−4},{0,4,−4}}，设黑色屏幕大小为 0≤x≤7，0≤y≤7，当视点在 z 轴的负无穷远处时，用深度缓存算法（基于种子填色算法）计算屏幕每个像素应该显示的颜色。

第15页：

第16页：

第17页：

第18页：算法的具体步骤（实例）

算法的具体步骤

• 初始化 ZB 和 CB：ZB(i, j) = Zmax，CB(i, j) = 背景色。
• For（每个多边形）
  • For（多边形内的每一点）
    • 计算它在这些点处的深度值 z(i, j)。
    • If z(i, j) < ZB(i, j)：ZB(i, j) = z(i, j)；CB(i, j) = 多边形在当前位置的颜色。

第19页：具体计算过程：初始化

具体计算过程

初始化 ZB 和 CB：ZB(i, j) = 100，CB(i, j) = 黑，0 ≤ i ≤ 7，0 ≤ j ≤ 7。

第20页：多边形ABCD的平面方程

• 对多边形 ABCD，可得到其平面方程为 z = 0。
• 忽略各点的 z 坐标，把多边形各边画到屏幕上，得到一些离散的点作为边界，并可知 (1,1) 为多边形内一点，其 z 值为常数 0。

第21页：ABCD内像素的填充顺序

填充 ABCD 内各像素的顺序：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 20 21 22 23 19 18 17 25 24 26 31 32 30 29 27 28 33 34 35 38 36 37 39 40 41 42 43 44 45

第22页：ABCD的逐点深度比较

从点 (1,1) 开始用种子填色算法遍历 ABCD 内每一点：

• 对点 (1,1)，不是边界，且 z(1,1) < ZB(1,1)，故 ZB(1,1) = z(1,1) = 0，CB(1,1) = 红。
• 对点 (2,1)，不是边界，且 z(2,1) < ZB(2,1)，故 ZB(2,1) = z(2,1) = 0，CB(2,1) = 红。
• 对点 (5,1)，不是边界，且 z(5,1) < ZB(5,1)，故 ZB(5,1) = z(5,1) = 0，CB(5,1) = 红。
• 对点 (6,1)，是边界，且 z(6,1) < ZB(6,1)，故 ZB(6,1) = z(6,1) = 0，CB(6,1) = 红。
• 对点 (4,1)，已被填充。
• 对点 (5,2)，不是边界，且 z(5,2) < ZB(5,2)，故 ZB(5,2) = z(5,2) = 0，CB(5,2) = 红。
• 对点 (6,2)，是边界，且 z(6,2) < ZB(6,2)，故 ZB(6,2) = z(6,2) = 0，CB(6,2) = 红。
• 对点 (4,2)，已被填充。

第23页：多边形EFGH的平面方程

• 对多边形 EFGH，可得到其平面方程为 x − y − z = 0。
• 忽略各点的 z 坐标，把多边形各边画到屏幕上，得到一些离散的点作为边界，并可知 (2,4) 为多边形内一点，其 z 值为 −2，a/c = −1，b/c = 1。

第24页：EFGH内像素的深度递推

填充 EFGH 内各像素的顺序与深度递推（z = x − y，a/c = −1，b/c = 1）：

• z(2,4) = −2
• z(3,4) = z(2,4) − a/c = −1
• z(4,4) = z(3,4) − a/c = 0
• z(3,5) = z(3,4) − b/c = −2
• z(3,3) = z(3,4) + b/c = 0
• z(4,3) = z(3,3) − a/c = 1

第25页：EFGH的逐点深度比较

从点 (2,4) 开始用种子填色算法遍历 EFGH 内每一点：

• 对点 (2,4)，不是边界，且 z(2,4) = −2，ZB(2,4) = 0，故 ZB(2,4) = z(2,4) = −2，CB(2,4) = 黄。
• 对点 (3,4)，不是边界，且 z(3,4) = z(2,4) − a/c = −1，ZB(3,4) = 0，故 ZB(3,4) = z(3,4) = −1，CB(3,4) = 黄。
• 对点 (4,4)，是边界，且 z(4,4) = z(3,4) − a/c = 0，ZB(4,4) = 0，故 ZB 和 CB 不变。
• 对点 (2,4)，已被填充。
• 对点 (3,5)，是边界，且 z(3,5) = z(3,4) − b/c = −2，ZB(3,5) = 0，故 ZB(3,5) = z(3,5) = −2，CB(3,5) = 黄。
• 对点 (3,3)，不是边界，且 z(3,3) = z(3,4) + b/c = 0，ZB(3,3) = 0，故 ZB 和 CB 不变。

第26页：

第27页：

第28页：算法实现

算法实现

第29页：基于种子填色深度缓存算法的优缺点

基于种子填色算法的深度缓存算法的优缺点

• 优点：实现简单，容易理解。
• 缺点：
  • 基于种子填色算法的深度缓存算法速度较慢。
  • 对大区域无法填满。

第30页：深度缓存算法的优缺点

深度缓存算法的优缺点

• 优点：实现简单，容易理解。
• 缺点：ZB 和 CB 两个缓存数组占用的存储单元太多。

第31页：本章作业

作业

设黑色屏幕已经画有一个红色四边形，此四个顶点 ABCD 的坐标分别为 {{0,0,0},{0,6,0},{6,6,0},{6,0,0}}，现另有一个黄色四边形的四个顶点 EFGH 的坐标分别为 {{0,4,4},{2,6,4},{6,2,−4},{4,0,−4}}，设黑色屏幕大小为 0≤x≤7，0≤y≤7，当视点在 z 轴的负无穷远处时，用深度缓存算法（基于种子填色算法）计算屏幕每个像素应该显示的颜色。画出图形加以解释。