3二维图形生成技术.ppt

* 第三章 二维图形生成技术 3.1 直线图形 一. 生成直线的 DDA 算法 无论是光栅扫描显示器还是绘图机，都可以看成有一个网格(离散单元组成的矩阵)存在，对显示器来说每一个像素就是一个网格点，对绘图机来说笔每走一步的终点也可以看成是一个网格的结点。 在光栅扫描显示器上表示一条 直线，就是要用最靠近直线的一 些网格点来代表这一直线。 这个网格就构成屏幕和绘图机 纸张的一个坐标系，相邻两个网 点的距离取为1，每个网格点的坐 标均取整数。 p1 p2 假设 直线的起点坐标为P1 (x1,y1)，终点坐标为P2 (x2,y2) x方向的增量为 △x＝x2－x1 ；y方向上增量为 △y＝y2－y1 直线的斜率为 k＝△y／△x 当 △x＞△y 时，让 x 从 x1 到 x2 变化，每步递增 1， 那么，x 的变化可以表示为 xi+1＝xi＋1 y 的变化可以表示为 yi+1＝yi＋k 用上式可求得图中直线 P1P2 和 y 方向网格线的交点，但显示时要用象素点(图中的网格结点)来表示，所以要用舍入的办法耒找到最靠近交点处的象素点，并用其来表示直线段。 这个方法称之为数字微分分析法，简称DDA。 算法描述如下： int x1，y1，x2，y2； int x； float dx，dy，k，y； dx＝x2 － x1 ； dy＝y2 － y1 ； k＝dy／dx ； x＝x1 ； y＝y1 ； for (x＝x1；x＜＝x2；x＋＋) { putpixel (x，(int)y，pixelcolor ) ； y＝y＋k ； } 该算法仅适用于｜k｜≤1 的情况，而当｜k｜＞1时，则需将 x 和 y 的位置交换。 void dda_line(int xa,int ya,int xb,int yb,int c) { float delta_x,delta_y,x,y; int dx,dy,steps,k; dx=xb-xa; dy=yb-ya; if(abs(dx)abs(dy)) steps=abs(dx); else steps=abs(dy); delta_x=float(dx)/float(steps); delta_y=float(dy)/float(steps); x=xa; y=ya; putpixel(x,y,c); for(k=1;k=steps;k++) {x=x+delta_x; y=y+delta_y; putpixel(x,y,c);} } 二. 生成直线的 Bresenham 算法 基本原理 二. 生成直线的 Bresenham 算法 设 k＝△y／△x ， 先讨论 0≤k≤1的情况： 若以屏幕上x方向的象素点作为横坐标，则有 xi+1－xi＝1 而 yi+1＝yi＋k(xi+1－xi)＝yi＋k (1) 设 b 点是直线上的点，其坐标是(xi+1，yi+1)，显然，该点只能用屏幕上的象素点c 或 d 来表示。 设 a 为c、d 的中点，若 b 在 a 的上面则应取 d，否则应取 c。 关键问题： (1) 如何判断 b是在 a 的上面还是 下面，设置一个标志变量 e ； (2) 如何建立标志变量 e 的递推公式。 xi Xi+1 Yi Yi+1 Yi+1 b a c d 设 e (xi+1)＝yi+1－yi′－0.5 (2) 若b在a的下面，则有 e (xi+1)0 若b在a的上面，则有 e (xi+1)0 由图中可知：当e (xi+1)≥0时 y′i+1＝yi′＋1 e (xi+1) 0时 y′i+1＝yi＇ 递推： 由(2)、(3)式可得： e (xi+2)＝yi+2－y′i+1－0.5＝yi+1＋k－y′i+1－0.5