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

第三章输出图元OutputPrimitives图形输出的概念•算法：几何图形点阵设备与画线设备点阵设备：显示器光栅矩阵（XY)，如何生成划线设备：笔式绘图机•坐标系世界坐标系设备坐标系本章主要介绍二维图元的算法点直线圆曲线填充域●●●●●●变换•画线算法实质：求二端点之间的所有的近似点y=m*x+b由于m不一定是整数，所以就要求哪一个像素最接近直线bxy●●●●●●增量法•y=mx+bm为斜率，b为截距，设二端点分别为（x1,y1),(x2,y2)∆y=y2-y1，∆x=x2-x1m=∆y/∆x对于任意的δy,δy=mδx则δx=δy/m讨论：︱m︱1由δx定δy的偏转电压︱m︱1由δy定δx的偏转电压DDA算法DigitalDifferentialAnalyzer•y=mx+bm为斜率，b为截距，设二端点分别为（x1,y1),(x2,y2)∆y=m∆x•若0m≤1,设∆x＝1，则xk+1=xk+1,yk+1=yk+m(取整）•若m1，设∆y＝1，则yk+1=yk+1xk+1=xk+1/m,•以上推导是基于自左向右划线，若自右向左划线，若0m≤1可设∆x＝－1yk+1=yk－m若m1，∆y＝－1，xk+1=xk－1/m,•若m0,分|m|1和|m|1两种情况讨论之。•程序示例中点划线算法•线段二端点（x0,y0),(x1,y1);m1,P(xp,yp)已定M为p1,p2的中点；M（xp+1，yp+0.5）M在Q的下方，应取P2（xp+1，yp+1）M在Q的上方，应取P1（xp+1，yp）考查一次函数F(x,y)=ax+by+ca=y0-y1b=x1-x0,c=x0y1-x1y0对任一点（x,y）,若F(x,y)=0，点(x,y)在直线上;F(x,y)0，点(x,y)在直线上方;F(x,y)0，点(x,y)在直线下方;令d=F(M)=a(xp+1)+b(yp+0.5)+cd0,M在直线的下方，取P2点(只与d的符号有关）d0,M在直线的上方，取P1点○○P(xp,yp)QP1P2M·●M1M2●中点划线算法（续）•求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.di≧0(取P1),xi+1=xi+1,yi+1=yi,di+1=di+2adi0(取P2),xi+1=xi+1,yi+1=yi+1,di+1=di+2(a+b)3.重复2，直到xi+1≧x1.斜率|m|1,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)+1if(pk0)yk+1=ykxk+1=xk+1pk+1=pk+2(xk+1)+1=pk+2xk+1+1if(pk=0)yk+1=yk-1xk+1=xk+1pk+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(ifrisaninteger)ykyk-1xkxk+1Mxk+2f中点画圆算法步骤1.输入（xc，yc），r,画第一个点（0，r),p0=1-r2.if(pk0)yk+1=ykxk+1=xk+1pk+1=pk+2xk+1+13.if(pk=0)yk+1=yk-1xk+1=xk+1pk+1=pk+2xk+1-2yk+1+14.确定其他七个八分圆中的对称点5.平移x=x+xcy=y+yc；画点6.重复2到5，直至x≧y中点画圆算法例题•r=10,圆心（0，0）,画（0，10）p0=1-10=-90•椭圆生成算法•椭圆的方程•参数方程表示x=xc+rxcosθy=yc+rysinθ•平移坐标轴，使椭圆中心位于原点x=rxcosθy=rysinθ•角度DDA算法(xc,yc)rxry2222()()1ccxyxxxyrrθ中点画椭圆算法•椭圆方程ry2x2+rx2y2=rx2ry2设f(x,y)=ry2x2+rx2y2－rx2ry2•x,y方向的切矢量相等2ry2x=2rx2y，此处的切线斜率为-1，以此方法将椭圆划分为2区域当2ry2x≧2rx2y时，移出区域1•区域1:2ry2x＜2rx2y,每次x走步，判别y是否走步•区域2:2ry2x≧2rx2y,每次y走步，判别x是否走步•f(x,y)为决策函数0(x,y)在椭圆内f(x,y)=0(x,y)在椭圆上0(x,y)在椭圆外22yfrxx22xfryy中点画椭圆算法（续）•区域1：x每次都走步中点m(xk+1,yk-0.5),判别函数P1k=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2P1k≦0,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⊿=2ry2xk+1+ry2-2rx2yk+1中点画椭圆算法（续）•初始时（0，ry）2ry2x=0;2rx2y=2rx2ry之后x的增量2ry2；y的增量或为-2rx2或为0，当2ry2x≧2rx2y时，移出区域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-rx2ry2P2k≦0,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⊿=2ry2xk+1-2rx2+rx2•对②xk+1=xk⊿=-2rx2yk+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圆、椭圆B2-4AC=0抛物线0双曲线例子：A=C=1B=0，D=-2xc,E=-2yc,F=xc2+yc2-r2填充区域（fillarea)图元•对一封闭区域用某种颜色或图案进行填充；•区域边界：规则的、不规则的曲线边界、封闭折线•一般用多边形填充；曲面可用平面逼近•曲线边界多边形填充区域•多边形的分类凸（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）求叉积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）分割31210233E3E6E5E4E1E2E3E3凸多边形分割成三角形集1.将多边形三个连续的顶点定义为一个新三角形；2.删去中间一个顶点，组成新多边形3.重复1，2；直到只剩下三个顶点，即为最后一个三角形。内外测试法判别区域内外•奇偶规则由任意一点P向对象引射线，统计沿射线与各边的交点，若为奇数，则P为内部点，若为偶数，P为外部点。•非零绕数规则多边形按逆时针方向定义，点P引射线同上，沿射线方向，多边形边从右到左通过射线时，绕数+1,反之，绕数-1，若绕数非零，则P为内部点，否则，P为外部点。特例：上图，二法不同的结果。非零绕数算法的实现•P点出发的向量定义为u,边向量定义为E,若u×E,+z方向，绕数+1，-z方向，绕数-1。•点积代叉积：设u(ux,uy),与u正交的向量u+为(-uy,ux),若u+•E绕数+1，否则，绕数-1。定义两区域的并、交、差并正边界方向，绕数为正的点；交正边界方向，绕数1的点;差A-B,A正边界方向，B负边界方向，绕数为正的点多边形表面polygonsurfaces•顶点表：vertexV1：x1,y1,z1V2：x2,y2,z2V3：x3,y3,z3V4：x4,y4,z4V5：x5,y5,z5•边表：edgeE1：V1,V2E2：V2,V3E3：V1,V3E4：V3,V4E5：V4,V5E6：V5,V1•面表：surfaceS1：E1,E2,E3S2：E3,E4,E5,E6四点以上有可能不共面V1V2V3V4V5E1E6E2E3E4E5•平面方程equationofplanesurfaceAx+By+Cz+D=0三点确定一个面时1y1z1x11z1A=1y2z2B=x21z21y3z3x31z3x1y11x1y1z1C=x2y21D=-x2y2z2x3y31x3y3z3•法向量(A，B，C)平面内外侧判定：Ax+By+Cz+D＜0内侧Ax+By+Cz+D＞0外侧已知平面上三点v1,v2,v3,计算法向量N•N=(v2-v1)×（v3-v1)•平面方程的向量形式N•P=-D填充函数单元阵列•填充函数FillArea(n,WcVertices）•单元阵列CellArray填充一个二维的网格图案研究生高级计算机图形学课题设计1.写一篇三维造型方面的论文，要求不少于3000字，独立完成。内容可以是以下几方面：2.绘制一个具有真实感的三维场景，其中至少含有2个三维物体。可以使用OpenGL或其他函数库，要求独立完成从建模、坐标变换到消隐算法、光照模型、面绘制算法、纹理映射的全部过程。3.计算机图形学理论或算法的研究。如：曲线、曲面拟合算法；并行面绘制算法；特定物体表面的纹理映射算法。4.分形几何造型的研究。如：分形树、分形山、树木、花草、云、瀑布等。5.科学计算的可视化。可将计算数据、物理、化学现象或其他自然现象的观察数据进行三维空间的可视化。6.CAD或其他应用研究。7.图形、图像、动画方面的研究EndofChapter3