本文最后更新于：2022年7月7日上午

第一章绪论

计算机图形学的主要研究内容是什么？

计算机中图形的表示方法，以及利用计算机进行图形的计算、处理和显示的相关原理与算法

列举三个以上图形学的应用领域

计算机辅助设计与制造（CAD/CAM）

可视化

真实感图形实时绘制与自然景物仿真

计算机动画

用户接口

计算机艺术

一个图形系统通常由哪些图形设备组成？

图形处理器、图形输入设备和输出设备

图形和图像的区别是什么？

图像：计算机内以位图形式存在的灰度信息

图形：含有几何属性，由场景的几何模型和景物的物理属性共同组成的

CRT显示器的原理是什么？

高速的电子束由电子枪发出，经过聚焦系统、加速系统和磁偏转系统就会到达荧光屏的特定位置

LCD有哪些技术指标？

可视角度 CR10、CR5

点距

分辨率

有哪些常用的图形输入设备？

键盘、鼠标

跟踪球、空间球、数据手套、光笔、触摸屏

图形学之父

Ivan E. Sutherland

ACM Siggraph最高奖以谁的名字命名

Steven A. Coons

第二章光栅图形学

直线段的扫描转换

数值微分法（DDA）

增量思想：对于直线y=kx+b，x每递增1，y则递增k

在该算法中，y和k都要用浮点数表示，且每一步都需要对y四舍五入取整，不适合硬件实现

void DDALine(int x0, int y0, int x1, int y1){
     float dx, dy, y, k;
    dx = x1-x0;
    dy = y1-y0;
    k = dy/dx;
    y = y0;
    for(int x=x0; x<=x1; x++){
        drawpixel(x, int(y+0.5));
        y += k;
    }
}

中点画线法

采用了直线的一般形式：F(x,y)=Ax+By+C=0，其中A=-dy，B=dx

画直线段过程中当前像素点为(x0,y0)，下一个像素点有两种选择P1(x0+1,y0), P2(x0+1,y0+1)，设M(x0+1,y0+0.5)是P1P2中点，Q为理想直线与x=x0+1的交点，当M在Q下方时F(M)<0，下一个像素点为P2，当M在Q上方时F(M)>0，下一个像素点为P1

采用增量计算，令d=F(M)=a+0.5b，取正右方P1后判断下一个像素时d1=d+a，取右上方P2后判断下一个像素时d2=d+a+b

void MidpointLine(int x0, int y0, int x1, int y1){
    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);
    }
}

Bresenham算法

过各行各列像素中心构造一组虚拟网格线，按照直线起点到终点的顺序计算直线与各垂直网格线的交点，根据误差项的符号确定该列像素中与此交点最近的像素

void IntegerBresenhamLine(x0, y0, x1, y1){
    x = x0;
    y = y0;
    dx = x1-x0;
    dy = y1-y0;
    e = -dx;
    for(i=0; i<=dx; i++){
        drawpixel(x, y);
        x++;
        e += 2*dy;
        if(e>=0){
            y++;
            e -= 2*dx;
        }
    }
}

多边形的扫描转换

多边形有两种重要的表示方法：顶点表示和点阵表示

多边形的顶点表示转换为点阵表示，这种转换称为多边形的扫描转换

扫描线算法

按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，以完成填充工作

对于一条扫描线，多边形的扫描步骤为：

求交。计算扫描线与多边形各边的交点
排序。把所有交点按照x值递增顺序排序
配对。将第一个与第二个、第三个与第四个等交点配对，每对交点代表扫描线与多边形的一个相交区间
填色。把相交区间内的像素置成多边形的颜色，把相交区间外的像素置成背景色

涉及的数据结构：

活性边表AET：为提高效率，在处理一条扫描线时仅对与它相交的多边形的边进行求交运算，与当前扫描线相交的边称为活性边，把活性边按与扫描线交点x坐标递增的顺序存放在一个链表中，该链表为AET

结点内容：
1. 当前扫描线与边的交点坐标x值
2. 从当前扫描线到下一条扫描线间x的增量$\Delta x$
3. 该边所交的最高扫描线号$y_{max}$
新边表NET：为方便AET的建立与更新，为每一条扫描线建立一个NET，存放在该扫描线第一次出现的边

