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

《计算机图形学课后题答案(第二版)--许长青、许志闻.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题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保证了在这两种

2、总情况下，仍然能正确的取到最接近真正直线的像素点。在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算法来进行像素选择的，所以实际上有一个先决条件，即直线的斜

3、率处于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)

4、点作为显示像素点时实际的直线上的点，根据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，因为如果yp

5、y-1之间时，该实际交点一定更靠近(x+1,y)点，所以一定会取(x+1,y)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y-1和y之间，所以有yp0，由此可得d=d1-d2<0，所以要取下点(x+1,y)作为下一个像素点，跟实际应取的点是一致的，所以在这种情况下Bresenham算法仍然可以正确工作。在第(2)种情况下，如下图所示：当前选择点为(x,y)，下一点实际为P点，该点处于(x+1,

6、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，而如果yq

7、1，所以直线斜率大于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之间，所以有

8、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之间，但只要要绘制