《【教学课件】第三章输出图元.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第三章输出图元.ppt（32页珍藏版）》请在三一办公上搜索。
1、第三章 输出图元,Output Primitives,图形输出的概念,算法：几何图形 点阵设备与 画线设备点阵设备：显示器光栅矩阵（XY)，如何生成 划线设备：笔式绘图机 坐标系 世界坐标系 设备坐标系 本章主要介绍二维图元的算法点 直线 圆 曲线填充域,变换,画线算法 实质：求二端点之间的所有的近似点 y=m*x+b由于m不一定是整数，所以就要求哪一个像素最接近直线,b,x,y,增量法,y=mx+bm为斜率，b为截距，设二端点分别为（x1,y1),(x2,y2)y=y2-y1，x=x2-x1 m=y/x 对于任意的y,y=mx 则x=y/m讨论：m1 由y定x的偏转电压,DDA算法Digit
2、al Differential Analyzer,y=mx+b m为斜率，b为截距，设二端点分别为（x1,y1),(x2,y2)y=m x若01，设y1，则 yk+1=yk+1 xk+1=xk+1/m,以上推导是基于自左向右划线，若自右向左划线，若01，y1，xk+1=xk1/m,若m1 两种情况讨论之。程序示例,中点划线算法,线段二端点（x0,y0),(x1,y1);m0，点(x,y)在直线上方;F(x,y)0,M在直线的上方，取P1点,P(xp,yp),Q,P1,P2,M,M1,M2,中点划线算法（续）,求d的增量 若取P1点，d1=F(xp+2，yp+0.5)=a(xp+2)+b(yp+
3、0.5)+c=d+a 若取P2点，d2=F(xp+2，yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b初始时：d0=F(x0+1，y0+0.5)=F(x0，y0)+a+0.5b=a+0.5b以2d代d,算法：d0=2*a+bdi0(取P1),xi+1=xi+1,yi+1=yi,di+1=di+2a di1中点取法 例题P1(0,0)P2(5,2),M,圆的位图,中点画圆算法,圆的特征（x-xc)2+（y-yc)2=r2 直接计算，计算量大，点间距不一致圆的八对称性 考虑点（0，r）右下方的1/8圆周中点圆算法 算法思想：f(x,y)=x2+y2-r2M（xk+1,yk-0.5
4、）pk=f(M）=f(xk+1,yk-0.5)=(xk+1)2+(yk-0.5)2-r2pk+1=f(xk+1+1,yk+1-0.5)=(xk+1+1)2+(yk+1-0.5)2-r2=pk+2(xk+1)+(yk+12-yk2)-(yk+1-yk)+1 if(pk=0)yk+1=yk-1 xk+1=xk+1 pk+1=pk+2xk+1+1-2yk+1=pk+2xk+1-2yk+1+1(2xk+1=2xk+2;2yk+1=2yk-2)p0=f(1,r-0.5)=1+(r-0.5)2-r2=1.25-r=1-r(if r is an integer),yk,yk-1,xk,xk+1,M,xk+2
5、,f,中点画圆算法步骤,输入（xc，yc），r,画第一个点（0，r),p0=1-r if(pk=0)yk+1=yk-1 xk+1=xk+1 pk+1=pk+2xk+1-2yk+1+1确定其他七个八分圆中的对称点平移 x=x+xc y=y+yc；画点重复2到5，直至xy,中点画圆算法例题,r=10,圆心（0，0）,画（0，10）p0=1-10=-90,椭圆生成算法,椭圆的方程参数方程表示 x=xc+rxcos y=yc+rysin平移坐标轴，使椭圆中心位于原点 x=rxcos y=rysin角度DDA算法,(xc,yc),rx,ry,中点画椭圆算法,椭圆方程 ry2x2+rx2y2=rx2ry2
6、 设f(x,y)=ry2x2+rx2y2 rx2ry2x,y方向的切矢量相等 2ry2x=2rx2y，此处的切线斜率为-1，以此方法将椭圆划分为2区域 当2ry2x2rx2y时，移出区域1区域1:2ry2x2rx2y,每次x走步，判别y是否走步区域2:2ry2x2rx2y,每次y走步，判别x是否走步 f(x,y)为决策函数 0(x,y)在椭圆外,中点画椭圆算法（续）,区域1：x每次都走步 中点m(xk+1,yk-0.5),判别函数 P1k=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2 P1k0,m在椭圆内，选(xk+1,yk)P1k0,m在椭圆外，选(xk+1,yk-1)对 P
7、1k+1=ry2(xk+1+1)2+rx2(yk+1-0.5)2-rx2ry2=P1k+1-P1k=2ry2(xk+1)+ry2+rx2(yk+1-0.5)2-(yk-0.5)2 yk+1=yk=2ry2(xk+1)+ry2对 yk+1=yk-1=2ry2 xk+1+ry2-2rx2yk+1,中点画椭圆算法（续）,初始时（0，ry）2 ry2x=0;2 rx2y=2 rx2ry 之后x的增量2 ry2；y的增量或为-2 rx2或为0，当2ry2x2rx2y时，移出区域1P10=f(1,ry-0.5)=ry2-rx2(ry-0.5)2-rx2ry2 区域1讨论结束区域2：中点m(xk+0.5，y
8、k-1)P2k=ry2(xk+0.5)2+rx2(yk-1)2-rx2ry2 P2k0,m在椭圆内，选(xk+1,yk-1)P2k0,m在椭圆外，选(xk,yk-1)P2k+1=ry2(xk+1+0.5)2+rx2(yk+1-1)2-rx2ry2=P2k+1-P2k=ry2(xk+1+0.5)2-(xk+0.5)2-2rx2(yk-1)+rx2,中点画椭圆算法（续）,对 xk+1=xk+1=2ry2 xk+1-2rx2+rx2 对 xk+1=xk=-2rx2 yk+1+rx2初始点取区域1的最后位置(x0,y0)P20=f(x0+0.5,y0-1)=ry2(x0+0.5)2+rx2(y0-1)
9、2-rx2ry2也可以从（rx，0）开始，逆时针方向直到区域1,例：中点画椭圆算法,圆锥曲线,一般方程 Ax2+Bxy+Cy2+Dx+Ey+F=-40(P95有错）0 双曲线例子：A=C=1 B=0，D=-2xc,E=-2yc,F=xc2+yc2-r2,填充区域（fill area)图元,对一封闭区域用某种颜色或图案进行填充；区域边界：规则的、不规则的曲线边界、封闭折线一般用多边形填充；曲面可用平面逼近曲线边界,多边形填充区域,多边形的分类 凸（convex)多边形（边的延长线）凹（concave）多边形 退化(degenerate)多边形 共线、共点,180,180,凹多边形识别,多边形的边
10、向量叉积，Z分量0步骤：多边形的向量表示求叉积判断Z分量0者，延长其一边与多边形交于一点，将多边形分为二部分,例3.4分割凹多边形,E1=（1，0，0）E2=（1，1，0）E3=（1，-1，0）E4=（0，2，0）E5=（-3，0，0）E6=（0，-2，0）求叉积E1 E2=（0，0，1）E2 E3=（0，0，-2）E3 E4=（0，0，2）E4 E5=（0，0，6）E5 E6=（0，0，6）E6 E1=（0，0，2）分割,3,1,2,1,0,2,3,3,E3,E6,E5,E4,E1,E2,E3,E3,凸多边形分割成三角形集,将多边形三个连续的顶点定义为一个新三角形；删去中间一个顶点，组成新多
11、边形重复1，2；直到只剩下三个顶点，即为最后一个三角形。,内外测试法,判别区域内外奇偶规则 由任意一点P向对象引射线，统计沿射线与各边的交点，若为奇数，则P为内部点，若为偶数，P为外部点。非零绕数规则 多边形按逆时针方向定义，点P引射线同上，沿射线方向，多边形边从右到左通过射线时，绕数+1,反之，绕数-1，若绕数非零，则P为内部点，否则，P为外部点。特例：上图，二法不同的结果。,非零绕数算法的实现,P点出发的向量定义为u,边向量定义为E,若uE,+z方向，绕数+1，-z方向，绕数-1。点积代叉积：设u(ux,uy),与u正交的向量u+为(-uy,ux),若u+E 绕数+1，否则，绕数-1。定义
12、两区域的并、交、差并 正边界方向，绕数为正的点；交 正边界方向，绕数1的点;差 A-B,A正边界方向，B负边界方向，绕数为正的点,多边形表面polygon surfaces,顶点表：vertex V1：x1,y1,z1 V2：x2,y2,z2 V3：x3,y3,z3 V4：x4,y4,z4 V5：x5,y5,z5边表：edge E1：V1,V2 E2：V2,V3 E3：V1,V3 E4：V3,V4 E5：V4,V5 E6：V5,V1面表：surface S1：E1,E2,E3 S2：E3,E4,E5,E6 四点以上有可能不共面,V1,V2,V3,V4,V5,E1,E6,E2,E3,E4,E5,
13、平面方程 equation of plane surface Ax+By+Cz+D=0三点确定一个面时 1 y1 z1 x1 1 z1 A=1 y2 z2 B=x2 1 z2 1 y3 z3 x3 1 z3 x1 y1 1 x1 y1 z1 C=x2 y2 1 D=-x2 y2 z2 x3 y3 1 x3 y3 z3,法向量(A，B，C)平面内外侧判定：Ax+By+Cz+D0 内侧 Ax+By+Cz+D0 外侧已知平面上三点v1,v2,v3,计算法向量N N=(v2-v1)（v3-v1)平面方程的向量形式 NP=-D,填充函数单元阵列,填充函数FillArea(n,WcVertices）单元阵
14、列 Cell Array 填充一个二维的网格图案,研究生高级计算机图形学课题设计写一篇三维造型方面的论文，要求不少于3000字，独立完成。内容可以是以下几方面：绘制一个具有真实感的三维场景，其中至少含有2个三维物体。可以使用OpenGL或其他函数库，要求独立完成从建模、坐标变换到消隐算法、光照模型、面绘制算法、纹理映射的全部过程。计算机图形学理论或算法的研究。如：曲线、曲面拟合算法；并行面绘制算法；特定物体表面的纹理映射算法。分形几何造型的研究。如：分形树、分形山、树木、花草、云、瀑布等。科学计算的可视化。可将计算数据、物理、化学现象或其他自然现象的观察数据进行三维空间的可视化。CAD或其他应用研究。图形、图像、动画方面的研究,End of Chapter 3,
