基本图元生成算法共44页

putpixel(xc+x,yc-y);
{ plotC(x,y,xc,yc); if(d<0)
putpixel(xc-x,yc+y); putpixel(xc-x,yc-y);
d+=4*x+6;
putpixel(xc+y,yc+x);
else {
putpixel(xc+y,yc-x);
d+=4*(x-y)+10;
d 1=F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c=d+a+b
增量d1-d=a+b * d>=0时，应取正右方的P1。 接着判断再下一个像素的选取，则需计算：
d2=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c=d+a
增量d2-d=a * d的初值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c
原理：每一步考察两个可能
Pi-1
Ti
的像素点中那一个更靠近理
t
论圆周，从而推出沿圆周的
s
整数位置。
为计算方便，先将圆心（xc,yc）
Si
移到原点(0,0)。
算法：
* 沿x方向每次递增1个单位，从x=0开始，x=y结束，起点坐
标（0,r）
* 已知Pi-1(xi-1,yi-1)是最接近圆周的像素点，那么下一个像素点 只有可能是Ti(xi-1+1,yi-1)或Si(xi-1+1,yi-1-1)

基函数（基本样条） 在局部参数区域分布 （支撑区间），因此 影响范围有限。
例题：有点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不 可能出现。

)
if (Flag) { //X方向单位增量
for (n=0; n<= Length; n++) {//X方向插补过程
WritePixel(ix, Round(y), value); ix+=idx; y+=dy; } //End of for } //End of if else { //Y方向斜率增量
第 2 章 基本图形生成算法(Ⅰ)
1) Bresenham的基本原理
假定直线斜率 k在 0~1之间 。 此时 ， 只需考
虑 x方向每次递增 1个单位 ， 决定 y方向每次 递增 0或 1。
设直线的
当前点为 (xi,y) 当前光栅点为 (xi,yi)
下一个
直线的点应为 (xi+1,y+k) 直线的光栅点
y
y 2
y1
k
x x2 x1
第 2 章 基本图形生成算法(Ⅰ)
1)David F. Rogers 描述描述
如果已知第 i点的坐标 ， 可用步长 StepX 和 StepY得到
第 i+1点的坐标为 ： – xi+1=xi+ StepX – yi+1=yi+ StepY 或 yi+1=yi+ k * StepX
Bresenham算法
– 基本原理 – Bresenham算法 – 整数 Bresenham算法 – 一般整数 Bresenham算法
第 2 章 基本图形生成算法(Ⅰ)
2.1.1 DDA算法算法
1)David F. Rogers 描述描述
直线的基本微分方程是 ：
dy dx ＝ 常数 (k)
设直线通过点 P1(x1,y1)和P2(x2,y2) , 则直线方程可表示为 ：

LinYi University School of Informatics Wang Libo
Computer Graphics 计算机图形学
程序实现
DDALine(int X0,int Y0,int X0,int Y0,Color color) { int X float dx,dy,k,y dx=x1-x0; dy=y1-y0; k=dy/dx; y=Y0; for(x=X0;x<=X1;x++){ putpixel(x,int(y+0.5),Color); y=y+k; } }
getch(); closegraph( ); }
LinYi University School of Informatics Wang Libo
Computer Graphics 计算机图形学
2、逐点比较法
1.偏差计算 <0 画笔在OA下方，走+y 一步 d=tgβ-tgα = =0 画笔在OA上，走+x 一步 >0 画笔在OA上方，走+ x 一步 第一象限： d=ym/xm—yA/xA=(ymxA-yAxm)/xAxm 判别式：Fm=ymxA-xmyA >=0 走+x <0 走+y
Computer Graphics 计算机图形学
Computer Graphics
计算机图形学
基本图元的生成
LinYi University School of Informatics Wang Libo
Computer Graphics 计算机图形学
第二章 基本图元生成算法
几何图形Ｇ＝｛Ｐi | Pi 最接近图形的象素 ｝

