资源描述：
《计算机图形学第3章-基本光栅图形生成算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、直线生成算法DDA方法Bresenham算法圆弧生成算法中点圆生成算法多边形的填充多边形表示方法多边形填充的扫描线算法边缘填充算法边界标志算法区域填充区域的基本概念简单种子填充算法扫描线种子填充算法光栅图形的反走样算法基本光栅图形生成算法在计算机上绘图的一般方法用现有绘图软件系统画图Word中的图文编辑工具AutoCADPhotoshop等大型绘图软件用绘图软件包OpenGL就是一个典型的、已经被接受的国际工业标准的图形软件包。Java3D用操作系统的绘图功能如Windows中Win32API中就提供了基本的绘
2、图功能在数学上，理想的直线是一条由无穷多个无限小的连续的点组成。在光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。直线生成算法DDA算法描述设(xs,ys)和(xe,ye)分别为直线的起点坐标和终点坐标，则：可通过计算由x方向的增量引起y的改变来生成直线。由，得到：同样，可通过计算由y方向的增量引起x的改变来生成直线。由，得到：直线生成算法—DDA算法DDA
3、算法基本思想选定和中较大者作为步进方向，在此方向上每次增加（或者减少）一个像素，然后计算另一个方向上增量的值，把每次计算出的值经取整后顺序输出到显示器，则可以得到光栅化的直线。DDA算法特点算法简单，实现容易，但计算量较大，每产生一个像素需要取整运算，此外算法还要除法运算，因此生成直线的速度较慢。直线生成算法—DDA算法例题1：已知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间生成一段直线。第一步：计算初值：，，由于，所以选定x轴方向作为步进方向；第二步：在x轴方向上每次的变化量为，则y轴方向的变化
4、量为第三步：循环计算点的坐标，并取整显示：直线生成算法—DDA算法Bresenham算法基本思想令，直线方程：，其中为起点坐标；考虑，则x方向增加1，y方向增加m，由起点(xs,ys)可求得直线上的点(xi，yi)，i=1,2,3,…,其中x1=xs,y1=ys；用坐标为(xi，round(yi))的象素来表示直线上的点，其中round(yi)表示最靠近y的整数；直线生成算法—Bresenham算法Bresenham算法基本思想令yi,r=round(yi),用坐标为(xi，yi,r)的象素来表示直线上的点，第i+1
5、个点只能在C和D中选取。令误差项当时，，即选C点当时，，即选D点直线生成算法—Bresenham算法Bresenham算法基本思想的递推公式=初始值直线生成算法—Bresenham算法实际上，误差项的数值大小与算法的执行没有关系，相关的只是的符号，因而我们可以改变的定义，在两边同乘以，可消除除法运算：令初始如果，则:如果，则:直线生成算法—Bresenham算法Bresenham算法基本思想上述算法扩展到任一八分圆坐标空间图，从而形成一般的Bresenham算法。下图是各象限的判断条件。直线生成算法—Bresenha
6、m算法例题2：已知起点A(20,10)和终点B(30,18)，用Bresenham法在A和B之间生成一段直线。解：Δx=10,Δy=8,斜率在0和1之间；直线生成算法—Bresenham算法ixiyi12010=2*8-10=6x加1，y加122111x加1，y加132212x加1，y不变42312x加1，y加152413x加1，y加162514x加1，y加172615x加1，y加182716x加1，y不变92816x加1，y加1102917x加1，y加1这里仅讨论圆心位于坐标原点的圆的扫描转换算法，对于圆心不在原点
7、的圆，可先用平移变换，将它的圆心平移到原点，然后进行扫描转换，最后再平移到原来的位置；圆的八分对称性中点算法生成圆圆的生成算法圆心位于原点的圆有四条对称轴x=0、y=0、y=x和y=－x，见下图。从而若已知圆弧上一点P(x，y)，就可以得到其关于四条对称轴的七个对称点，这种性质称为八分对称性。因此只要能画出八分之一的圆弧，就可以利用对称性的原理得到整个圆弧。圆的生成算法—圆的八分对称性设要显示圆的圆心在原点(0,0)，半径为R，起点在(0,R)处，终点在(,)，顺时针生成八分之一圆，利用对称性扫描转换全部圆；为了应用
8、圆的生成算法，我们定义一个圆函数：F(x,y)=任何点(x,y)的相对位置可由圆函数的符号来确定：若F(x,y)<0，点(x,y)位于圆内若F(x,y)=0，点(x,y)位于圆上若F(x,y)>0，点(x,y)位于圆外圆的生成算法—中点算法生成圆如何选取下一象素点？假定当前取点为P(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(
