计算机图形学各种算法VC版本.docVIP

基本图形的生成 注：本文档主要解释了构建图形的主要操作步骤以及操作重点。 1.1 直线 数学上，理想的直线是由无数个点构成的集合没有宽度。在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，显示器绘制直线通常所说直线的扫描转换直线光栅化。 由于一图中可包含成千上万条直线，所以要求绘制算法应尽可能快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法Bresenham 算法 DDA（数值微分法如图1-1所示，已知过端点的直线段；直线斜率为从的左端点开始，向右端点步进画线，步长=1个素，计算相应的坐标；取素点?, round（y）]?作为当前点的坐标。计算当即当x每递增1，y递增k即直线斜率注意上述分析的算法仅适用于k(1的情形。在这种情况下，x每增加1, y最多增加1。当时，必须把x，y地位互换，y每增加1，x相应增加1/k。.1.2 生成直线的中点画线法中点画线法的基本原理画直线段的过程中，当前素点为，一个像素点有两种选择点1或2。M为1与2中点，Q为理想直线与=Xp+1垂线的交点。当M在Q的下方，则P2应为下一个像素点；M在Q的上方，应取P1为下一点。 中点画线法的实现令直线段L[?p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0点与L的关系F(x, y)=0； 在直线上方，F(x, y)0； 在直线下方，F(x, y)0。 把M代入F（x, y）判断的符号，Q点在中M的上方还是下方。构造判别式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c当d??0，L(Q点)在M上方，取P2为下一个像素当d??0，L(Q点)在M下方，取P1为下一个像素 当d=0，选P1或P2均可，取P1为下一个像素 其中d是xp, yp的线性函数。 Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个素取右边点还是右上点。 (x1, y1)到终点(x2, y2)。直线可表示为方程y?=?mx+b，其中b=y1–mx1， m?=?(y2–y1)/(x2–x1)=dy/dx；此处的讨论直线方向限于第一象限，如图1-3所示，当直线光栅化时，x每次都增加1个单元，设x素为xi，yi。下一个素的列坐标为xi+1，行坐标为yi递增1为yi+1y与yi及yi+1的距离d1及d2的大小而定。计算公式为 y = m(xi + 1) + b （1.1） d1 = y – yi （1.2） d2=yi+1–y （1.3） 如果d1–d20，则yi+1=yi+1，否则yi+1=yi。 式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式两边，并以Pi=(d1–d2)，dx代入上述等式，得 Pi = 2xidy–2yidx+2dy+(2b–1)dx （1.4） d1–d2是用以判断符号的误差。由于在第一象限，dx总大于0，所以Pi仍旧可以用做判断符号的误差。Pi+1为 Pi+1 = Pi+2dy–2(yi+1–yi)dx （1.5） 求误差的初值P1，可将x1、y1和b代入式（1.4）中的xi、yi，而得到 P1 = 2dy–dx 综述上面的推导，第一象限内的直线Bresenham算法思想如下： （1）画点（x1, y1），dx=x2–x1，dy=y2–y1，计算误差初值P1=2dy–dx，i=1。 （2）求直线的下一点位置xi+1 = xi + 1，如果Pi0，则yi+1=yi+1，否则yi+1=yi。 （3）画点(xi+1, yi+1)。 （4）求下一个误差Pi+1，如果Pi0，则Pi+1=Pi+2dy–2dx，否则Pi+1=Pi+2dy。 （5）i=i+1；如果idx+1则转步骤（2）；否则结束操作。 1.1.4 程序设计 1．程序设计功能说明 为编程实现上述算法，本程序利用最基本的绘制元素（如点、直线等），绘制图形。如图1-4所示，为程序运行主界面，通过选择菜单及下拉菜单的各功能项分别完成各种对应算法的图形绘制。 图1-4 基本图形生成的程序运行界面 2．创建工程名称为“基本图形的生成”单文档应用程序框架 （1）启动VC，选择“文件”|“新建”菜单命令，并在弹出的新建对话框中单击“工程”标签。 （2）选择MFC AppWizard(exe)