2006年秋双学位计算机图形学

2006年秋双学位计算机图形学 作业题目 教材 计算机图形学（第二版）

第一次 P105

3.17 利用中点算法并考虑对称性，推导在区间-10<=x<=10上，对下列曲线进行扫描转换的有效算法：y=(1/12)*x3

3.20 考虑对称性，建立中点算法对形式为y=ax2-b的任意抛物线进行扫描转换，参数a,b及x的范围从输入值获得。

第二次 P106

3.34 利用circle函数，编写一个程序，显示具有合适标记的饼图。程序的输入包括：在某些区间上给定数据分布的数据组，饼图的名称和区间的名称。每部分的标记将是显示在饼图边界外靠近对应饼图部分的地方。

第三次 10.7 P139

4.20 编写一个程序，使用指定的图案对给定的椭圆内部进行填充。

第四次10.14 P168

5.12 确定对于任何直线y=mx+b的反射变换矩阵的形式。

第四次 10.22

比较若干条相对于裁剪窗口的不同方向的线段的Cohen-Sutherland和梁友栋-Barsky裁剪算法的算术运算次数。

第五次 10.29

6.18 将梁友栋-Barsky算法改称多边形裁剪算法。

第六次 11.4

8.13 设计一个程序，该程序允许用户使用一个笔画设备交互式地画图。

第七次 11.11

10.9 建立一个将给定的球、椭球或圆柱体变成多边形网格的一个算法。

第八次 11.18

10.20 给出d=5的均匀周期性B-样条曲线的混合函数。

第九次 11.25

11.13 设计关于任选平面反射的例程。

第十次

12.8 编写一个将透视投影棱台变换到规则平行六面体的程序。

上机

1. 实现Cohen-Sutherland多边形裁剪算法，要求显示多边形被每一条窗口边裁剪后的结果。 2. 编写一个程序，允许用户通过一个基本形状菜单并使用一个拾取设备，将每一个选取的

形状拖曳到指定位置，并提供保存和载入的功能。

3.. 写一篇综述性的调研报告，要求不少于3000字，独立完成。内容可以是 计算机图形学理论或算法的研究。如：曲线、曲面拟合算法；几何造型方法的研究。如：分形树、分形山、树木、花草、云、瀑布、粒子系统等等。或任何你感兴趣的领域。 4.

2006年秋双学位计算机图形学 作业参考答案

P105

3.17 利用中点算法并考虑对称性，推导在区间-10<=x<=10上，对下列曲线进行扫描转换的有效算法： y=(1/12)*x3

解答：第一象限和第三象限中心对称

内 外

考滤第一象限：对于斜率大于1的曲线段和斜率小于1的曲线段要分别考虑。 dy/dx=(1/4)*x2 ，当0≤x≤2时，dy/dx≤1；当x>2时，dy/dx>1； 定义函数：f(x,y)=y-(1/12)*x3

??0(x,y)位于曲线外?f(x,y)?＝0(x,y)位于曲线上

??0(x,y)位于曲线内?决策参数pk

1)当0≤x≤2（区域1）时, P1k = f(xk+1,yk+1/2)，P1 k+1=f(x k+1+1,yk+1+1/2), xk ＋1= xk+1

2

P1 k+1= P1k + (yk+1-yK)-(1/12)*(3*xk+9*xk+7)；

?12??3xp1k?0k?1?3xk?1?1??12 增量??12?1??3xkp1k?0?1?3xk?1?1??122)当x>2（区域2）时，P2k = f(xk+1/2,yk+1)，P2 k+1=f(x k+1+1/2,yk+1+1),

yk ＋1= yk+1

33

P2 k+1= P2k + 1-(1/12)*[(xk+1+1/2)-(xk+1/2)]；

1p2k?0??增量?? 121?3x?1/4p2?0k?1k??12??

算法描述：

1. 初始点(0,0)

2. 计算区域1中的初始决策参数值p10 = f(1,1/2)=5/12 3. 对区域1中，0≤x≤2，从k=0开始，完成下列测试：

