第四章 光栅图形学
计算机图形学 第四章 光栅图形学的相关内容,包括:直线段的扫描转换算法、圆弧的扫描转换算法、多边形区域填充、字符的生成、裁剪、反走样 等
Def 光栅显示器:一个像素矩阵(因此,要在光栅显示器上显示的图形逼近真实图形,需要用到下面的算法)
4.1 直线段的扫描转换算法
目标:需要在光栅显示器上画出过两点 P0(x0,y0)P_0(x_0,\,y_0)P0(x0,y0) 和 P1(x1,y1)P_1(x_1,\,y_1)P1(x1,y1) 的直线 LLL 的最佳逼近
直线的三个算法轮流考,中点画线法和Bresenham算法一定要写出递推的优化算法
数值微分法(DDA)
算法
① 当 k≤1k\le1k≤1 时,以 LLL 横坐标起点 x0x_0x0 向横坐标终点以步长为 1 个像素步进,每次计算当前纵坐标的理论值 yiy_iyi 并做四舍五入:令 y=kx+by=kx+by=kx+b ,则令 (xi,round(kxi+b))(x_i,\,round(kx_i+b))(xi,round(kxi+b)) 作为当前像素的坐标
② 但是这样每次都要计算 kxi+bkx_i+bkxi+b ,比较麻烦,可以使用增量计算:
yi+1=kxi+1+b=k(xi+1)+b=yi+ky_{i+1}=kx_{i+1}+b=k(x_i+1)+b=y_i+k yi+1=kxi+1+b=k(xi+1)+b=yi+k
因此,只需令纵坐标每次递增 kkk ,再做四舍五入
代码
void DDALine(int x0, int y0, int x1, int y1, int color) {int x;float dx, dy, y, k;dx = x1 - x0;dy = y1 - y0;k = dy / dx;y = y0;for (x = x0; x < x1; ++x) {drawPixel(x, int(y + 0.5), color);y += k;}}
注意:当 k≥1k\ge1k≥1 时,以 LLL 纵坐标起点 y0y_0y0 向纵坐标终点 y1y_1y1 以步长为 1 个像素步进,每次计算当前横坐标的理论值 xix_ixi 并做四舍五入
注意:四舍五入后取整不利于硬件实现
例:用 DDA 方法扫描转换连接两点 P0(0,0)P_0(0,\,0)P0(0,0) 和 P1(5,2)P_1(5,\,2)P1(5,2) 的直线段
中点划线法
算法
① 当 k≤1k\le1k≤1 时,设当前坐标为 (xi,yi)(x_i,\,y_i)(xi,yi) ,则下一个坐标可以是 (xi+1,yi)(x_i+1,\,y_i)(xi+1,yi) 或 (xi+1,yi+1)(x_i+1,y_i+1)(xi+1,yi+1) ,怎么选择呢?令下一点的实际位置为 QQQ 点,下一位置的两个选择的中点为 MMM :
若 QQQ 在 MMM 上方,则选择 (xi+1,yi+1)(x_i+1,y_i+1)(xi+1,yi+1)若 QQQ 在 MMM 下方,则选择 (xi+1,yi)(x_i+1,y_i)(xi+1,yi)
② 如何判别 QQQ 与 MMM 的位置关系?设过点 P0(x0,y0)P_0(x_0,\,y_0)P0(x0,y0) 和 P1(x1,y1)P_1(x_1,\,y_1)P1(x1,y1) 的直线 LLL 方程为:
F(x,y)=ax+by+c=0;(a=y0−y1;b=x1−x0;c=x0y1−x1y0)F(x,\,y)=ax+by+c=0;\quad (a=y_0-y_1;\,b=x_1-x_0;\,c=x_0y_1-x_1y_0) F(x,y)=ax+by+c=0;(a=y0−y1;b=x1−x0;c=x0y1−x1y0)
只需要将 MMM 带入 F(x,y)F(x,\,y)F(x,y) 即可得到 MMM 与直线的位置关系:
d=F(M)=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+cd=F(M)=F(x_i+1,y_i+0.5)=a(x_i+1)+b(y_i+0.5)+c d=F(M)=F(xi+1,yi+0.5)=a(xi+1)+b(yi+0.5)+c
当 d<0d\lt 0d<0 ,MMM 在 QQQ 点(直线 LLL )下方,取 (xi+1,yi+1)(x_i+1,\,y_i+1)(xi+1,yi+1) 为下一个像素点当 d>0d\gt 0d>0 ,MMM 在 QQQ 点(直线 LLL )上方,取 (xi+1,yi)(x_i+1,\,y_i)(xi+1,yi) 为下一个像素点当 d=0d=0d=0 ,MMM 和 QQQ 点重合,约定取 (xi+1,yi)(x_i+1,\,y_i)(xi+1,yi) 为下一个像素点
③ 每次需要计算下一个 ddd,太麻烦了,同样也可以使用增量计算:
ddd 的初始值为:
F(x0+1,y0+0.5)=(ax0+by0+c)+a+0.5b=F(x0,y0)+a+0.5b=a+0.5bF(x_0+1,\,y_0+0.5)=(ax_0+by_0+c)+a+0.5b=F(x_0,\,y_0)+a+0.5b=a+0.5b F(x0+1,y0+0.5)=(ax0+by0+c)+a+0.5b=F(x0,y0)+a+0.5b=a+0.5b
若 di>0d_i\gt 0di>0 ,则 di+1=F(xi+2,yi+0.5)=di+ad_{i+1}=F(x_i+2,\,y_i+0.5)=d_i+adi+1=F(xi+2,yi+0.5)=di+a ,增量为 aaa
若 di<0d_i\lt 0di<0 ,则 di+1=F(xi+2,yi+1.5)=di+a+bd_{i+1}=F(x_i+2,\,y_i+1.5)=d_i+a+bdi+1=F(xi+2,yi+1.5)=di+a+b ,增量为 a+ba+ba+b
④ 由于 aaa、bbb 和 ccc 都是整数,而加 0.5b0.5b0.5b 又涉及浮点数运算了,所以可以使用 2d2d2d 来代替 ddd 加速
代码
void MidPointLine(int x0, int y0, int x1, int y1, int color) {int a, b, d1, d2, d, x, y;a = y0 - y1;b = x1 - x0;d = 2 * a + b;d1 = 2 * a;d2 = 2 * (a + b);x = x0;y = y0;while (x < x1) {if (d < 0) {++x; ++y; d += d2;} else {++x; d += d1;}drawPixel(x, y, color);}}
注意:当 k≥1k\ge1k≥1 时,以 LLL 纵坐标起点 y0y_0y0 向纵坐标终点 y1y_1y1 以步长为 1 个像素步进,ddd 的初始值为 0.5a+b0.5a+b0.5a+b ,d1=bd_1=bd1=b ,d2=a+bd_2=a+bd2=a+b
例:用中点画线法扫描转换连接两点 P0(0,0)P_0(0,\,0)P0(0,0) 和 P1(5,2)P_1(5,\,2)P1(5,2) 的直线段
// initializationa = y0 - y1 = -2;b = x1 - x0 = 5;d0 = 2 * a + b = 1;d1 = 2 * a = -4;d2 = 2 * (a + b) = 6;
Bresenham 算法
算法
①(假设斜率 k≤0k\le0k≤0 )过各行各列像素中心构造网格线;采用增量计算,计算直线与垂直网格线交点到下一水平网格线的距离 ddd (误差项),依据 ddd 的大小判断下一像素点的选取:
当 d>0.5d\gt 0.5d>0.5 时,选取 (xi+1,yi+1)(x_i+1,\,y_i+1)(xi+1,yi+1)当 d≤0.5d\le 0.5d≤0.5 时,选取 (xi+1,yi)(x_i+1,\,y_i)(xi+1,yi)
误差项 ddd 的初值 d0=0d_0=0d0=0 ;当横坐标增加 1 时,误差项 ddd 的增量为 kkk ;当 ddd 大于 1 时,将其减一,保证 d∈[0,1]d\in[0,\,1]d∈[0,1] :
② 为了方便计算,可令 e=d−0.5e=d-0.5e=d−0.5 ,e0=−0.5e_0=-0.5e0=−0.5 ,增量为 kkk :
当 e>0e\gt 0e>0 时,选取 (xi+1,yi+1)(x_i+1,\,y_i+1)(xi+1,yi+1)当 e≤0e\le 0e≤0 时,选取 (xi+1,yi)(x_i+1,\,y_i)(xi+1,yi)
(因为只用到误差项 eee 的符号,所以可以改用整数 2e2e2e 来避免除法)
代码
void BresenhamLine(int x0, int y0, int x1, int y1, int color) {int x, y, dx, dy;float k, e;dx = x1 - x0;dy = y1 - y0;k = dy - dx;e = -0.5;x = x0;y = y0;for (int i = 0; i < dx; ++i) {drawPixel(x, y, color);++x;e += k;if (e > 0.5)e -= 1;if (e >= 0)++y;}}
例:用Bresenham画线法扫描转换连接两点 P0(0,0)P_0(0,\,0)P0(0,0) 和 P1(5,2)P_1(5,\,2)P1(5,2) 的直线段
4.2 圆弧的扫描转换算法
目标:
需要在光栅显示器上画出以原点 O(0,0)O(0,\,0)O(0,0) 为圆心、以 RRR (RRR 为整数)为半径的圆需要在光栅显示器上画出以原点 O(0,0)O(0,\,0)O(0,0) 为对称中心、以 aaa 、bbb 为椭圆参数的椭圆
圆
#### 简单方程产生圆弧(DDA)算法
利用函数方程直接离散计算:
x2+y2=R2xi+1=xi+1,x∈[0,R2]yi+1=round(R2−xi+12)x^2+y^2=R^2 \\ x_{i+1}=x_i+1,\quad x\in[0,\,\frac{R}{\sqrt{2}}] \\ y_{i+1}=round(\sqrt{R^2-x_{i+1}^2}) x2+y2=R2xi+1=xi+1,x∈[0,2R]yi+1=round(R2−xi+12)
中点画圆法
算法
原方程:F(x,y)=x2+y2−R2F(x,\,y)=x^2+y^2-R^2F(x,y)=x2+y2−R2
构造判别式:d=F(M)=F(xp+1,yp−0.5)=(xp+1)2+(yp+1)2−R2d=F(M)=F(x_p+1,\,y_p-0.5)=(x_p+1)^2+(y_p+1)^2-R^2d=F(M)=F(xp+1,yp−0.5)=(xp+1)2+(yp+1)2−R2 :
初始值为 d0=F(1,R−0.5)=1.25−Rd_0=F(1,\,R-0.5)=1.25-Rd0=F(1,R−0.5)=1.25−R
若 d<0d\lt 0d<0 ,取 P1P_1P1 为下一像素点,再下一像素的判别式为:
d=F(xp+2,yp−0.5)=d+2xp+3d=F(x_p+2,\,y_p-0.5)=d+2x_p+3 d=F(xp+2,yp−0.5)=d+2xp+3
若 d≥0d\ge 0d≥0 ,取 P2P_2P2 为下一像素点,再下一像素的判别式为:
d=F(xp+2,yp−1.5)=d+2(xp−yp)+5d=F(x_p+2,\,y_p-1.5)=d+2(x_p-y_p)+5 d=F(xp+2,yp−1.5)=d+2(xp−yp)+5
代码
void MidPointCircle(int r, int color) {int x = 0, y = r;float d = 1.25 - r;circlePoint(x, y, color);while (x <= y) {if (d < 0)d += 2 * x + 3;else {d += 2 * (x - y) + 5;--y;}++x;circlePoints(x, y, color);}}
Bresenham算法
考试不会考
原理和前面 Bresenham 算法画直线的原理差不多
椭圆
计算量比较大,考的概率较低
中点画椭圆法
算法
以 a>ba\gt ba>b 的椭圆为例:
方程式:F(x,y)=b2x2+a2y2−a2b2=0F(x,\,y)=b^2x^2+a^2y^2-a^2b^2=0F(x,y)=b2x2+a2y2−a2b2=0 (椭圆外的点,F(x,y)>0F(x,\,y)\gt0F(x,y)>0 )
法向量:N(x,y)=2b2xi+2a2yjN(x,\,y)=2b^2xi+2a^2yjN(x,y)=2b2xi+2a2yj ,因此分界点为 (22a,22b)(\frac{\sqrt2}{2}a,\,\frac{\sqrt2}{2}b)(22a,22b)
上半部分
判别式 d1=F(xi+1,yi−0.5)=b2(xi+1)2+a2(yi−0.5)2−a2b2d_1=F(x_i+1,\,y_i-0.5)=b^2(x_i+1)^2+a^2(y_i-0.5)^2-a^2b^2d1=F(xi+1,yi−0.5)=b2(xi+1)2+a2(yi−0.5)2−a2b2 :
判别式初始值为 d10=F(1,b−0.5)=b2+a2(−b+0.25)d_{10}=F(1,\,b-0.5)=b^2+a^2(-b+0.25)d10=F(1,b−0.5)=b2+a2(−b+0.25)若 d1≤0d_1\le0d1≤0 ,取 PuP_uPu 为下一像素点,下一判别式的值为:
d1=F(xi+2,yi−0.5)=d1+b2(2xi+3)d_1=F(x_i+2,\,y_i-0.5)=d_1+b^2(2x_i+3) d1=F(xi+2,yi−0.5)=d1+b2(2xi+3)
若 d1>0d_1\gt0d1>0 ,取 PdP_dPd 为下一像素点,下一判别式的值为:
d1=F(xi+2,y1−1.5)=d1+b2(2xi+3)+a2(−2yi+2)d_1=F(x_i+2,\,y_1-1.5)=d_1+b^2(2x_i+3)+a^2(-2y_i+2) d1=F(xi+2,y1−1.5)=d1+b2(2xi+3)+a2(−2yi+2)
下半部分
判别式 d2=F(xi+0.5,yi−1)=b2(xi+0.5)2+a2(yi−1)2−a2b2d_2=F(x_i+0.5,\,y_i-1)=b^2(x_i+0.5)^2+a^2(y_i-1)^2-a^2b^2d2=F(xi+0.5,yi−1)=b2(xi+0.5)2+a2(yi−1)2−a2b2
判别式初始值按照上半部分的最后一个点确定若 d2>0d_2\gt0d2>0 ,取 PlP_lPl 为下一像素点,下一判别式的值为:
d2=F(xi+0.5,yi−2)=d2+a2(−2yi+3)d_2=F(x_i+0.5,\,y_i-2)=d_2+a^2(-2y_i+3) d2=F(xi+0.5,yi−2)=d2+a2(−2yi+3)
若 d2<0d_2\lt0d2<0 ,取 PrP_rPr 为下一像素点,下一判别式的值为:
d2=F(xi+1.5,yi−2)=d2+b2(2xi+2)+a2(−2yi+3)d_2=F(x_i+1.5,\,y_i-2)=d_2+b^2(2x_i+2)+a^2(-2y_i+3) d2=F(xi+1.5,yi−2)=d2+b2(2xi+2)+a2(−2yi+3)
(仔细观察一下,上半部分和下半部分的判别式增量是对称的)
4.3 多边形区域填充
两种表示方法:顶点表示和点阵表示
扫描线算法
考过好几次。给图形,写出活性边表的迭代过程,还要写出扫描线的四个转换步骤。可能也要写伪代码,或解释活性边表项的内容
步骤:
求交:计算扫描线与多边形各边的交点排序:把所有交点按照横坐标递增顺序排序配对:排序后的交点序列中相邻的两个进行配对着色:把相交区间内的像素置成多边形颜色,区间外的像素填充为背景色
算法:
活性边:多边形中与当前扫描线相交的边
(图中每个点代表每个像素)
活性边表(AET):链表,结点代表多边形的某条边与当前扫描线的脚店情况,按照横坐标递增存放,保存的信息有:
xxx :当前扫描线与边的交点Δx\Delta xΔx :从当前扫描线到下一条扫描线之间的交点的 xxx 增量ymaxy_{max}ymax :该边所交的最高扫描线号(扫描线号就是纵坐标)
(活性边表只有一个,但是会随着遍历扫描线的过程而动态变化,表里每一项代表多边形的一条边)
(活性边表代表当前被遍历到的扫描线与多边形各边的交点情况)
如扫描线 666 和 777 的活性边表(AET):
新边表(NET):每一条扫描线都建立一个新边表,用于存放 第一次出现交点是与当前扫描线相交的多边形的边(若某边的较低端点为 yminy_{min}ymin ,则该边存放在扫描线 yminy_{min}ymin 的新边表中)
交点取舍:扫描线与多边形的顶点相交时,需要做取舍
方法:检查顶点的两条边的另外两个端点 yyy 值,按这两个 yyy 值中大于交点 yyy 值的个数是 0、1、2 来决定取零个、一个还是两个交点
共享顶点的两条边落在扫描线两侧,则只取一个交点,如 P1P_1P1共享顶点的两条边落在扫描线同一侧: 若交点是局部最高点,即 yi>yi−1y_i\gt y_{i-1}yi>yi−1 且 yi>yi+1y_i\gt y_{i+1}yi>yi+1 ,则取零个交点,如 P6P_6P6若交点是局部最高点,即 yi<yi−1y_i\lt y_{i-1}yi<yi−1 且 yi<yi+1y_i\lt y_{i+1}yi<yi+1 ,则取两个交点,如 P2P_2P2
增量法:下一扫描线与多边形某条边的交点横坐标不需要重新计算,只需要 xi+Δxx_i+\Delta xxi+Δx
若该边的方程为 ax+by+c=0ax+by+c=0ax+by+c=0 ,则Δx=−ba\Delta x=-\frac{b}{a}Δx=−ab
算法步骤:
void polyfill(多边形 polygon, int color) {for (i : 扫描线) {初始化新边表头指针NET[i];将 ymin = i 的边放入新边表 NET[i];}创建空的AET表;for (i : 扫描线) {插入排序法: 将NET[i]中的所有边结点插入AET;//保证按横坐标递增顺序排列// 此时AET表中除了新边,还有ymax > i 的边结点遍历AET表,删除 ymax = i的结点;for((x, y) : 左闭右开的配对交点区间) {drawpixel(x, y, color);将ymax > i的结点的x值递增dx;}}}
举例:沿用上面的多边形,活性边表 AET 的迭代过程:(加粗代表新增加的边)
边界标志算法
在帧缓冲器中对边界经过的像素打上标志,然后对每行循环每个像素填充颜色
简单暴力,计算量大,适合硬件实现、对多边形形状没有要求
(记录一个 flag 用于指示是否在多边形内部,每次遇到多边形的边界就反转 flag)
种子填充算法
有点像是 BFS,从区域内某一点(种子点)出发,通过四个(4向连通区域)或八个(8向连通区域)的移动组合来到达区域内的任意像素
因此要求填充区域是联通的,且初始状态下填充区域内部颜色统一,填充区域边界颜色统一
原理简单,但递归费时费内存,效率不高
种子填充的扫描线算法
从种子点向左右填充直到边界,再从两端向上下找未填充像素作为种子压栈,重复上述过程
每个区间只需入栈一次
4.4 字符的生成
字符编码
美国信息交换标准代码集ASCII码
汉字编码国家标准字符集GB2312-80
字符最高位 0表示ASCII码,1表示汉字编码
字符表达和生成
点阵式字符
硬件操作快,可以加粗、旋转90度、斜体、比例缩放等,任意角度旋转比较困难
加粗:每个像素 (xi,y)(x_i,\,y)(xi,y) 右边相邻的像素 (xi+1,y)(x_{i+1},\,y)(xi+1,y) 也被写入旋转90°:每个像素先交换 xxx 和 yyy 坐标,再改变 yyy 的符号(先沿对角线翻转,在上下翻转)斜体:逐行拷贝像素,每隔 nnn 行左移一单元
压缩技术
黑白段压缩法:简单,还原快,不失真,压缩较差,使用不方便,用于低级文字处理系统
部件压缩法:压缩比大,字型质量不能保证
轮廓字型法:压缩比大,能保证质量,符合工业标准化方法
采用直线或二/三次贝塞尔曲线的集合来描述一个字符的轮廓线,加上指示横宽、竖宽、基点、基线等的控制信息(即构成压缩数据),采用适当的区域填充算法;TrueType轮廓字型技术由Apple和Microsoft联合开发;占领主要电子印刷市场的是北大方正激光照排系统;
矢量式字符
方向编码式字符
用若干种方向编码(如8方向编码)来表达一个字符,偶数方向固定长度为 1 ,奇数方向固定长度为 2\sqrt22
字母“B”的方向矢量构成:{0000 123 444 000 123 4444 0 666666}
容易填入帧缓存寄存器显示,所占空间小,易放大缩小或45度旋转,但难以进行任意角度的旋转
4.5 裁剪
三个算法不会同时考
一般是先裁剪再扫描转换
直线段裁剪
Cohen-Sutherland裁剪算法
考了无数次 [\doge]
延长窗口四条边,将平面分为九宫格;每个格用四位编码 CtCbCrClC_tC_bC_rC_lCtCbCrCl :
C_t = y > y_max ? 1 : 0;// topC_b = y > y_max ? 0 : 1;// bottomC_r = x > x_max ? 1 : 0;// rightC_l = x > x_max ? 0 : 1;// left
裁剪一条线段 P1P2P_1P_2P1P2 时,先求出所在区号 code1code_1code1 、code2code_2code2 :
若 code1=0code_1=0code1=0 且 code2=0code_2=0code2=0 ,则说明线段 P1P2P_1P_2P1P2 完全在窗口内,不需要裁剪,直接保留若 code1&code2≠0code_1\,\&\,code_2\not=0code1&code2=0 ,则说明线段 P1P2P_1P_2P1P2 完全在窗口外,不需要裁剪,直接舍弃否则,求出线段与窗口某边的交点,在交点处把线段一分为二,其中必有一段完全在窗口外,舍弃;再对另一段重复上述处理
注意:第三种情况求交点时,可以取任意一个编码不为 0 的端点,然后按顺序遍历编码的每一位,取编码不为 0 的那一位对应的窗口边界,求边与此窗口边界的交点
中点分割方法(求交点的算法)
Cohen-Sutherland 裁剪算法在的第三种情况需要求出 P0P1P_0P_1P0P1 与窗口的一个交点,可以用中点分割算法进行求交点的优化:
首先求出 P0P1P_0P_1P0P1 的中点 PmP_mPm 及其编码 若 P0PmP_0P_mP0Pm 不是显然不可见的:(此时已知 P0P1P_0P_1P0P1 在窗口中有可见部分)则 P0PmP_0P_mP0Pm 中必与窗口有一个交点,所以用 P0PmP_0P_mP0Pm 代替 P0P1P_0P_1P0P1若 P0PmP_0P_mP0Pm 是显然不可见的:则用 PmP1P_mP_1PmP1 代替 P0P1P_0P_1P0P1 重复上述过程,直到 P0P1P_0P_1P0P1 的长度小于给定的常数为止,此时 PmP_mPm 收敛于交点
(Cohen-Sutherland 裁剪算法在的第三种情况需要求出 P0P1P_0P_1P0P1 与窗口的一个交点,而且只需要求出一个交点就够了)
注意:由于该算法的主要计算过程只用到加法和除 2 运算,所以特别适合硬件实现和并行计算
梁友栋-Barskey算法
设线段 P0P1P_0P_1P0P1 端点坐标分别为 (X1,Y1)(X_1,\,Y_1)(X1,Y1) 和 (X2,Y2)(X_2,\,Y_2)(X2,Y2) ;以 (X1,Y1)(X_1,\,Y_1)(X1,Y1) 为起点,参数 0≤μ≤10\le\mu\le10≤μ≤1 ,ΔX=X2−X1\Delta X=X_2-X_1ΔX=X2−X1 ,ΔY=Y1−Y2\Delta Y=Y_1-Y_2ΔY=Y1−Y2 ,则裁剪的保留条件为:
XL≤X1+μΔX≤XRYB≤Y1+μΔY≤YTX_L\le X_1+\mu\Delta X\le X_R \\ Y_B\le Y_1+\mu\Delta Y\le Y_T \\ XL≤X1+μΔX≤XRYB≤Y1+μΔY≤YT
可以表示为:μpk≤qk\mu p_k\le q_kμpk≤qk ,pkp_kpk 和 qkq_kqk 定义为:
p1=−ΔXq1=X1−XLp2=ΔXq2=XR−X1p3=−ΔYq3=Y1−YBp4=ΔYq4=YT−Y1p_1=-\Delta X\quad q_1=X_1-X_L\quad\quad p_2=\Delta X\quad q_2=X_R-X_1\\ p_3=-\Delta Y\quad q_3=Y_1-Y_B\quad\quad p_4=\Delta Y\quad q_4=Y_T-Y_1\\ p1=−ΔXq1=X1−XLp2=ΔXq2=XR−X1p3=−ΔYq3=Y1−YBp4=ΔYq4=YT−Y1
位置关系:
若 pk=0p_k=0pk=0 ,则平行于裁剪边界之一: 若同时有 qk<0q_k\lt 0qk<0 ,则线段完全在边界外,舍弃该线段若此时 qk≥0q_k \ge 0qk≥0 ,则线段平行于裁剪边界且在窗口内 若 pk≠0p_k\not=0pk=0 ,则可以计算出线段与边界 kkk 的延长线的交点的 uuu 值:u=qkpku=\frac{q_k}{p_k}u=pkqk 若 pk<0p_k\lt 0pk<0 ,线段从裁剪边界及延长线的外部延伸到内部,对于不同的边界,有正负不同的 ΔX\Delta XΔX 和 ΔY\Delta YΔY若 pk>0p_k\gt 0pk>0 ,线段从裁剪边界及延长线的内部延伸到外部,对于不同的边界,有正负不同的 ΔX\Delta XΔX 和 ΔY\Delta YΔY
**参数计算:**对于每条直线,计算参数 u1u_1u1 和 u2u_2u2 ,它们定义了裁剪矩形的线段部分:
u1u_1u1 代表线段相对于矩形边界从外到内( pk<0p_k\lt 0pk<0 ),u1=max(0,u_1=max(0,u1=max(0, 其他从外到内的 u)u)u)u2u_2u2 代表线段相对于矩形边界从内到外( pk>0p_k\gt 0pk>0 ),u2=min(1,u_2=min(1,u2=min(1, 其他从内到外的 u)u)u)
交点判断:
若 u1>u2u_1 \gt u_2u1>u2 ,则线段完全落在裁剪窗口之外,舍弃;
否则,裁剪线段可以由参数 u1u_1u1 和 u2u_2u2 计算出来:
(X1+u1ΔX,Y1+u1ΔY)→(X1+u2ΔX,Y1+u2ΔY)(X_1+u_1\Delta X,\,Y_1+u_1\Delta Y)\to(X_1+u_2\Delta X,\,Y_1+u_2\Delta Y) (X1+u1ΔX,Y1+u1ΔY)→(X1+u2ΔX,Y1+u2ΔY)
(实际算法就是对裁剪矩形上下左右边界都进行判断,只要有一个出现舍弃就舍弃;否则算出参数 u1u_1u1 和 u2u_2u2 ,进而算出裁剪线段)
注意:使用参数化的算法,计算更快
多边形裁剪
Sutherland-Hodgeman算法
考虑窗口的每一条边与线段的关系,设线段 SPSPSP 为有向线段,S→PS\to PS→P :
若 SSS 、PPP 均可见,则输出终点 PPP若 SSS 、PPP 均不可见,则不输出若 SSS 可见,PPP 不可见,则输出 SPSPSP 与裁剪线的交点 III若 SSS 不可见,PPP 可见,则输出 SPSPSP 与裁剪线的交点 III 与终点 PPP
记忆:输出 = 交点(如果存在)+ 终点(如果可见)
(即若存在交点,则需输出交点;若终点可见,则需输出终点)
遍历窗口四条裁剪线;对于某一条裁剪线,遍历多边形每一条边,将输出的顶点按顺序连接:
字符串裁剪
经常考简答题,画出四种裁剪精度下裁剪结果的示意图
字符串精度裁剪
求出字符串外包盒(box),与窗口裁剪边进行比较:当字符串外包盒完全再窗口内时显示,否则不显示;字符精度裁剪
先以字符串 box 判断字符串是全删、全留或部分留对于部分留的字符串,逐个测量字符的 box 与窗口裁剪边关系而决定字符保留或删除像素精度裁剪
先以字符串 box 判断字符串是全删、全留或部分留对于部分留的字符串,逐个测量字符的 box 与窗口裁剪边关系而决定字符全删、全留或部分留对部分留的字符的每一笔划,用直线裁剪法对窗边裁剪4.6 反走样
Def 走样:使用离散的光栅显示器显示连续的图形信号,引起失真现象(包括:阶梯状的边界、图形细节失真、狭小图形遗失)
区域采样可能考简答题
提高分辨率
依靠硬件设施,存储器代价和扫描转换时间增加,只能减轻而不能消除锯齿问题
区域采样
根据直线段与像素相交区域面积大小确定该像素的亮度值
将一个像素的面积看作1,则亮度 === 最大亮度 ×\times× 相交面积
面积可以采用离散估计的方法,即将像素均分为 nnn 个子像素,计算中心点落在直线段内的子像素个数 kkk ,则相交区域面积近似值为 kn\frac{k}{n}nk
加权区域采样
相交区域对像素亮度的贡献依赖于该区域与像素中心的距离
同样可以使用离散的计算方法,即将像素均分为 nnn 个子像素,选定一个加权表,则该像素亮度 === 最大亮度 ×∑i=1npiwi\times\,\sum\limits_{i=1}^n p_iw_i×i=1∑npiwi ,其中 wiw_iwi 为子像素权重,当子像素中心落在直线段内时,pi=1p_i=1pi=1 ,否则为 000;
例:将屏幕划分为 n=3×3n=3\times3n=3×3 个子象素,加权表可以取作:
[w1w2w3w4w5w6w7w8w9]=116[121242121]\left[ \begin{matrix} w_1 & w_2 & w_3 \\ w_4 & w_5 & w_6 \\ w_7 & w_8 & w_9 \\ \end{matrix} \right] =\frac{1}{16} \left[ \begin{matrix} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \\ \end{matrix} \right] ⎣⎡w1w4w7w2w5w8w3w6w9⎦⎤=161⎣⎡121242121⎦⎤
8