第四章 基本图形生成算法

10,,111<≤??=???+=+=++m x y m m

y y x x i i i i 其中：第四章 基本图形生成算法

一、 直线的扫描转换

1． 数值微分算法

直接使用直线方程法、DDA 算法（增量算法）

优点：DDA 算法比直接用直线方程的方法快：没有浮点乘法；

缺点：求每个连续点时，需要浮点加法；加0.5舍尾取整，不利于硬件实现；表示长直线时，由于精度限制→累计误差；

2． 中点画线法

原理：1、确定与直线距离最近的点P ；2、利用点P 确定下一个点

3． Bresenham 画线算法

算法基本思想：每次迭代在增量最大方向上均走一步，其方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。

例如取X 方向为最大增量方向，则有：

算法优点：-快速增量算法；-要获得准确的数学结果，只需通过整数的加、减法和乘2运算；计算机中乘2可以容易的通过算术移位实现。 给出使用Bresenham 算法画斜率介于0到45度之间的直线所需的步骤。

-解答：

§1、计算初始值：dx=x2-x1; dy = y2 – y1; lnc1=2dy; lnc2 = 2(dy – dx)；d = lnc1-dx

§2、设置左下方的端点坐标为（x,y ）,同时将Xend 设为x 的最大值。如果dx<0,则x=x2,y=y2,Xend=x1. 如果dx>0，则x=x1,y=y1,Xend=x2;

§3、在当前（x ，y ）坐标画一个点；

§4、判断整条线段是否已经画完，如果x=Xend ，则停止；

§5、计算下一个象素的位置，如果d<0，那么d=d+lnc1，如果d>=0,则d=d+lnc2,且y=y+1;

§6、增加x:x=x+1; §7、在当前的(x,y)坐标画一个点； §8、转到步骤4；

)),(,22222r i i i i i y x x R y x R y x ，（利用隐函数方程取整??→?-==+))sin (),cos ((sin cos i i R round R round R y R x θθθθ???==利用参数方程二、 圆与椭圆的扫描转换

1、 圆的扫描转换

两种直接离散方法：

离散点 离散角度

2、 resenham 画圆算法

仅考虑圆心在原点，半径为R 的第一象限上的一段圆弧。且取（0，R ）为起点，按顺时针方向(+x, -y 方向)绘制该1/4圆弧。

算法原理 ：从当前点亮象素（x,y ）出发，按顺时针方向生成圆时，最佳逼近该圆的下一个象素只可能为H 、D 、V 三象素之一。H 、D 、V 中距圆周边界距离最小者，即为所求的象素点；H 、D 、V 三点到圆心的距离平方与圆的半径平方差，即为H 、D 、V 到圆弧距离的一种度量：为根据这些度量值可确定最佳象素点，首先，将H 、D 、V 与理想圆弧的关系进行分类。

存在以下五种情况：

1）H 、D 、V 全在圆内；

2）H 在圆外，D 、V 在圆内；

3）D 在圆上，H 在圆外，V 在圆内；

4）H 、D 在圆外，V 在圆内；

5）H 、D 、V 全在圆外。 §习题：使用Bresenham 算法扫描转换圆的步骤是什么？

§解答：

-1、设置初始变量(h,k)=圆心坐标；x=0;y=圆的半径r ；d=3-2r;

-2、测试整个圆是否已经扫描转换完。如果x>y 则停止；

-3、以中心（h,k ）为对称点，对当前的(x,y)坐标画8个圆上的点：

Plot(x+h,y+k); plot(-x+h,-y+k);plot(y+h,x+k);plot(-y+h,-x+k)

Plot(-y+h,x+k);plot(y+h,-x+k);plot(-x+h,y+k);plot(x+h,-y+k);

-4、计算下一个象素的位置，如果d<0,则d=d+4x+6,和x=x+1.如果d>=0,则d=d+4(x-y)+10、x=x+1、y=y-1. -5、转到步骤2；

§习题：当使用8路对称方法从0度到45度或90度到45度的8分圆中生成整个圆时，有些象素被设置或画了两次，这种现象成为重击。请说明如何判断重击发生？

§解答：

-在初始坐标为（r,0)或(0,r)时的位置。因为（0,r ）= （-0,r ）, （0,-r ）= （-0,-r ）, （r,0）= （r,-0）, （-r,0）= （-r,-0）;

-如果最后生成的象素在对角线上，坐标为（ar,ar ），其中a 约为0.7071,则在(ar,ar)、(-ar,ar)、(ar,-ar)、(-ar,-ar)处会发生重击；

§习题：重击除了浪费时间外还有其它坏处吗？

§解答：

-通常不会有问题；

-但是如果直接操纵输出设备，可能有问题

3、 椭圆的扫描转换

§椭圆的中点算法

-算法原理

-1、上半部分：

§M（Xi+1，Yi-0.5)