假如p1k<0,则下一个点为（xk+1,yk+1）并且

2P1 k+1= P1k + 1 -(1/12)*( 3xk?1?3xk?1?1)

否则下一个点为（xk+1,yk）

2P1 k+1= P1k -(1/12)*( 3xk?1?3xk?1?1)

4. 当x>2时，进入区域2, 使用区域1的最后点(2,2/3)计算区域2的决策参数值：p20=f(2+1/2, 2/3+1)

完成下列测试：

假如p2k>0，则下一个点为（xk+1,yk+1）并且

P2 k+1= P2k + 1?123xk?1?1/4 12??否则下一个点为（xk,yk+1） P2 k+1= P2k + 1

5. 利用中心对称确定第三象限的点。

6. 重复区域1中的步骤直到x=2，重复区域2中步骤直到x=10。

3.20 考虑对称性，建立中点算法对形式为y=ax2-b的任意抛物线进行扫描转换，参数a,b及x的范围从输入值获得。 解答：

考虑y=ax2-b的任意曲线都可以由y=|a| x2通过翻转和平移得到，所以先计算y=|a| x2曲线。 令|a|=A;

dy/dx=2Ax，当0≤x≤1/(2A)时，dy/dx≤1；当x>1/(2A)时，dy/dx>1； 定义函数：f(x,y)=y-Ax2

??0(x,y)位于曲线外?f(x,y)?＝0(x,y)位于曲线上

??0(x,y)位于曲线内?决策参数pk

1)当0≤x≤1/(2A)（区域1）时, P1k = f(xk+1,yk+1/2)，P1 k+1=f(x k+1+1,yk+1+1/2), xk ＋1= xk+1

P1 k+1= P1k + (yk+1-yK)-A*(2*xk+3)；

?A*(2*xk?1?1)p1k?0 增量???1-A*(2*xk?1?1)p1k?02)当x>1/(2A)（区域2）时，P2k = f(xk+1/2,yk+1)，P2 k+1=f(x k+1+1/2,yk+1+1), yk ＋1= yk+1

22

P2 k+1= P2k + 1 - A*[(xk+1+1/2)-(xk+1/2)]；

p2k?0?1 增量???1?2Axk?1p2k?0

算法描述：

1. 输入a,b和x范围[xmin, xmax]，令A=|a|。

2. 令MAX=max{ |xmin|, |xmax |}, 在范围[-MAX,MAX]中作曲线

3. 初始点为(0,0),计算区域1中的初始决策参数值p10 = f(1,1/2) 4. 对区域1中，0≤x≤1/(2A)，从k=0开始，完成下列测试：

假如p1k<0,则下一个点为（xk+1,yk+1）并且

P1 k+1= P1k + 1-A*(2*xk?1?1) 否则下一个点为（xk+1,yk） P1 k+1= P1k - A*(2*xk?1?1)

5. 当x>1/(2A)时，进入区域2, 使用区域1的最后点(x0,y0)为初值计算区域2的决策参数

值初值：p20=f(x0+1/2, y0+1) 完成下列测试：

假如p1k>0，则下一个点为（xk+1,yk+1）并且

P2 k+1= P2k + 1?2Axk?1 否则下一个点为（xk,yk+1）

6. 7.

8. 9.

P106

3.34 利用circle函数，编写一个程序，显示具有合适标记的饼图。程序的输入包括：在某些区间上给定数据分布的数据组，饼图的名称和区间的名称。每部分的标记将是显示在饼图边界外靠近对应饼图部分的地方。

解答：

