【教学课件】第三章输出图元.ppt

第三章 输出图元Output Primitives图形输出的概念算法：几何图形 点阵设备与 画线设备点阵设备：显示器光栅矩阵（XY)，如何生成 划线设备：笔式绘图机 坐标系 世界坐标系 设备坐标系 本章主要介绍二维图元的算法点 直线 圆 曲线填充域 变换画线算法 实质：求二端点之间的所有的近似点 y=m*x +b由于m不一定是整数，所以就要求哪一个像素最接近直线bxy增量法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算法Digital Differential Analyzery=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,若m0,分|m|1 两种情况讨论之程序示例中点划线算法线段二端点（x0,y0),(x1,y1);m0，点(x,y)在直线上方;F(x,y)0，点(x,y)在直线下方;令d=F(M)=a(xp+1)+b(yp+0.5)+c d0,M在直线的上方，取P1点 P(xp,yp)QP1P2MM1M2中点划线算法（续）求d的增量 若取P1点，d1=F(xp+2，yp+0.5)=a(xp+2)+b(yp+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,算法：1.d0=2*a+b2.di0(取P1),xi+1=xi+1,yi+1=yi,di+1=di+2a3.di0(取P2),xi+1=xi+1,yi+1=yi+1,di+1=di+2(a+b)3.重复2，直到xi+1x1.斜率|m|1中点取法 例题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）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)ykyk-1xkxk+1Mxk+2f中点画圆算法步骤1.输入（xc，yc），r,画第一个点（0，r),p0=1-r2.if(pk=0)yk+1=yk-1 xk+1=xk+1 pk+1=pk+2xk+1-2yk+1+14.确定其他七个八分圆中的对称点5.平移 x=x+xc y=y+yc；画点6.重复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)rxry中点画椭圆算法椭圆方程 ry2x2+rx2y2=rx2ry2 设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)对 P1k+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，yk-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)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凹多边形识别多边形的边向量叉积，Z分量0步骤：多边形的向量表示求叉积判断Z分量1的点;差 A-B,A正边界方向，B负边界方向，绕数为正的点多边形表面多边形表面polygon surfacespolygon 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 四点以上有可能不共面四点以上有可能不共面V1V2V3V4V5E1E6E2E3E4E5平面方程平面方程 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）单元阵列 Cell Array 填充一个二维的网格图案 研究生高级计算机图形学课题设计研究生高级计算机图形学课题设计1.写一篇三维造型方面的论文，要求不少于3000字，独立完成。

内容可以是以下几方面：2.绘制一个具有真实感的三维场景，其中至少含有2个三维物体可以使用OpenGL或其他函数库，要求独立完成从建模、坐标变换到消隐算法、光照模型、面绘制算法、纹理映射的全部过程3.计算机图形学理论或算法的研究如：曲线、曲面拟合算法；并行面绘制算法；特定物体表面的纹理映射算法4.分形几何造型的研究如：分形树、分形山、树木、花草、云、瀑布等5.科学计算的可视化可将计算数据、物理、化学现象或其他自然现象的观察数据进行三维空间的可视化6.CAD或其他应用研究7.图形、图像、动画方面的研究End of Chapter 3。