图形学期末复习资料.docx
《图形学期末复习资料.docx》由会员分享，可在线阅读，更多相关《图形学期末复习资料.docx（38页珍藏版）》请在冰点文库上搜索。
图形学期末复习资料
一、问答题
1.什么是计算机图形学？
答：
计算机图形学是研究怎样用计算机生成、处理和显示图形的一门学科。
ISO定义：
计算机图形学是研究通过计算机将数据转换为图形，并在专用设备上显示的原理、方法和技术的学科。
2.什么是图形？
什么是图像？
图形和图像主要有哪些区别？
答：
图形：
是用一个指令集合来描述的。
这些指令结合构成一幅图的所有直线、圆、圆弧、矩形、曲线等的位置、维数和大小、形状、颜色，也被称为矢量图形或几何图形。
⏹计算机图形学的研究对象（广义的图形）
⏹能在人的视觉系统中产生视觉印象的客观对象
⏹包括自然景物、拍摄到的图片、用数学方法描述的图形等等
⏹构成图形的要素
⏹几何要素：
刻画对象的轮廓、形状等
⏹非几何要素：
刻画对象的颜色、纹理等
图像：
是由描述图像中各个像素点的亮度与颜色的数位集合组成。
也叫点阵图像或位图图像。
区别：
图形与分辨率无关，放大后不会失真；图像与分辨率有关，放大后会失真。
在文件存储方面，图像的文件一般比较大，而图形文件小得多。
3.计算机中图形的表示方法有哪几种？
答：
计算机中图形的表示方法有2种。
⏹点阵表示
⏹枚举出图形中所有的点（强调图形由点构成）
⏹简称为图像（数字图像）
⏹参数表示（矢量图形）
⏹由图形的形状参数（方程或分析表达式的系数，线段的端点坐标等）+属性参数（颜色、线型等）来表示图形
⏹简称为图形
4.图形输出设备包括哪两类？
列举出你知道的输出设备？
答：
显示器，画点设备；绘图仪，画线设备。
无论是画点设备或画线设备，其输出的图线都是不连续的，而是由离散的点或是折线近似地组成。
5.什么是光栅图形输出设备？
答：
可以输出栅格图像的各类输出设备的统称，例如显示器，绘图仪等等。
6.什么是扫描线？
答：
栅格中一组水平和垂直的线被称为扫描线。
7.什么是光栅图形？
答：
光栅显示器上显示的图形，称之为光栅图形。
8.什么是基本图形生成？
答：
基本图形主要指直线或圆弧。
在图形输出设备上绘制基本图形，称为基本图形生成。
9.什么是图形的扫描转换？
扫描转换的两个任务是什么？
答：
在光栅设备上基本图形生成也被称为基本图形的扫描转换或光栅化。
图形（直线）的扫描转换的任务：
⏹确定最佳逼近于该图形（直线）的一组象素
⏹按扫描线顺序，对这些象素进行写操作
10.列举出你知道的直线扫描转换的方法。
答：
数值微分（DDA）算法、中点画线法、Bresenham画线算法。
11.什么是增量算法？
答：
在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。
DDA算法就是一个增量算法。
12.什么是多边形的扫描转换？
答：
光栅图形学的一个基本问题是把多边形的顶点表示转换为点阵表示。
这种转换称之为多边形的扫描转换。
多边形的扫描转换本质是多边形填充。
13.什么是裁剪？
为什么我们要在计算机图形学中研究裁剪算法？
答：
确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形的方法叫做裁剪。
研究裁剪可以有目的的研究图形的性质，形状等等。
14.一条直线和裁剪窗口之间的关系有几种？
答：
三种。
线段完全可见；显然不可见；其他。
15.图形变化的本质是什么？
怎样实现图形变换？
答：
经过几何变换的图形具有以下两个特点：
●图形变化了，但原图形的构成规则（拓扑关系）没有改变；
●图形发生的变化，是因为其顶点位置（几何关系）的改变决定的。
实现图形变换的方法：
平移、旋转、对称、基本比例变换等等。
二、图形学基本原理
1.DDA算法的基本原理是什么？
答：
是最直观的根据斜率的偏移程度，决定是以x为步进方向还是以y为步进方向。
然后在相应的步进方向上，步进变量每次增加一个像素，而另一个相关坐标变量则为y=kx+b，DDA算法是一种迭代算法，也是增量算法。
DDA算法的核心：
分析|K|的取值范围如下：
当|K|<1时，y=y+k，x=x+1；|K|>1时，x=x+1/k，y=y+1。
代码：
voidDDA（intx0,inty0,intx1,inty1,COLORREFc）//DDA算法画线函数
{
CClientDCdc（this）;
floatdx,dy,x,y,k;
dx=（float）x1-x0;//横坐标增量
dy=（float）y1-y0;//纵坐标增量
if（dx!
=0&&dy!
=0）//横坐标增量及纵坐标增量不为0
{
k=dy/dx;//直线斜率
if（（k>0&&k<=1）||（k>=-1&&k<0））//斜率在1、2象限下半部
{
if（x0{
y=y0;
for（x=x0;x<=x1;x++）//循环画点形成直线
{
dc.SetPixel（x,（int）（y+0.5）,c）;
y=y+k;
}
}
else//起点横坐标大于终点横坐标
{
y=y1;
for（x=x1;x<=x0;x++）//循环画点形成直线
{
dc.SetPixel（x,（int）（y+0.5）,c）;
y=y+k;
}
}
}
elseif（k>1||k<-1）//斜率在1、2象限上半部
{
if（y0{
x=x0;
for（y=y0;y<=y1;y++）//循环画点形成直线
{
dc.SetPixel（（int）（x+0.5）,y,c）;
x=x+1/k;
}
}
else//起点纵坐标大于终点纵坐标
{
x=x1;
for（y=y1;y<=y0;y++）//循环画点形成直线
{
dc.SetPixel（（int）（x+0.5）,y,c）;
x=x+1/k;
}
}
}
}
elseif（dx==0）//横坐标增量为0，即画垂直线
{
x=x0;
if（y0{
for（y=y0;y<=y1;y++）//循环画点形成直线
{
dc.SetPixel（int（x+0.5）,y,c）;
x=x;
}
}
else//起点纵坐标大于终点纵坐标
{
for（y=y1;y<=y0;y++）//循环画点形成直线
{
dc.SetPixel（int（x+0.5）,y,c）;
x=x;
}
}
}
else//纵坐标增量为0，即画水平线
{
y=y0;
if（x0{
for（x=x0;x<=x1;x++）//循环画点形成直线
{
dc.SetPixel（x,int（y+0.5）,c）;
y=y;
}
}
else//起点横坐标大于终点横坐标
{
for（x=x1;x<=x0;x++）//循环画点形成直线
{
dc.SetPixel（x,int（y+0.5）,c）;
y=y;
}
}
}
}
数值微分（DDA）法分析
⏹优点：
⏹去掉了浮点乘法运算
⏹缺点：
⏹在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。
2.中点画线算法的基本原理是什么？
答：
假设确定象素点（xi,yi）为选定的像素，则下一个像素只能是（xi+1,yi）或（xi+1,yi+1），设M为这两点之间的中点，通过M点和直线的位置关系确定下一像素的位置。
M在直线的下方，取（xi+1,yi+1）为下一像素点；
M在直线的上方，取（xi+1,yi）为下一像素点。
直线方程：
将平面分为了三个区域：
当di<0
此时，M点在直线下方，应取（xi+1,yi+1）为下一像素点，再下一个点可能取（xi+2,yi+1）或（xi+2,yi+2），这两个点的中点为（xi+2,yi+1.5），则：
当di>0
此时，M点在直线下方，应取（xi+1,yi）为下一像素点，再下一个点可能取（xi+2,yi+1）或（xi+2,yi），这两个点的中点为（xi+2,yi+0.5），则：
d的初值为：
中点画线法步骤：
改进：
因为d只用来做符号判断，用2*△x*d代替d
1）输入直线的两端点P0（x0,y0）和P1（x1,y1）。
2）计算初始值△x、△y、d=△x-2△y、x=x0、y=y0。
3）绘制点（x,y）。
判断d的符号。
若d<0，则（x,y）更新为（x+1,y+1），d更新为d+2△x-2△y；
否则（x,y）更新为（x+1,y）,d更新为d-2△y。
4）当直线没有画完时，重复步骤3。
否则结束。
中点画线法代码
voidMidpointLine（intx0,inty0,intx1,inty1,intcolor）
{
inta,b,d1,d2,d,x,y;
dy=y0-y1;dx=x1-x0;d=2*dy+dx;
d1=2*dy;d2=2*（dx+dy）;
x=x0;y=y0;
putpixel（x,y,color）;
while（x{
if（d<0）{x++;y++;d+=d2;}
else{x++;d+=d1;}
putpixel（x,y,color）;
}/*while*/
}/*midPointLine*/
K>1：
初始d值：
1-0.5k
当d大于0,取右上方点
当d小于0,取上方点
K<-1：
初始d值：
1+0.5k
当d大于0,取左上方点
当d小于0,取上方点
K在0到-1之间
初始d值：
-（k+0.5）
当d大于0,取右下方点
当d小于0,取右方点
中点画线法分析
⏹画线从（x0,y0）开始，d的初值
d0=△x-2△y
⏹优点：
⏹只有整数运算，不含乘除法
⏹可用硬件实现
3.Bresenham画线算法的基本原理是什么？
答：
0≤k≤1，如果已经确定（xi，yi）为直线上的一点，那么下一点的坐标为
d值的计算
d初=0，
每走一步：
d=d+k，
一旦y方向上走了一步，d=d-1。
Bresenham画线算法步骤：
1）输入直线的两端点P0（x0,y0）和P1（x1,y1）。
2）计算初始值△x、△y、d=0、x=x0、y=y0。
3）绘制点（x,y）。
4）d更新为d+k，判断d的符号。
若d>0.5，则（x,y）更新为（x+1,y+1），同时将d更新为d-1；否则（x,y）更新为（x+1,y）。
5）当直线没有画完时，重复步骤3和4。
否则结束。
Bresenham画线算法代码：
voidBresenhamline（intx0,inty0,intx1,inty1,intcolor）
{
dx=x1-x0;dy=y1-y0;k=dy/dx;
d=0;x=x0;y=y0;
for（i=0;i{
putpixel（x,y,color）;
x=x+1；d=d+k;
if（d>0.5）
{y++；d=d-1;}
}
}
Bresenham画线算法改进：
改进1：
令e=d-0.5
e值的变化为：
●e初=-0.5，
●每走一步有e=e+k。
●if（e>0）thene=e-1
Bresenham画线算法代码：
voidBresenhamline（intx0,inty0,intx1,inty1,intcolor）
{
dx=x1-x0;dy=y1-y0;k=dy/dx;
e=-0.5;x=x0;y=y0;
for（i=0;i{
putpixel（x,y,color）;
x=x+1；e=e+k;
if（e>0）
{y++；e=e-1;}
}
}
改进2：
用2e△x来替换e
e值的变化为：
●e初=-△x，，
●每走一步有e=e+2△y。
●if（e>0）thene=e-2△x
Bresenham画线算法改进步骤
1）输入直线的两端点P0（x0,y0）和P1（x1,y1）。
2）计算初始值△x、△y、e=-△x、x=x0、y=y0。
3）绘制点（x,y）。
4）e更新为e+2△y，判断e的符号。
若e>0，则（x,y）更新为（x+1,y+1），同时将e更新为e-2△x；否则（x,y）更新为（x+1,y）。
5）当直线没有画完时，重复步骤3和4。
否则结束。
Bresenham画线算法代码：
voidBresenhamline（intx0,inty0,intx1,inty1,intcolor）
{
dx=x1-x0;dy=y1-y0;k=dy/dx;
e=-dx;x=x0;y=y0;
for（i=0;i{
putpixel（x,y,color）;
x=x+1；e=e+2*dy;
if（e>0）
{y++；e=e-2*dx;}
}
}
Bresenham画线算法分析：
Bresenham算法与中点画线法比较类似，都是根据理想直线与网格的交点与像素点距离来选择下一个像素点。
优点：
●不必计算直线之斜率，因此不做除法；
●不用浮点数，只用整数；
●只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。
Bresenham算法速度很快，适于用硬件实现。
4.八分圆思想的基本原理是什么？
答：
由于圆被定义为到给定点中心位置（xc，yc）的距离为r的点集。
圆心位于原点的圆有4条对称轴x=0,y=0,x=y,x=-y。
若已知圆弧上一点（x，y），可以得到其关于4条对称轴的其他7个点，这种性质就是圆的八对称性。
因此，只要扫描转换1/8圆弧，就可以用八对称性求出整个圆弧的像素集。
代码：
voiddrawpixel（intx0,inty0,intx1,inty1,intcolor）//画圆心在任意点的八分圆
{
CClientDCdc（this）;
dc.SetPixel（（x0+x1）,（y0+y1）,color）;
dc.SetPixel（（x0+y1）,（y0+x1）,color）;
dc.SetPixel（（x0+y1）,（y0-x1）,color）;
dc.SetPixel（（x0+x1）,（y0-y1）,color）;
dc.SetPixel（（x0-x1）,（y0-y1）,color）;
dc.SetPixel（（x0-y1）,（y0-x1）,color）;
dc.SetPixel（（x0-y1）,（y0+x1）,color）;
dc.SetPixel（（x0-x1）,（y0+y1）,color）;
}
5.中点画圆法的基本原理是什么？
答：
P为当前点亮象素，那么，下一个点亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp-1）。
F（X，Y）=X2+Y2-R2，有如下结论：
F（M）<0则M在圆内取P1
F（M）>=0则M在圆外取P2
⏹
d=F（M）=F（xp+1,yp-0.5）
=（xp+1）2+（yp-0.5）2-R2
⏹若d>=0,则P2（xp+1,yp–1）为下一个象素，那么：
d1=F（xp+2,yp-1.5）
=d+（2xp+3）+（-2yp+2）
⏹若d<0,则P1（xp+1,yp）为下一个象素，那么：
d2=F（xp+2,yp-0.5）=d+2xp+3
⏹d的初值:
⏹d0=F（1,R-0.5）=1+（R-0.5）2-R2=1.25–R
中点画圆法算法步骤：
1）输入圆的半径R。
2）计算初始值d=1.25-R、x=0、y=R。
3）绘制点（x,y）及其在八分圆中的另外七个对称点。
4）判断d的符号。
若d<0，则先将d更新为d+2x+3，再将（x,y）更新为（x+1,y）；否则先将d更新为d+2（x-y）+5，再将（x,y）更新为（x+1,y-1）。
5）当x否则结束。
中点画圆法代码：
voidMidpointCircle1（intx1,inty1,intr,COLORREFcolor）//圆心在任意点的中点画圆函数
{
intx,y;
floatd;
x=0;
y=r;
d=1.25-r;
drawpixel（x1,y1,x,y,color）;
while（x<=y）
{
if（d<0）
{
d+=2*x+3;
x++;
}
else
{
d+=2*（x-y）+5;
x++;
y--;
}
drawpixel（x1,y1,x,y,color）;
}
}
中点画圆法分析：
⏹为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。
⏹使用e=d-0.25代替d
⏹e0=1-R
6.Cohen-Sutherland裁剪算法的基本原理是什么？
答：
将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识。
编码的顺序为：
上，下，右，左。
直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。
●若P1P2完全在窗口内则code1=0,且code2=0；
●若P1P2完全在窗口外则code1&code2≠0；
●其他情况在交点处把线段分为两段。
其中一段完全在窗口外，可弃之。
然后对另一段重复上述处理。
编码的计算：
#defineLEFT1
#defineRIGHT2
#defineBOTTOM4
#defineTOP8
⏹intencode（floatx,floaty）
⏹{
⏹intc;
⏹c=0;
⏹if（x⏹c=c|LEFT;
⏹elseif（x>XR）
⏹c=c|RIGHT;
⏹if（y⏹c=c|BOTTOM;
⏹elseif（y>YT）
⏹c=c|TOP;
⏹returnc;
⏹}
交点的计算：
计算线段P1（x1,y1）P2（x2,y2）与窗口边界的交点
if（（LEFT&code）!
=0）/*当直线和左边界有交点*/
{x=XL;y=y1+（y2-y1）*（XL-x1）/（x2-x1）;}
elseif（（RIGHT&code）!
=0）
{x=XR;y=y1+（y2-y1）*（XR-x1）/（x2-x1）;}
elseif（（BOTTOM&code）!
=0）
{y=YB;x=x1+（x2-x1）*（YB-y1）/（y2-y1）;}
elseif（（TOP&code）!
=0）
{y=YT;x=x1+（x2-x1）*（YT-y1）/（y2-y1）;}
Cohen-Sutherland代码
voidCS_LineClip（floatx1,floaty1,floatx2,floaty2）
⏹{
⏹code1=encode（x1,y1）;code2=encode（x2,y2）;
⏹while（code1!
=0||code2!
=0）
⏹{
⏹if（（code1&code2）!
=0）return;
⏹code=code1;
⏹if（code1==0）code=code2;
⏹……（求交点）
⏹if（code==code1）{x1=x;y1=y;code1=encode（x,y）;}
⏹else{x2=x;y2=y;code2=encode（x,y）;}
⏹}
⏹setcolor（4）;
⏹line（x1,y1,x2,y2）;
⏹}
Cohen-Sutherland算法分析
⏹优点：
⏹用编码方法可快速判断线段的完全可见和显然不可见。
⏹简单，易于实现。
⏹缺点：
⏹本算法对于其它形状的窗口未必同样有效。
7.中点分割裁剪算法的基本原理是什么？
答：
所谓中点分割算法实质上是采用对分查找法求交点。
将线段分割成相等的两段，然后对每一小段重复上述的检查，直至找到每段与窗口边界的交点或分割小段的长度充分小，可以视为一点时为止。
例题：
从P0点出发利用中点分割算法找出离P0最近的可见点A。
从P1点出发利用中点分割算法找出离P1最近的可见点B。
从P0出发找距离P0最近可见点：
先求出P0P1的中点Pm,
若P0Pm不是显然不可见的，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1；
否则取PmP1代替P0P1。
再对新的P0P1求中点Pm。
重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点。
中点分割裁剪算法分析
⏹对分辩率为2N*2N的显示器，上述二分过程至多进行N次。
⏹主要过程只用到加法和除法运算，适合硬件实现，它可以用左右移位来代替乘除法，这样就大大加快了速度。
8.逐边裁剪是针对什么样的图形的裁剪算法？
针对什么样的窗口，基本思想是什么？
答：
每次用窗口的一条边界对要裁剪的多边形进行裁剪，裁剪时，顺序地测试多边形各顶点，保留边界内侧的顶点，删除外侧的顶点，同时，适时地插入新的顶点：
即交点和窗口顶点，从而得到一个新的多边形顶点序列。
然后以此新的顶点序列作为输入，相对第二条窗边界线进行裁剪，又得到一个更新的多边形顶点序列。
依次下去，相对于第三条、第四条边界线进行裁剪，最后输出的多边形顶点序列即为所求的裁剪好了的多边形。
逐边裁剪法规则：
假设当前处理的多边形的
升级会员 