《计算机图形学》基本图形生成-精

— CRT显示器工作原理 — LCD显示器工作原理
2.3．基本图形生成算法
— 直线生成算法 — 圆弧生成算法 — 其它基本图形生成
2.4．图形裁减算法 2.5．多边形填充算法（选学） 2.6．图形反走样算法（选学） 2.7．基于OpenGL图形库生成图形（选学）
华中科技大学CAD中心
思考问题：
1）图形如何在屏幕上显示出来？？ 2）CAD图形如何生成？？
象素的亮度值控制电子束对荧光屏的轰 击强度，象素在帧缓存寄存器中的位置编码 控制电子束的偏转位置。
图形系统为灵活控制图形颜色变化，往 往不直接将帧缓冲器中的数值作为显示的亮 度值，而是先经过颜色查找表（称调色板) 产生变换值来控制光点亮度。其工作方式：
显存中某位值 度
颜色表地址
华中科技大学CAD中心
为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。
不妨设函数：
F (x, y) = x2 + y 2 - r 2
显然有： F（x，y）< 0，则（x,y)位于圆边界内 F（x，y）＝ 0，则（x,y)位于圆边界上 F（x，y）> 0，则（x,y)位于圆边界外
考虑到圆的八对称 性，不妨以第二个 八分圆进行分析， 其它八分圆则可通 过镜像实现。
华中科技大学CAD中心
刷新频率
（仅CRT）
每秒钟重绘屏幕的次数， CRT产生稳定图像所需要的最小刷新频率： = 1秒 / 荧光物质的持续发光时间 （Hz）
注：液晶显示器原理不同于CRT，不受刷新频率影响。但液晶显示 有拖尾现象，是因液晶偏转延迟所致，延时越长，拖尾越重。
帧扫描
与电视工作原理类 似，CRT电子束从上 到下、从左到右扫描 进行，每扫描一遍称 为一帧。