-2、下半部分：

§M（Xi+0.5，Yi-1）§注意：

-上半部分的终止判别;

-下半部分误差项的初值;

§算法步骤:

- 1.输入椭圆的长半轴a和短半轴b;

- 2.计算初始值d=b2+a2(-b+0.25)、x=0、y=b;

- 3.绘制点(x,y)及其在四分象限上的另外三个对称点;

- 4.判断d的符号。若d≤0，先将d更新为d+b2(2x+3)，再将(x, y)更新为(x+1,y)；否则将d更新为d+b2(2x+3)+a2(-2y+2)，再将(x,y)更新为(x+1,y-1);

- 5.当b2(x+1)

- 6.用上半部分计算的最后点(x,y)来计算下半部分中d的初值：

- 7.绘制点(x,y)及其在四分象限上的另外三个对称点;

- 8.判断d的符号:

§若d≤0，则先将d更新为b2(2xi+2)+a2(-2yi+3)，再将(x,y)更新为(x+1,y-1)；§否则先将d更新为d+a2(-2yi+3)，再将(x,y)更新为(x,y-1);

- 9.当y>0时，重复步骤7和8。否则结束;

三、区域填充

1、多边形域的填充

§多边形的表示方法：

-顶点表示：用多边形的顶点序列刻划多边形；

-点阵表示：用位于多边形内象素的集合来刻划多边形；

-扫描转换多边形：将顶点表示形式转换成点阵表示形式；

§三种方法：逐点判断法；扫描线算法；边缘填充法；

?逐点判断法

逐个判断绘图窗口内的像素：

?如何判断点在多边形的内外关系？1）射线法; 2）累计角度法; 3）编码法；

射线法步骤：1) 从待判别点v发出射线; 2) 求交点个数k; 3) K的奇偶性决定了点与多边形的内外关系; 4)奇异情况处理;

?累计角度法

?编码方法：累计角度方法的离散方法

结论：逐点判断法程序简单，速度太慢，效率低。

2、边填充算法：

算法1（以扫描线为中心的边填充算法）：

§1、将当前扫描线上的所有象素着上颜色；

§2、求余： for(i = 0;i <= m; i++)在当前扫描线上从横坐标为Xi的交点向右求余；

算法2（以边为中心的边填充算法）：

§1、将绘图窗口的背景色设置；

§2、对多边形的每一条非水平边做：从该边上的每个象素开始向右求余；

结论：

§适于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备；

§优点：算法简单；

§缺点：对于复杂图形，每一象素可能被访问多次，输入/输出的量比扫描线算法大得多；

§边标志算法：分为两步骤：

-第一步，对多边形的每条边进行直线扫描转换，亦即对多边形边界所经过的象素打上边标志；

-第二步，填充。对每条与多边形相交的扫描线，依从左到右顺序，逐个访问该扫描线上象素。使用一个布尔量inside来指示当前点的状态，若点在多边形内，则inside为真。若点在多边形外，则inside为假。inside 的初始值为假，每当当前访问象素为被打上边标志的点，就把inside取反。对未打标志的象素，inside不变。若访问当前象素时，对inside作必要操作之后，inside为真，则把该象素置为多边形色。

3、圆域的填充

§将多边形区域填充原理推广到圆域的填充；

-1）计算每条扫描线与圆域的相交区间；

-2）把区间内象素用指定颜色填充；

§相交区间的确定：

-中点画圆法→计算交点→确定相交区间；

-函数F的计算可以采用增量法提高效率

四、线宽与线型的处理

1、直线线宽处理

-线刷子：垂直刷子、水平刷子；

-线刷子特点（1/2）

§实现简单、效率高。

§斜线与水平(或垂直)线不一样粗。

§当线宽为偶数个象素时，线的中心将偏移半个象素。

§问题：利用线刷子生成线的始末端总是水平或垂直的，看起来不太自然。

§解决：添加“线帽（line cap）”

-线刷子特点(2/2)

§当比较接近水平的线与比较接近垂直的线汇合时，汇合处外角有缺口;

§解决：斜角连接（miter join）、圆连接（round join）、斜切连接（bevel join）;

-方刷子：

-特点:方刷子绘制的线条（斜线）比用线刷子所绘制的线条要粗一些;

方刷子绘制的斜线与水平（或垂直）线不一样粗;

方刷子绘制的线条自然地带有一个“方线帽”;

2、曲线线宽处理

-线刷子