void scanLinePolyFill(polygon){
    //初始化新边表NET
    for(各条扫描线i){
        初始化NET[i]头指针;
        把ymin=i的边放入NET[i]中;
    }
    //扫描准备
    初始化AET为空;
    y=0;
    //开始扫描
    for(各条扫描线i){
        //加入边
        将NET[i]中的边插入排序到AET中;
        若要自交,则对AET冒泡排序;
        //区间填色
        遍历AET，配对交点区间，对区间上的点改写像素值;
        //删除边 
        删除ymax=i的边;
        //更新AET
        将AET中结点的x值递增dx;
    }
}

边界标志算法

帧缓冲器对多边形进行直线扫描转换时在边界像素打上标志，再采用和扫描线算法类似的方法将位于多边形的各个区间填色。适合硬件实现

多边形的区域填充

这里的区域是指已经表示成点阵形式的填充图形，它是像素的集合

区域可采用内点表示和边界表示

区域可分为四连通区域和八连通区域（容易穿出脆弱边界）

递归算法

假设在多边形内有一个像素已知，由此出发利用连通性找到区域内的所有像素

扫描线算法

给定种子点时，首先填充种子点所在扫描线上位于给定区域的一个区间，然后确定与这一区间相连通的上下两条扫描线上位于给定区域内的区间，并依次保存下来，反复这个过程直到填充结束

区域填充的扫描线算法步骤：

初始化。堆栈置空，将种子点(x,y)入栈
出栈。若栈空则结束；否则取栈顶元素(x,y)，以y作为当前扫描线
填充并确定种子点所在区段。从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左右端点坐标为xl和xr
确定新的种子点。在区间[xl,xr]中检查与当前扫描线y上下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，返回第2步

直线段裁剪

Cohen-Sutherland法

对线段端点进行编码code1 code2，判断直线段与窗口的关系，分为三种情况：

全在窗口内，显示该线段；code1 | code2 == 0
完全不在窗口内，丢弃该线段；code1 & code2 != 0
线段与窗口有交，求出该交点，把线段一分为二，丢弃在窗口外的一段，对另一端重复上述处理

中点分割法

首先对线段端点进行编码，并把线段与窗口的关系分为三种情况：

全在窗口内，显示该线段
完全不在窗口内，丢弃该线段
线段与窗口有交，用中点分割的方法求出线段与窗口的交点

改进之处：不用解方程组求交，而是采用二分法求交

改进理由：主要计算过程只用到加法和除2运算，适合硬件实现和并行计算

梁友栋-Barskey裁剪算法

参数化裁剪条件：

$\begin{cases} XL \le x_1+u\Delta x\le XR\\ YB \le y_1+u\Delta y\le YT \end{cases}$

可以表示为统一形式：$up_k\le q_k$

$p_k=0$，直线段平行于裁剪边界之一
- $q_k<0$，则线段完全在边界外，舍弃该线段
- $q_k\ge0$，则该线段平行于裁剪边界并且在窗口内
$p_k<0$，线段从裁剪边界所在直线的外部指向内部

计算线段与边界k的延长线的交点u值$r_k=q_k/p_k$，$u_1=max\{0,r_k\}$
$p_k>0$，线段从裁剪边界所在直线的内部指向外部

计算线段与边界k的延长线的交点u值$r_k=q_k/p_k$，$u_2=min\{1,r_k\}$

如果$u_1>u_2$则线段完全落在裁剪窗口之外被舍弃；否则裁剪线段由参数$u_1,u_2$计算出来，它们定义了在裁剪矩形内的线段部分

它比前两种方法快，因为线段与窗口边界的交点仅需计算一次，且更新参数$u1,u2$仅需要一次除法

多边形裁剪

Sutherland-Hodgman算法

一次用窗口的一条边裁剪多边形，得到一个顶点序列，作为下一条裁剪边处理过程的输入

每条线段端点S,P与裁剪线的位置关系有如下4种，红色标注点为输出的点：

算法优点：裁剪窗口可以是任意凸多边形

算法不足：只能裁剪凸多边形；裁剪窗口不能是凹多边形

算法改进：可以将凹多边形分割成多个凸多边形再去运行该算法

字符

