《计算机图形学第三章讲义》由会员分享，可在线阅读，更多相关《计算机图形学第三章讲义（80页珍藏版）》请在金锄头文库上搜索。
1、第三章 输出图元,点绘制 画线算法 圆生成算法 多边形,第三章 输出图元,图元的概念,最基本的图形元素/图形输出原语类型 图形一级元素：点、线 图形二级元素：弧、圆、多边形、曲线、字符 其他：.,3.1 点和直线,点 直线,点的绘制,光栅扫描系统：帧缓冲器对应位置设为1 其他元素的绘制都在以点为基础产生。,直线的绘制,光栅扫描系统 屏幕位置以整数值表示; 以线路径上的离散点来显示线段 显示的线段具有阶梯效果,直线的绘制,计算机绘制的直线是由一系列与该直线最近的像素绘制而成 理论直线与计算机绘制的直线之间总有一定的偏差 只能尽量减少偏差 偏差取决于屏幕光栅(分辨率)和光点的运动方向,阶梯效果的直
2、线,3.2 画线算法,问题 画线算法 DDA算法 Bresenham算法,3.2 画线算法,问题 已知直线的两个端点P1(x1, y1)，P2(x2, y2) 求直线的中间各点,3.2 画线算法,已知：P1(x1,y1)，P2(x2,y2) 直线的笛卡尔斜率截距方程y = m*x + bm = (y2y1)/(x2x1)b = y1m*x1y= m* x x = y/m,3.2 画线算法,对于模拟显示设备，方程y、 x是决定偏转电压变化的基础。 当|m|1， y 可以设置为正比于一垂直偏转电压， x则可以根据公式计算。,直线绘制要求,直 端点准确 亮度均匀 速度 属性,求直线中间的各个像素点,
3、1. DDA算法,数字微分分析仪 思想：在一个坐标轴上以单位间隔对线段取样，则另一个坐标轴以常数m或1/m变化，从而获得线段上各像素点,直线中间的各个像素点沿x轴取样,|m| 1,DDA算法公式,直线斜率满足|m|1时，取y方向为单位步长 递推公式为：yk+1=yk1xk+1=xk1/m,画直线的DDA算法可表示为: 若|m|1:xk+1=xk+1,yk+1=yk+m ;xaxb若|m|1:yk+1=yk+1, xk+1=xk+1/m ;yayb,DDA算法,DDA算法 举例,已知直线的两个端点P1(20,10)，P2(30,18)，用DDA算法使该线段光栅化。 解：dx = 10; dy =
4、 8; 循环次数：steps = 10;沿X轴单位取样：x_in= 1Y按斜率变化： y_in = 0.8,DDA算法 举例,DDA算法 举例,DDA算法的C实现 #define Round(a) (int)(a + 0.5) void lineDDA(int xa, int ya, int xb, int yb) int dx = xb - xa, dy = yb - ya, steps, k;float xIncrement, yIncrement, x=xa, y=ya;if (abs(dx) abs(dy) steps = abs(dx);else steps = abs(dy);,x
5、Increment = dx/(float) steps;yIncrement = dy/(float) steps;setpixel(Round(x), Round(y), RED);for(k=0;ksteps;k+)x += xIncrement;y += yIncrement;setpixel(Round(x), Round(y), RED); ,DDA算法 评价,比直接使用公式 y=m*x+b快 ，没有用乘法 运算仍然耗时 设置增量的除法运算 取整操作 浮点 较长线段的误差积累,2. Bresenham算法,由Bresenham提出的一种精确而有效的光栅线段生成算法，可用于直线、圆(
6、圆弧)和其它曲线的生成 思想 算法公式推导 算法描述 举例,Bresenham 算法思想,从(10,10)像素开始，绘制0m1直线的屏幕网格,思想：只用整数计算寻找最接近实际直线的整数坐标,Bresenham 算法思想,Bresenham 算法公式推导,假定：0m1， 已知(xk, yk)，求下一点(xk+1, yk+1)(xk+1, yk+1)的两种可能：(xk+1, yk) 和 (xk+1, yk+1)，其中xk+1 xk+1,Bresenham 算法公式推导,推导：设两点与理想直线距离分别为d1、d2 d1y - ykm*xk+1+b - yk m*(xk+1)+b- ykd2 yk+1
7、 - yyk+1-m*(xk+1)-bd1 - d22m(xk+1)-2yk+2b-1代入m= y / x，,Bresenham 算法公式推导,d1-d2 = 2*y / x(xk+1)-2yk+2b-1方程两边同乘以xx(d1-d2) = 2 y* xk+2 y - 2 x*yk+ x(2b-1) 引入决策参数Pk表示相对距离，其值为Pk = x (d1-d2)2y*xk - 2x*yk + C其中C = 2y + x*(2b-1),Bresenham 算法公式推导,推论：Pk 1，交换x和y方向的规则，y单位步长移动，计算x 从任何端点开始绘制像素 水平线、垂直线和对角线,3.3 圆生成算
8、法,圆的属性中点画圆算法,3.3.1 圆的特性,圆的方程(xxc)2(yyc)2r2xxc r cosyyc r sin,圆的对称性,直接基于圆的方程绘圆,圆的标准方程(xxc)2(yyc)2r2y= yc sqrt(r2-(x-xc)2) 圆的极坐标参数方程xxcr cosyycr sin,圆的对称性,3.3.2 中点画圆算法,思想 判断公式 算法描述 程序实现 举例,3.3.2 中点画圆算法,思想 中点在圆边界内，选(x+1, y) 中点在圆边界外，选(x+1, y-1),定义圆函数 fcircle (x, y)=x2+y2-r2pk = f(xk+1, yk-0.5) = (xk+1)2
9、+(yk-0.5)2-r2如果 pk 0，选择 (xk+1, yk)pk 0，选择(xk+1, yk-1),中点画圆算法公式推导,pk+1 = f(xk+1+1, yk+1-0.5) = (xk+1+1)2+(yk+1-0.5)2-r2 pk+1 = pk+2(xk+1)+(yk+12-yk2)-(yk+1-yk)+1p0 = 5/4 r = 1- r,中点画圆算法公式推导,r取整,中点画圆算法的步骤,1) 输入圆半径r和圆心(xc, yc)，获得(x0, y0) = (0, r) 2) 计算P0 = 1 - r; 3) 在每个xk位置，测试计算下一个点Pk = 0， (xk+1, yk -1
10、)根据公式计算Pk+1； 4) 确定对称点； 5) 重复步骤3，直至x y,中点画圆算法举例 圆半径r=10,P0= 1-10=-9 P1= -9+2*1+1=-6 P2= -6+2*2+1=-1 P3= -1+2*3+1=6 P4= 6+2*(4-9)+1=-3 P5= -3+2*5+1=8 P6= 8+2*(6-8)+1=5,中点画圆算法举例 圆半径r=10,圆的标准方程包括乘法和平方根运算 圆的极坐标参数方程包含乘法和三角运算 Bresenham算法以决策参数的增量计算为基础，仅包括简单的整数处理 中点方法更易应用于其他圆锥曲线，沿任何圆锥曲线所确定的像素位置，其误差限制在像素分段的1/
11、2以内,不同算法的比较,3.4 多边形,多边形分类、识别与分割凹多边形 内-外测试 多边形表 前向面与后向面,3.4.1 多边形分类,(1) 有封闭折线边界且无交叉边的平面图形 凹多边形 凸多边形,(2) 识别凹多边形,叉积法 延长线法,凹多边形判定叉积法,绕多边形的周长计算相邻边向量的叉乘 如果各叉积有正、有负，则为凹多边形；,多边形凹凸性判定叉积法,(2) 识别凹多边形,延长线法：延长每边，观察：如果顶点分布在延长线两侧，则为凹多边形,按逆时针方向计算多边形的边向量的叉积 并记录叉积结果Z分量的符号。 如果Z分量变为负值，则多边形为凹多边形，可以沿叉乘向量对中的第一条边的延长线将多边形分解
12、开,(3) 分割凹多边形,分割凹多边形的向量方法,1,2,6,5,4,3,3.4.2 内-外测试,目标: 确认对象的内部区域 方法 奇偶规则 非零环绕数规则,(1) 奇偶规则,从任意位置P作不经过顶点的射线 计算射线穿过的多边形边的数目 奇数：内部点 偶数：外部点,(1) 奇偶规则,A,B,C,D,E,P,A,B,C,D,E,P,交点数=偶数（包括0） 点在多边形之外,交点数=奇数 点在多边形之内,奇偶规则举例,自相交多边形的顶点分别为ABCDEFG,奇偶规则举例,(2) 非零环绕数规则,统计多边形边以逆时针方向环绕某一特定点的次数，称为环绕数 环绕数初始为零 从位置P作不经过顶点的射线 多边
13、形边从右至左穿过射线，加1 多边形边从左至右穿过射线，减1 非零：内部点 零：外部点,(2) 非零环绕数规则举例,自相交多边形的顶点分别为ABCDEFG,多边表数据表分为两组，进行组织： 几何表：顶点坐标和用来标识多边形表面空间方向的参数 属性表：指明物体透明度及表面反射度的参数和纹理特征,3.4.3 多边形表,几何数据的组织结构_三表法 顶点表 边表 多边形面表,3.4.3 多边形表,三表可简化成两表(顶点表和多边形表)：但这种方法不方便，某些边可能要画二次 只用一张边表，但由于每个多边形中的每个顶点的坐标值都需要列出，因此坐标信息有重复，而且边信息也肯定由多边形表中的顶点重复地构造,3.4
14、.3 多边形表,为了加快信息的存取，可将边表扩充成包括指向多边形表面表的指针，这样两多边形的公共边可以很快地标识 在明暗处理时，跨越一边的两多边形之间平滑过渡的绘制程序特别有利。 类似地，可扩充顶点表以可从顶点指引到相应的边,E1: V1, V2, S1 E2: V2, V3, S1 E3: V3, V1, S1, S2 E4: V3, V4, S2 E5: V4, V5, S2 E6: V5, V1, S2,平面方程： Ax + By + Cz + D = 0A、B、C、D是描述平面和空间特征的常数,平面是曲面的特例，在图形学中有重要作用，曲面可由小平面来近似，许多算法是基于平面的。,3.4.4 前向面与后向面,向着对象内部的一侧称为后向面 可见或朝外的一侧称为前向面,3.4.4 前向面与后向面,点(x, y, z)与平面的位置关系 Ax + By + Cz + D 0 (x, y, z)在平面上 Ax + By + Cz + D 0 (x, y, z)在平面前方,