基函数（基本样条） 在局部参数区域分布 （支撑区间），因此 影响范围有限。
例题：有点P0（4，3）；P1（6，5）；P2（10，
6 ）；P3（12，4），用以上4点构造2次B样条曲线。
2.1.7 非均匀有理B样条
非均匀有理B样条NURBS（Non Uniform Rational BSpline）；
3.2.2
Bresenham画圆法
该算法是最有效的算法之一。
不失一般性，假设圆心(xc，yc) ,圆上的点(x′，y′)，则：
x' x xc
y ' y yc
圆心为原点，半径为R的位于第一象限1/8圆弧的画法，即(0, R)～( R , R )。
2 2
yi )， 思想:每一步都选择一个距离理想圆周最近的点P( xi ， 使其误差项最小。
画其他曲线。
3.3
自由曲线的生成
正弦函数曲线
指数函数曲线
多项式函数曲线
自 由 曲 线
概率分布曲线及样条函数曲线
3.3.1 曲线的基本理论
基本概念
2.1.4
规则曲线：可用数学方程式表示出来的，如抛物 线等。
自由曲线：很难用一个数学方程式描述的，如高
速公路等。可通过曲线拟合(插值、逼近)的方法来
例题： 利用Bresenham算法生成P （0，0）到Q（6，5）的直 线所经过的像素点。要求先 列出计算式算出各点的坐标 值，然后在方格中标出各点。
（1，1）
3.1.5 双步画线法 原理
模式1：当右像素位于右下角时，中间像素位于底线 模式4：当右边像素位右上角时，中间像素位于中线 模式2和模式3：当右像素位于中线时，中间像素可能位于底线 上，也可能位于中线上，分别对应于模式2和模式3，需进一步 判断。 当0≤k≤1/2时，模式4不可能出现，当1/2≤k≤1时，模式1不 可能出现。

for (x=x0; xx1, x++) drawpixel (x, int(y+0.5), color); y=y+k;



例：画直线段P0(0,0)--P1(5,2)
int(y+0.5) 0 0 1 1 2 2 y+0.5 0+0.5 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5 2.0+0.5
角度DDA法
显然，确定x,y的初值及d值后，即可以增量方 式获得圆周上的坐标，然后取整可得象素坐标。 但要采用浮点运算、乘法运算、取整运算。
中点画圆法
利用圆的对称性，只须讨论1/8圆。第二个8分 圆 P（Xp ，Yp ）
P1
M P2
P为当前点亮象素，那么，下一个点亮的象素可 能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。
pi 2 xi dy 2 yi dx 2dy (2b 1)dx
（2.4）
在1a象限内，dx总大于0，所以pi可以判断d1d2的符号。Pi+1为
pi 1 2 xi 1dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
2( xi 1)dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
本算法是Bresenham在1965年提出。
设直线起点（x1，y1）终点（x2，y2），直 线可表示为 y mx b
y2 y1 dy b y1 m x1 , m x2 x1 dx
此处讨论先将直线方向限于1a象限，当
xi 1 xi 1

多边形的填充
•奇异点的处理 •将多边形的顶点分为两大类： •局部极值点：如图中的点P1、P2、P4和P6。对于这些点来说，进 入该点的边线和离开该点的边线位于过该点扫描线的同一侧。 •非极值点：如图中的点P3、P5。对于这些点来说，进入该点的边 线和离开该点的边线位于过该点扫描线的两侧。 •处理奇异点规则 •对于局部极值点，应看成两个点； •对于非极值点，应看成一个点。
多边形的填充—逐点判别算法
• 逐点判别算法
求出多边形的最小包围盒：从Pi(xi，yi)中求极值，xmin、ymin、xmax、 ymax。 对包围盒中的每个象素引水平射线进行测试。 求出该射线与多边形每条边的有效交点个数。 如果个数为奇数：该点置为填充色。
• 逐点判别算法虽然简单，但不可取，原因是速度慢。它割 断了各象素之间的联系，孤立地考虑问题，由于要对每个 象素进行多次求交运算，求交时要做大量的乘除运算，从 而影响了填充速度。
基本光栅图形生成算法
• 直线生成算法
• DDA方法
• Bresenham算法
• 圆弧生成算法
• 中点圆生成算法
• 多边形的填充
• 多边形表示方法
• 多边形填充的扫描线算法 • 边缘填充算法 • 边界标志算法
在计算机上绘图的一般方法
• 用现有绘图软件系统 • 画图\Word中的图文编辑工具\AutoCAD\Photoshop 等大型绘图软件 • 用绘图软件包 • OpenGL就是一个典型的、已经被接受的国际工业 标准的图形软件包。 • Java3D • 用操作系统的绘图功能 • 如Windows中Win32API中就提供了基本的绘图功能
直线生成算法—DDA算法
•
直线生成算法—DDA算法
•

《计算机图形学（第3版）》作为经典教材阐述了计算机图形学基本图形生成算法的基本概念。特别是在第四章的内容中主要讨论了一些基本图形的扫描转换的问题，如一维线框图形直线段、圆、椭圆的扫描转换问题，二维图形（多边形）的填充问题，以及图形的反走样和裁剪问题，而这些问题就是本题主要需要着重提出讨论的问题。
本文中研究的一维图形的算法主要包括直线段、圆与椭圆。
在使用计算机处理相应图形信息时经常会遇到计算机内部储存比较大的图形，以至于屏幕显示图形只是部分图形，不能完整显示。这个时候确定图形中哪些部分在显示区域中显示，而哪些不在显示区域内显示则对计算机的选择处理过程提出了要求，遇到这种情况就要运用裁剪操作，从线段裁剪到多边形裁剪有许多方法，其中主要的方法有：Cohen-Sutherland裁剪算法、中点分割算法、参数化方法和Reentrant Polygon Clipping算法。在王慧玲、冯雪花发表于《伊犁师范学院学报(自然科学版)》2008年第4期上的《对Cohen-Sutherland线段裁剪算法的分析及改进》一文中则针对上述方法中的Cohen-Sutherland线段裁剪算法提出了重点分析，首先，作者对Cohen-Sutherland线段裁剪算法提出了详细的解析：该算法运用编码的方法实现了对在显示区域内和显示区域外的判断来决定是否显示在在显示区域内显示，与此同时，这篇文章中除了研究和分析Cohen-Sutherland线段裁剪算法，还针对Cohen-Sutherland线段裁剪算法对判断所有的完全位于裁剪窗口之外的线段不能有效地情况下提出了可以通过添加判断条件，使之能完全判断出来，这使得减少了求交的次数，也提高得该算法的运算效率。关于中点分割法和参数化方法孙家广等在《计算机图形学（第3版）》一书中进行了阐述，中点分割法与Cohen-Sutherland线段裁剪算法相同点是利用对线段的端点编码，与之不同的是对于跨窗口边界的线段中点分割法将其等分为两段，直到最后的分割点与线段的端点距离达到分辨率的精度为止。多边形的裁剪与线段的裁剪不一样，如若把多边形分解成边界线段逐段进行裁剪会使得原来封闭的图形变得不封闭或者成为一些离散的线段。Suther-land和Hodgeman发明的逐次多边形裁剪（Reentrant Polygon Clipping）算法则解决了上面这个问题，该方法的基本思想是一次用裁剪窗口的一条边对多边形进行裁剪。上面对线段和多边形的裁剪的基本算法进行了一些介绍，在上面一些算法的基础上，韩俊卿，葛永慧和张东升在《太原理工大学学报》2005年第36卷第2期上面发表的《多边形窗口的矢量图形裁剪算法》一文则讨论了对于改进后的多边形窗口中的点、线、面等目标的裁剪算法，在这些算法之中，点目标的裁剪算法采用的是射线交叉法，线目标的裁剪算法采用的是通过对计算被裁剪线段和多边形的各个边真实交点之间的各个线段中点来判断是否对它们裁剪，在点和线的裁剪基础上实现面目标的裁剪。

dy=ye-ys； steps=abs(dx)；
16
第三章 基本图形生成技术
if (abs(dy)>abs(dx)) steps=abs(dy)； xIncrement=dx/steps； yIncrement=dy/steps； setPixel(x， y， c)； for (i=1； i<=steps； i++) { x+=xIncrement； y+=yIncrement； setPixel(x， y， c)； }
并计算每个连续的x值：
xi+1=xi+m－1
(3.4)
14
第三章 基本图形生成技术
当直线的斜率为负时， 如果－1≤m≤0， 那么， Δx=－
1， 并且
yi+1=yi－m 当m<－1时， 则Δy=－1， 且
(3.5)
xi+1=xi－m－1
(3.6)
总结起来也可以将问题简化为： 当|m|≤1时， 令
xs<xe， 则Δx=1， yi+1=yi+m； 当|m|>1时， 令ys<ye， 则Δy=1， xi+1=xi+m－1。
8
第三章 基本图形生成技术 另外， 一个明显的事实是只有水平线、 垂直线和45°线 的亮度线段是沿直线段不变的， 而其他方向直线的亮度由于 光栅化导致其结果是不均匀的。 即使对于上述的特殊情形， 直线的亮度也与其方向有关。 如图3.2所示， 45°线上像素 间距大于垂直线和水平线上的像素间距， 这使垂直线和水平 线比45°线较亮。
}
17
第三章 基本图形生成技术 算法将直线两个端点的像素位置作为输入， 其过程可概 括为： 将端点位置的水平和垂直差赋给参数dx和dy， 两者中 绝对值大者决定参数steps的值。 从像素位置(xs，ys) 开始， 确定沿直线生成下一个像素位置每步的所需偏移量， 并循环上述过程steps次。 如果dx的绝对值大于dy的绝对值， 那么x方向和y方向的 增量分别为±1和±m； 如果dy的绝对值大于dx的绝对值， 那 么y向和x方向的增量分别为±1和±m－1。

