计算机图形学画多边形

《计算机图形学画多边形》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、43第1章Error!Notextofspecifiedstyleindocument.基本图形的生成计算机图形学已成为计算机技术中发展最快的领域，计算机图形软件也相应得到快速发展。计算机绘图显示有屏幕显示、打印机打印图样和绘图机输出图样等方式，其中用屏幕显示图样是计算机绘图的重要内容。计算机上常见的显示器为光栅图形显示器，光栅图形显示器可以看作像素的矩阵。像素是组成图形的基本元素，一般称为“点”。通过点亮一些像素，灭掉另一些像素，即在屏幕上产生图形。在光栅显示器上显示任何一种图形必须在显示器的相应像素点上画上所需颜色，即具有一种或多种颜色的像素集合构成图形。确定最佳接近图形的像素集合，并用指

2、定属性写像素的过程称为图形的扫描转换或光栅化。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案进行显示，即区域填充。复杂的图形系统，都是由一些最基本的图形元素组成的。利用计算机编制图形软件时，编制基本图形元素是相当重要的，也是必需的。点是基本图形，本章主要讲述如何在指定的输出设备（如光栅图形显示器）上利用点构造其他基本二维几何图形（如点、直线、圆、椭圆、多边形域及字符串等）的算法与原理，并利用VisualC++编程实现这些算法。1.1直线数学上，理想的直线是由无数个点构成的集合，没有宽度。计算机绘制直线是在显示器所给

3、定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，实现显示器绘制直线，即通常所说的直线的扫描转换，或称直线光栅化。由于一图形中可能包含成千上万条直线，所以要求绘制直线的算法应尽可能地快。本节介绍一个像素宽直线的常用算法：数值微分法（DDA）、中点画线法、Bresenham算法。1.1.1DDA（数值微分）算法DDA算法原理：图1-1DDA方法扫描转换连接两点图1-2中点画线法每步迭代涉及的像素和中点示意图如图1-1所示，已知过端点的直线段；直线斜率为，从的左端点开始，向右端点步进画线，步长=1（个像素），计算相应的坐标；取像素点 [,round（

4、y）] 作为当前点的坐标。计算，当，即当x每递增1，y递增k（43第1章Error!Notextofspecifiedstyleindocument.即直线斜率）。注意：上述分析的算法仅适用于k£1的情形。在这种情况下，x每增加1,y最多增加1。当时，必须把x，y地位互换，y每增加1，x相应增加1/k（请参阅后面的VisualC++程序）。1.1.2生成直线的中点画线法中点画线法的基本原理如图1-2所示。在画直线段的过程中，当前像素点为P，下一个像素点有两种选择，点P1或P2。M为P1与P2中点，Q为理想直线与X=Xp+1垂线的交点。当M在Q的下方时，则P2应为下一个像素点；当M在Q的上方时，

5、应取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），判断F的符号，可知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

6、均可，取P1为下一个像素。其中d是xp,yp的线性函数。1.1.3Bresenham算法Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。由误差项符号决定下一个像素取右边点还是右上方点。图1-3第一象限直线光栅化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+1，由y与yi及y

7、i+1的距离d1及d2的大小而定。计算公式为y=m(xi+1)+b（1.1）d1=y–yi（1.2）d2=yi+1–y（1.3）如果d1–d2>0，则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）43第1章Error!Not