第 3 章 基本图形元素生成算法
图3.1 中点画线示意图
第 3 章 基本图形元素生成算法
设Q是理想直线与垂直线x=xP+1的交点。 若M 在Q的下方, 则P2离理想直线近, 应取为下一个像素; 否 则应取P1。 为此, 我们构造判别式
d=F(M)=F(xP+1,yP+0.5)=a(xP+1)+b(yP+0.5)+c 当d<0时, M在直线下方, 应取右上方的P2作为下 一个像素; 当d>0时, M在直线上方, 则应取正右方的P1; 当d=0时, 约定取正右方的P1。
根据以上分析, 可得中点画圆法算法如下: void MidPoint -Circle(r, color) int r, clor; { int x, y;
float d; x=0; y=r; d=1.25-r; putpixel(x, y, color); while(x<y)
{ if(d<0) { d+=2*x+3; x++; }
float k, e; dx=x1-x0; dy=y1-y0; k=dy/dx; e=-0.5; x=x0; y=y0;
第 3 章 基本图形元素生成算法
for(i=0; i<=dy; i++) { putpixel(x, y, color); x=x+1; e=e+k; if(e>=0){ y=y+1; e=e-1; } }
第 3 章 基本图形元素生成算法
x++; }
else { e+=(deltax+deltay); deltax+=2; deltay+=2; x++; y--; }

计 算 机 图 形 学
第三章 基本图形元素的生成算法
计 算 机 图 形 学
光栅显示器上显示的图形，称之为光栅图形。光 栅显示器可以看作是一个象素矩阵，在光栅显 示器上显示的任何一个图形，实际上都是一些 像素的集合。由于对一个具体的光栅显示器来 说，象素个数是有限的，象素的颜色和灰度等 级也是有限的，象素是有大小的，所以光栅图 形只是近似的实际图形。如何使光栅图形最完 美地逼近实际图形，便是光栅图形学要研究的 内容。确定最佳逼近图形的像素集合的过程称 为图形的扫描转换或光栅化。
计 算 机 图 形 学
第三章 基本图形元素的生成算法
a)
b)
图3.2 直线的生成
c)
计 算 机 图 形 学
直线的绘制首先要考虑的是绘制的质量。怎样才算高质量？ 当然，看上去要象直线。 ： 1. 画的直线应是直的 2. 线的端点位置应正确 3. 线的浓度应均匀 4. 直线生成的速度要快
第三章 基本图形元素的生成算法
（X1,Y1)的像素点，对应的显示缓冲器地址为： 字节地址= S + ( H / 8 ) * Y1 + ( X1 / 8 ) 的整数部分 字节内的位地址= X1 / 8 的余数 计 算 机 图 形 学
第三章 基本图形元素的生成算法
3.1.2 直线段的生成
数学上的直线是由无数个点构成的集合，显 然，光栅显示器只能近地似显示直线。对 于水平、垂直和45°斜线是可以达到较为 满意的效果的。当我们对直线进行光栅化 时，需要确定最佳逼近该直线的一组象素。 扫描转换直线段就是计算出落在直线段上 或充分靠近它的一串像素，并以此像素近 似代替原连续直线段在屏幕上显示的过程。
第三章 基本图形元素的生成算法
3.1直线的生成算法

给定圆心在原点，半径为整数R的圆，其方程为
x2 y2 R2
构造函数F(x,y)=x2+y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)>0； 而对于圆内的点，F(x,y)<0。
31
y
Pu
PM
Pd
x
图5.13 中点Bresenham画圆的原理
中点Bresenham画圆
y
yi
k
19
改进的Bresenham算法
kd
k d
kd
k kd
图5.10 改进的Brensemham算法绘制直线的原理
改进的Bresenham算法——原理
xi1 yi1
xi
yi yi
1
1
(d 0.5) (d 0.5)
误差项的计算
d初=0， 每走一步：d=d+k
一旦y方向上走了一步，d=d-1
中点Bresenham画圆
判别式的初始值
d0 F ( x0 1, y0 0.5) F (1, R 0.5) 1 (R 0.5)2 R2 1.25 R
36
改进：用d-0.25代替d 此时有：
d d 2xi 3
d 0.25
d d 2(xi yi ) 5 d 0.25
yi-2
(xi 2)2 ( yi 0.5)2 R2
xi xi+1 xi+2
d2 ( xi 1 1)2 ( yi 0.5)2 R2 图5.14 d≤0的情况
( xi 1)2 2xi 3 ( yi 0.5)2 R2
d1 2xi 3
误差项的递推（d>0）
yi
P
yi-1
构造判别式：

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();