xi 1 xi x xi yi 1 yi y yi 1 1 x xi y k 1 y yi 1 y
DDA算法原理
• 对求出的xi+1，yi+1进行四舍五入，即 round(xi+1)=(int)(x i+1+0.5)或round(y i+1)=(int)(y i+1+0.5)
DDA算法原理
xi 1 xi x yi 1 yi y
其中，
yi+1 ε△y yi xi ε△x xi+1 x
y
1 / | x |, | x || y | 1 / max(|x |, | y |) 1 / | y |, | y || x |
示例图片
右图中，
红色填充点表示的线段： 起点为(0，0) 终点为(10，20)
绿色填充点表示的线段：
起点为(0，0) 终点为(20，10)
• • • • • • • • • • • • • • • • •
Void DDAline(int x0,int y0,int x1,int y1) { int dx,dy,epsl,k; 变量定义：整数型： dx,dy,epsl,k; float x,y,xIncre,yIncre; 符点型：x,y,xIncre,yIncre; dx=x1-x0; dy=y1-y0; 变量赋初值：线段起点与终点的x,y轴向 x=(float)x0; y=(float)y0; 增量；起点变量类型转换后赋值。 if( abs(dx)>abs(dy)) epsl=abs(dx); else 求x,y轴向增量的大值。 epsl=abs(dy); xIncre=(float)dx/(float)epsl; 求线段在x,y轴向上的步进增量 yIncre=(float)dy/(float)epsl; for(k=0;k<=epsl;k++) { putPixel((int)(x+0.5),(int)(y+0.5))); x+=xIncre; y+=yIncre; } 增量式依次计算线段上个点，并输出。 }

