基本光栅图形生成算法.pptVIP

基本光栅图形生成算法*第1页，共41页，星期日，2025年，2月5日在计算机上绘图的一般方法用现有绘图软件系统画图\Word中的图文编辑工具\AutoCAD\Photoshop等大型绘图软件用绘图软件包OpenGL就是一个典型的、已经被接受的国际工业标准的图形软件包。Java3D用操作系统的绘图功能如Windows中Win32API中就提供了基本的绘图功能第2页，共41页，星期日，2025年，2月5日在数学上，理想的直线是一条由无穷多个无限小的连续的点组成。在光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。直线生成算法第3页，共41页，星期日，2025年，2月5日DDA算法描述设(xs,ys)和(xe,ye)分别为直线的起点坐标和终点坐标，则：可通过计算由x方向的增量引起y的改变来生成直线。由，得到：同样，可通过计算由y方向的增量引起x的改变来生成直线。由，得到：直线生成算法—DDA算法第4页，共41页，星期日，2025年，2月5日DDA算法基本思想选定和中较大者作为步进方向，在此方向上每次增加（或者减少）一个像素，然后计算另一个方向上增量的值，把每次计算出的值经取整后顺序输出到显示器，则可以得到光栅化的直线。DDA算法特点算法简单，实现容易，但计算量较大，每产生一个像素需要取整运算，此外算法还要除法运算，因此生成直线的速度较慢。直线生成算法—DDA算法第5页，共41页，星期日，2025年，2月5日例题1：已知起点A(16,-5)和终点B(-4,8)，用DDA法在A和B之间生成一段直线。第一步：计算初值：，，由于，所以选定x轴方向作为步进方向；第二步：在x轴方向上每次的变化量为，则y轴方向的变化量为第三步：循环计算点的坐标，并取整显示：直线生成算法—DDA算法第6页，共41页，星期日，2025年，2月5日Bresenham算法基本思想令，直线方程：，其中为起点坐标；考虑，则x方向增加1，y方向增加m，由起点(xs,ys)可求得直线上的点(xi，yi)，i=1,2,3,…,其中x1=xs,y1=ys；用坐标为(xi，round(yi))的象素来表示直线上的点，其中round(yi)表示最靠近y的整数；直线生成算法—Bresenham算法第7页，共41页，星期日，2025年，2月5日Bresenham算法基本思想令yi,r=round(yi),用坐标为(xi，yi,r)的象素来表示直线上的点，第i+1个点只能在C和D中选取。令误差项当时，，即选C点当时，，即选D点直线生成算法—Bresenham算法第8页，共41页，星期日，2025年，2月5日Bresenham算法基本思想的递推公式=初始值直线生成算法—Bresenham算法第9页，共41页，星期日，2025年，2月5日实际上，误差项的数值大小与算法的执行没有关系，相关的只是的符号，因而我们可以改变的定义，在两边同乘以，可消除除法运算：令初始如果，则:如果，则:直线生成算法—Bresenham算法第10页，共41页，星期日，2025年，2月5日Bresenham算法基本思想上述算法扩展到任一八分圆坐标空间图，从而形成一般的Bresenham算法。下图是各象限的判断条件。直线生成算法—Bresenham算法第11页，共41页，星期日，2025年，2月5日例题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加1ixiyi12010x加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加