字库的分类

点阵型：存储空间大、易于显示

矢量型：存储空间小、美观、变换方便

字符裁剪

串精度

字符精度

笔画或像素精度

反走样

走样aliasing：用离散量表示连续量引起的失真现象

反走样antialiasing：用于减少或消除这种效果的技术

提高分辨率

把显示器分辨率提高一倍，直线经过两倍像素，锯齿增加一倍，但同时每个阶梯也减少了一倍，显示的直线段看起来平直光滑。方法简单，但不经济，只能减轻而不能消除锯齿问题

非加权区域采样

假定每个像素是具有一定面积的小区域，直线段是具有一定宽度的狭长矩形，当直线段与像素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该像素的亮度值

两个缺点：

像素的亮度与相交区域的面积成正比，而与相交区域落在像素内的位置无关，这仍然会导致锯齿效应
直线条上沿理想直线方向的相邻两个像素有时会有较大的灰度差

加权区域采样

使相交区域对像素亮度的贡献依赖于该区域与像素中心的距离

消隐

画家算法

先把屏幕置成背景色，再把物体各个面按离视点的远近进行排序，结果存放在深度优先级表中，按照由远到近的顺序绘制各个面

优点：原理简单

缺点：只能处理互不相交的面，而且深度优先级表中面的顺序可能出错，深度排序计算量大

Z-Buffer算法

设置帧缓存存放每个像素的颜色值，深度缓存来存放每个像素的深度值。把显示对象的每个面上每一点的属性值填入帧缓冲区相应单元前，要把这点的z坐标值与Z缓冲器中相应单元的值进行比较，只有前者大于后者时才改变帧缓冲区该单元的值，同时Z缓冲器相应单元的值更新

优点：比总体排序灵活简单，有利于硬件实现

缺点：占用空间大，没有利用图形的相关性与连续性

Z-Buffer(){
    帧缓存全置为背景色;
    深度缓存全置为最小Z值;
    for(每一个多边形){
        扫描转换该多边形;
        for(该多边形覆盖的每个像素(x,y)){
            计算该多边形在该像素的深度值Z(x,y);
            if(Z(x,y)大于Z缓存在(x,y)的值){
                把Z(x,y)存入Z缓存中(x,y)处;
                把多边形在(x,y)处的颜色值存入帧缓存的(x,y)处;
            }
        }
    }
}

改进的Z-Buffer算法

用一个深度缓存变量zb代替缓存数组。对屏幕上的每个像素，对于每个多边形，若该像素在该多边形内，则计算该多边形在该像素的深度值，找出对应最大深度值的多边形，更新像素属性值

Z-Buffer(){
    帧缓存全置为背景色;
    for(屏幕上的每一个像素(x,y)){
        深度缓存变量zb置最小值MinValue;
        for(每个多边形P){
            if(像素(x,y)在该多边形P_k内){
                计算该多边形在该像素的深度值depth;
                if(depth>zb){
                    zb=depth;
                    index=k;
                }
            }
        }
        if(zb!=MinValue)
            计算多边形P_index在像素(x,y)的光照颜色并显示;
    }
}

第6行的包含性检测可采用射线法或弧长法

扫描线Z-Buffer算法

在处理当前扫描线时，开一个一维数组作为当前扫描线的Z-Buffer。首先找出与当前扫描线相关的多边形，以及每个多边形中相关的边对；然后计算边对之间区间上各像素的深度，与Z-Buffer中的值相比较，找出各像素处对应的可见平面，计算颜色，写帧缓存。对深度计算采用增量算法。

优点：将整个绘图窗口内的消隐问题分解到扫描线上解决，使所需的Z缓冲器大大减小；计算深度时利用了面的连贯性，只用了一个加法

缺点：被多个多边形覆盖的像素还要进行多次计算，计算量仍然很大

数据结构：

多边形Y表：保存所有多边形的序号和其顶点最大y坐标，根据多边形顶点最小y坐标插入到Y表相应位置
活化多边形表APT：保存与当前扫描线相交的多边形
边表ET：每个APT中的多边形都有一个边表，存放每条边端点中较大的y值，增量$\Delta x$，y值较小一端的x坐标和z坐标
活化边对表AET：存放当前多边形中与当前扫描线相交的各边对的信息