-方刷子§要显示一致的曲线宽度可通过旋转刷子方向,使其在沿曲线移动时与斜率方向一致;

-圆弧刷子§采用填充的办法

3、线型的处理

§直线线型处理

-实心段和中间空白段的长度（象素数目）可用象素模板(pixel mask)指定；-存在问题：如何保持任何方向的划线长度近似地相等？

-解决：根据线的斜率来调整实心段和中间空白段的象素数目；

§曲线线型处理

-采用象素模板的方法；

五、字符

1、矢量字符

§对每个字符定义矢量代码序列描述字符的几何形状：

-不同的应用使用不同的方法。

§以AutoCAD采用的定义方法为例：

-AutoCAD采用一种称为形（SHAPE）的实体来定义字符

-基本笔画：直线和圆弧

-形描述格式如下：

* <形编号>，<字节数>，<形名称> <字节1>，<字节2>， 0

形编号：1－255整数；

字节数：形定义描述行中包括结束符0在内的字节数目；

形名称：用大写字母；否则认为是形的解释性信息，不存储；

<字节N>：定义字符组成矢量的方向和大小，分为标识位、低四位和高四位三组数字。标识位表示十六进制（0）或十进制（无标识位）;高四位表示矢量的长度，低四位表示矢量方向。

如：040即表示一16进制数，其中，4表示矢量的长度，0表示矢量方向。

§实例：二极管符号：

§* 133, 11, DIDOE

040, 044, 04c, 042, 04c, 040, 048, 04c, 046, 04c, 0

§把每一个字符都按上述方法描述后，存入一形文件中，即建立了相应的矢量字符库。

2、点阵字符

§每个字符定义成称为字符掩膜的矩阵；

§西文字符：5×7的点阵字符；

§汉文字符：16×16的点阵字符；

§打印：24×24，40×40，72×72的点阵字符

§特殊字符：按需确定。

3、字型技术

节约空间，采用压缩技术（字型数据压缩存储，使用时，还原成字符点阵）：

-黑白段压缩法：

§优点：简单快速不失真；

§缺点：压缩较差，不方便，一般用于低级文字处理系统；

-部件压缩法：

§优点：压缩比大

§缺点：字型质量不保证；

-轮廓字型法：

压缩比大，质量保证（采用直线、BEZIER曲线的集合描述字符的轮廓线）;

-轮廓线和控制信息（属性、控制点/线）构成压缩数据，结合填充算法以取得较好的效果；

4、字符的输出

-绘图仪输出：方向、位移值转换为设备驱动指令；

-显示器/打印机输出：指定字符掩膜的原点与帧缓存中的字符左下脚位置对应，从而将字符掩膜中的值平移的写入帧缓存中；

六、裁剪

1、线段裁剪

§线段裁剪方法：

-Cohen-SutherLand裁减算法

-中点分割算法；

-参数化方法

§Cohen-SutherLand算法的改进：编码算法

-目的：对显然不可见线段实现快速判别；

-编码方法：由窗口四条边所在直线把二维平面分成9个区域，每个区域赋予一个四位编码，C t C b C r C l，上下右左

§Nicholl-Lee-Nicholl算法

-目的：通过对二维平面的更详细划分，消除Cohen_Sutherland算法中线段在被裁剪时需多次求交的情况。

§中点分割法

-思想：从P0点出发找出距P0最近的可见点，从P1点出发找出距P1最近的可见点。

-取中点Pm=(P1+P2)/2

§参数化方法

-思想：利用数学上线段的参数方程；

-如：考虑凸多边形R和线段P1，计算线段落在区域R中的部分，上述算法简化为Liang-Barsky算法

四种算法比较：

-Cohen-Sutherland与中点法在区码测试阶段能以位运算方式高效率进行→大多数线段能够简单地取舍时，效率较好；

-Cyrus-Beck(参数化方法)：在多数线段需要进行裁剪时效率高：因为运算只涉及到参数，仅仅必要时才进行坐标计算；

-Liang Barsky算法只能应用在矩形窗口情形，效率比参数化方法更高。

2、多边形裁剪

§Sutherland-Hodgman算法（逐边裁剪算法）：

-分割处理策略：将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪；

-流水线过程(左上右下)：左边的结果是上边的开始；

-内侧空间与外侧空间；

-多边形的边与裁减线形成空间的关系

-多边形各边与裁减线的四种位置关系：

§S,P与裁剪线同侧：

-同在可见一侧；

-同在不可见一侧；

§S,P与裁剪线不同侧：

-S可见，P不可见；

-S不可见，P可见；

结论：

--裁剪算法采用流水线方式，适合硬件实现；

