第二章 基本图形的生成与算法_m-新2.pptVIP

图形的生成 给定直线段的两个端点(x0,y0)和(x1,y1), 把其在光栅扫描显示器上显示出来 在数学上，理想的直线是没有宽度的，是由无数个在它上面的点构成的集合。直线可以向一个方向及其相反的方向无限延长 在图形学中研究的对象是直线段，它是一条具有一个Pixel或多个Pixel宽的直线段 在数学上，理想的直线是一条由无穷多个无限小的连续的点组成 直线的扫描转换 直线的扫描转换，就是要找出显示平面上最佳逼近理想直线的那些象素的坐标值，并将这些象素置成所要求的颜色 显示线段的速度应快： 生成直线可用软件和硬件来实现，一般情况下，硬件要比软件实现得快 数值微分法(digital differential analyzer，DDA) 是一种基于直线的微分方程来生成直线的方法 先对一个方向的坐标取单位步长的变化,然后计算另一方向坐标相应的变化值 一、直线DDA算法描述： 　设(x1，y1)和(x2，y2)分别为所求直线的起点和终点坐标，由直线的微分方程得 可通过计算由x方向的增量△x引起y的改变来生成直线 也可通过计算由y方向的增量△y引起x的改变来生成直线： 注意到公式: 因此当Dx=1时， 有yi+1=yi+m 即： Dy=m 所以:当x每递增1，y递增m(即直线斜率) 注意上述分析的算法仅适用于?m? ≤1的情形。在这种情况下，x每增加1,y最多增加1 当 ?m? ?1时，必须把x，y的位置互换，依此处理，要保证任意两点连线正确显示 数字微分(DDA)法缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现 在直线生成的算法中Bresenham算法是最有效的算法之一 该方法最初是为数字绘图仪设计的，由于适用于光栅图形显示器，所以被广泛用于直线的扫描转换与其他一些应用 Bresenham也是通过在每列像素中确定与理想直线最近的像素来进行直线的扫描转换的 算法原理：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素 如下图所示，线段的方向可分为八种，从原点出发射向八个区。由线段按图中所示的区域位置可决定xi+1和yi+1的变换规律。 根据上面的推导，圆周生成算法思想如下： ⒈ 求误差初值，p1=3?2r，i=1，画点(0, r)； ⒉ 求下一个光栅位置，其中xi+1=xi+1，如果pi0则yi+1=yi， 　　否则yi+1=yi?1； ⒊ 画点(xi+1, yi+1)； ⒋ 计算下一个误差，如果pi0则pi+1=pi+4xi+6，否则pi+1=pi+4(xi?yi)+10； ⒌ i=i+1，如果x=y则结束，否则返回步骤2。 在光栅扫描显示器中表示一个区域，仅仅画出其边界是不够的，有时还要填上一定的灰度、色彩 区域填充区域填充即给出一个区域的边界，要求对边界范围内的所有像素单元赋予指定的颜色代码。区域填充中最常用的是多边形填色 错判情况 A、B、C点处发生的错判 需要加以改进 进行求交点之前，先对每个左右顶点进行预处理，然后再求交点 方法：如下图，将Pi-1Pi , PiPi+1两条边中位于yi上方的那条边在Pi处去掉一个单位长 扫描线填色程序 程序2.3.1示出扫描线填色算法的程序。主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共count个）的x和y坐标。它调用8个子程序，彼此的调用关系如图2.3.5所示。各子程序的功能为： 各子程序的功能： 1、sort_on_bigger_y子程序的主要功能是按照输入的多边形，建立起活性边表 操作步骤是：对每条边加以判断：如非水平边则调用put_in_side_list子程序放入活性边来；如是水平边则直接画出 2、put_in_sides_list子程序的主要功能是将一条边存入活性边表之内 操作步骤是：对该边判别是否左顶点或右顶点，如果将入边之终点删去，按照y_top的大小在活性边表中找到该点的合适位置，在该边的位置中填入数据 3、update_first_and_last子程序的主要功能是刷新活性边表的first和last两根指针的所指位置，以保证指针指出激活边的范围 4、process_x_intersections子程序的主要功能是对活性边表中的激活边（即位于first和last之间的，并且△ y 不为0的边）按照x_int的大小排序 操作步骤是：从first到last，对每一根?y不为 0的边，调用sort_on_x子程序排入活性边表中合适位置 5、sort_on_x子程序主要功能是将一条边side[entry]，