Z-Buffer(){
    建立多边形Y表;
    初始化活化多边形表APT，活化边对表AET为空;
    for(每条扫描线i){
        帧缓存CB置为背景色;
        深度缓存ZB置为负无穷;
        将对应扫描线i的Y表中的多边形加入APT中;
        生成新加入多边形的边表ET;
        对APT中每一个多边形，若其边表ET中对应扫描线i增加了新边，则将新边配对，加入AET中;
        对AET中每一个边对:
            对xl<j<xr的每一个像素，按增量公式z=z+dz_a计算各点深度depth;
            若depth>ZB(j)则令ZB(j)=depth，并计算颜色值写帧缓存;
        删除APT中多边形顶点最大y坐标为i的多边形，并删除相应的边;
        对AET中每一个边对:
            删除y_lmax或y_rmax等于i的边，若一边对中只删除了一边则对该多边形的边重新配对;
            用增量公式计算新的x_l,x_r,z_l=z_l+dx_l*dz_a+dz_b;
    }
}

区间扫描线算法

把当前扫描线各多边形在投影平面的投影的交点进行排序后，使扫描线分为若干子区间，只要在区间任一点处找出在该处z值最大的一个面，这个区间上的每一个像素就用这个面的颜色来表示

优点：在一条扫描线上每个区间只计算一次深度值，并且不需要Z缓冲器

区域子分割算法（Warnack算法）

把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标足够简单，可以显示为止

如果窗口内没有物体，则按背景色显示；如果窗口内只有一个面，则把该面显示出来；如果窗口内含有两个以上的面，则把窗口等分成4个子窗口，对每个小窗口作上述同样的处理

窗口与多边形的覆盖关系有4种：内含，相交，包围，分离

光线投射算法

考查由视点出发穿过观察屏幕的一个像素而射入场景的一条射线，则可确定出场景中与该射线相交的物体。在计算出光线与物体表面的交点后，离像素最近的交点所在面片的颜色为该像素的颜色；如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示。

for(屏幕上的每一像素){
    形成通过该屏幕像素的射线;
    for(场景中的每一物体)
        将该射线于物体求交;
    if(存在交点)
        以最近的交点所属的颜色显示像素;
    else
        以背景色显示像素;
}

第三章几何造型技术

曲线的基本概念

位置矢量

切矢量

法矢量

曲率：弯曲程度，曲线的单位切矢对弧长的转动率

挠率：扭曲程度，副法线方向对于弧长的转动率

三次Hermite曲线

三次曲线的代数形式：$P(t)=a_3t^3+a_2t^2+a_1t+a_0, t\in[0,1]$

三次曲线的几何形式：用端点位矢$P_0,P_1$，切矢$P’_0,P’_1$表示

代入推导(……)，几何系数是$P_0,P_1,P’_0,P’_1$，调和函数是$F_0, F_1, G_0, G_1$

$P(t)=F_0P_0+F_1P_1+G_0P'_0+G_1P'_1, t\in[0,1]$

矩阵化表达

$P(t)=\left( \begin{matrix} P_0 & P_1 & P'_0 & P'_1 \end{matrix}\right) \left( \begin{matrix} F_0 \\ F_1 \\ G_0 \\ G_1 \end{matrix}\right) =\left( \begin{matrix} P_0 & P_1 & P'_0 & P'_1 \end{matrix}\right) \left( \begin{matrix} 2 & -3 & 0 & 1\\ -2 & 3 & 0 & 0\\ 1 & -2 & 1 & 0\\ 1 & -1 & 0 & 0\\ \end{matrix}\right) \left( \begin{matrix} t^3 \\ t^2 \\ t \\ 1 \end{matrix}\right)\\$

Bezier曲线

$P(t)=\sum_{i=0}^nP_iC_n^it^i(1-t)^{n-i},t\in[0,1]$

性质：

端点性质
- 起点终点与对应的特征多边形的起点终点重合
- 端点切向量$P’(t)=n\sum_{i=1}^{n-1}P_i[B_{i-1,n-1}(t)-B_{i,n-1}(t)]$
  
  起点终点处的切线方向和特征多边形的第一条边及最后一条边的走向一致