--可推广到任意凸多边形裁剪窗口；

Weiler-Athenton算法（内裁剪方法）

-裁剪窗口为任意多边形（凸、凹、带内环）的情况：

-主多边形：被裁剪多边形，记为A

-裁剪多边形：裁剪窗口，记为B

-算法（内裁剪）步骤：

§1、建立主多边形和裁剪多边的顶点表．

§2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针。

§3、裁剪：如果存在没有被跟踪过的交点，执行以下步骤：

-(1)建立裁剪结果多边形的顶点表．

-(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．

-(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．

-(4)跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．

-(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．

-(6)重复(4)、(5)直至回到起点

3、字符裁剪

1)基于字符串

2)基于字符

§基于构成字符的最小元素：

-点阵字符：点裁剪，字符掩膜写入象素前，判断是否在窗口内；

-矢量字符：线裁剪，对跨越窗口边界的笔划进行裁剪；

d y x w 1),(∝1),(=?A

dA y x w 七、 反走样

§混淆现象（反走样）

-混淆:用离散量（象素）表示连续量（图形）引起的失真；

-不光滑(阶梯状)的图形边界；

-图形细节失真（比象素更窄的细节丢失）§静态：容易被丢弃或忽略；

-狭小图形的遗失（引起动态图形的闪烁） §什么是反混淆（走样）

-在图形显示过程中，用于减少或消除混淆现象的方法；

§提高分辨率的反混淆方法：

缺陷：硬件代价太大，只能减轻，而不能消除走样问题； §加权区域采样方法→盒式滤波器：进行前置滤波后再取样

§加权区域采样方法

-权函数W(x,y)；

-以象素A 的中心为原点建立二维坐标系；

-w(x,y)反应了微面积元dA 对整个象素亮度的贡献大小：

-权性（ w(x,y)在象素上具有权性）

基本图元的生成算法

基本图元的生成算法 一、实验目的1、初步了解显示窗口与视区的关系2、掌握OpengGL点、直线、多边形的绘制3、掌握DDA直线生成算法。4、掌握Bresenham直线生成算法二、实验环境硬件要求：PC机，主流配置，最好为独立显卡，显存512M以上。 软件环境：操作系统：Windows XP。语言开发工具：VC6.0。 三、实验内容与要求 1、调出实验一的源代码运行，调整修改使得显示窗口大小改变时，绘制的矩形大小随之改变。如图2-1所示。提示：(1)在main函数里添加注册窗口变化函数glutReshapeFunc(myreshape); （放在glutMainLoop()之前）(2)在程序中添加窗口改变子函数，参数w,h为当前显示窗口的宽和高 void myreshape(GLsizei w, GLsizei h) { glViewport(0,0,w,h); //设置视区位置 glMatrixMode(GL_PROJECTION);//设置投影变换模式 glLoadIdentity(); //调单位矩阵，清空当前矩阵堆栈 if(w<=h) gluOrtho2D(0,300,0,300*(GLfloat)h/(GLfloat)w); //设置裁剪窗口大小 else gluOrtho2D(0,300*(GLfloat)w/(GLfloat)h,0,300); } a) 显示窗口改变前 b)显示窗口变大后 未修改前的初始源程序参考如下： /*my first program.cpp*/ #include void display(void)

{ glClear(GL_COLOR_BUFFER_BIT); //刷新颜色缓冲区 glRectf(0,0,0.5,0.5); glFlush(); //用于刷新命令队列和缓冲区，使所有尚未被执行的 OpenGL命令得到执行 } void main(int argc, char** argv) { glutInit(&argc, argv); //初始化GLUT库 glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB); //设置显示模式 glutInitWindowSize(100, 200); glutCreateWindow("hello"); //创建窗口，标题为“hello” glutDisplayFunc(display); //用于绘制当前窗口 glutMainLoop(); //表示开始运行程序，用于程序的结尾 } 2、自己参照讲义或教材按照自己的构思画二维平面图形, 修改样本程序 circle-algorithm.cpp将上面的矩形替换成自己构思的二维平面图形。注意顶点的顺序。 参考函数： （1）、点绘制举例 glPointSize(2.0) //点的大小设置 glBegin(GL_POINTS); glColor3f(1.0,1.0,1.0); glVertex2f(-0.5,-0.5); //顶点 glColor3f(1.0,0.0,1.0); glVertex2f(-0.5,0.5); glColor3f(0.0,1.0,1.0); glVertex2f(0.5,0.5); glColor3f(1.0,1.0,0.0); glVertex2f(0.5,-0.5); glEnd() （2）、直线/三角形/四边形绘制举例 glLineWidth(2.0); glBegin(GL_LINES); // glBegin(GL_LINE_STRIP); // glBegin(GL_LINE_LOOP); // glBegin(GL_TRIANGLES); // glBegin(GL_TRIANGLE_STRIP); // glBegin(GL_TRIANGLE_FAN); // glBegin(GL_QUADS); // glBegin(GL_TRIANGLE_STRIP); glVertex2f(-0.5,0.5);

D图像生成算法原理

D图像生成算法原理 Standardization of sany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#

3D图像生成算法原理 一、建齐次坐标 二、着色模型 三、Z缓存 四、纹理映射 在这些步骤中，显示部分（GPU）只负责完成第三、四步，而前两个步骤主要是依靠 CPU 来完成。而且，这还仅仅只是3D图象的生成，还没有包括游戏中复杂的AI运算。 场景切换运算等等……无疑，这些元素还需要CPU去完成，这就是为什么在运行大型3D的时候，当场景切换时再强劲的显卡都会出现停顿的现象。 3D芯片的处理对象是多边形表示的物体。用多边形表示物体有两个优点：首先是直接（尽管繁琐）， 多边形表示的物体其表面的分段线性特征除轮廓外可以通过明暗处理(shading)技术消除；其次是仅存储多边形顶点的几何信息， 多边形内部每个象素的明暗颜色计算所需的信息由这些顶点信息插值而来，这正是易于用图形硬件支持的快速明暗处理技术。 支持多边形绘制的图形硬件同样也可以绘制由双三次曲面片表示的物体，通过对这种物体的表面进行三角剖分， 用逼近的三角形网格代替原物体的曲面表示就可以做到这一点。

当然，用多边形表示物体也有其缺点，如增加了纹理映射和阴影生成的难度，当需要详细表示复杂物体时所需的三角形数量将变得非常庞大。 将多边形表示的物体显示到计算机屏幕上，这一过程涉及物体在计算机内部的表示方式即物体的数据结构， 由物体组成的场景的组织结构，物体从场景到屏幕空间要经过的一系列变换，以及产生最终屏幕图象要经过的一系列光栅化处理。 这些方面都涉及到特定的处理算法,相应的算法又有许多不同的变种。 下面仅就3D芯片涉及的图形处理过程及相关算法做一简单分析介绍，这些是理解3D图形处理及图形硬件的基础。 一、3D物体的表示法 具有复杂外形的物体其表面可以由多边形面片来近似表示。以图1的圆柱为例，其柱面可以由2N个三角形近似，其两端可以由两个N边形来近似。 多边形模型在其轮廓上的分段线性特征是这一表示法主要的视觉缺陷,改进的唯一途径是增加多边形的分辨率。 对于一个复杂形体来说，为了充分表示其细节，常常要用到十万个以上的多边形。这将耗费许多数据库访问时间和绘制时间。 当将多边形模型进行放大处理时，会产生连接问题。这就是所谓的“几何走样”。

计算机图形学实验一

实验一二维基本图元的生成与填充 实验目的 1.了解并掌握二维基本图元的生成算法与填充算法。 2.实现直线生成的DDA算法、中点算法和Bresenham算法。 3.实现圆和椭圆生成的DDA和中点算法, 对几种算法的优缺点有感性认识。 二.实验内容和要求 1. 2.创建良好的用户界面,包括菜单,参数输入区域和图形显示区域。 3.实现生成直线的DDA算法、中点算法和Bresenham算法。 4.实现圆弧生成的中点算法。 5.实现多边形生成的常用算法, 如扫描线算法,边缘填充算法。 6.实现一般连通区域的基于扫描线的种子填充算法。 7.将生成算法以菜单或按钮形式集成到用户界面上。 8.直线与圆的坐标参数可以用鼠标或键盘输入。 6. 可以实现任何情形的直线和圆的生成。 实验报告 1．用户界面的设计思想和框图。 2．各种实现算法的算法思想。 3．算法验证例子。 4．上交源程序。 直线生成程序设计的步骤如下： 为编程实现上述算法，本程序利用最基本的绘制元素（如点、直线等），绘制图形。如图1-1所示，为程序运行主界面，通过选择菜单及下拉菜单的各功能项分别完成各种对应算法的图形绘制。 图1-1 基本图形生成的程序运行界面 2．创建工程名称为“基本图形的生成”单文档应用程序框架 （1）启动VC，选择“文件”|“新建”菜单命令，并在弹出的新建对话框中单击“工程”标签。 （2）选择MFC AppWizard(exe)，在“工程名称”编辑框中输入“基本图形的生成”作为工程名称，单击“确定”按钮，出现Step 1对话框。 （3）选择“单个文档”选项，单击“下一个”按钮，出现Step 2对话框。 （4）接受默认选项，单击“下一个”按钮，在出现的Step 3～Step 5对话框中，接受默认选项，单击“下一个”按钮。 （5）在Step 6对话框中单击“完成”按钮，即完成“基本图形的生成”应用程序的所有选项，随后出现工程信息对话框（记录以上步骤各选项选择情况），如图1-2所示，单击“确定”按钮，完成应用程序框架的创建。 图1-2 信息程序基本

3D图像生成算法原理

3D图像生成算法原理 一、建齐次坐标 二、着色模型 三、Z缓存 四、纹理映射 在这些步骤中，显示部分（GPU）只负责完成第三、四步，而前两个步骤主要是依靠 CPU 来完成。而且，这还仅仅只是3D图象的生成，还没有包括游戏中复杂的AI运算。 场景切换运算等等……无疑，这些元素还需要CPU去完成，这就是为什么在运行大型3D的时候，当场景切换时再强劲的显卡都会出现停顿的现象。 3D芯片的处理对象是多边形表示的物体。用多边形表示物体有两个优点：首先是直接（尽管繁琐）， 多边形表示的物体其表面的分段线性特征除轮廓外可以通过明暗处理(shading)技术消除；其次是仅存储多边形顶点的几何信息， 多边形部每个象素的明暗颜色计算所需的信息由这些顶点信息插值而来，这正是易于用图形硬件支持的快速明暗处理技术。 支持多边形绘制的图形硬件同样也可以绘制由双三次曲面片表示的物体，通过对这种物体的表面进行三角剖分， 用逼近的三角形网格代替原物体的曲面表示就可以做到这一点。 当然，用多边形表示物体也有其缺点，如增加了纹理映射和阴影生成的难度，当需要详细表示复杂物体时所需的三角形数量将变得非常庞大。

将多边形表示的物体显示到计算机屏幕上，这一过程涉及物体在计算机部的表示方式即物体的数据结构， 由物体组成的场景的组织结构，物体从场景到屏幕空间要经过的一系列变换，以及产生最终屏幕图象要经过的一系列光栅化处理。 这些方面都涉及到特定的处理算法,相应的算法又有许多不同的变种。下面仅就3D芯片涉及的图形处理过程及相关算法做一简单分析介绍，这些是理解3D图形处理及图形硬件的基础。 一、3D物体的表示法 具有复杂外形的物体其表面可以由多边形面片来近似表示。以图1的圆柱为例，其柱面可以由2N个三角形近似，其两端可以由两个N边形来近似。 多边形模型在其轮廓上的分段线性特征是这一表示法主要的视觉缺陷,改进的唯一途径是增加多边形的分辨率。 对于一个复杂形体来说，为了充分表示其细节，常常要用到十万个以上的多边形。这将耗费许多数据库访问时间和绘制时间。 当将多边形模型进行放大处理时，会产生连接问题。这就是所谓的“几何走样”。 物体的多边形表示既可以通过交互设计人工提取，也可以通过激光扫描设备得到。总之，多边形表示的物体并不特别适合于交互操作或做自由的形状改变。 当改变物体的形状时很难保证多边形表示的完整性得到保持。 对多边形明暗着色所需要的信息存储在一个分层的数据结构中，每一个物体表面由指向多边形表的指针定义，该多边形表包含了近似该表

计算机图形学--圆的的生成算法的实现

计算机图形学--圆的的生成算法的实现

实验三：圆的的生成算法的实现 班级08信计2班学号20080502063 姓名李宁分数 一、实验目的与要求： 1、了解WIN-TC1.72等编程环境中常用控件命令与绘图函数，初步掌 握在实验设 计集成环境下进行图形处理程序的设计方法。 2、熟练掌握圆的两种换算法：基于正负算法画圆和基于中点算法画圆。 、二、实验内容： 1、在WIN-TC1.72环境中设计程序，利用消息处理函数，搭建能运行 图形算法程 序的平台。 2、根据教材中给定的算法，实现圆的两种生成算法：基于中点算法画圆和基于 正负算法 三、实验结果分析： 1、实验程序 （1）基于中点算法画圆程序实现的完整源程序 #include #include

// 中点画圆法 void Circle_Midpoint(int x, int y, int r, int color) { int tx = 0, ty = r, d = 1 - r; while(tx <= ty) { // 利用圆的八分对称性画点 putpixel(x + tx, y + ty, color); putpixel(x + tx, y - ty, color); putpixel(x - tx, y + ty, color); putpixel(x - tx, y - ty, color); putpixel(x + ty, y + tx, color);

putpixel(x + ty, y - tx, color); putpixel(x - ty, y + tx, color); putpixel(x - ty, y - tx, color); if(d < 0) d += 2 * tx + 3; else d += 2 * (tx - ty) + 5, ty--; tx++; } } // 主函数 void main() { initgraph(640, 480); // 测试画圆 Circle_Midpoint(320, 240, 200, RED);

计算机图形学 实验一 基本图形元素生成算法

西北农林科技大学实习报告 学 院名称：理 学 院 专业班级： 姓名： 学 号： 课程：计算机图形学实验 报告日期： 第十二周 实验一 基本图形元素生成算法 一．实验目的 1）熟练掌握基本图形元素生成算法。 2）对高级语言的图形模式的设定有比较详细的了解。 3）对基本图形类（或函数）的调用方法有一个比较详细的了解。 二．实验步骤 1）DDA 算法、Bresenham 算法进行比较，选定比较合适的算法。 2）画出程序流程图； 3）编写程序的源程序； 4）编辑源程序并进行调试； 5）进行特殊模式的运行测试，并结合情况进行调整。 三．实验内容 选定一种基本图形（直线段），编写生成该基本图形的源程序，并能在计算机上编译运行，画出正确的图形。 1. 原理简介 Bresenham 算法是计算机图形学领域使用最广泛的直线扫描转换方法。 其原理是：过各行、各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线各垂直网格线的交点,然后确定该列像素中与此交点最近的像素。该算法的优点在于可以采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列所求的像素。 如果令d0=0, d=d+k (k 为直线斜率,假设k ＜1,当d ≥1时,减1) 保证d 在0、1之间；当d ＞0.5, (X0,Y0)→(X0+1,Y0+1) ；d ＜0.5, (X0,Y0)→(X0+1,Y0)。 具体步骤： 下面是01k ≤≤的时候的算法,其他时候类似 (1) 输入直线的两个端点000111(,)(,)P x y P x y 和

(2)计算初始值00,,,,x y e x x x y y ??=-?== (3)绘制点(,)x y (4)e 更新为2e y +?。判断e 的符号,若0e >,则(,)x y 更新为(1,1)x y ++,同时将e 更新为2e x -?；否则(,)x y 更新为(1,)x y + (5)当直线没画完时,重复步骤(3)和(4),否则结束 流程图为： 2.图形描述： 用中点Bresenham 算法画出从（0，0)到（800,200）的直线段。如图所示： 用中点Bresenham 算法画出从（0，0)到（800,200）的直线段。如图所示：

