《图形学课件cs3章节》由会员分享，可在线阅读，更多相关《图形学课件cs3章节（47页珍藏版）》请在金锄头文库上搜索。
1、第三章 基本图形的扫描转换,扫描转换的基本概念 绘制像素点函数Setpixel的用法 直线和圆的中点Bresenham原理 直线反走样原理,本章内容,3.1 直线的扫描转换 3.2 圆的扫描转换 3.3 椭圆的扫描转换（略讲） 3.6 本章小结 3.7 习题,显示器是由离散像素组成的矩阵，在绘制具有连续性质的直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。当光栅化按照扫描线的顺序进行时，它被称为扫描转换。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示之，即区域填充。光栅化和扫描转换
2、是光栅图形学的基本问题，其算法的好坏对系统的效率有直接的关系。,用一系列的象素点来逼近直线,具体实现时，在离散位置上对线段取样，并且按扫描线顺序，在每个取样位置上决定距线段最近的像素。,高分辨率,低分辨率,3.1 直线的扫描转换,在数学上，直线是没有宽度的、由无数个点构成的集合。对直线进行光栅化就是在显示器所给定的有限个像素矩阵中，确定最佳逼近于该直线的一组像素。 对于水平线、垂直线和45线，选择哪些光栅元素是显而易见的，而对于其它方向的直线，像素的选择较为困难。,解决的问题： 给定直线两端点 ，画出该直线。,直线方程：,从起点到终点，x每次增加(或减少)1，用直线方程计算对应的y值，再用Op
3、enGL绘点函数输出该像素。 复杂度：乘法+加法+取整,上述方法称为直线绘制基本算法，缺点：每步都需要一个浮点乘法运算和一个四舍五入运算，所以效率太低。由于一个图中可以包含成千上万条直线，所以要求绘制算法应尽可能的快。,常用算法： 1）数值微分法（DDA，Digital Differential Analyzer） 2）Bresenham算法。,数值微分(DDA)法,给定两个端点P0(x0,y0)和P1(x1,y1)，线段的斜率k和截距b为：,画线过程从x的左端点x0开始，向x右端点步进，步长=1(个像素)，计算相应的y坐标：y=kx+b，取像素点(x, round(y)作为当前点的坐标。 计
4、算 yi+1= kxi+1+b=k(xi+ x)+b = kxi+b+kx = yi+kx 当x =1时 yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)。,DDA算法基本原理,复杂度：加法+取整,DDA算法就是一个增量算法。 增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。,作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。,Bresenham算法,Bresenham算法1965年提出，基本原理是借助于一个误差量(直线与当前实际绘制像素点的距离) 来确定下一个
5、像素点的位置。算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查误差量的符号，就可以确定该下一列的像素位置。,理想直线将平面划分成三个区域：对于直线上的点，F(x，y)0；对于直线上方的点，F（x，y）0；对于直线下方的点，F（x，y）0。假设直线的斜率为0k1，则，所以确定x方向为主位移方向。按照Bresenham原理，x方向上每次加1，y方向上加不加1取决于中点偏差判别式的值。 假定直线的当前点是P（xi，yi），沿主位移x方向走一步，下一点只能在Pu（x i1，y i1）和Pd（x i1，yi）两点中选取。Pu和Pd的中点为M（x i1，y i0.5），如图3-2所示。显然，若中点
6、M在理想直线的下方，则Pu点距离直线近，点亮Pu；否则点亮 Pd。,F（x，y）0,F（x，y）=0,F（x，y）0,图3-2 直线中点Bresenham算法原理,Pu（x i+1，y i+1）,M（x i+1，y i+0.5）,P（xi，yi）,Pd（x i+1，yi）,3.1.2 构造中点偏差判别式,从P（xi，yi）点走第一步后，为了进行下一像素点的选取，需将Pu和Pd的中点M（x i1，y i0.5）代入隐函数方程，构造中点偏差判别式d。,（3-2）,3.1.3 递推公式,图3-3 中点偏差判别式的递推,1.中点偏差判别式的递推公式 在主位移x方向上已走一步的情况下，现在考虑沿主位移方
7、向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素，如图3-3所示，分两种情况讨论。,(1)当d0时,当d0时,（3-5）,（3-4）,直线的起点坐标为P0（x0，y0），x为主位移方向。因此，第一个中点是（x 01，y 00.5），相应的d的初始值为：,其中，因为（x 0，y 0）在直线上，所以,则：,（3-6）,2.中点偏差判别式的初始值,0k1时Bresenham算法的算法步骤为： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、d=0.5-k、x=x0、y=y0； 3.绘制点(x,y)。判断d的符号； 若d0，则(x,y)更新为(
8、x+1,y+1)，d更新为d+1-k； 否则(x,y)更新为(x+1,y)，d更新为d-k。 4.当直线没有画完时，重复步骤3。否则结束。,改进：用2dx代替d 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、d=x-2y、x=x0、y=y0。 3.绘制点(x,y)。判断d的符号。 若d0，则(x,y)更新为(x+1,y+1)，d更新为 d+2x-2y； 否则(x,y)更新为(x+1,y), d更新为d-2y。 4.当直线没有画完时，重复步骤3。否则结束。 程序,例题:,例：Line: P0(0, 0), P1(5,2) x y d 0 0 1 1 0 -3
9、 2 1 3 3 1 -1 4 2 5 5 2 1,课堂作业,用Bresenhan算法扫描转换从像素点(1,1)到(8,5)的线段时的像素位置。,x = 7 y = 4 初始d= x-2y= -1 2x-2y= 6 -2y=-8 x y d 1 1 -1 2 2 5 3 2 -3 4 3 3 5 3 -5 6 4 1 7 4 -7 8 5 -1,3.2 圆的扫描转换,3.2.1 算法原理 3.2.2 构造中点偏差判别式 3.2.3 递推公式,解决的问题： 绘出圆心在原点，半径为整数R的圆x2+y2=R2,(y,x),(-y,x),(-x,y),(-x,-y),(-y,-x),(y,-x),(x
10、,-y),八分法画圆:,解决问题：,本节主要讲解仅包含加减操作的顺时针绘制1/8圆的中点Bresenham算法原理。,理想圆,F（x，y）0,F（x，y）=0,F（x，y）0,图3-4 圆的扫描转换,3.2.1 算法原理,圆心在原点、半径为R的圆方程的隐函数表达式为：,圆将平面划分成三个区域：对于圆上的点，F(x，y)0；对于圆外的点，F（x，y）0；对于圆内的点，F（x，y）0，如图3-4所示。,（3-7）,事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。因为AC段圆弧和CB段圆弧以对称轴xy完全对称，如图3-6所示，所以可以用四条对称轴x0，y0， x y， xy把圆分成8等份
11、。只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。假定第一象限内的任意点为P（x，y），可以顺时针确定另外7个点： P（y，x）P（y，x）,P（x, y ） ,P（x，y），P（y，x），P（y，x），P（x，y）。,P（-y，x）,P（-y，-x）,x=-y,P（-x，-y）,P（x，-y）,P（y，-x）,P（y，x）,P（x，y）,P（-x，y）,x=y,x=0,y=0,图3-6 圆的对称性,本算法只考虑图3-6所示阴影部分的45圆弧，即第一象限内,的1/8圆弧。,（0，R）到（,从前述讨论知道，x方向为主位移方 向，因此中点Bresenham算法的原
12、理简化为：x方向上每次加1，y方向上减不减1取决于中点偏差判别式的值。,）顺时针确定最佳逼近于该段圆弧的像素点集。,此时中点Bresenham算法要从,假定圆当前点是P（xi，yi）,下一点只能在Pu（x i1，y i）和Pd（x i1，yi1）中选取，如图3-7所示。Pu和Pd的中点为M（x i1，y i0.5）显然，若M点在理想圆弧的下方，则Pu点离圆弧近，点亮Pu；否则应点亮Pd。,Pu（x i1，y i）,y,P（xi，yi）,M（x i+1，y i0.5）,Pd（x i1，yi1）,图3-7 圆中点Bresenham算法原理,x,3.2.2 构造中点偏差判别式,从P（xi，yi）开始
13、，为了进行下一像素点的选取，需将Pu和Pd的中点M（x i1，y i0.5）代入隐函数，构造中点偏差判别式：,（3-9）,当d0时，中点M在圆外，下一像素点应点亮Pd，即y方向退一步；当d0时，中点M在圆上， Pu、Pd和圆的距离相等，点亮Pu或Pd均可，约定取Pd。,因此，,（3-10）,3.2.3 递推公式,1.中点偏差判别式的递推公式 现在如果考虑主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步应该点亮的像素，如图3-8所示，分两种情况讨论。,当d0时，下一步的中点坐标为：M（x i2，y i0.5）。,所以下一步中点偏差判别式为：,（3-11）,当d0时，下一步的中点
14、坐标为：M（x i2，y i1.5）。,所以下一步中点偏差判别式为：,P（xi，yi）,M（x i1，y i0.5）,M（x i+2，y i0.5）,P（xi，yi）,M（x i1，y i0.5）,M（x i2，y i1.5）,d0,d0,图3-8 中点偏差判别式的递推,2.中点偏差判别式的初始值 圆的起点为P0（0，R），x为主位移方向。因此，第一个中点是（1，R-0.5），对应的d的初始值为：,（3-13）,（3-12）,3.4 反走样,用离散量表示连续量引起的失真，就叫做走样（Liasing）。,走样现象： 一是光栅图形产生的阶梯形 一是图形中包含相对微小的物体时，这些物体在静态图形中容
15、易被丢弃或忽略，在动画序列中时隐时现，产生闪烁,反走样,用于减少或消除这种效果的技术，称为反走样（antialiasing）。 反走样技术主要分为两类： 1）硬件技术：通过提高显示器的分辨率 2）软件技术：通过改进软件算法来实现,3.6 本小结,本章主要讲解了直线、圆和椭圆的中点Bresenham算法原理以及直线的反走样技术。直线、圆和椭圆作为图形基本图元，其生成算法的优劣对整个图形系统的效率至关重要。在像素级生成算法中，中点Bresenham 算法避免了复杂运算，使用了最小的计算量，使单点基本图形生成算法已无优化的余地，已经成为使用最广泛的扫描转换算法。走样是直线光栅化扫描转换的必然结果，只
16、能减轻，不可避免，如何设计直线的反走样算法是计算机图形学的前沿研究课题。,3.7 习题,1.将中点Bresenham画直线算法推广到能绘制任意斜率直线，并编程实现之 。,2.逐个访问像素点绘制直线的算法是今后真实感图形绘制的基础算法。要求将中点Bresenham直线算法修改为起点闭区间，终点开区间的可绘制任意斜率直线的算法，即要达到VC+的MoveTo和LineTo语句绘制直线的效果。,3.圆的方程为,，试针对该方程编程实现直角坐标画,圆算法。,4.圆的极坐标方程为,，试按照该方程编程实现,极坐标画圆算法。,5.计算起点坐标为（0,0），终点坐标为（12,7）直线的Bresenham算法每一步坐标值及中点偏
