（本科）5章 图形裁剪、消隐和光栅化(I)ppt课件.ppt

课程主讲人：5章 图形裁剪、消隐和光栅化(I)2022/5/11第第5章章 图形裁剪、消隐和光栅化图形裁剪、消隐和光栅化5.1 图形的窗口裁剪图形的窗口裁剪 线段裁剪算法线段裁剪算法 多边形裁剪算法多边形裁剪算法5.2 图形光栅化图形光栅化 线段光栅化线段光栅化DDA算法算法 线段光栅化线段光栅化Bresenham算法算法 多边形光栅化多边形光栅化5.3 图形消隐图形消隐 凸多面体消隐凸多面体消隐 画家算法画家算法 Z缓存算法缓存算法 光线投射算法光线投射算法2022/5/115.1 图形的窗口裁剪图形的窗口裁剪裁剪的概念裁剪的概念 - 图形绘制是在显示器的一个有限的区域内进行，这个区域图形绘制是在显示器的一个有限的区域内进行，这个区域称为窗口。称为窗口。 - 一个图形可能仅有一部分被绘制。一个图形可能仅有一部分被绘制。 - 需要对图形进行裁剪，将超出窗口的部分去除，保留落在需要对图形进行裁剪，将超出窗口的部分去除，保留落在窗口内的部分。窗口内的部分。 - 图形是基本几何元素点、线、多边形组成的，图形裁剪计图形是基本几何元素点、线、多边形组成的，图形裁剪计算就是对点、线、多边形的裁剪运算。算就是对点、线、多边形的裁剪运算。 - 裁剪在投影变换后进行，属于图形空间的计算。裁剪在投影变换后进行，属于图形空间的计算。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪裁剪窗口的定义裁剪窗口的定义2022/5/115.1 图形的窗口裁剪图形的窗口裁剪5.1.1 点的裁剪点的裁剪 点点P(x,y)的窗口裁剪就是判断的窗口裁剪就是判断P位置是在窗口内还是在窗口外。位置是在窗口内还是在窗口外。可以用下面的表达式进行判断可以用下面的表达式进行判断 若若m=1 点在窗口内部点在窗口内部)bottomy(and)topy(and)leftx(and)rightx(m2022/5/115.1 图形的窗口裁剪图形的窗口裁剪5.1.2 线段的裁剪：线段的裁剪：Cohen-Sutherland区域编码算法区域编码算法线段与窗口的关系线段与窗口的关系（a）整条线段在窗口之内。）整条线段在窗口之内。（b）整条线段在窗口之外。）整条线段在窗口之外。（c）线段的一部分在窗口之）线段的一部分在窗口之 内，另一部分在窗口之外。内，另一部分在窗口之外。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪区域编码算法将窗口及其周围分为九个区域区域编码算法将窗口及其周围分为九个区域2022/5/115.1 图形的窗口裁剪图形的窗口裁剪区域编码的优点：区域编码的优点：1 容易将不需剪裁的线段挑出。容易将不需剪裁的线段挑出。 如果一条线段的两端都在窗口内，或都在同一侧外部区域，如果一条线段的两端都在窗口内，或都在同一侧外部区域，则该线段不需剪裁，否则，该线段为可能剪裁直线。则该线段不需剪裁，否则，该线段为可能剪裁直线。2 对可能剪裁的线段，容易对相交边框进行判断，缩小了求交对可能剪裁的线段，容易对相交边框进行判断，缩小了求交范围。范围。3 裁剪规则，如果线段的一个端点在上（下，左，右）区域，裁剪规则，如果线段的一个端点在上（下，左，右）区域，则此线段与上边框求交，然后删去边框以外的部分。则此线段与上边框求交，然后删去边框以外的部分。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪 设线段两个段端点为设线段两个段端点为P1(x1,y1)、P2(x2,y2)，执行裁剪计算共，执行裁剪计算共4步，步，步骤如下：步骤如下： 1) 对线段两端点对线段两端点P1,P2分别进行区域编码，记为：分别进行区域编码，记为： C1(P1)=( a1, b1, c1, d1 ) C2(P2)=( a2, b2, c2, d2 )其中其中ai, bi, ci, di取值域为取值域为1或或0。例如：例如：if ( x1y1，则，则P1与与P组合为新线段，否则组合为新线段，否则P与与P2组合组合为新线段。返回为新线段。返回1)，重新进行裁剪计算。，重新进行裁剪计算。if(b1 or b2=1)，求线段与窗口下边直线（，求线段与窗口下边直线（y=bottom）的交点。）的交点。if(c1 or c2=1)，求线段与窗口右边直线（，求线段与窗口右边直线（x=right）的交点。）的交点。if(d1 or d2=1)，求线段与窗口左边直线（，求线段与窗口左边直线（x=left）的交点。）的交点。 产生交点后，去除窗口外部分得到新线段。然后立即回到第产生交点后，去除窗口外部分得到新线段。然后立即回到第1步开始对新形成的线段进行再次裁剪。步开始对新形成的线段进行再次裁剪。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪交点的计算按下面公式交点的计算按下面公式 因为窗口边界都是平行于坐标轴的直线，所以与线段交点的因为窗口边界都是平行于坐标轴的直线，所以与线段交点的计算只需要计算一个分量。线段与平行于计算只需要计算一个分量。线段与平行于x轴的直线计算交点，轴的直线计算交点，此时此时y=yw为已知，只需按第一式计算为已知，只需按第一式计算xw。线段与平行于。线段与平行于y轴的直轴的直线计算交点，此时线计算交点，此时x=xw为已知，只需按第二式计算为已知，只需按第二式计算yw。11w1212w11w1212wy)xx(xxyyyx)yy(yyxxx2022/5/115.1 图形的窗口裁剪图形的窗口裁剪例：裁剪窗口例：裁剪窗口(0,0)(1,1)对线段对线段(-0.2,0) (0.5,1.2)进行裁剪进行裁剪1) 对两个端点进行编码对两个端点进行编码 C1=0001，C2=1000。（上下右左）（上下右左）2) 编码是否全为编码是否全为0？不是。？不是。3) 某一位置编码是否全为某一位置编码是否全为1？不是。？不是。线段和窗口有交点。线段和窗口有交点。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪4) 第第1位有一个是位有一个是1？是。？是。 计算与窗口边界交点，上边界计算与窗口边界交点，上边界yw=1，计算，计算xw xw = (0.5-(-0.2)/(1.2-0)*(1-0)+(-0.2)=0.38 根据对根据对y的判断，新线段为的判断，新线段为(-0.2,0)(0.38,1)，对这个线段重新，对这个线段重新进行计算。进行计算。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪5) 进行编码进行编码C1=0001，C2=0000。6) 编码是否全为编码是否全为0？不是。？不是。7) 某一位置编码是否全为某一位置编码是否全为1？不是。？不是。8) 第第1位有一个是位有一个是1？不是；？不是； 第第2位有一个是位有一个是1？不是；？不是； 第第3位有一个是位有一个是1？不是；？不是； 第第4位有一个是位有一个是1？是？是 与左边界有交点。与左边界有交点。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪计算交点计算交点 xw=0 yw= (1.2-0) / (0.5-(-0.2)*(0-(-0.2)+0=0.34根据对根据对x的判断，新线段为的判断，新线段为(0,0.34)(0.38,1)，对这个线段重新进，对这个线段重新进行计算。行计算。9) 进行编码进行编码C1=0000，C2=0000。10) 编码是否全为编码是否全为0？是。？是。 不再需要进行裁剪，不再需要进行裁剪， 保存此线段即裁剪结果。保存此线段即裁剪结果。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪5.1.3 多边形裁剪：多边形裁剪：Sutherland-Hodgeman逐边裁剪算法逐边裁剪算法 通过计算去除多边形在窗口外的部分。与直线不同，多边形通过计算去除多边形在窗口外的部分。与直线不同，多边形裁剪后必须仍是多边形。裁剪后必须仍是多边形。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪逐边裁剪算法的基本思想如下：逐边裁剪算法的基本思想如下： 将多边形的顶点按顺序排列，多边形的边就成为多个有向线将多边形的顶点按顺序排列，多边形的边就成为多个有向线段组成的折线序列，每个线段都具有方向，是有向线段。对其段组成的折线序列，每个线段都具有方向，是有向线段。对其中的一段，起点表示为中的一段，起点表示为S，终点表示为，终点表示为P。 裁剪过程中重新生成的点的序列，裁剪过程中重新生成的点的序列，裁剪结果就是新产生的顶点序列构裁剪结果就是新产生的顶点序列构成新多边形。成新多边形。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪裁剪过程：裁剪过程：1) 取出窗口的一个边界线。取出窗口的一个边界线。该边界线把平面分成两个部分：该边界线把平面分成两个部分：内侧、外侧。内侧、外侧。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪2) 定义一个数组定义一个数组C，并置为空。，并置为空。3) 依次取出多边形的每个线段，逐个进行下面的计算。依次取出多边形的每个线段，逐个进行下面的计算。当前线段当前线段SP与窗口边界的位置关系有下面四种情况：与窗口边界的位置关系有下面四种情况：1、S在外侧，在外侧，P在内侧。计算交点在内侧。计算交点Q，将，将Q、P保存到数组保存到数组C。2、S、P均在内侧，将当点均在内侧，将当点P保保 存到数组存到数组C。3、S在内侧，在内侧，P在外侧。计算交在外侧。计算交 点点Q，将，将Q保存到数组保存到数组C。4、S、P均在外侧，没有点被保均在外侧，没有点被保 存。存。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪4) 取出窗口的下一个边界线，回到取出窗口的下一个边界线，回到1)重新进行。重新进行。 每个窗口边界对每个线段都做了上述计算后，最后的数组每个窗口边界对每个线段都做了上述计算后，最后的数组C中保存的点，依次取出连接成新多边形，即为裁剪结果。中保存的点，依次取出连接成新多边形，即为裁剪结果。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪例：多边形由例：多边形由4个点个点P1,P2, P3,P4构成构成（1）取窗口左边界线。）取窗口左边界线。（2）逐个取出线段计算）逐个取出线段计算 对于对于P1P2，判断，判断P1在外在外 部，部，P2在内部。计算交在内部。计算交 点点Q1，记录下，记录下Q1、P2。 对于对于P2P3，全在内部，记录下，全在内部，记录下P3。 对于对于P3P4，判断全在内部，记录下，判断全在内部，记录下P4 对于对于P4P1，判断，判断P4内部，内部，P1外部。求交点外部。求交点Q2，记录下，记录下Q2。 记录下的点序列记录下的点序列Q1、P2、P3、P4、Q2构成被左边界裁剪后的构成被左边界裁剪后的多边形。接着对窗口的其它边界，重复上述步骤。多边形。接着对窗口的其它边界，重复上述步骤。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪例：例：OpenGL的裁剪的裁剪 点元：如果点在裁剪体外部，那么这个点将被扔掉。点元：如果点在裁剪体外部，那么这个点将被扔掉。 线元：如果整个线在裁剪体外部，那么将被扔掉。如果线的线元：如果整个线在裁剪体外部，那么将被扔掉。如果线的部分在裁剪体外部，那么将被裁减生成新的线段，新生成的顶部分在裁剪体外部，那么将被裁减生成新的线段，新生成的顶点是与裁剪面的交点。点是与裁剪面的交点。 三角形图元：三角形被裁减到裁剪体内部，新生成的顶点组三角形图元：三角形被裁减到裁剪体内部，新生成的顶点组成新的三角形。三角形被裁减之后有可能重新生成多个三角形。成新的三角形。三角形被裁减之后有可能重新生成多个三角形。 裁剪之后将生成新的顶点，对于新顶点的裁剪之后将生成新的顶点，对于新顶点的PerVertex值（前一值（前一个顶点着色器传过来的值，包括坐标、颜色、纹理坐标）将根个顶点着色器传过来的值，包括坐标、颜色、纹理坐标）将根据线性插值生成。据线性插值生成。2022/5/115.1 图形的窗口裁剪图形的窗口裁剪例：例：OpenGL的裁剪的裁剪 2022/5/115.2 图形光栅化图形光栅化 光栅是指显示器上的颜色点，像素是指一个抽象的颜色点。光栅是指显示器上的颜色点，像素是指一个抽象的颜色点。因此光栅化也可以称为像素化。因此光栅化也可以称为像素化。 几何图形最终要转化为像素点，以便在显示器上显示或保存几何图形最终要转化为像素点，以便在显示器上显示或保存为图像。所谓光栅化就是寻找适当的光栅点，在这些点上着色为图像。所谓光栅化就是寻找适当的光栅点，在这些点上着色后能最接近于所要显示的几何图形。后能最接近于所要显示的几何图形。 光栅的特点是点的坐标都为整数值，光栅化的结果就是将图光栅的特点是点的坐标都为整数值，光栅化的结果就是将图形离散成具有整数坐标的点集。形离散成具有整数坐标的点集。2022/5/115.2 图形光栅化图形光栅化5.2.1 点的光栅化点的光栅化 对一个点对一个点P(x,y)，如果，如果x,y不是整数，需要进行取整处理不是整数，需要进行取整处理 x = int( x+0.5 )，y = int( y+0.5 ) 这样得到的就是最接近这样得到的就是最接近(x,y)的整数点。的整数点。2022/5/115.2 图形光栅化图形光栅化5.2.2 线段的光栅化：线段的光栅化：DDA算法算法 设线段为设线段为(x1,y1), (x2,y2)，坐标值均为整数，坐标值均为整数，且且x2-x10，x2-x1y2-y1。 斜率斜率m= (y2-y1)/(x2-x1)，0m1。 若其中已经存在一个光栅化后的若其中已经存在一个光栅化后的 点点(xi,yi)，则它右侧的点为，则它右侧的点为my)xx(myy1xxii1ii1ii1i2022/5/115.2 图形光栅化图形光栅化按上式进行光栅化，是一个循环过程，初值为按上式进行光栅化，是一个循环过程，初值为每次循环开始时给每次循环开始时给x坐标加坐标加1，直到，直到x=x211yy,xx2022/5/115.2 图形光栅化图形光栅化例：模拟线段例：模拟线段(0,0),(5,2)的计算过程的计算过程 m = 2/5 = 0.4 初始值为初始值为x0=0,y0=0，接下来循环计算得，接下来循环计算得 x1=1,y1=0.4 x2=2,y2=0.8 x3=3,y3=1.2 x4=4,y4=1.6 x5=5,y5=2。 循环完成后再将非整数坐标四舍五入转为整数，此线段光栅循环完成后再将非整数坐标四舍五入转为整数，此线段光栅化结果共得到化结果共得到6个光栅点，为个光栅点，为(0,0),(1,0),(2,1),(3,1),(4,2),(5,2)。是。是最接近线段的光栅点。最接近线段的光栅点。2022/5/115.2 图形光栅化图形光栅化上面的循环公式是每次为上面的循环公式是每次为x值加值加1，计算，计算y值。如果线段不在这个值。如果线段不在这个方向上，即不满足给出的条件，就不能这样循环。下面给出其方向上，即不满足给出的条件，就不能这样循环。下面给出其它情况时的循环公式它情况时的循环公式当当x0, |x|y|, 当当y0, |x|y|, 当当x|y|, 当当y0, |x|y|, 练习：推导后三个式子。练习：推导后三个式子。myy, 1xxi1ii1im/1xx, 1yyi1ii1imyy, 1xxi1ii1im/1xx, 1yyi1ii1i2022/5/115.2 图形光栅化图形光栅化5.2.3 线段的光栅化：线段的光栅化：Bresenham算法算法 Bresenham算法增加了一个判别参数，实现了全整数计算，算法增加了一个判别参数，实现了全整数计算，每步计算只包括一个正负判别和一个整数加法，比每步计算只包括一个正负判别和一个整数加法，比DDA算法效算法效率更高，而且适合硬件实现。率更高，而且适合硬件实现。 设线段为设线段为 (x1,y1),(x2,y2) 且满足且满足 x2-x10 y2-y10 m= (y2-y1)/(x2-x1)1。2022/5/115.2 图形光栅化图形光栅化线段的直线方程为线段的直线方程为xymyyy,xxxbxmy12122022/5/115.2 图形光栅化图形光栅化现设现设x=xi时已经已有光栅化计算结果，为时已经已有光栅化计算结果，为(xi,yi)，接着要计算接着要计算xi+1时的时的y。 y是直线上的点，它的整数点是直线上的点，它的整数点要从要从yi或或yi+1中选择一个。中选择一个。bxmy1xx1ii1i2022/5/115.2 图形光栅化图形光栅化计算距离计算距离d1-d2可以作为选择可以作为选择y的判别量，的判别量， d1-d20，y离离yi+1近近iii1y)b) 1x(m(yyd)b) 1x(m(1yy) 1y(diii21b2y2) 1x(m2ddii212022/5/115.2 图形光栅化图形光栅化令令则则且在线段左端点且在线段左端点x1,y1 时有时有)dd(xe21i) 1b2(xyx2) 1x(y2)dd(xeii21ixy2xb2xbx2xy2y2xy2) 1b2(x)bxxy(x2y2xy2) 1b2(xyx2)1x(y2e1111111?2022/5/115.2 图形光栅化图形光栅化两个两个ei的差的差所以所以e的意义：的意义：（1）在第一个点）在第一个点(x1,y1)为已知为已知（2）后续可以递推得到，取决于前一个点对）后续可以递推得到，取决于前一个点对y的选择的选择（3） e是下一个光栅点选择的判别量是下一个光栅点选择的判别量)yy(x2y2) 1b2(xyx2) 1x(y2) 1b2(xyx2)2x(y2eei1iii1iii1i)yy(x2y2eei1ii1i2022/5/115.2 图形光栅化图形光栅化Bresenham光栅化算法步骤：光栅化算法步骤：（1） (x1,y1)， (x2,y2)为已知为已知（2）计算）计算（3）循环计算）循环计算 若若ei 0 若若ei 0 xstep = 1 else xstep = -1if y0 ystep = 1 else ystep = -1if (|x|y|) x=x1, y=y1, d=2|y|-|x| for (i=x1;ix2;i+) x=x+xstep if(d0) d=d+2|y|-2|x| y=y+ystep else d=d+2|y|if (|y|x|)x=x1, y=y1, d=2|x|-|y| for (i=y1;iy2;i+) y=y+ystep if(d0) d=d+2|x|-2|y| x=x+xstep else d=d+2|x|2022/5/11习题习题1 对线段对线段(2,4)(-9,13) ，按，按DDA算法进行光栅化模拟计算。算法进行光栅化模拟计算。2 分别对线段分别对线段(2,4)(-9,13)和线段和线段(1,1)(8,5)， 按按Bresenham算法进算法进行光栅化模拟计算。行光栅化模拟计算。3 推导推导y0, |x|y|时时DDA算法的计算公式。算法的计算公式。4 推导推导 时的时的Bresenham公式。公式。5 分别对以下线段对窗口分别对以下线段对窗口(-3,1)-(2,6)进行裁剪计算。进行裁剪计算。 (-4,7),(-2,10) (-4,2),(-1,7) (-1,5),(3,8) (-2,3),(1,2) (1,-2),(3,3)6 总结编码裁剪算法的原理及特点总结编码裁剪算法的原理及特点xy, 0y, 0 x