3D图像生成算法原理

3D 图像生成算法原理 一、建齐次坐标 二、着色模型 三、Z缓存 四、纹理映射 在这些步骤中，显示部分（GPU只负责完成第三、四步，而前两个步骤主要就是依靠CPU来完成。而且，这还仅仅只就是3D图象的生成,还没有包括游戏中复杂的AI运算。 场景切换运算等等?…无疑，这些元素还需要CPU去完成，这就就是为什么在运行大型3D的时候，当场景切换时再强劲的显卡都会出现停顿的现象。 3D 芯片的处理对象就是多边形表示的物体。用多边形表示物体有两个优点:首先就是直接（尽管繁琐）, 多边形表示的物体其表面的分段线性特征除轮廓外可以通过明暗处理（shading技术消除;其次就是仅存储多边形顶点的几何信息，多边形内部每个象素的明暗颜色计算所需的信息由这些顶点信息插值而来,这正就是易于用图形硬件支持的快速明暗处理技术。支持多边形绘制的图形硬件同样也可以绘制由双三次曲面片表示的物体,通过对这种物体的表面进行三角剖分, 用逼近的三角形网格代替原物体的曲面表示就可以做到这一点。当然,用多边形表示物体也有其缺点,如增加了纹理映射与阴影生成的难度,当需要详细表示复杂物体时所需的三角形数量将变得非常庞大。 将多边形表示的物体显示到计算机屏幕上,这一过程涉及物体在计算机内部的表示方式即物体的数据结构, 由物体组成的场景的组织结构,物体从场景到屏幕空间要经过的一系列变换,以及产生最终屏幕图象要经

