计算机图形学课后题答案(第二版)--许长青、许志闻.pdf 21页

'习题4.在本章第一节说明Bresenham算法如何选择下一个像素点位置的图2-3中，其实是假定了在当前选择的点是(x,y)时，真正直线与横坐标为x+1的直线的交点是在y和y+1之间。如果不是这样，而是下面两种情况：(1)在y到y-1之间。例如从(0,0)到(7,2)的直线，在点(2,1)处向后。(2)在y+1到y+2之间。例如从(0,0)到(7,5)的直线，在点(2,1)处向后。试说明为什么对所列两种情况算法仍能正确地工作。解答：在给出两种情况下，Bresenham算法仍然能够正确工作的原因是判别式d保证了在这两种总情况下，仍然能正确的取到最接近真正直线的像素点。在Bresenham算法中，按照判别式d的正负来决定选择哪一点作为下一个像素点，判别式d如下计算：d=d1–d2。其中d1=yp–y，d2=y+1–yp，y是当前选中点(x,y)的纵坐标，yp是真正直线与横坐标为x+1的直线的交点的纵坐标。当d>0时，取上点，即(x+1,y+1)作为下一个像素点，当d<0时，取下点，即(x+1,y)作为下一个像素点。这里还要说明一下，因为此处是按照书上给出的Bresenham算法来进行像素选择的，所以实际上有一个先决条件，即直线的斜率处于0和1之间。只要保证斜率满足条件，在当前选择的点是(x,y)时，真正直线与横坐标为x+1的直线的交点即使不在y和y+1之间，书上所给的Bresenham都可以正确工作。题目所给两种情况中的直线斜率都满足算法的先决条件。在第(1)种情况下，如下图所示：当前选择点为(x,y)，下一点实际为P点，该点处于(x+1,y-1)和(x+1,y)两点之间，实际应取(x+1,y)点作为下一个像素点。现在来看一下为什么一定会取(x+1,y)点作为下一个像素点，而不是取(x+1,y-1)点作为下一个像素点。设Q点为选择(x,y)点作为显示像素点时实际的直线上的点，根据Bresenham算法的特点Q点的纵坐标yq一定满足y-0,5≤yq≤y+0.5，否则不会选择(x,y)点作为显示像素点，因为P点的纵坐标处于y和y-1之间，所以y-0.5≤yq≤y，否则该直线斜率将不满足条件（直线斜率将小于0）。当y-0,5≤yq≤y时，则一定有y-0,5≤yp≤y，因为如果yp0，由此可得d=d1-d2<0，所以要取下点(x+1,y)作为下一个像素点，跟实际应取的点是一致的，所以在这种情况下Bresenham算法仍然可以正确工作。在第(2)种情况下，如下图所示：当前选择点为(x,y)，下一点实际为P点，该点处于(x+1,y+1)和(x+1,y+2)两点之间，实际应取(x+1,y+1)点作为下一个像素点。现在来看一下为什么一定会取(x+1,y+1)点作为下一个像素点，而不是取(x+1,y+2)点作为下一个像素点。设Q点为选择(x,y)点作为显示像素点时实际的直线上的点，根据Bresenham算法的特点Q点的纵坐标yq一定满足y-0,5≤yq≤y+0.5，否则不会选择(x,y)点作为显示像素点，因为P点的纵坐标处于y+1和y+2之间，所以y≤yq≤y+0.5，否则该直线斜率将不满足条件（直线斜率将大于1，因已知yp>y+1，而如果yq1，所以直线斜率大于1）。当y≤yq≤y+0.5时，则一定有y+1≤yp≤y+1+0.5，因为如果yp>y+1+0.5，同时又有yq≤y+0.5，则yp-yq>1，这时直线的斜率大于1，不满足先决条件。所以因为直线斜率先决条件的限制，当真正直线与横坐标为x+1的直线的交点是在y+1和y+2之间时，该实际交点一定更靠近(x+1,y+1)点，所以一定会取(x+1,y+1)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y+1和y+2之间，所以有yp>y，yp>y+1，所以有d1=yp-y>0，d2=y+1-yp<0，由此可得d=d1-d2>0，所以要取上点(x+1,y+1)作为下一个像素点，跟实际应取的点是一致的，所以在这种情况下Bresenham算法仍然可以正确工作。综上所述，虽然书中所说算法在当前选择的点是(x,y)时，假定了真正直线与横坐标为x+1的直线的交点是在y和y+1之间，但只要要绘制的直线斜率满足处于0与1之间的先决条件，那么即使真正直线与横坐标为x+1的直线的交点不是在y和y+1之间，书上所介绍的Bresenham算法仍然可以正确工作。习题6.推广本章第二节给出的Bresenham画圆算法使能够画出一个内部填充的实心圆。解答：因为Bresenham画圆算法在画圆的时候通过绘制对称点来完成整个圆周的绘制，所以只需绘制对称点之间连线上的象素点即可完成对圆形内部的填充。推广算法的实现代码如下：//参数：(x0,y0)为圆心，R为半径，edgeColor为圆形边界颜色，inColor为圆形内部填充颜 色voidCDraw::BresenhamFillCircle(CDC*pDC,intx0,inty0,intR,COLORREFedgeColor,COLORREFinColor){intx,y,p;inti;x=0;y=R;p=3-(R<<1);for(;x<=y;x++){for(i=-y+y0;iSetPixel(-x+x0,i,inColor);pDC->SetPixel(x+x0,i,inColor);}for(i=-y+x0;iSetPixel(i,x+y0,inColor);pDC->SetPixel(i,-x+y0,inColor);}//绘制圆弧上对称的八个像素点pDC->SetPixel(x+x0,y+y0,edgeColor);pDC->SetPixel(-x+x0,y+y0,edgeColor);pDC->SetPixel(x+x0,-y+y0,edgeColor);pDC->SetPixel(-x+x0,-y+y0,edgeColor);pDC->SetPixel(y+x0,x+y0,edgeColor);pDC->SetPixel(-y+x0,x+y0,edgeColor);pDC->SetPixel(y+x0,-x+y0,edgeColor);pDC->SetPixel(-y+x0,-x+y0,edgeColor);if(p<0)p+=((x<<2)+6);else{p+=(((x-y)<<2)+10);y--;}}}习题8.本章第三节叙述了使用活跃边表的多边形扫描转换算法中ET表的填写方法。试写一个算法，输入多边形顶点坐标的逆时针序列，输出正确填写的ET表。解答：下面直接给出获得ET表的实现代码，为了构造书中所给样式的ET表，需要定义如下两个结构：structEdgeNode{//边节点intymax;//最大y值，吊桶数据doublexmin;//小y值端点的x值，吊桶数据doublefm;//斜率倒数，吊桶数据 EdgeNode*next;//连接下一个边};structHeadNode{//头节点intymin;//最小y值，ET表中登记项的y值EdgeNode*link;//连接边节点HeadNode*next;//连接下一个头节点};下面的实现代码用户获得构造完成的ET的头节点的头指针。其中参数points存放多边形的顶点的逆时针序列。HeadNode*CTestAView::GetET(CArray*points){HeadNode*pHead=NULL;intymin;//记录正在处理的当前边的最小y值intnymin,nymax;//记录与正在处理的当前边连接的下一边的最小y值和最大y值//循环点列表构造最初的边链表for(inti=0;iGetSize();i++){//获得当前点和下一点，构成一条边CPointpoint1=(CPoint)points->GetAt(i);CPointpoint2;//如果当前点已经是最后一个点，则和第一点构成一条边if(i==points->GetSize()-1)point2=(CPoint)points->GetAt(0);elsepoint2=(CPoint)points->GetAt(i+1);//边平行于x轴，舍弃if(point1.y==point2.y)continue;//构造边结构EdgeNode*edge=newEdgeNode();edge->next=NULL;//计算斜率倒数edge->fm=(double)(point2.x-point1.x)/(point2.y-point1.y);//设置ymin，ymax和xminif(point1.y>point2.y){edge->ymax=point1.y;ymin=point2.y;edge->xmin=point2.x;}else{edge->ymax=point2.y;ymin=point1.y;edge->xmin=point1.x;} CPointpoint3;//获得比较局部极大极小的第三点，该点和第二点够成一条边//如果前两点已经取到顶点序列尾部，则顺序从头取点作为第三点intj=i+2;do{if(jGetSize())point3=(CPoint)points->GetAt(j);elsepoint3=(CPoint)points->GetAt(j-points->GetSize());j++;}while(point2.y==point3.y);if(point2.y>point3.y){//计算point2和point3点对应的ymin和ymaxnymax=point2.y;nymin=point3.y;}else{nymax=point3.y;nymin=point2.y;}//下面判断局部极大极小并缩短相应的边//如果连续的两条边的ymin值和ymax值都不同//表示连接两边的节点不为局部极大或极小if(ymin!=nymin&&edge->ymax!=nymax){//缩短当前边//如果当前边的ymax值较大，则缩短当前边的ymin值if(edge->ymax>nymax){ymin++;edge->xmin+=edge->fm;}else//否则，缩短当前边的ymax值edge->ymax--;}//以下处理将当前边加入ET表if(pHead==NULL){//当前没有头节点pHead=newHeadNode();pHead->ymin=ymin;pHead->link=edge;pHead->next=NULL;}elseAddEdge(pHead,ymin,edge);}//返回获得的ET表头指针returnpHead;} 在上面的实现代码中用到了一个添加边函数，该函数作用是将处理完成的一条边加入到当前已有的ET表中，该函数的实现代码如下：voidCTestAView::AddEdge(HeadNode*head,intymin,EdgeNode*edge){HeadNode*temphead;while(head!=NULL){//循环头节点if(head->ymin==ymin){//找到了对应的头节点EdgeNode*p=head->link;//获得头节点对应的第一条边节点if(p->xmin>edge->xmin){//新加入边的xmin值较小head->link=edge;edge->next=p;return;}while(p->next!=NULL){//循环当前头节点下所有边节点if(p->next->xmin>edge->xmin){edge->next=p->next;p->next=edge;return;}p=p->next;}//到这里说明新加入的边的xmin值比原有的都大p->next=edge;return;}elseif(head->ymin>ymin){//当前头节点的ymin值大于新加入的边的ymin//下面处理新加入头节点HeadNode*newhead=newHeadNode();newhead->ymin=head->ymin;newhead->link=head->link;newhead->next=head->next;head->ymin=ymin;head->link=edge;head->next=newhead;return;}temphead=head;head=head->next;}//到这里说明新加入的边的ymin值比原有的头节点的ymin值都大HeadNode*newhead=newHeadNode();newhead->ymin=ymin;newhead->link=edge;newhead->next=NULL; temphead->next=newhead;}获得ET的实现函数中有两处需要说明：1、判断局部极大极小时，是用多边形顶点序列中相邻的3个点所构成的两条边进行判断，这是要求这两个边不能存在平行于x轴的边，因为当取得point1和point2点时已经判断了确定的边是否平行于x轴，所以主要处理在于确保获得的point3点，不会和point2点同时在一条平行于x轴的直线上，如果获得的point3点与point2点的y坐标相同，就按顶点序列继续取下一点作为point3点，直到point2点的y坐标与取得的point3点的y坐标不同为止。2、在判断不是局部极大或极小后，缩短的都是当前处理的边，这样做可以保证边一次处理完毕，否则就会有处理当前边时，却需要去缩短以前处理的边或者还没有处理的边的情况存在。对当前边处理的方式就是如果当前边的ymax最大，则在ymin方向上缩短当前边，否则就在ymax方向上缩短当前边。为了检测以上构造的ET表是否正确，下面编写实现了使用上面方法构造的ET表完成多边形扫描转换算法。代码如下：voidCTestAView::Polygonfill(CDC*pDC,CArray*points,COLORREFcolor){//获得ET表HeadNode*pET=GetHEET(points);//AET表EdgeNode*pAET=NULL;//最小y值inty=pET->ymin;//最大y值intymax=y;//有需要处理的扫描线while(y<=ymax){//ET表不为空，并且当前的边的ymin和当前扫描线相等if(pET!=NULL&&pET->ymin==y){//将当前头节点对应的边合并到AET表中//获得当前要合并的头节点下边链表的头指针EdgeNode*p=pET->link;if(pAET==NULL)pAET=p;else{EdgeNode*q=pAET;while(q->next!=NULL)q=q->next;q->next=p;}//清除已经处理过的头节点，并释放空间HeadNode*deletehead=pET;pET=pET->next;deletedeletehead; //根据移动过来的边，修改ymax值while(p!=NULL){if(ymaxymax)ymax=p->ymax;p=p->next;}//排序SortAET(pAET);}EdgeNode*pFill=pAET;//填充AET表中的区间while(pFill!=NULL){//填充当前边和下一条边之间的区间for(inti=(int)pFill->xmin;i<=(int)pFill->next->xmin;i++)pDC->SetPixel(i,y,color);//AET表中的边应成对出现pFill=pFill->next->next;}//将AET表中ymax为当前扫描线的边清除出表pFill=pAET;EdgeNode*pFore=NULL;while(pFill!=NULL){//当前边ymax等于扫描线if(pFill->ymax==y){if(pFore!=NULL)//说明要删除的不是第一个节点pFore->next=pFill->next;//修改上一条边的指向else//说明要删除的是第一个节点pAET=pFill->next;//需要修改AET表头指针指向下一条边//销毁已经清除出链表的边对象EdgeNode*deleteedge=pFill;//移动到下一条边pFill=pFill->next;deletedeleteedge;}else{//记录当前边作为下次处理时的上一边pFore=pFill;//移动到下一条边pFill=pFill->next;}} //AET表中仍然有边if(pAET!=NULL){//重新计算AET中各边的xmin值pFill=pAET;while(pFill!=NULL){pFill->xmin+=pFill->fm;pFill=pFill->next;}//重新排序SortAET(pAET);}//处理下一条扫描线y++;}}上面代码中使用到对AET表进行排序的函数，其代码如下：voidCTestAView::SortAET(EdgeNode*pEDGE){//要排序的边链表中第一个边EdgeNode*p1=pEDGE;//第一个边的下一个边EdgeNode*p2=NULL;while(p1!=NULL){p2=p1->next;//获得下一条边while(p2!=NULL){//如果前一条边的xmin大于后一条边if(p1->xmin>p2->xmin){//交换数据intcid;doublecdd;cid=p1->ymax;p1->ymax=p2->ymax;p2->ymax=cid;cdd=p1->xmin;p1->xmin=p2->xmin;p2->xmin=cdd;cdd=p1->fm;p1->fm=p2->fm;p2->fm=cdd;}//下一条边p2=p2->next;}//下一条边p1=p1->next;} }以上代码均测试通过。习题8.若窗口在定义为平行于用户坐标轴的直立矩形后，还允许此窗口再绕左下角点旋转θ角，写出由旋转后窗口到直立矩形视见区的变换矩阵。解答：设在绕左下角点旋转θ角之前，窗口的左下角点坐标为（wxl,wyl），右上角点坐标为（wxh,wyh），直立矩形视见区的左下角点坐标为（vxl,vyl），右上角点坐标为（vxh,vyh）。变换矩阵可按如下方式求得：首先平移窗口，使其左下角点与坐标系原点重合，然后绕原点旋转−θ角，使窗口变回直立矩形，然后对其作比例变换使其大小与视见区相同，最后通过平移使其与视见区重合。由此得到视见变换矩阵为：vxh−vxlvyh−vylH=T(−wxl,−wyl)•R(−θ)•S(,)•T(vxl,vyl)wxh−wxlwyh−wyl⎡vxh−vxl⎤00⎢⎥⎡100⎤⎡cos(−θ)sin(−θ)0⎤wxh−wxl⎡100⎤⎢⎥⎢⎥⎢⎥vyh−vyl⎢⎥=010−sin(−θ)cos(−θ)0⎢00⎥010⎢⎥⎢⎥⎢wyh−wyl⎥⎢⎥⎢⎣−wxl−wyl1⎥⎦⎢⎣001⎥⎦⎢001⎥⎢⎣vxlvyl1⎥⎦⎢⎥⎣⎦⎡vxh−vxl⎤00⎢⎥⎡cosθ−sinθ0⎤wxh−wxl⎡100⎤⎢⎥⎢⎥vyh−vyl⎢⎥=sinθcosθ0⎢00⎥010⎢⎥⎢wyh−wyl⎥⎢⎥⎢⎣−wxlcosθ−wylsinθwxlsinθ−wylcosθ1⎥⎦⎢001⎥⎢⎣vxlvyl1⎥⎦⎢⎥⎣⎦⎡vxh−vxlvyh−vyl⎤⎢cosθ−sinθ0⎥⎢wxh−wxlwyh−wyl⎥⎡100⎤⎢vxh−vxlvyh−vyl⎥⎢⎥=sinθcosθ0010⎢wxh−wxlwyh−wyl⎥⎢⎥⎢vxh−vxlvyh−vyl⎥⎢⎣vxlvyl1⎥⎦⎢−(wxlcosθ+wylsinθ)(wxlsinθ−wylcosθ)1⎥⎢⎣wxh−wxlwyh−wyl⎥⎦⎡vxh−vxlvyh−vyl⎤⎢cosθ−sinθ0⎥wxh−wxlwyh−wyl⎢⎥⎢vxh−vxlvyh−vyl⎥=sinθcosθ0⎢wxh−wxlwyh−wyl⎥⎢⎥vxh−vxlvyh−vyl⎢vxl−(wxlcosθ+wylsinθ)vyl+(wxlsinθ−wylcosθ)1⎥⎢⎣wxh−wxlwyh−wyl⎥⎦习题10.求完成如下空间图形变换的变换矩阵：(3)产生对z=3平面对称的图形。(4)绕过原点和（1，1，1）的直线旋转45°。解答：(3)变换矩阵如下： T(0,0,−3)⋅S(1,1,−1)⋅T(0,0,3)⎡1000⎤⎡1000⎤⎡1000⎤⎢⎥⎢⎥⎢⎥010001000100=⎢⎥⎢⎥⎢⎥⎢0010⎥⎢00−10⎥⎢0010⎥⎢⎥⎢⎥⎢⎥⎣00−31⎦⎣0001⎦⎣0031⎦⎡1000⎤⎢⎥0100=⎢⎥⎢00−10⎥⎢⎥⎣0061⎦(4)在以过坐标原点的任意直线为旋转轴作旋转变换的变换矩阵中代入向量值及旋转角度，得变换矩阵如下：R(θ)=R(α)R(β)R(θ)R(−β)R(−α)xyzyx22⎡n+(1−n)cosθnn(1−cosθ)+nsinθnn(1−cosθ)−nsinθ0⎤11123132⎢22⎥nn(1−cosθ)−nsinθn+(1−n)cosθnn(1−cosθ)+nsinθ0=⎢12322231⎥⎢nn(1−cosθ)+nsinθnn(1−cosθ)−nsinθn2+(1−n2)cosθ0⎥13223133⎢⎥⎢⎣0001⎥⎦⎡1+22−2+62−2−6⎤⎢0⎥366⎢⎥⎢2−2−61+22−2+6⎥0=⎢636⎥⎢⎥2−2+62−2−61+2⎢0⎥⎢663⎥⎢⎣0001⎥⎦习题14.等轴投影是投影方向与三个坐标轴有相等夹角时的正交投影，设要实现一个投影方向为（1，1，1）的等轴投影，可以先绕y轴再绕x轴做旋转变换使投影方向重合于z轴正方向，然后就可以进行正交投影了。试用这个想法推导出做等轴投影的变换矩阵，然后验证三根坐标轴上的单位向量被相等地缩短，并且可以使三个坐标轴的投影具有相等的夹角。解答：已知：22222v=x+z,u=x+y+z11111zxvy111cosα=−,sinα=−,cosβ=,sinβ=vvuu y(x1,y1,z1)(0,y1,v)βOxαz在视觉坐标系下可得如下变换：⎡z1x1⎤⎡1000⎤⎢00⎥⎢vy1⎥vv00⎢0100⎥⎢uu⎥Ry(α)=⎢xz⎥Rx(β)=⎢yv⎥111⎢−00⎥⎢0−0⎥⎢vv⎥⎢uu⎥⎢⎣0001⎥⎦⎢⎣0001⎥⎦⎡z1x1⎤⎡1000⎤⎢0−0⎥⎢vy1⎥vv0−0⎢0100⎥⎢uu⎥Ry(−α)=⎢xz⎥Rx(−β)=⎢yv⎥111⎢00⎥⎢00⎥⎢vv⎥⎢uu⎥⎢⎣0001⎥⎦⎢⎣0001⎥⎦⎡1000⎤⎢⎥0100M=⎢⎥ob⎢0000⎥⎢⎥⎣0001⎦获得变换矩阵为 M"=R(α)R(β)MR(−β)R(−α)obyxobxy⎡22⎤⎡1000⎤⎡1000⎤⎢00⎥⎢66⎥⎡1000⎤⎢66⎥⎢22⎥⎢00⎥⎢0100⎥⎢0−0⎥=⎢0100⎥⎢33⎥⎢⎥⎢33⎥⎢22⎥⎢66⎥⎢0000⎥⎢66⎥⎢−00⎥⎢0−0⎥⎢⎥⎢00⎥2233⎣0001⎦33⎢⎣0001⎥⎦⎢⎣0001⎥⎦⎢⎣0001⎥⎦⎡22⎤⎢0−0⎥22⎢⎥0100⎢⎥⎢22⎥00⎢22⎥⎢⎣0001⎥⎦⎡211⎤−−0⎢⎥333⎢121⎥⎢−−0⎥=⎢333⎥⎢112⎥−−0⎢333⎥⎢⎣0001⎥⎦在观察坐标系下可得如下变换矩阵： A⎡1001⎤⎢⎥B0101R(α)R(β)M⎢⎥yxobC⎢⎣0011⎥⎦⎡263⎤⎢−0⎥⎢233⎥⎡1000⎤⎡1001⎤⎢63⎥⎢⎥⎢⎥00⎢0100⎥=⎢0101⎥⎢33⎥⎢⎥⎢0000⎥⎢⎣0011⎥⎦⎢263⎥⎢⎥−−0⎣0001⎦⎢233⎥⎢⎣0001⎥⎦⎡26⎤⎢−00⎥26⎡1001⎤⎢⎥⎡22−6601⎤A"⎢⎥⎢0600⎥⎢⎥=⎢0101⎥⎢3⎥=⎢06301⎥B"⎢⎣0011⎥⎦⎢26⎥⎢−22−6601⎥C"⎢−−00⎥⎣⎦⎢26⎥⎢⎣0001⎥⎦因为：222O"A"=,O"B"=,O"C"=，即O"A"=O"B"=O"C"3332∴三个坐标轴上的单位向量以相同比例系数缩短3三个坐标轴上的单位向量在投影平面上的点为(2/2,−6/6)，(0,6/3)，(−2/2,−6/6) 266122O"A"⋅O"B"=(,−)⋅(0,)=−=⋅⋅cosα263333�∴α=120626122O"B"⋅O"C"=(0,)⋅(−,−)=−=⋅⋅cosβ326333�∴β=1202626122O"C"⋅O"A"=(−,−)⋅(,−)=−=⋅⋅cosγ2626333�∴γ=120∴三个坐标轴上的投影具有相等的夹角。习题20.修改Cohen-Sutherland直线裁剪算法，使其成为一个直线“开窗”算法，即指定一个窗口后，窗口内舍弃，窗口外保留。解答：根据题意，可知只需要对原Cohen-Sutherland算法中的两处进行修改即可满足要求。第一处是判断C1和C2的逻辑乘结果不为0时，此时如果该条件满足，表示线段完全在窗外，原算法此处需要将原线段完全舍弃，这里就需要将原线段完全绘制出来即可。第二处是最后要将原线段中窗口中可见部分绘制出来，此时原算法已经完成对原线段的裁剪，得出来原线段在窗口内的部分，这里只需要改成将原线段去掉窗口以内部分后的线段绘制出来即可。根据以上分析，修改Cohen-Sutherland直线裁剪算法为直线“开窗”算法如下：doublexl,xr,yt,yb;(这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示voidCohen_Sutherland(doublex0,y0,x2,y2){intc,c1,c2;doublex,y;//需要将原线段的端点保存起来，以备后面需要确定原线段去除窗口内部分时使用doublex00=x0,y00=y0,x22=x2,y22=y2;makecode(x0,y0,c1);makecode(x2,y2,c2);while(c1!=0||c2!=0){if(c1&c2!=0){showline(x00,y00,x22,y22);//显示原线段，能走到这说明原线段都在窗口外return;}c=c1;if(c==0)c=c2;if(c&1==1){y=y0+(y2-y0)*(x1-x0)/(x2-x0);x=x1;}elseif(c&2==2){y=y0+(y2-y0)*(xr-x0)/(x2-x0);x=xr;}elseif(c&4==4){x=x0+(x2-x0)*(yb-y0)/(y2-y0);y=yb;} elseif(c&8==8){x=x0+(x2-x0)*(yt-y0)/(y2-y0);y=yt;}if(c==c1){x0=x;y0=y;makecode(x,y,c1);}else{x2=x;y2=y;makecode(x,y,c2);}}//因为原算法的线段分割保证了端点的顺序性，所以采用如下的方法可确定原线段在窗口外的部分if(x00!=x0||y00!=y0)showline(x00,y00,x0,y0);if(x2!=x22||y2!=y22)showline(x2,y2,x22,y22);}此算法已经编码实现并测试通过。另一种方法是在分割线段的同时绘制窗口外的线段，该方法无需记录初始点坐标。doublexl,xr,yt,yb;(这里事先给出窗口的位置，四个数值是已知的)，修改的部分用蓝色表示voidCohen_Sutherland(doublex0,y0,x2,y2){intc,c1,c2;doublex,y;makecode(x0,y0,c1);makecode(x2,y2,c2);while(c1!=0||c2!=0){if(c1&c2!=0){//显示线段，此时绘制的是分割完后，完全在窗口外同侧的线段showline(x0,y0,x2,y2);return;}c=c1;if(c==0)c=c2;if(c&1==1){y=y0+(y2-y0)*(x1-x0)/(x2-x0);x=x1;}elseif(c&2==2){y=y0+(y2-y0)*(xr-x0)/(x2-x0);x=xr;}elseif(c&4==4){x=x0+(x2-x0)*(yb-y0)/(y2-y0);y=yb;}elseif(c&8==8){x=x0+(x2-x0)*(yt-y0)/(y2-y0);y=yt;}if(c==c1){showline(x0,y0,x,y);//绘制被分割抛弃的线段x0=x;y0=y;makecode(x,y,c1);}else{showline(x,y,x2,y2);//绘制被分割抛弃的线段x2=x;y2=y;makecode(x,y,c2);}}}此算法已经编码实现并测试通过。习题10.设平面上四点设平面上四点(1，1)，(2，3)，(4，3)，(3，1)确定的Bezier曲线是P(t)，如果在点P(1/2)处将它分为两段，求前后两段做为Bezier曲线各自的四个控制点坐标。解答： 使用分裂法，有：Q0P0(1,1)→R0Q1P1(2,3)→R1R0=(3/2,2)Q2P2(4,3)→R2R1=(3,3)R0=(9/4,5/2)Q3P3(3,1)→R3R2=(7/2,2)R1=(13/4,5/2)R0=(11/4,5/2)i=0i=1i=2前半段四个控制点Q0(1,1)，Q1(3/2,2)，Q2(9/4,5/2)，Q3(11/4,5/2)，0≤t≤1/2；后半段四个控制点R0(11/4,5/2)，R1(13/4,5/2)，R2(7/2,2)，R3(3,1)，1/2≤t≤1。习题17.设给定n个型值点P，P，……，P，问如何作出一条均匀4阶3次B样条曲线，12n使曲线分别以P和P为起点和终点，并与边PP和边PP相切。1n12n−1n解答：解法1：根据题意，在已有的n个型值点前面增加两个型值点V和V，在后面增加两个型值点V和123V。4第一段曲线由V，V，P，P控制，要求曲线要以P为起点，并且与边PP相切，则有：12121121Q(0)=(V+4V+P)=P121161Q"(0)=(P−V)=P−P11212解上面方程可得出V和V为：12V=3P−2P1121V=(P+P)2122最后一段曲线由P，P，V，V控制，要求曲线要以P为终点，并且与边PP相切，n−1n34nn−1n则有：1Q(1)=(P+4V+V)=Pn34n61Q"(1)=(V−P)=P−P4nnn−12解上面方程可得出V和V为：34 1V=(P+P)3n−1n2V=3P−2P4nn−1增加如上4点到已有的型值点中，可使作出的均匀4阶3次B样条曲线满足题目要求。解法2：也可以只在前后各增加一个型值点V和V。12第一段曲线由V，P，P，P控制，要求曲线要以P为起点，并且与边PP相切，则有：11231121Q(0)=(V+4P+P)=P112161Q"(0)=(P−V)=P−P21212解上面方程可得出V为：1V=2P−P112最后一段曲线由P，P，P，V控制，要求曲线要以P为终点，并且与边PP相n−2n−1n2nn−1n切，则有：1Q(1)=(P+4P+V)=Pn−1n2n61Q"(1)=(V−P)=P−P2n−1nn−12解上面方程可得出V为：2V=2P−P2nn−1增加如上2点到已有的型值点中，可使作出的均匀4阶3次B样条曲线满足题目要求。习题20.确定通过Q=（-1，0），Q=（0，1），Q=（1，0）这三个型值点的平面上的没012有直线段的四阶三次均匀B样条曲线。解答：设待求四阶三次均匀B样条曲线的四个控制点分别为P(x,y)，P(x,y)，P(x,y)，111222333P(x,y)。444根据给定点的特点，可以使曲线的四个控制点两两关于y轴对称（P(x,y)与P(x,y)对111444 1称，P(x,y)与P(x,y)对称），并且曲线起点为Q，终点为Q，在参数值为时曲222333022线上的点为Q。1根据以上假设可以得到下列式子：1Q(0)=(P+4P+P)=Q123061Q(1)=(P+4P+P)=Q2342611123231Q()=(P+P+P+P)=Q12341268888带入坐标值，并且根据对称关系，可得如下两个方程组：⎧1(x+4x+x)=−1⎪1236⎪⎪1(x+4x+x)=1⎪2346⎪⎪1123231⎨(x1+x2+x3+x4)=0⎪68888⎪x=−x14⎪x=−x⎪23⎪⎪⎩⎧1(y+4y+y)=0⎪1236⎪⎪1(y+4y+y)=0⎪2346⎪⎪1123231⎨(y1+y2+y3+y4)=1⎪68888⎪y=y14⎪y=y⎪23⎪⎪⎩解上面两个方程组可得如下结果：⎧x1=t⎪1⎪x=−t−22⎪3⎨⎪1x=t+23⎪3⎪⎩x4=−t ⎧20y=−⎪13⎪⎪4y=⎪23⎨⎪4y=3⎪3⎪20⎪y=−4⎩3根据结果可知满足要求的控制点可以是无限多组，只需这些点的x坐标满足关于t的参数方程，并且y坐标是求出的固定值即可。204420例如，令t=3，可得出四个控制点为P(3,−)，P(−3,)，P(3,)，P(−3,−)。12343333习题22.设有一段Hermite形式的三次曲线，且是由两个控制点P，P及两点处的导数值14P"，P"确定的。14（1）求四个控制点B，B，B，B，使这四点确定的三次Bezier曲线，与原Hermite1234形式的三次曲线相同。（2）求四个控制点V，V，V，V，使这四点确定的4阶3次等距B样条曲线仍与原1234来那条曲线相同。解答：（1）根据习题的第8题可知，给出四点P0，P1，P2，P3，使P0’=3(P1-P0)，P3’=3(P3-P2)，这时用P0，P3，P0’，P3’可以确定一条Hermite形式的三次曲线，所确定的曲线与用原来四点确定的Bezier形式的三次曲线相同，以上结论可通过如下证明得到：根据Hermite三次曲线定义，可知P0，P3，P0’，P3’确定的Hermite三次曲线参数方程式为：32323232P(t)=P0(2t−3t+1)+P3(−2t+3t)+P0"(t−2t+t)+P3"(t−t)(0≤t≤1)将使P0’=3(P1-P0)，P3’=3(P3-P2)带入上面的方程式，得到Hermite三次曲线参数方程式为：32323232P(t)=P0(2t−3t+1)+P3(−2t+3t)+3(P1−P0)(t−2t+t)+3(P3−P2)(t−t)3232323=P0(−t+3t−3t+1)+P1(3t−6t+3t)+P2(−3t+3t)+P3t3223=(1−t)P0+3(1−t)P1+3t(1−t)P2+tP3(0≤t≤1)根据三次Bezier曲线定义，可知P0，P1，P2，P3确定的三次Bezier曲线方程为：3223P(t)=(1−t)P0+3(1−t)P1+3t(1−t)P2+tP3(0≤t≤1)两个曲线方程相同，所以用P0，P3，P0’，P3’确定的Hermite形式的三次曲线与用P0，P1，P2，P3确定的Bezier形式的三次曲线相同。 本题已知Hermite曲线由两个控制点P，P及两点处的导数值P"，P"确定，根据1414以上结论，可知：P=B；P=B；P"=3（B-B）；P"=3（B-B）1144121443可计算得出用于确定三次Bezier曲线的四个控制点分别为：B=P111B=P"+P21131B=P−P"3443B=P44由上面四个控制点确定的三次Bezier曲线与给定的Hermite形式的三次曲线相同。（2）4阶3次等距B样条曲线与给定的Hermite形式的三次曲线相同，则该B样条曲线必然具有如下特点：曲线的起点和终点分别是P和P，曲线在起点和终点处的导数值分别为P"和P"，1414即有如下式子成立（Q为4阶3次等距B样条曲线）：1Q(0)=(V+4V+V)=P123161Q(1)=(V+4V+V)=P234461Q"(0)=(V−V)=P"31121Q"(1)=(V−V)=P"4242解上面的方程组，可得：72V=−P−P"+2P−P"111443321V=2P+P"−P+P"211443312V=−P−P"+2P−P"311443327V=2P+P"−P+P"4114433以上四点确定的4阶3次等距B样条曲线与给定的Hermite形式的三次曲线相同。'