＃define TWO_PI 6.28 Typedef struct{

Int number; //数据组中元素的个数 Char[20] ChartName;

Data_t* pdata; //指向数据组的指针 }pieChart_array;

Typedef struct{ Float data

Char[20] SecName; }Data_t;

Void pieChart(pieChart_array dataArray) { wcPt2 pts[2],center; float radius = WINDOW_HEIGHT/4.0 float newSlice, total=0.0, lastSlice=0.0; int counter; center.x=WINDOW_WIDTH/2; center_y=WINDOW_WIDTH/2;

//画圆 pCircle(center,radius); //求总数 for(counter=0;counter

total += (dataArray.pdata[counter])->data; }

P2 k+1= P2k + 1

利用中心对称确定第二象限的点。

如果MAX≤1/(2A),那么重复区域1中步骤，计算到x=MAX，无须计算区域2；否则重复计算区域1中步骤，直到x=1/(2A),进出区域2,重复计算区域2中步骤，直到x=MAX。 截取[xmin, xmax]中的部分，如果a<0,那么就将计算所得点(x,y)变换到(x,-y)。 将上面所得曲线点(x,y)移到(x,y-b)

pts[0].x=center.x; pts[0].y=center.y;

//求每个区间的数据和的大小并画线，标明区间名 for(counter=0;counterdata/total+lastSlice; pts[1].x=center.x+radius*cosf(newSlice); pts[1].y=center.y+radius*sinf(newSlice); pPolyline(2,pts); //设置文字的对齐方式 if (newSliceTWO_PI*3/4){

setTextAlignment(right,normal); }else{ setTextAlignment(left,normal); } text(pts[1], (dataArray.pdata[counter])-> SecName);

lastSlice=newSlice; }

//画饼图名称 pts[0].x=center.x;

pts[0].y=center.y+ radius+4;

text(pts[0], dataArray.ChartName);

}

4.20 编写一个程序，使用指定的图案对给定的椭圆内部进行填充。 参见 课本p119

第四次10.14 P168

5.12 确定对于任何直线y=mx+b的反射变换矩阵的形式。 解答：

假设直线与x轴的夹角为?, tag? = m

直线y=mx+b的反射变换可以通过一下过程得到： a) 在y方向上平移 –b b) 旋转 -?

c) 对x轴做反射 d) 旋转 ?

e) 在y方向上平移 b

整个过程如下式：

????cos(??)?sin(??)0???100??x?????100?x'??????100???cos??sin?0???????????y'????01b????sin?cos?0????0?10????????sin(??)cos(??)0????01?b???y????????????????????????????????????????001?001?001?001?001?1??1?????????????????????????

也即是：

?x'???100??cos??sin?0??100??cos(??)?sin(??)0??100???x??y'????01b???sin?cos?0???0?10???sin(??)cos(??)0???01?b????y??????????????????001??0?1??01?01??1??????????001????0???001??????

化简得：

?bsin(2?)??x??x'??cos(2?)sin(2?)??y'??sin(2?)?cos(2?)b(cos(2?)?1)???y?

?????????1??01?1???0???又：

2tg?1?tg2? ， sin(2?)?cos(2?)?221?tg?1?tg?2m1?m2sin(2?)?即cos(2?)?，

1?m21?m2

所以：

?1?m2?2?x'??1?m?y'???2m???1?m2???1????0?

2m1?m21?m2?1?m20?2bm??21?m??x?2b????y 2???1?m??1????1??第六次 10.22

比较若干条相对于裁剪窗口的不同方向的线段的Cohen-Sutherland和梁友栋-Barsky裁剪算法的算术运算次数。 参考 课本 p182

第七次 10.29

6.18 将梁友栋-Barsky算法改称多边形裁剪算法。

解题思路：使用一种多边形裁减算法，将其中边的裁减改为使用梁友栋-Barsky算法

第六次 11.4

8.13 设计一个程序，该程序允许用户使用一个笔画设备交互式地画图。 参考课本 p224

第七次 11.11

10.9 建立一个将给定的球、椭球或圆柱体变成多边形网格的一个算法。 略

第八次 11.18

10.20 给出d=5的均匀周期性B-样条曲线的混合函数。 公式在课本 p265