对称性：曲线的起点终点处几何性质一样
凸包性：曲线落在$P_i$构成的凸包之中
几何不变性：曲线的位置和形状不依赖坐标系的选择
变差缩减性：平面内任意直线与$P(t)$的交点个数不多于该直线与其特征多边形的交点个数，反映了bezier曲线比特征多边形的折线更光顺
仿射不变性：在仿射变换下，$P(t)$的形式不变

de Casteljau算法：

$P_i^k=\begin{cases} P_i,&k=0\\ (1-t)P_i^{k-1}+tP_{i+1}^{k-1},&k=1,2,...,n,i=0,1,...,n-k \end{cases}$

升阶：保持Bezier曲线的形状与定向不变，增加定义它的控制顶点数

$P_i^*=\frac{i}{n+1}P_{i-1}+(1-\frac{i}{n+1})P_i\\i=0,1,...,n+1$

不足：

Bezier曲线不能做局部修改
Bezier曲线的拼接比较复杂

例题1：计算以(30,0) (60,10) (80,30) (90,60) (90,90)为控制顶点的四次Bezier 曲线在$t=\frac{1}{2}$处的值，并画出de Casteljau三角形。

例题2：给定型值点(0,0) (0,100) (100,0) (100,100)，如对应的参数为$0,\frac{1}{3},\frac{2}{3},1$，反求插值这四个型值点的三次Bezier曲线的控制点。

B样条

k阶（k-1次）B样条曲线的定义为：

$P(t)=\sum_{i=0}^n P_iN_{i,k}(t) \\ t\in[t_{k-1},t_{n+1}]$

de Boor算法：

给定控制顶点$P_i(i=0,1,…,n)$和节点矢量$T=[t_0,t_1,…,t_{n+k}]$，定义k阶（k-1次）B样条曲线

$t\in[t_j,t_{j+1}](k-1\le j\le n)\\ P_i^r(t)=\begin{cases} P_i,&r=0;\\&i=j-k+1,j-k+2,...,j\\ \frac{t-t_i}{t_{i+k-r}-t_i}P_i^{r-1}(t)+\frac{t_{i+k-r}-t}{t_{i+k-r}-t_i}P_{i-1}^{r-1}(t),&r=1,2,..,k-1;\\ &i=j-k+r+1,j-k+r+2,...,j \end{cases}\\ P(t)=P_j^{k-1}(t)$

三次B样条的Bezier表示：

在区间$[t_j,t_{j+1}]$上的B样条曲线，如表示成三次Bezier曲线，则控制顶点为：

$P_{j-1}^{[2]}(t_j),P_{j-1}^{[1]}(t_j),P_{j-1}^{[1]}(t_{j+1}),P_{j}^{[2]}(t_{j+1})$ $P(t)=\sum_{i=j-3}^j P_iN_{i,4}(t)\\ =P_{j-1}^{[2]}(t_j)B_{0,3}(\frac{t-t_j}{\Delta t_j})+P_{j-1}^{[1]}(t_j)B_{1,3}(\frac{t-t_j}{\Delta t_j})+P_{j-1}^{[1]}(t_{j+1})B_{2,3}(\frac{t-t_j}{\Delta t_j})+P_{j}^{[2]}(t_{j+1})B_{3,3}(\frac{t-t_j}{\Delta t_j})$

三角网格

半边表示

把一条无向的边拆分成两条有向的半边，半边的方向在模型中总是沿着逆时针方向

每条半边需要存储的信息：

该半边的源顶点origin(e)
该半边在同一三角形中的下一半边next(e)
与该半边同属一条边的对边opposite(e)
该半边所属的面IncFace(e)

网格简化

三种基本化简操作：顶点删除、边压缩、面片收缩

网格细分

Loop细分方法：第一步增加顶点，第二步调整顶点位置使网格更加平滑

第四章真实感图形学

颜色的特性

心理学和视觉的角度：色调(hue)、饱和度(saturation)、亮度(lightness)

光学物理学的角度：主波长、纯度、明度

三色学说

是真实感图形学的生理视觉基础，是颜色视觉中最基础、最根本的理论

CIE色度图

马蹄形区域

常见的颜色模型

RGB

用于彩色光栅图形显示设备，采用红、绿、蓝为原色，面向硬件