过的一系列光栅化处理。这些方面都涉及到特定的处理算法,相应的算法又有许多不同的变 种。 下面仅就3D芯片涉及的图形处理过程及相关算法做一简单分析介绍，这些就是理解3D 图形处理及图形硬件的基础。 一、3D物体的表示法 具有复杂外形的物体其表面可以由多边形面片来近似表示。以图1 的圆柱为例,其柱面可以由2N 个三角形近似,其两端可以由两个N 边形来近似。 多边形模型在其轮廓上的分段线性特征就是这一表示法主要的视觉缺陷,改进的唯一途径就是增加多边形的分辨率。 对于一个复杂形体来说,为了充分表示其细节,常常要用到十万个以上的多边形。这将耗费许多数据库访问时间与绘制时间。 当将多边形模型进行放大处理时,会产生连接问题。这就就是所谓的“几何走样”。 物体的多边形表示既可以通过交互设计人工提取,也可以通过激光扫描设备得到。总之,多边形表示的物体并不特别适合于交互操作或做自由的形状改变。 当改变物体的形状时很难保证多边形表示的完整性得到保持。 对多边形明暗着色所需要的信息存储在一个分层的数据结构中,每一 个物体表面由指向多边形表的指针定义,该多边形表包含了近似该表面的一组多边形,每一个多边形由指向顶点表的指针定义,顶点表包含了每个多边形的所有顶点。

