计算机图形学（徐长青、许志闻）习题解答.docVIP

习题4. 在本章第一节说明Bresenham算法如何选择下一个像素点位置的图2-3中，其实是假定了在当前选择的点是(x,y)时，真正直线与横坐标为x+1的直线的交点是在y和y+1之间。如果不是这样，而是下面两种情况： 在y到y-1之间。例如从(0,0)到(7,2)的直线，在点(2,1)处向后。 在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的直线的交点的纵坐标。 当d0时，取上点，即(x+1,y+1)作为下一个像素点，当d0时，取下点，即(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，因为如果ypy-0.5，则P点的纵坐标会比Q点纵坐标更小，这时直线的斜率就不满足先决条件了（直线斜率将小于0）。所以因为直线斜率先决条件的限制，当真正直线与横坐标为x+1的直线的交点是在y和y-1之间时，该实际交点一定更靠近(x+1,y)点，所以一定会取(x+1,y)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y-1和y之间，所以有ypy，ypy+1，所以有d1=yp-y0，d2=y+1-yp0，由此可得d=d1-d20，所以要取下点(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，因已知ypy+1，而如果yqy，那么yp-yq1，所以直线斜率大于1）。当y≤yq≤y+0.5时，则一定有y+1≤yp≤y+1+0.5，因为如果ypy+1+0.5，同时又有yq≤y+0.5，则yp-yq1，这时直线的斜率大于1，不满足先决条件。所以因为直线斜率先决条件的限制，当真正直线与横坐标为x+1的直线的交点是在y+1和y+2之间时，该实际交点一定更靠近(x+1,y+1)点，所以一定会取(x+1,y+1)点作为下一个像素点。再来看一下按照Bresenham算法计算会取哪一点。从图可知，因为P点纵坐标yp在y+1和y+2之间，所以有ypy，ypy+1，所以有d1=yp-y0，d2=y+1-yp0，由此可得d=d1-d20，所以要取上点(x+1,y+1)作为下一个像素点，跟实际应取的点是一致的，所以在这种情况下Bresenham算法仍然可以正确工作。 综上所述，虽然书中所说算法在当前选择的点是(x,y)时，假定了真正直线与横坐标为x+1的直线的交点是在y和y+1之