三维直角坐标系，单位立方体来表示，原点为黑色，从黑色中加入某种颜色

CMY

用于印刷行业，采用青(Cyan)、品红(Magenta)、黄(Yellow)为原色，面向硬件

减性原色系统，单位立方体，原点为白色，在白色中减去某种颜色

HSV

面向用户，对应于画家的配色方法，圆锥形

写出Phong模型公式，并指出其中各个参数的含义

环境光ambient + 漫反射光diffuse + 镜面反射光specular

$I=I_aK_a+I_pK_d(L\cdot N)+I_pK_s(R\cdot V)^n\\ R=2N(L\cdot N)-L$

$I_a$——环境光强度

$K_a$——物体对环境光的反射系数

$I_p$——入射光强度

$K_d$——物体的漫反射系数

$L$——光源方向单位向量

$N$——物体法向量

$K_s$——物体的镜面反射系数

$R$——反射方向单位向量

$V$——视线方向单位向量

$n$——镜面反射指数

Gouraud明暗处理

计算多边形顶点的平均法向相邻多边形的平均法向
用Phong光照明模型计算顶点的平均光强
插值计算离散边上的各点光强
插值计算多边形内域中各点的光强

优点：能有效地显示漫反射效果，计算量小

缺点：镜面发射效果不理想，相邻多边形边界处的马赫带效应不能完全消除

Phong明暗处理

计算多边形顶点的平均法向
插值计算离散边上的各点法向
插值计算多边形内域中各点的法向
用Phong光照明模型计算各点的光强

优点：可以产生正确的高光区域

缺点：计算量大

针对多面体模型，直接用Phong模型绘制会有什么问题？

由于光源和视点都被假定为无穷远，且每一个多边形由于法向一致，所以多边形内部像素的颜色都是相同的，因此在不同法向的多边形邻接处不仅有光强突变还会产生马赫带效应

两种增量式光照明模型的基本思想及算法区别

在每一个多边形的顶点处计算合适的光照明强度或其他参数，然后在各个多边形内部进行均匀插值，最后得到多边形的光滑颜色分布

Gouraud明暗处理采用光强插值，Phong明暗处理采用法向插值

局部光照明模型

$I_r=I_aK_a+I_i(N\cdot L)d\omega (K_dR_d+K_sR_s)$

与简单光照模型比较的优点：

是基于入射光能量导出的光辐射模型，更具有理论基础
可以反映表面的粗糙度对反射光强的影响
可以根据材料的物理性质决定颜色
可以改进简单光照模型的失真现象
可以模拟金属的光泽

整体光照明模型—光线跟踪算法

终止条件：

该光线未碰到任何物体
该光线碰到了背景
光线在经过多次反射和折射后衰减，光线对于视点的光强贡献很小
光线反射或折射次数大于给定值

RayTracing(start, direction, weight, color){
    //光线起点start 光线方向direction 光线衰减权值weight 返回光线方向上的颜色值color
    if(weight < MinWeight)
        color = black;
    else{
        计算光线与所有物体的交点中离start最近的点;
        if(没有交点)
            color = black;
        else{
            I_local = 在交点处用局部光照模型计算出的光强;
            计算反射方向R = 2N(L*N)-L;
            RayTracing(最近的交点, R, weight*w_r, I_r);
            计算折射方向T;
            RayTracing(最近的交点, T, weight*w_t, I_t);
            color = I_local + K_sI_r + K_tI_t;
        }
    }
}

加速方法：自适应深度控制；包围盒及层次结构；三维DDA算法；空间八叉树剖分技术

包围盒

基本思想：用体积稍大且特性简单的集合体来近似代替复杂的几何对象

AABB

包含该对象，且边平行于坐标轴的最小六面体。六个标量即可表示$(x_{min},y_{min},z_{min})(x_{max},y_{max},z_{max})$。

不随物体旋转，紧密性差。

OBB

包围盒无需和坐标轴垂直，根据物体表面的顶点，通过PCA获得特征向量，即OBB的主轴。具有方向性，可以旋转。

附录

二维图形的几何变换

平移变换

$\left[ \begin{matrix} 1 & 0 & t_x\\ 0 & 1 & t_y\\ 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} x\\y\\1 \end{matrix}\right]$