第四章 基本图形生成算法

10,,111<≤??=???+=+=++m x y m m y y x x i i i i 其中：第四章 基本图形生成算法 一、 直线的扫描转换 1． 数值微分算法 直接使用直线方程法、DDA 算法（增量算法） 优点：DDA 算法比直接用直线方程的方法快：没有浮点乘法； 缺点：求每个连续点时，需要浮点加法；加0.5舍尾取整，不利于硬件实现；表示长直线时，由于精度限制→累计误差； 2． 中点画线法 原理：1、确定与直线距离最近的点P ；2、利用点P 确定下一个点 3． Bresenham 画线算法 算法基本思想：每次迭代在增量最大方向上均走一步，其方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。 例如取X 方向为最大增量方向，则有： 算法优点：-快速增量算法；-要获得准确的数学结果，只需通过整数的加、减法和乘2运算；计算机中乘2可以容易的通过算术移位实现。 给出使用Bresenham 算法画斜率介于0到45度之间的直线所需的步骤。 -解答： §1、计算初始值：dx=x2-x1; dy = y2 – y1; lnc1=2dy; lnc2 = 2(dy – dx)；d = lnc1-dx §2、设置左下方的端点坐标为（x,y ）,同时将Xend 设为x 的最大值。如果dx<0,则x=x2,y=y2,Xend=x1. 如果dx>0，则x=x1,y=y1,Xend=x2; §3、在当前（x ，y ）坐标画一个点； §4、判断整条线段是否已经画完，如果x=Xend ，则停止； §5、计算下一个象素的位置，如果d<0，那么d=d+lnc1，如果d>=0,则d=d+lnc2,且y=y+1; §6、增加x:x=x+1; §7、在当前的(x,y)坐标画一个点； §8、转到步骤4；

