图形学复习

计算机考试复习

实时更新.

发布地址已变更.

差不多已完结.

发布地址：作业部落

发布总地址：Blog

1 知识点

1.1 直线段的扫描转换算法

1.1.1 数值微分法

Code: 数值微分法（DDA）算法

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

1.1.2 中点画线法

Code: 中点画线算法程序

// 因为d0 = a + 0.5b，所以用2d代替d来摆脱浮点运算。
void Midpoint_Line(int x0, int y0, int x1, int y1, int color){
    int a = y0 - y1;
    int b = x1 - x0;
    //int c = x0 * y1 - x1 * y0; //这行用不到
    int d = (a + 0.5 * b) * 2;
    int d1 = a * 2;
    int d2 = (a + b) * 2;
    int x = x0, y = y0;
    dralPixel(x, y, color);
    while(x < x1){
        if(d < 0){
            x++; y++; d+=d2;
        }else{
            x++; d+=d1;
        }
        drawPixel(x, y, color);
    }
}

题目1

Question: 依次写出用中点画线法进行直线扫描转换，从点(5,5)到(15,11)经过的像素点。

Answer:

a = y0 - y1 = -6

b = x1 - x0 = 10

c = x0y1 - x1y0 = -20

F(x, y) = -6x + 10y - 20

d0 = F(M) = F(x0+1, y0+0.5) = F(x0, y0) + a + 0.5b

因为增量a = -6，a + b = 4，故有下表

d	d的计算	d的值	x	y
d0	a + 0.5b	-1	5	5
d1	d0 + (a+b)	3	6	6
d2	d1 + a	-3	7	6
d3	d2 + (a+b)	1	8	7
d4	d3 + a	-5	9	7
d5	d4 + (a+b)	-1	10	8
d6	d5 + (a+b)	3	11	9
d7	d6 + a	-3	12	9
d8	d7 + (a+b)	1	13	10
d9	d8 + a	-5	14	10
d10	d9 + (a+b)	-1	15	11

所以答案是(5,5)、(6,6)、(7,6)、(8,7)、(9,7)、(10,8)、(11,9)、(12,9)、(13,10)、(14,10)、(15,11)。

1.1.3 Bresenham算法

void Bresenham_Line(int x0, int y0, int x1, int y1, int color){
    float k = (y1 - y0) / (x1 - x0);
    float e = -0.5;
    int y = y0;
    for(x=x0; x<=x1; x++){
        drawPixel(x, y, color);
        e += k;
        if(e >= 0){
            y++;
            e--;
        }
    }
}

1.2 多边形的扫描填充

1.2.1 扫描线算法（和边界标识算法）

扫描线算法和NET、AET

1.2.2 区域填充算法（油漆桶）

//内点表示的四连通区域的递归填充算法
void FloodFill4(int x, int y, int oldColor, int newColor){
    if(getPixel(x, y) == oldColor){
        drawPixel(x, y, newColor);
        FloodFill4(x, y+1, oldColor, newColor);
        FloodFill4(x, y-1, oldColor, newColor);
        FloodFill4(x+1, y, oldColor, newColor);
        FloodFill4(x-1, y, oldColor, newColor);
    }
}

//边界表示的四连通区域的递归填充算法
void BoundaryFill4(int x, int y, int boundaryColor, int newColor){
    int color = getPixel(x, y);
    if(color != boundaryColor && color != newColor){
        drawPixel(x, y, newColor);
        BoundaryFill4(x, y+1, boundaryColor, newColor);
        BoundaryFill4(x, y-1, boundaryColor, newColor);
        BoundaryFill4(x+1, y, boundaryColor, newColor);
        BoundaryFill4(x-1, y, boundaryColor, newColor);
    }
}

1.3 裁剪

1.3.1 直线段裁剪

1.3.1.1 Cohen-Sutherland裁剪算法

1.3.1.2 中点分割裁剪算法

是一种二分法求边界交点的方法。

数学二分法是无限的，但图形像素二分法是有限的。

题目1

1.3.1.3 梁友栋-Barskey裁剪算法

1.3.2 多边形裁剪

题目1

如下图所示，裁减窗口为正方形，采用逐边裁件算法，依次按左、下、右、 上的顺序，用四条窗口边界裁减多边形ABCDE。试写出每条框口边界裁减后 输出的新的多边形的顶点序列。

答：左边界裁减后：ABCD12，下边界裁减后：4B56D123，右边界裁减后：4B7D123，上边界裁减后：4B789123。

1.3.3 字符裁剪

• 串精度裁剪
• 字符精度裁剪
• 笔画或像素精度裁剪

1.4 反走样

Q：什么叫做走样？什么叫做反走样？反走样技术包括那些？

A：走样指的是用离散量表示连续量引起的失真。

为了提高图形的显示质量。需要减少或消除因走样带来的阶梯形或闪烁效果，用于减少或消除这种效果的方法称为反走样。

• 1、提高分辨率
• 2、简单区域取样
• 3、加权区域取样

加权区域取样的方法是：

①前滤波，以较高的分辨率显示对象；

②后滤波，即加权区域取样，在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个像素的属性进行平均得到较低分辨率下的像素属性。

1.5 参数曲线和曲面

1.6 Bezier曲线与曲面

简单易懂Bezier与B样条

Bezier曲线的性质