y= k· x+b
k=0.571429
b=0.428571
2 X[0]=1 y0 X[1]=2
Y[0]=1 Y[0]=1 Y[1]=kx[1]+b=1.57 Y[1]=y0+k=1.57 Y[2]=y1+k=2.14 Y[2]=kx[2]+b=2.14 Y[3]=y2+k=2.71 Y[3]=kx[3]+b=2.71 Y[4]=y3+k=3.28 Y[4]=kx[4]+b=3.28 Y[5]=y4+k=3.85 Y[5]=kx[5]+b=3.85 Y[6]=y5+k=4.4 Y[6]=kx[6]+b=4.4 Y[7]=5 Y[7]=5
第3章 基本图形生 成算法
1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法
2015/4/19
1
图元
• 图元：图形软件包中用了描述各种几何 图形元素的函数称为图形输出原语，简 称图元。 • 描述对象几何要素的输出图元一般称为 几何图元。点的定位和直线段是最简单 的几何图元。 • 在选定坐标系中指定一个图形的几何要 素后，输出图元投影到该输出设备显示 区域对于的二维平面上，并扫描转换到 帧缓存的整数像素位置。
2015/4/19
5

1 直线生成算法(DDA、BRES) 2 圆生成算法（Mid） 3 多边形填充算法（扫描线、区域） 4 字符图元算法
1 直线的DDA算法
2015/4/19
6
OpenGL画点和画线函数 1) 画点函数 glVertex*( ); (*={234}{sifd}[v]) 表示该函数有后缀，指 明空间尺寸、坐标数据类型或向量形式描述。 Ex: glBegin(GL_POINTS); glVertex2i(100,50); glEnd(); glBegin(GL_POINTS); glVertex2i(100,50); glVertex2i(75,90); glVertex2i(300,590); glEnd();

思考题
对于前述几种直线生成算法和程序：
1.当最大位移方向是y时，应如何修改？ 2. 要达到通用时，应如何修改？
5.2 圆的扫描转换
解决的问题：
绘出圆心在原点，半径为整数R的圆 x2+y2==R2
■八分法画圆
y y=-x
(-y,x)
(y,x)
y=x
(-x,y) (-x,-y)
(x,y)
(x,-y)
改进1：令e=d-0.5
xi 1 xi 1 y yi 1 (e 0) i 1 yi (e 0)
•e初=-0.5， •每走一步有e=e+k。 •if (e>0) then e=e-1
算法步骤为：
1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值△x、△y、e=-0.5、x=x0、y=y0。 3.绘制点(x,y)。 4.e更新为e+k，判断e的符号。若e>0，则(x,y)更新 为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为 (x+1,y)。
初始值d的计算
d 0 F ( x0 1, y0 0.5) y0 0.5 k ( x0 1) b y0 k x0 b k 0.5 0 .5 k
P(x i,y i) Pu(x i+1,y i+1) Q M(x i+1,y i+1/2) Pd(x i+1,y i)
y F(x,y)=0 F(x,y)>0 x F(x,y)<0 F(x,y)=0
y
F(x,y)>0
F(x,y)<0
x
图5-4

yi+1 （画非水平线时，y的值变化，需要计算）
其中：yi+1的计算为：
yi+1=kxi+1 +B
=k(xi+△x)+B =kxi+k△x +B =kxi+B+k△x =yi +k△x
//yi=kxi+B
=yi +k
//当△x的步进为1时
故Pi
点的坐标为：
+1
xi+1=xi+1
yi+1=round ( yi+k) //进行取整运算
xi+1=xi+1 yi+1=round ( yi+k)
分析：下一点的y坐标为当前点y 坐标加上斜率k,省略了浮点乘法。
数
值
微
(xi+1,(int) (yi+k))
分
法
示
意 图
(xi, yi)
(xi+1, yi+k)
(xi, (int) (yi))
理想直线上的坐标点 扫描转换后的像素点
2 算法：
基本图形的生成
概论
一 光栅扫描：
1 光栅扫描的基本原理： 电子束在荧光屏上按照固定的扫描线和扫描顺序扫出 一个由行和列组成的光的栅网。
2 像素： 栅网中的每一个孤立的光点，它是光栅显示的最小单位。 像素可以有不同的亮度,像素的坐标值都是整数。
3 提出问题
(1)目前使用的图形输出设备显示器：光栅图形显示器
二 数值微分法的改进算法（关键：找到Pi(Xi,Yi), Pi+1(Xi+1,Yi+1)的关系）
1 推导：