putpixel(x,y,color); while (x<x1) {
if (d<0) { x++; y++; d+=delta2; //取P2，并且计算下一点的d值 } else { x++; d+=delta1; //取P1，并且计算下一点的d值 } putpixel(x,y,color); } }
当|k|≤1时，让x每步增加1，y最多增加1，
然后用四舍五入的方法来确定直线上的
像 素 位 置 为 (x,round(y)) 。 设 当 前 点 为 (xi,yi)，则下一个像素xi+1 = xi +1，则 yi+1 =k xi+1 +B =k(xi+1)+B=(k xi +B)+k = yi +k 即当x每递增1时，y递增斜率k。
即可。
算法举例：
设直线的起点为（0，0），终点为（5， 3），按Bresenham 算法计算并确定个 像素点位置。
计算dx=5,dy=3,k=3/5=0.6,误差e=-0.5; x=0,y=0
(1) i=0: 输出像素(0,0)
x=1,e=e+k=-0.5+0.6=0.1>0, 则 有
y=y+1=1,e=e-1=0.1-1=-09
其中，a=y0-y1,b=x1-x0,c=x0y1-x1y0。
对于直线中的点，则有F(x,y)=0;对于直 线上方的点，则有F(x,y)>0;对于直线下 方的点，则有F(x,y)<0。
• 判断中点M在Q的上方，还是 在下方，只要将中点坐标 M(xi+1,yi+0.5) 代 入 F(x,y) 方 程 中，并判断它的符号。构造判 别式

4.5 区域填充
基础知识: 基础知识 区域： 区域：通常由一个封闭的轮廓线来定义，处于一个 封闭轮廓线内的所有像素点即构成了一个区域。 区域填充： 区域填充：给出一个区域的边界，要求对应边界范 围内的所有像素单元赋予指定的颜色值或图案。 区域填充要解决两个问题： 区域填充要解决两个问题：一是确定需要填充哪些 像素；二是确定用什么颜色填充（实心填充）或 图案填充。 在光栅系统中有两种基本的区域填充方法： 在光栅系统中有两种基本的区域填充方法： 扫描线填色方法 种子填色方法
一般来讲，任何图形输出设备都能准确地画出水 平线X和垂直线Y，但要画出一条准确的斜线不是 件容易的事。怎样生成斜线段呢？图形显示器是 由一个个排列有序的像素构成，划分的像素点越 多分辨率越高。例如，VGA卡640×480的显示 VGA 640 480 器，分成640×480个网络，网络的单元称为像素， 一条线段就是由一些连续可见的像素所组成。画 一条直线实际上是根据一系列计算出来并与该线 靠近的像素绘制的。（见书P51）
4.4 椭圆的生成
4.4.1 概述 4.4.2 中点椭圆算法
4.4.1 概述
椭圆被定义为到两个定点（也称为焦点） 的距离之和等于常数的点的集合。假如椭 圆上任意点P=（x,y）到两个焦点F1= （x1,y1）和F2=（x2,y2）的距离之和等于 常数R，那么椭圆的通用方程可表示为： 对方程平方处理去掉根号后，椭圆的方程 可表示为：
4.5.3 种子填充
种子填充算法允许从四个方向寻找下一个 像素的，称为四向算法；允许从八个方向 搜索下一像素的，称为八向算法。八向算 法可以填充八向连通区域，也可以填充四 向连通区域。但四向算法只能填充四向连 通区域，而不能填充八向填充区域。
4.5.3 种子填充