?10?u?1 B0,1?u???0else??11?u?2 B1,1?u???else?0B0,2?u??u?02?uB0,1?u??B1,1?u? 1?02?1?uB0,1?u???2?u?B1,1?u?

0?u?1?u???2?u1?u?2 ?0else?12?u?20?u?1?1?1B0,3?u???u?2?u???u?1??3?u?1?u?2

2?22?u?312??3?u??2?1?2??u?1?21?u?2?11?B1,3?u????u?1??3?u???u?2??4?u?2?u?3

2?23?u?412??4?u??2?u?04?uB0,4?u??B0,3?u??B1,3?u?

3?04?1?4?u?B?u? u?B0,3?u??1,333???130?u?1?6u?1u2?2?u??1u?u?1??3?u??1?4?u1?u?2???666??u?1?2

?1u?3?u?2?1?u?1??3?u??4?u??1?u?2??4?u?2?2?u?3?6616??4?u?3?63?u?4????1?u?1?31?u?2?6?1?u?1?2?3?u??1?u?1??u?2??4?u??1?5?u??u?2?22?u?3B?1,4?u???666

?1??u?1??4?u?2?1?u?2??4?u??5?u13?u?4?66???u?3??5?u?216??6?5?u?34?u?5?

B0,5?u??u?04?0B?5?u0,4?u?B1,4?u? ?u4B?5?15?u?0,4?u??4B1,4?u? ??1u4??124?u3?2?u??1u2?u?1??3?u??1u?4?u??u?1?2?1?53?124242424?u??u?1?22112??u?3?u???2424u?u?1??3?u??4?u??24u?u?2??4?u???1?u?1?2?3?u??5?u??1?u?1??u?2??4?u??5?u??1?5?u?2?u?2?2???124u?4?u?3?124?u?1??4?u?2?5?u??124?u?2??4?u??5?u?2?1????3?242424u?35?u?124?24?5?u?4

第九次 11.25

11.13 设计关于任选平面反射的例程。 设计思路：

1、对原来点做旋转变换，使反射平面与一个坐标平面重合；

0?u?11?u?22?u?33?u?44?u?52、对变换后的反射平面作点的反射变换；

3、将反射点做反旋转变换，恢复到真正的反射点的位置。

第十次

12.8 编写一个将透视投影棱台变换到规则平行六面体的程序。 参见课本 p355

课上讨论：

11.11 自然样条曲线。

练习参考答案

一、填空

1．假设投影中心为Pc(0,0,0),投影平面为z=2,三维空间中的点P(x,y,z)在投影平面上的透视投影为点Pp(xp,yp,2),则xp=(1),yp=(2)。 Xp=2x/z Yp=2y/z

2．投影平面是XOY平面，投影方向是（a,b,c），其中，a、b、c都不为0，则平行投影变换矩阵是(3)。

1 0 -a/c 0 0 1 -b/c 0 0 0 0 0 0 0 0 1 或

1 0 -a/c 0 1 -b/c 0 0 0

3.椭圆的长轴是8，和x轴重合，短轴是6，和y轴重合，椭圆的中心在坐标原点。采用中点画椭圆的算法，在第一象限的椭圆轨迹上的所有的像素位置是（4）（5）（6）（7）（8）（9）（10）。

(0,3)，(1,3)，(2,3)，(3,2)，(4,1)，(4,0)

争议：有同学指出第一象限内的点应该不包括坐标轴上的点。但考虑到本题出题的本意并不在此，所以将会同时认可这两个答案 4. 在Cohen-Sutherland算法中，线段EF的两个端点的编码分别为0101和1001,线段EF的可见性为（11）。线段EF的两个端点的编码分别为1001和0110,线段EF的可见性为（12）。 完全不可见

既不完全可见，也不完全不可见

争议：经付峥同学提醒，第(12)空应该为不完全可见，也就是部分可见或完全不可见，如下图所示：

5. 字符的表示方法有（13）和（14）两种方式。(15)表示字库的主要缺点是占用大量存储空间，（16）表示字库的主要缺点是表示字符的过程复杂。 位图