旋转变换（逆时针）

$\left[ \begin{matrix} \cos\theta & -\sin\theta & 0\\ \sin\theta & \cos\theta & 0\\ 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} x\\y\\1 \end{matrix}\right]$

关于$(x_f,y_f)$点的旋转变换：需要先将该点移到坐标原点处，然后再进行旋转变换，最后将该点移回原来的位置

$T(x_f,y_f)\cdot R(\theta)\cdot T(-x_f,-y_f) =\left[ \begin{matrix} 1 & 0 & x_f\\ 0 & 1 & y_f\\ 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} \cos\theta & -\sin\theta & 0\\ \sin\theta & \cos\theta & 0\\ 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} 1 & 0 & -x_f\\ 0 & 1 & -y_f\\ 0 & 0 & 1\\ \end{matrix}\right]$

三维图形的几何变换

绕x轴旋转

$\left[ \begin{matrix} 1 & 0 & 0 & 0\\ 0 & \cos\theta & -\sin\theta & 0\\ 0 & \sin\theta & \cos\theta & 0\\ 0 & 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} x\\y\\z\\1 \end{matrix}\right]$

绕y轴旋转

$\left[ \begin{matrix} \cos\theta & 0 & \sin\theta & 0\\ 0 & 1 & 0 & 0\\ -\sin\theta & 0 & \cos\theta & 0\\ 0 & 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} x\\y\\z\\1 \end{matrix}\right]$

绕z轴旋转

$\left[ \begin{matrix} \cos\theta & -\sin\theta & 0 & 0\\ \sin\theta & \cos\theta & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \end{matrix}\right] \left[ \begin{matrix} x\\y\\z\\1 \end{matrix}\right]$

绕任意轴AB旋转

将A点移到坐标原点
使AB分别绕x轴、y轴旋转与z轴重合
将AB绕z轴旋转$\theta$角
作上述变换的逆操作，使AB回到原来位置

矩形求交

给定两个矩形A和B，矩形A的左上角坐标为$(x_{a1},y_{a1})$，右下角坐标为$(x_{a2},y_{b2})$；矩形B的左上角坐标为$(x_{b1},y_{b1})$，右下角坐标为$(x_{b2},y_{b2})$。

假设两矩形相交区域为矩形C，左上角坐标为$(x_{c1},y_{c1})$，右下角坐标为$(x_{c2},y_{c2})$

分析相交情况可知

$x_{c1}=max(x_{a1},x_{b1})\\ y_{c1}=min(y_{a1},y_{b1})\\ x_{c2}=min(x_{a2},y_{b2})\\ y_{c2}=max(y_{a2},y_{b2})$

若要相交则$\begin{cases}x_{c1}y_{c2}\end{cases}$，即

$\begin{cases} max(x_{a1},x_{b1})<min(x_{a2},x_{b2})\\ min(y_{a1},y_{b1})>max(y_{a2},y_{b2})\\ \end{cases}$

线面求交

圆柱面

$x^2+y^2=r^2$

线的参数方程$x=x(t),y=y(t),z=z(t)$

代入解方程t

判断点在多边形内部

根据向量叉乘，按照逆时针（顺时针）取向量进行叉乘，所得值同号，则说明点在多边形内部。

即判断方式为：取向量AB和AP、BC和BP、CD和CP、DE和DP、EA和EP进行叉乘，判断所得值是否同号。

三角形相关

已知三角形三顶点A$(x_1,y_1)$，B$(x_2,y_2)$，C$(x_3,y_3)$

$\vec{AB}=(x_2-x_1,y_2-y_1,z_2-z_1)$，$\vec{AC}=(x_3-x_1,y_3-y_1,z_3-z_1)$

单位法向量

$\frac{\vec{AB}\times\vec{AC}}{|{\vec{AB}\times\vec{AC}}|}$

面积

$\frac{1}{2}|\vec{AB}||\vec{AC}|\sin\theta=\frac{1}{2}|\vec{AB}\times\vec{AC}|$

两个三角形是否相交

设两个三角形$T_1,T_2$，所在平面分别为$\pi_1,\pi_2$