基本图形生成算法(基于VC++6.0实现)

仲恺农业工程学院实验报告纸计算科学学院（院、系）信计082 班计算机图形学课学号：200811314211 姓名：孙青海实验日期：2011/5/20 教师评定 实验一基本图形生成算法 一、实验目的与要求： 1. 掌握中点Bresenhanm绘制直线的原理 2. 设计中点Bresenhanm算法 3. 掌握八分法中点Bresenhanm算法绘制圆的原理 4. 设计八分法绘制圆的中点Bresenhanm算法 5. 掌握绘制1/4椭圆弧的上半部分和下半部分的中点Bresenhanm算法原理 6. 掌握下半部分椭圆偏差判别式的初始值计算方法 7．设计顺时针四分法绘制椭圆的中点Bresenhanm算法 二、实验描述： 1. 使用中点Bresenhanm算法绘制斜率为01 ≤≤的直线。 k 2. 使用中点Bresenhanm算法绘制圆心位于屏幕客户区中心的圆。 3. 使用中点Bresenhanm算法绘制圆心位于屏幕中心的椭圆。 三、实验结果： 1.打开VC++6.0程序； 2.创建一个MFC工程，命名为exper1；选择单文档和作为静态的DLL，然后完 成创建MFC工程； 3.在ResourceView工作区窗口插入三个Dialog，第一个对话框作为画直线时用户 输入起点坐标和终点坐标使用，第二个对话框作为画圆时用户输入所要画圆的半径使用，第三个对话框作为画椭圆时用户输入所要画椭圆的长半径和短半径

使用； 4.通过右键点击对话框选择建立类向导，因为本对话框是新建对话框还没有建立 类向导，在此要新建一个line类，如下图所示，按照此方法将其他的两个对话框建立类向导分别为画圆建立Round类，画椭圆，建立Ellips类； 5.完成类得建立后，对该对话框中的输入框进行添加变量与其关联，具体步骤如 下图所示，按照此方法将所有的对话框中的输入框进行变量添加；