图形学-实验二.doc

贵州大学实验报告学院：计算机科学与信息学院 专业：计科 班级：计科081 姓名杨茜学号080806110125实验组实验时间2011-4-6指导教师张建成绩实验项目名称实验二 实现圆、椭圆的中点算法。实验目的通过本实验，使学生了解并掌握在光栅显示系统中圆、椭圆的生成和显示算法，进一步熟悉相关开发平台。实验要求优化后的算法：二次差分法可任意指定圆心坐标。书写实验报告：给出算法描述：包括理论、算法和数据结构；根据算法和数据结构：编制源程序；给出实验数据和结果（参照例题）；报告以说明问题为原则，不必写得过长；请勿在报告中贴大段源程序，对于一些较为重要的算法，可以摘抄在报告中；将自己的算法同MFC/OpenGL的函数进行比较实验原理F(x,y)0F(x,y)0，(x,y)在园外；F(x,y)0，(x,y)在园内；F(x,y)=0，(x,y)在园上。设(xi,yi)为已确定的象素坐标，则下一个象素只能是正右方的E点或右下方的SE点。xi，yiMESE设M是E和SE的中点，M=(xi+1,yi-0.5)：如F(M)0，则M在园外，说明SE距离圆弧更近,下一点取右下方SE点；如F(M)=0，则M在园上，下一点取E点或SE点。构造判别式：d=F(M)=F(xi+1,yi-0.5)=(xi+1)2+(yi-0.5)2-R2（1）d=0,中点在圆外,选右下方的SE点,再下一个象素的判别式为：dnew=F(xi+2,yi-1.5) =(xi+2)2+(yi-1.5)2-R2=d+(2xi+3)+(- yi+2)=d+2(xi-yi)+5沿右下方向,d的增量为：（3）d初始值为：d0=F(1,R-0.5) =1+(R-0.5)2-R2 =1.25-R在d的运算中包含了浮点数的运算，为了消除d中的浮点数运算，分析上述算法，可以看出，算法中取作用的只是d的符号，所以可设另一整数变量h：h=d-0.25所以：初始化运算d0 = 1.25R 对应于:h0=1-R判别式 d0 对应于 h-0.25又因为：h的初值h0为整数，运算过程中的分量也为整数(E和SE为整数)，故h始终为整数。所以可用h代替d作判断。其初始值：h0=d0-0.25=(1.25-R)-0.25=1-R有以下对应关系：h0 d0 d0h=0 d=0算法分析：二阶差分法：利用二阶差分降低增量的阶数二阶差分(降低增量的阶数,用差分法消除中点算法中的乘法运算)。中点算法中：1，如在现有点p(xp,yp)上，对p+1点选择了E(xp+1,yp)点(1)增量E二阶差分增量为：(2)增量SE二阶差分增量为：2，如在现有点p(xp,yp)上，对p+1点选择了SE(xp+1,yp-1)点(1)增量E二阶差分增量为：(2)增量SE二阶差分增量为：xydDED SEx=x+1 ( d0)y-1d + DSEDE+2DSE+4算法步骤：1，依据上一次迭代中的d的符号来选择现在点E或SE (d0=1-R)；2，用在上一次迭代计算的和来计算新的d；3，用移到新象素点的二次差分值，并用它来更新和移到下一点。二、椭圆中点算法yxba算法原理：中点算法可以推广到一般二次曲线如椭圆。xyp(x,y)上下中心在原点的椭圆方程为：隐函数的形式为：a=b时，该方程表示的是圆。椭圆具有四对称性，可只考虑第一象限的椭圆弧。椭圆上任一点(x,y)处的法向量为：如在p点法线两分量相等,则p点将椭圆第一象限分成两部份，上半部份法向量在y方向的分量比x方向的大，在下半部份相反。在p点：在当前中点处，法向量（2b2 (Xp+1)，2a2 (Yp-0.5)的y分量比x分量大，即：b2 (Xp+1) a2 (Yp-0.5)而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分。BMTPi(xi,yi)与圆弧中点算法类似：确定一个象素Pi后，接着在下两个候选象素的中点计算一个判别式dF（M）的值，由判别式的符号确定更近的点。1.先讨论椭圆弧的上半部分(令x=1)设Pi(xi，yi)已确定，则下一对待选像素的中点是：M(xi+1,yi-0.5)对初始点（0,b)，第一个中点为(1,b-0.5)，则：(1)当d=0(取B点)时，下一点(i+1)点的坐标为(xi+1，Yi-1)，为确定i+2点取的下一个中点M的坐标为：(xi+2，Yi -1.5) LMRPi(xi, yi)2.在每一次迭代中都要判断椭圆是否已从上半部进入了下半部，如果b2x=a2y，则椭圆进入下半部份，此时令y=1，且：(1)若d=0,取正下方像素L，则3.终止条件为：y=0MidpointEllipe(a,b, color)int a,b,color; int x,y; float d1,d2; x = 0; y = b; d1 = b*b +a*a*(-b+0.25); putpixel(x,y,color); while( b*b*(x+1) a*a*(y-0.5) if (d10) if (d2 0) d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x+; y-； else d2 += a*a*(-2*y+3); y-; putpixel(x,y,color); /下部分实验环境硬件平台：PC、Windows XP软件：Microsoft Visual Studio 2010实验步骤1. 掌握算法原理；2. 依据算法，编写源程序并进行调试；3. 对运行结果进行保存与分析；4. 把源程序以文件的形式提交；5. 按格式书写实验报告。实验内容实现圆、椭圆的中点算法。实验结果1、 选择菜单项圆的中点画圆2、 选择菜单项椭圆的中点画椭圆3、 画出圆和椭圆的结果如下：4、可以改变相应的半径画出不同的圆和椭圆实验总结1 通过这次实验使我对于生成圆和椭圆的过程有了清晰的认识，同时对于各种圆和椭圆生成算法和思想也有了很好的理解，2 算法比较：（1） 中点算法中含有大量的乘法运算，所