计算机图形学提纲
计算机图形学提纲
注：本代码为伪代码，部分风格依据 python
扫描转换算法
直线
DDA算法
当斜率绝对值小于1时
def LineDDA(x0: int, y0: int, x1: int, y1: int):
m = (y1-y0)/(x1-x0) # y增量
x = x0
y = float(y0)+0.5 # 始点
for x in range(x0, x1):
putPixel(x, int(y))
y += m
中点画线法
令 \(f(x, y)=Ax+By+C\) ，则
- f > 0，则位于直线上方
- f = 0，则位于直线
- f < 0，则位于直线下方
计算 \(f (x+1, y+0.5)\) ，若 < 0 则取 (x+1, y+1)，若 > 0 则取 (x+1, y)
- 若取 (x+1, y+1)，则 \(f\) 增量为 \(f (x+2, y+1.5)-f (x+1, y+0.5)=A+B\)
- 若取 (x+1, y)，则 \(f\) 增量为 \(f (x+2, y+0.5)-f (x+1, y+0.5)=A\)
初始值为 d = (x0+1, y0+0.5) ，后随节点更新加上增量
def MidPointLine(x0: int, y0: int, x1: int, y1: int):
dx = x1-x0
dy = y1-y0
d = dx-2*dy # 初始值
incrE = -2*dy # (x+1, y)增量
incrNE = 2*(dx-dy) # (x+1, y+1)增量
y = y0
for x in range(x0, x1):
putPixel(x, y)
if d > 0:
d += incrE
else:
d += incrNE
y += 1
Bresenham 算法
按照增量计算下一点，即
-
累计的 \(\Delta y+k>0.5\)，则向上画点，\(\Delta y\) – – += k
-
累计的 \(\Delta y+k\leq0.5\)，则向上画点，\(\Delta y\) += k
初始 \(\Delta y\) = – 0.5，然后同时乘\(\Delta x\)，有
def BresenhamLine(int x0,int y0,int x1,int y1):
dx = x1-x0
dy = y1-y0
d = -dx
y = y0
for x in range(x0, x1):
putPixel(x, y)
x += 1
d += 2*dy
if d >= 0:
y += 1
d -= 2*dx
圆形
中点画圆法
圆是1 / 8 对称的图形，所以只需要会绘制 1 / 8，判断 1 / 2 点在圆内还是圆外
def MidPointCircle(r: int):
x=0
y=r # 从最上方点开始向左绘制
d=1-r
putPixel(x,y)
while x < y:
if d < 0:
d += 2*x+3
x += 1
else:
d += 2*(x-y)+5
x += 1
y -= 1
putPixel(x,y)
Bresenham 画圆算法
绘制1 / 4的圆，与上同理，为一步一步的递推判断
def BresenhamCircle(r: int):
x = 0
y = r
delta = 2*(1-r)
while y >= 0: # 判断点移动方向
putPixel(x,y)
if delta < 0: # 右中方向
delta1 = 2*(delta+y)-1
if delta1 <= 0:
direction=1
else:
direction=2
else if delta > 0: # 右下方向
delta2 = 2*(delta-x)-1
if delta2 <= 0:
direction=2
else:
direction=3
else:
direction=2
switch direction: # 移动后更新值
case 1: # 右方
x++;
delta += 2*x+1
break
case 2: # 右下方
x++; y--;
delta += 2*(x-y+1)
break
case 3: # 下方
y--;
delta += (-2*y+1)
break
椭圆
导数为1的点为 \((x_p, y_p)\)
\begin{array}{}
x_p=\frac{a^2}{\sqrt{a^2+b^2}}\\
y_p=\frac{b^2}{\sqrt{a^2+b^2}}
\end{array}
\right.
\]
\((0,b)\)到 p：
d = f(1, b-0.5) = b**2 + (-b+0.25)*a**2
if d <= 0: # 右
d = d+(2*x+3)*b**2
else if d > 0: # 右下
d = d+(2*x+3)*b**2+(-2y+2)*a**2
p 到 \((a,0)\)：
d = f(x+0.5, y-1) = b**2*(x+0.5)**2+a**2*(y-1)**2-a**2*b**2
if d <= 0: # 右下
d = d+(-2*y+3)*a**2+(2x+2)*b**2
else if d > 0: # 下
d = d+(-2*y+3)*a**2
图形裁剪
线段
Cohen-Sutherland 代码裁剪算法
四位二进制码表示所在区域，四位分别为 [上下右左]
- code1 = code2 = 0，在窗内
- code1 & code2 != 0，在窗外
- 都不对，则取交点，分类讨论
中点分割裁剪算法
一直二分，直到到达交点
Liang－Barsky 算法
| p | q | |
|---|---|---|
| 1 | –\(\Delta\)x | \(x1-xl\) |
| 2 | \(\Delta\)x | \(xr-x1\) |
| 3 | –\(\Delta\)y | \(y1-yb\) |
| 4 | \(\Delta\)y | \(yt-y1\) |
\(u_k=q_k / p_k\)
- 若\(\Delta x=0\)，则
- if q1<0 || q2<0
- 不在窗口
- \(u_{max}=\max(0, u_k|pk<0)\)，k=3,4
- \(u_{min}=\min(1, u_k|pk>0)\)
- 转后
- if q1<0 || q2<0
- 若\(\Delta y=0\)，则
- if q3<0 || q4<0
- 不在窗口
- \(u_{max}=\max(0, u_k|pk<0)\)，k=1,2
- \(u_{min}=\min(1, u_k|pk>0)\)
- 转后
- if q3<0 || q4<0
- 若都不满足
- \(u_{max}=\max(0, u_k|pk<0)\)，k=1,2,3,4
- \(u_{min}=\min(1, u_k|pk>0)\)
- 转后
- 后：
- if \(u_{max}>u_{min}\)
- 不在窗口
- x = x1 + u · (x2-x1)，y = y1 + u · (y2-y1)，计算交点坐标，然后画线
- if \(u_{max}>u_{min}\)
多边形
Sutherland－Hodgman 逐边裁剪法
逐个点判断是否位于一侧入栈，穿越时计算交点入栈
存在退化边，可以使用颜色异或计算消除
边界裁剪算法
加入交点的窗点集，加入交点的多边形点集，按同一旋转方向排列，遇到交点就判断是否跳转。可能生成多个点集，一直到所有交点都遍历。
内裁剪 / 外裁剪
即保留窗内 / 窗外内容
二维三维图形变换
基本变换
二维变换
\(p’ = p·T\)
点形式：[[x, y, 1], …] ，1为放大倍率
变换矩阵形式：
平移
1 & 0 & 0 \\
0 & 1 & 0 \\
T_x & T_y & 1
\end{bmatrix}
\]
比例
s_x & 0 & 0 \\
0 & s_y & 0 \\
0 & 0 & 1
\end{bmatrix}
\]
旋转
\cos\theta & \sin\theta & 0 \\
-\sin\theta & \cos\theta & 0 \\
0 & 0 & 1
\end{bmatrix}
\]
对称
对称于y轴：\(\begin{bmatrix}
-1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)
对称于x轴：\(\begin{bmatrix}
1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)
对称于原点：\(\begin{bmatrix}
-1 & 0 & 0 \\
0 & -1 & 0 \\
0 & 0 & 1
\end{bmatrix}\)
对称于y=x：\(\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}\)
对称于y=-x：\(\begin{bmatrix}
0 & -1 & 0 \\
-1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}\)
错切
x = x + cy OR y = y + bx
三维变换
同理，只是最右端上方三个参数代表透视
复合变换
\(p’ = p·T_1·T_2· …\)
x1 & y1 & 1
\end{bmatrix}
\begin{bmatrix}
a & b & p \\
c & d & q \\
l & m & s
\end{bmatrix}=
\begin{bmatrix}
ax1+cy1+l & bx1+dy1+m & px1+qy1+s
\end{bmatrix}
\]
三维图形投影和消隐
视图
主视图
\(\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)
侧视图
\(\begin{bmatrix}
0 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)
俯视图
\(\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}\)
透视投影
\(\begin{bmatrix}
1 & 0 & 0 & p\\
0 & 1 & 0 & q\\
0 & 0 & 1 & r\\
0 & 0 & 0 & 1
\end{bmatrix}\)
结果为\(\begin{bmatrix}
x & y & z & px+qy+rz+1
\end{bmatrix}\)
主灭点\(\begin{bmatrix}
1/p & 0 & 0 & 0
\end{bmatrix}\)同理有y,z灭点
消隐画法
逆时针面向量与视线夹角
若投影到Z-X面上，可见条件为
\(\begin{bmatrix}
Z_A-Z_S & X_A-X_S\\
Z_B-Z_A & X_B-X_A
\end{bmatrix}>0\)
① 按照三表结构的形式建立描述立体模型的顶点表、环表和面表；
② 根据要生成立体图形的种类（正等轴测投影），采用相应变换矩阵对立体的顶点进行坐标变换；
③ 按照面表中的指示地址从相应的环表中取出顶点序号，利用变换后的顶点坐标对立体的面逐一计算出每个面的E值，根据E的正负判别面的可见性；
④ 对于可见面，按照该面所对应的环表连点绘出多边形的边框。
曲线曲面
抛物线
Hermite 曲线
\(\begin{bmatrix}
2 & -2 & 1 & 1\\
-3 & 3 & -2 & -1\\
0 & 0 & 1 & 0\\
1 & 0 & 0 & 0
\end{bmatrix}\begin{bmatrix}
p_0\\p_1\\p’_0\\p’_1
\end{bmatrix}\)
Bezier曲线
分割递归算法
C(t)=\sum^n_{i=0}p_iB_{i,n}(t)
\]
\(C(0)=p_0\)
\(C(1)=p_n\)
- 曲线在两端点处的 r 阶导数只与 r＋1 个相临点有关，而与更远的点无关。
- 点次序颠倒，形状不变
二次Bezier曲线
\begin{bmatrix}
t^2 & t & 1
\end{bmatrix}
\begin{bmatrix}
1 & -2 & 1\\
-2 & 2 & 0\\
1 & 0 & 0
\end{bmatrix}
\begin{bmatrix}
p_0\\p_1\\p_2
\end{bmatrix}
\]
三次的矩阵
\(\begin{bmatrix}
-1 & 3 & -3 & 1\\
3 & -6 & 3 & 0\\
-3 & 3 & 0 & 0\\
1 & 0 & 0 & 0
\end{bmatrix}\)
k次B样条曲线
C(t)=\sum^n_{k=0}p_{i+k}F_{i,n}(t)
\]
二次B样条曲线，\(t\in [0,1]\)
\(\frac{1}{2}*\begin{bmatrix}
1 & -2 & 1\\
-2 & 2 & 0\\
1 & 1 & 0
\end{bmatrix}\)
三次B样条曲线，\(t\in [0,1]\)
\(\frac{1}{6}*\begin{bmatrix}
-1 & 3 & -3 & 1\\
3 & -6 & 3 & 0\\
-3 & 0 & 3 & 0\\
1 & 4 & 1 & 0
\end{bmatrix}\)