计算$T_1$每个顶点到$\pi_2$的距离，若同号则$T_1$在$\pi_2$一边，两三角形不相交
计算$T_2$每个顶点到$\pi_1$的距离，若同号则$T_2$在$\pi_1$一边，两三角形不相交
否则可能相交，计算$T_1$和$\pi_2$的交线$l_1$，$T_2$和$\pi_1$的交线$l_2$

若$l_1$和$l_2$有重叠，则两三角形相交；否则不相交

投影

世界坐标到观察坐标

原点平移矩阵
$\left[ \begin{matrix} 1 & 0 & 0 & -x_0\\ 0 & 1 & 0 & -y_0\\ 0 & 0 & 1 & -z_0\\ 0 & 0 & 0 & 1\\ \end{matrix} \right]$
旋转矩阵（单位矢量法）
- 取观察坐标系的z轴方向为观察平面的法向，单位化得$n=(n_x,n_y,n_z)$
- 取观察坐标系的x轴方向为观察方向，单位化得$u=(u_x,u_y,u_z)$
- 取观察坐标系的y轴方向的单位矢量，或直接计算得$v=n\times u=(v_x,v_y,v_z)$

一点透视

假定视点位置为 (0,-2,0)，沿y轴正方向投影，投影面与y轴垂直并经过点 (0,1,0)

(a) 请写出点 (2, 2, 2) 经过透视投影后的坐标。

(b) 请写出投影矩阵。

投影后坐标为：（3/2, 1, 3/2）

投影矩阵如下：

回忆

选择题

Bresenham与中点画线法相比的改进

灭点个数

曲线参数方程

Phong明暗处理中代价最高的步骤

颜色代码000000为什么颜色

简答计算题

多边形的扫描填充伪代码

简述面消隐的各种算法

Phong光照模型公式及示意图，反射方向R的推导

对称变换矩阵

空间中一正方形和一多边形求交

给定控制点求Bezier曲线方程，转换为B-Spline的新控制点，转换为Hermite曲线的端点和切矢

给定视点、投影面，在世界坐标与观察坐标下的投影矩阵

Note

SDU ComputerGraphics

本文作者: 31
本文链接: http://uuunni.github.io/2022/01/15/CGreview/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

SDU机器学习试题回忆上一篇

SDU操作系统复习笔记下一篇

SDU计算机图形学复习笔记

第一章 绪论

计算机图形学的主要研究内容是什么？

列举三个以上图形学的应用领域

一个图形系统通常由哪些图形设备组成？

图形和图像的区别是什么？

CRT显示器的原理是什么？

LCD有哪些技术指标？

有哪些常用的图形输入设备？

图形学之父

ACM Siggraph最高奖以谁的名字命名

第二章 光栅图形学

直线段的扫描转换

数值微分法（DDA）

中点画线法

Bresenham算法

多边形的扫描转换

扫描线算法

边界标志算法

多边形的区域填充

递归算法

扫描线算法

直线段裁剪

Cohen-Sutherland法

中点分割法

梁友栋-Barskey裁剪算法

多边形裁剪

Sutherland-Hodgman算法

字符

字库的分类

字符裁剪

反走样

提高分辨率

非加权区域采样

加权区域采样

消隐

画家算法

Z-Buffer算法

改进的Z-Buffer算法

扫描线Z-Buffer算法

区间扫描线算法

区域子分割算法（Warnack算法）

光线投射算法

第三章 几何造型技术

曲线的基本概念

三次Hermite曲线

Bezier曲线

B样条

三角网格

半边表示

网格简化

网格细分

第四章 真实感图形学

颜色的特性

三色学说

CIE色度图

常见的颜色模型

RGB

CMY

HSV

写出Phong模型公式，并指出其中各个参数的含义

Gouraud明暗处理

Phong明暗处理

针对多面体模型，直接用Phong模型绘制会有什么问题？

两种增量式光照明模型的基本思想及算法区别

局部光照明模型

整体光照明模型—光线跟踪算法

包围盒

AABB

OBB

附录

二维图形的几何变换

三维图形的几何变换

矩形求交

线面求交

判断点在多边形内部

三角形相关

单位法向量

面积

两个三角形是否相交

第一章绪论

第二章光栅图形学

第三章几何造型技术

第四章真实感图形学