第三章_输出图元

则得到前一点与后点的递推关系
pk +1 = pk + 2∆y ( xk +1 − xk ) − 2∆x( yk +1 − yk )
其中( yk +1 − yk ) = 0或1，取决于p k的正负
Pk>0, 取1; Pk<0, 取0
p0 = 2∆y − ∆x
由 pk = ∆x(d1 − d 2 ) = ∆y ⋅ xk − 2∆x ⋅ yk + 2∆x(2b − 1) ∆y m= ∆x
第三章 输出图元
输出图元是基本几何结构 。 输出图元种类：点、直线线段、圆、 圆锥曲线、二次曲面、样条线段、多 边形填色区域、字符串等。
本章内容： 点和线
直线段扫描转换 DDA算法 Bresenham画线算法 中点画线法 圆弧扫描转换 Bresenham画圆算法 中点画圆算法 椭圆弧扫描转换 填充区域图元
•设斜线在（xk, yk）已经确定了一个点，下一步是xk+1处 的点，如何确定？
• 设点Q为斜线段与xk+1直 线的交点，d1、d2分别 为点Q距上下平行线yk, yk+1距离 设斜线y=m•x+b，点Q的x轴 坐标为xk+1，则点Q的y轴坐 标为： y=m（ xk +1 ）+ b 则可求出d1、d2的长度
• 算法缺点： 在此算法中，y、m必须是float，且每一步都必须对y 进行舍入取整，不利于硬件实现。
Bresenham画线算法
• Bresenham算法是Bresenham提出的一种精确且有效的 光栅生成算法。 • 它用于显示线、圆和其它曲线的整数运算 • 它是目前最有效的线段生成算法
• 考虑斜率0<m<1时的扫描转换情况 如图：
(X i +1,Yi + m)
栅格交点表示 象素点位置
(X i , Int(Yi +0.5))
如果采用一般计算方法
y=mx+b 那么直线斜率为
y1 − y0 m= x1 − x0
x = x + stepx
令x = x0 → x1 y = mx + b ∴ ( x, round ( y ))
这种方法直观，但效率太低，因为每一步需要一次浮点 乘法和一次舍入运算。
∆x ( d1 − d 2 ) = 2 ∆y ( xk + 1) − 2 ∆x ⋅ y k + ∆x ( 2b − 1) = 2 ∆y ⋅ xk − 2 ∆x ⋅ y k + 2 ∆y + ∆x ( 2b − 1)
设决策参数 pk = ∆x 1 - d2 ） （d pk 的正负决定了使用哪一个象素点
}
• 其他情况
1、利用对称性 2、d1=d2时，总选择最高（低）的像素 3、特殊情况
• Bresenham画线算法例子
如二版书p58例3.1 三版书p75例3.1
中点画线算法
假定直线斜率0<K<1， 且已确定点亮象素点P （Xp ,Yp ）,则下一个与直 线最接近的像素只能是P1 点或P2点。设M为中点，Q 为交点 现需确定下一个 需要点 亮的象素。
例：画直线段P0(0,0)--P1(5,2) 则k=0.4
x 0 1 2 3 4 5 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
当∆x = 1时， y i +1 = yi + m
Line: P0(0, 0)-- P1(5, 2) 3 2 1 0 1 2 3 4 5
计算机图形学
主讲： 潘华伟 Email:hw_pan@
湖南大学计算机与通信学院
计算机图形生成算法
• 内容：
目标：掌握二维图形学的基本思想，理解扫描转换法生 成图形的基本原理。 要求：掌握图形的扫描转换、区域填充、裁剪、反走样 等概念。 掌握直线段的扫描转换算法、区域填充的扫描线算法、 多边形裁剪算法、反走样的基本思想。 熟悉多边形的扫描转换算法、区域采样的基本思想。 了解圆弧的扫描转换算法、字符的基本概念。
4、从k=0开始，在沿线路径的每个xk处，进行两个步骤地 判断： a、若pk<0, 下一点绘制（ xk +1，yk），且 p k +1 = p k + 2 ∆ y b、若pk>=0, 下一点绘制（ xk +1，yk +1 ）且
p k +1 = p k + 2 ∆ y − 2 ∆ x
5、重复步骤4, 共 ∆ x 次
• DDA算法 是一种线段扫描转换算法，它是在一个坐标 轴上以单位间隔对线条取样，从而确定另一个轴上最靠 近线段路径的对应整数值。 • 首先考虑斜率值m在（0，1）之间的直线。
假定直线的起点、终点分别为： （x0,y0), (x1,y1)，且都为整数。 x 、 y 轴的单位间隔为1
(X i , Yi)
• 增量算法：在一个迭代算法中，如果每一步的x、y值 是用前一步的值加上一个增量来获得，则称为增量算 法。 • DDA算法就是一个增量算法。
|m| ≤1情形时的算法
void DDALine(int x0,int y0,int x1,int y1,int color) { int x； float dx, dy, y, m; dx= x1-x0, dy=y1-y0; m=dy/dx, y=y0; for (x=x0; x≤x1, x++) { setpixel (x, int(y&DA方法思想
由 yi +1 = mxi +1 + b
= mxi + b + m∆x
= yi + m∆x 当∆x = 1时， y i +1 = yi + m
• 即：当x每递增1，y递增m(即直线斜率)； • 注意上述分析的算法仅适用于|m| ≤1的情形。在这种 情况下，x每增加1, y最多增加1。 • 当 |m| >1时，必须把x，y地位互换, y每增加1，x相应增 加1/m 。
该直线方程将平面分为三个区域： •对于直线上的点，F(x,y)=0； •对于直线上方的点，F(x,y)>0； •对于直线下方的点，F(x,y)<0。
欲判断M点是在Q点上方还是在Q点下方，只 需把M代入F(x,y),并检查它的符号。
构造递推式： d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c 当d>0，M在直线(Q点)上方， 取右方P1； 当d<0，M在直线(Q点)下方， 取右上方P2； 当d=0，选P1或P2均可，约 定取P1； 能否采用增量算法呢？
3
(1 - 4) (-3 +6) (3 - 4) (-1 +6)
2 1 0 1 2 3 4 5
void Midpoint Line (int x0,int y0,int x1, int y1,int color)
假设若d≥0, 中间点M在直线上方, 则取P1; 那么此时再下一个象素的递推式为 d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量为a
• 假设若d<0， 中间点M在直线下方，则取P2;
• 那么此时再下一个象素的递推式为 d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量为a＋b
• 画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。
例：用中点画线法P0(0,0) P1(5,2)
• d1 =m(xk+1)+b - yk • d2 = (yk+1 ) – [m(xk+1)+b ]
则： d1、d2的差值为 d1 - d2 = 2 m(xk+1) - 2 yk + 2b - 1
∆y 又m= ∆x
∆y 则 d1 - d2 = 2 (xk+1) – ∆x
2 yk + 2b - 1
• 三个常用算法：
数值微分法（DDA） Bresenham算法 中点画线法
直线基础
• 我们知道：直线的笛卡儿斜率截距方程为： y=m•x+b
– m---直线的斜率 – b --- 直线于y轴的截距
给定线段的两个端点（x0,y0), (x1,y1)，可以计算斜
率m和截距b：
y1 − y0 m= x1 − x0
a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 d3= 2a=-4 d4= 2(a+b)=6 xi 0 1 2 3 4 yi 0 0 1 1 2 d 1 -3 3 -1 5
d0=2(a+0.5b)
若d≥0, 增量为2a 若d<0， 增量为2(a＋b)
• 图形的扫描转换：在光栅显示器等数字 设备上确定一个最佳逼近于图形的象素 集的过程。
用一系列的象素点来逼近直线