图形学--大题.pptxVIP

2.1直线的生成2.1.2 中点画线算法 消除DDA算法中的浮点运算（浮点数取整运算，不利于硬件实现； DDA算法，效率低）。 中点画线算法条件：同DDA算法斜 率：直线段的隐式方程（(x0,y0)(x1,y1)两端点） F(x,y)=ax+by+c=0 式中 a=y0-y1,b=x1-x0,c=x0y1-x1y0 。中点画线算法直线的正负划分性直线上方点：F(X，Y)＞0直线下方的点F(X，Y)＜0中点画线算法问题：判断距直线最近的下一个象素点 构造判别式：di=F(M)=F(Xp+1,Yp+0.5) 由di＞0，＜0可判定下一个象素，P2P1P中点画线算法要判定再下一个象素，分两种情形考虑： 1）若di0，取右下方象素P1，再下一个象素判定，由： di= a(Xp+1)+b(Yp+0.5)+c di+1=F(Xp+2,Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c = di +a， di的增量是aP2P1P中点画线算法要判定再下一个象素，分两种情形考虑： 2）若di≤0，取右上方象素P2，再下一个象素，由：di+1=F(Xp+2,Yp+1.5)= a(Xp+1)+b(Yp+0.5)+c+a+b=di+a+b di的增量为a+bP2P1P中点画线算法d的初始值d0=F(x0+1,y0+0.5) =a(x0+1)+b(y0+0.5)+c = F(x0,y0)+a+0.5b因(x0,y0)在直线上，F(x0，y0)=0,所以，d0=a+0.5b中点画线算法d的增量都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。算法中只有整数变量，不含乘除法，可用硬件实现。中点画线算法a=y0-y1,b=x1-x0, Δy=y1-y0, Δx=x1-x0,d0=2(a+0.5b)=2a+b=Δx -2Δyd0 di+1= di+2a= di-2Δy (取下点) d≤0 di+1= di+2(a+b)= di-2(Δy- Δx)（取上点）中点画线算法例：设第一象限直线OE，起点为(2，1)，终点坐标为(12，9)试用中点画线算法计算，并作出走步轨迹图。 初始决策参数的计算为: 计算后继决策参数的增量为： 绘制初始点（x0,y0）=(2,1),并从决策参数中确定沿线路径的后继像素位置为：中点画线算法kdk(xk+1,yk+1)kdk(xk+1,yk+1)01234-6-22-14-10（3，2）（4，3）（5，3）（6，4）（7，5）56789-6-22-14-10（8，6）（9，7）（10，7）（11，8）（12，9）中点画线算法有效边表扫描线填充算法（1）基本概念边的连贯性：某条边与当前扫描线相交，很可能与下一条扫描线也相交。扫描线的连贯性：当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或类似。区间连贯性：同一区间上的像素很可能取同一颜色属性。有效边表扫描线填充算法（1）基本概念边表（Edge Table ET）：用来存放多边形边的信息的表，包括除水平边以外的所有边。有效边（Active Edge）:与当前扫描线相交的多边形的边，也称为活性边。有效边表（AET）：将有效边与扫描线交点x坐标递增顺序存放在一个链表中，此链表就是有效边表。有效边表扫描线填充算法（2）有效边表的构造有效边表的每个结点：Ymax：所交边的最高扫描线的Y值。X：所交边在当前扫描线中的x值。△x：从当前扫描线到下条扫描线之间的x增量。 next：指向下一节点。ymax x|ymin △x nextxi+1,yi+1xi,yi有效边表扫描线填充算法（2）有效边表的构造△x：从当前扫描线到下条扫描线之间的x增量。设该边的直线方程为：ax+by+c=0，当前扫描线及下一条扫描线与边的交点分别为(xi,yi)、(xi+1,yi+1)，则：? axi+byi+c=0? axi+1+byi+1+c=0?? 由于yi+1=yi+1? 所以? 其中△x=-b/a =dx/dy为常数 有效边表扫描线填充算法为了方便有效边表的建立和更新，构造边表：（1）构造一个纵向链表，长度为多边形所占有的最大扫描线数。（2）按照边的下端点y坐标对非水平边进行分类的指针数组,下端点y坐标值等于i的边属于第i类。绘图窗口中有多少条扫描线，ET就分为多少类。（3）同一类中的边按x值（x值相等的，按△x值）递增的顺序排列。多边形的裁剪逐边裁剪（Sutherland-Hodgman裁剪法）双边裁剪（Weiler-Atherton裁剪法）逐边裁剪 将多边形边界作为一个整体，并根据窗口的每一条边进行裁剪。逐边裁剪算法：每次用窗口的一条边界对要裁剪的多边形进行裁剪，把落在窗口外部区域的图形去掉，只保留窗口内部区域的图形，并把它作为下一次待裁