• 端点性质
• 对称性
• 凸包性
• 几何不变性
• 变差缩减性
• 仿射不变性

1.7 B样条

B样条的性质

• 局部性
• 连续性
• 凸包性
• 分段参数多项式
• 导数公式
• 变差缩减性
• 几何不变性
• 仿射不变性
• 直线保持性
• 造型的灵活性

1.8 颜色视觉

• RGB（红、绿、蓝）
• CMY（青、品红、黄）
• HSV（色调、饱和度、明度）

1.9 简单光照明模型

1.9.1 Phong光照明模型

1.9.2 增量式光照明模型

1.10 光线跟踪算法

//伪代码
RayTracing(start, direction, weight, color){
    if(weight < MinWeight)
        color = black;
    else{
        计算光线与所有物体交点中离start最近的点;
        if(没有交点)
            color = black;
        else{
            Ilocal = 在交点处用局部光照模型计算出的光强;
            计算反射方向R;
            RayTracing(交点, R, weight * w, Ir);
            计算折射方向T;
            RayTracing(交点, T, weight * w, It);
            color = Ilocal + KsIr + KtIt;
        }
    }
}

1.11 附录

窗口区到视图区坐标变换（简单方法）

Q：假设在观察坐标系下窗口区的左下角坐标为（wxl=10,wyb=10），右上角坐标为（wxr=50，wyt=50）。设备坐标系中视区的左下角坐标为（vxl=10,vyb=30），右上角坐标为（vxr=50,vyt=90）。已知在窗口内有一点p(20,30)，要将点p映射到视区内的点p，请问p点在设备坐标系中的坐标是多少？

A：书上的解法太麻烦了。设从窗口区到视图区的转换矩阵

$$M=\left[ \begin{matrix} a & 0 & b \\ 0 & c & d \\ 0 & 0 & 1 \end{matrix} \right]$$
则左下角坐标转换
$$M·\left[ \begin{matrix} 10 \\ 10 \\ 1 \end{matrix} \right] =\left[ \begin{matrix} 10 \\ 30 \\ 1 \end{matrix} \right]$$
右上角坐标变换
$$M·\left[ \begin{matrix} 50 \\ 50 \\ 1 \end{matrix} \right] =\left[ \begin{matrix} 50 \\ 90 \\ 1 \end{matrix} \right]$$
解得
$$[a, b, c, d] = [1, 0, 1.5, 15]$$
所以将点P映射就是
$$M·\left[ \begin{matrix} 20 \\ 30 \\ 1 \end{matrix} \right] =\left[ \begin{matrix} 20 \\ 60 \\ 1 \end{matrix} \right]$$
∴p点在设备坐标系中的坐标是(20, 60)。

2 习题

Bezier曲线

习题文档地址

1. 设有一条二次Bezier曲线的控制点为P0,P1,P2，另一条二次曲线Bezier曲线的控制顶点为Q0,Q1,Q2，P2=Q0。请写出两条曲线可以精确合并（表示）为一条二次Bezier曲线的条件。

解：P2＝Q0，且P1，P2（Q0），Q1三点共线,切平面重合，曲率相等

2. 已知Bezier曲线上的4个点分别为Q0(50,0),Q1(100,0),Q2(0,50)和Q3(0,100)，它们对应的参数分别为0，1/3，2/3，1，反求Bezier曲线的控制点。

Q（0）＝P0B0，3（0）＋P1B1，3（0）＋P2B2，3（0）＋P3B2，3（0）（50，0）＝P0×1＋P1×0＋P2×0＋P3×0＝P1

Q（1）＝P3＝（0，100）

Q（1/3）＝P0×1×8/27＋P1×3×4/27＋P2×3×2/27＋P3×1×1/27＝（100，0）

Q（2/3）＝P0×1×1/27＋P1×3×2/27＋P2＋3×4/27＋P4×8/27＝（0，50）

方程连立求出：P0，P1，P2，P3

3. 设一条三次Bezier曲线的控制点为P0,P1,P2,P3。对曲线上一点P(0.5)及一个给定的目标点T，给出一种调整Bezier曲线形状的方法，使得P(0,5)精确通过点T。

对曲线进行二维平易拉伸变换，设T(X,Y) 将P1调整到P1+X, T=P(0.5)+XB1,3(0.5) 将P1调整到P1+（T-P(0.5)）/B1,3(0.5)

4. 计算以（30，0），（60，10），（80，30），（90，60），（90，90）为控制顶点的4次Bezier曲线在t=1/2处的值。

C(1/2)=(30,0)×1×1/16+(60,10)×4×1/16+(80,30)×6×1/16+(90,60)×4×1/16+(90,90)×1×1/16

5. 给定三次Bezier曲线的控制点（0，0），（0，100），（100，0），（100，100），计算升阶一次后的控制顶点。

Pj(1)=(j/(n+1))pj-1+(1-j/(n+1))pj

P0(1)=(0/4)P0-1+(1-0)P0=P0=(0,0)

P1(1)=(1/4)P0+(1-1/4)P1=(0,75)

P2(1)=(2/4)P1+(1-2/4)P2=(50,50)

P3(1)=(3/4)P2+(1-3/4)P3=(100,25)

P4(1)=(4/4)P3+(1-1)P4=(100,100)

综合复习题

计算机图形学试题及答案

计算机图形学5套模拟题