轮廓线(矢量) 位图

轮廓线(矢量)

二、画出Weiler-Atherton算法的流程图，并写出图1的裁剪过程和结果，并用图示说明，并标注需要的记号。细线画的多边形是窗口，粗线画的是待裁剪的多边形

图1

算法思想

规定待裁剪多边形和裁剪窗口的顶点都按照顺（逆）时针方向排列。

待裁剪多边形的边与裁剪窗口的边界可能相交，也可能不相交。如果相交的话，交点必然成对出现，即一个交点为多边形的边进入裁剪窗口时的交点，称为入点；另一个交点为多边形的边走出裁剪窗口时的交点，称为出点。

沿着待裁剪多边形的边按照顺（逆）时针方向跟踪，直到遇到与窗口边界的交点为止；如果该交点为入点，那么继续沿着待裁剪多边形的边按照逆时针方向跟踪；如果该交点为出点，那么保存该交点供以后恢复跟踪时使用，并且在出点处沿着裁剪窗口的边界按照逆时针方向跟踪；重复上述过程，直到形成封闭的多边形；如果待裁剪多边形尚未完全遍历，那么就从前面保存的出点处恢复跟踪，继续沿着待裁剪多边形的边按照逆时针方向跟踪，直到待裁剪多边形完全遍历为止。

裁剪结果图如下：

三、由A（0,0,0）、B（1,0,0）、C（0,1,0）、D（0,0,1）定义的棱锥绕轴L旋转 45度，L的方向是（0，1，1）,并且经过C(0,1,0),请求出旋转后A和B的新位置A’和B’。 A’=（1/2，（2-sqart（2））/4，（sqart(2)-2）/4）

B’=((1+sqart(2))/2,(4-sqart(2))/4,(sqart(2)-4)/4)

四、请推导将三次参数曲线从Hermit表示转换为Bézier表示的转换矩阵。

假设参数多项式曲线的一种表示的几何矩阵为G1、基矩阵为M1，与之等价的另一种表示的基矩阵为M2，要求出对应的几何矩阵G2。

因为

G1·M1·T=G2·M2·T 即

G1·M1=G2·M2 所以

G2=G1·M1·M2-1=G1·M1→2

将参数多项式曲线的一种表示的几何矩阵转换为另一种表示的几何矩阵的转换矩阵为 M1→2=M1·M2-1 (1.9.4)

从Hermit表示转换为Bézier表示的转换矩阵为 MH→B=MH·MB-1 MH

1 0 -3 2 0 0 3 -2 0 1 -2 1 0 0 -1 1 MB

1 -3 3 -1 0 3 -6 3 0 0 3 -3 0 0 0 1

或：Mgeomh为Hermit几何矩阵，MgeomB为Bezier几何矩阵。

P(u)=U.MH.Mgeomh P(u)=U.MB.MgeomB

MB.MgeomB= MH.Mgeomh MgeomB= MB-1。MH.Mgeomh MH-〉B= MB-1。MH MB

-1 3 -3 1 3 -6 3 0 -3 3 0 0 1 0 0 0 MH

2 -2 1 1 -3 3 -2 -1 0 0 1 0 1 0 0 0

五、图示四叉树的结构，并写出实现两个用四叉树表示的二维物体的并集的算

法。

考虑计算物体S和T的并集U：自顶向下同步地访问表示S和T的四叉树。 （1）如果S和T的对应节点中有一个为满节点（full），那么在U中加入一个满节点； （2）如果S和T的对应节点中有一个为空节点（empty），那么将与空节点对应的另一个节点加入U中；

（3）如果S和T的对应节点都为部分满节点（partially full），那么在U中加入一个部分满节点，再递归地计算S和T中对应子树（各四棵）的并集，最后检查得到的四个子节点，若都为满节点，则删去这四个子节点，并将原来加入的部分满节点改为满节点。

本文来源：https://www.bwwdw.com/article/896o.html