第三章 输出图元 - 中国科学技术大学.ppt

1、第三章 输出图元,Output Primitives,图形输出的概念,算法：几何图形 点阵设备与 画线设备 点阵设备：显示器光栅矩阵（XY) ，如何生成 划线设备：笔式绘图机 坐标系 世界坐标系 设备坐标系 本章主要介绍 二维图元的算法 点 直线 圆 曲线填充域,变换,画线算法 实质：求二端点之间的 所有的近似点 y = m * x + b 由于m不一定是整数， 所以就要求哪一个 像素最接近直线,b,x,y,增量法,y=mx+b m为斜率，b为截距，设二端点分别为（x1,y1),( x2,y2) y=y2- y1 ， x =x2-x1 m= y/ x 对于任意的y, y=mx 则x=y/m 讨

2、论：m1 由y定x的偏转电压,DDA算法Digital 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的增量 若取

3、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,算法： d0=2*a+b di0 (取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 直接计算，计算量大，点间距不一致 圆的八对称性 考虑点（

4、0，r）右下方的1/8圆周 中点圆算法 算法思想： f(x,y)=x2+y2-r2 M（xk+1,yk-0.5） pk =f(M）=f(xk+1,yk-0.5)= (xk+1)2+(yk-0.5)2- r2 pk+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

5、=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,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

6、y=yc+rysin 平移坐标轴，使椭圆中心位于原点 x=rxcos y=rysin 角度DDA算法,(xc,yc),rx,ry,中点画椭圆算法,椭圆方程 ry2x2+ rx2y2=rx2ry2 设f(x,y)= ry2x2+ rx2y2 rx2ry2 x,y方向的切矢量相等 2ry2x=2rx2y，此处的切线斜率为-1，以此方法将椭圆划分为2区域 当2ry2x2rx2y时，移出区域1 区域1:2ry2x2rx2y,每次x走步，判别y是否走步 区域2:2ry2x2rx2y,每次y走步，判别x是否走步 f(x,y)为决策函数 0 (x,y) 在椭圆外,中点画椭圆算法（续）,区域1：x每次都走步

7、中点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

8、= 2 rx2ry 之后x的增量2 ry2； y的增量或为-2 rx2或为0， 当2ry2x2rx2y时，移出区域1 P10=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

9、)+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)图元,对一封闭区域用某种颜色

10、或图案进行填充； 区域边界：规则的、不规则的曲线边界、封闭折线 一般用多边形填充；曲面可用平面逼近 曲线边界,多边形填充区域,多边形的分类 凸（convex)多边形 （边的延长线） 凹（concave）多边形 退化(degenerate)多边形 共线、共点,180,180,凹多边形识别,多边形的边向量叉积，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） 求叉积 E

11、1 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,凸多边形分割成三角形集,将多边形三个连续的顶点定义为一个新三角形； 删去中间一个顶点，组成新多边形 重复1，2；直到只剩下三个顶点，即为最后一个三角形。,内外测试法,判别区域内外 奇偶规则 由任意一点P向对象引射线，统计沿射线与各边的交点，若为奇数，则P为内部点，若为偶数， P为外部点。 非零绕数规则 多边形按逆时针方向定义，点P引射线同上，沿

12、射线方向，多边形边从右到左通过射线时，绕数+1,反之，绕数-1，若绕数非零，则P为内部点，否则，P为外部点。 特例：上图，二法不同的结果。,非零绕数算法的实现,P点出发的向量定义为u,边向量定义为E, 若uE, +z方向，绕数+1，-z方向，绕数-1。 点积代叉积：设u(ux,uy),与u正交的向量u+为(-uy,ux), 若u+ E 绕数+1，否则，绕数-1。 定义两区域的并、交、差 并 正边界方向，绕数为正的点； 交 正边界方向，绕数1的点; 差 A-B,A正边界方向，B负边界方向，绕数为正的点,多边形表面polygon surfaces,顶点表：vertex V1：x1,y1,z1 V2

13、：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,平面方程 equation of plane surface Ax+By+Cz+D=0三点确定一个面时 1 y1 z1 x1 1 z1 A= 1

14、 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 填充一个二维的 网格图案,研究生高级计算机图形学课题设计 写一篇三维造型方面的论文，要求不少于3000字，独立完成。内容可以是以下几方面： 绘制一个具有真实感的三维场景，其中至少含有2个三维物体。可以使用Open